Hey blind can someone please help with this hackerrank question? Python or Pseudocode preferred. TC: ~184k
Reads like the cumulative sum on a tree
Pseudocode?
- Subset sum but on trees - hard problem. which company’s interview was this ?
Isn't it simply picking the subtree S that minimizes |total_flow(root)/2 - total_flow(S)| ?
recursively do node.total_flow = node.input_flow + sum(node.children.total_flow) answer = None for each node: if node == root: continue current_diff = abs(root.total_flow/2 - node.total_flow) if answer is None or current_diff < answer: answer = current_diff return answer
Why is root.total_flow halved? Trying to understand that part.
Find subtree sum for each node i. Subtree sum = total flow of the subtree rooted at node i. Then go through each node and find ans where ans = min(ans, abs(B - C)). A = total sum of the tree B = total subtree sum of the tree rooted at that node C = A - B
Thank you!
Why you tagged snap and amazon when it's a two sigma question. Anyway the question is fucking easy. Why even bother interview you can't solve this? Wherever you cut the tree, one of the subtree always flow to root, you can find that by calculate the total sum to root if not cutting. Then compare the two result and return the min. Anyway don't even bother applying to two sigma if you can't solve this. Their interview is notoriously hard.
Cuz these companies use hackerank. How do you recommend studying for these types of questions cuz you can't really get that on leetcode?
OP, this is very similar to LC problems. The only difference in HackerRank and Leetcode is their I/O style. And this is an easy-medium problem, you just need more practice. I'd recommend solving problems on Codeforces, Codechef and Hackerrank. Leetcode has very narrow topics range and that can hinder your growth.
India
2h
423
What do vegetarian Indians eat for protein?
Tech Industry
Yesterday
2971
1 vs 5 Million - no lifestyle change
Tech Industry
Yesterday
415
Bitcoin is the only possible future
Ask Blinders
Yesterday
752
Why is our country owned by Israel? I don't want my tax dollars fund genocide. How can we stop this nonsense?
Tech Industry
Yesterday
402
Is it true the baby boomers had it easier?
Are you in an interview?
No, this is from before just want to know how to solve it.
Im p sure thats from the two sigma OA lol