Solve tree partition and IPO allocation
Overview
This question evaluates algorithmic problem-solving skills in tree processing and allocation simulations, specifically assessing understanding of subtree-sum computation for tree partitioning and deterministic round-robin allocation logic for IPO-style share distribution, along with appropriate data structure selection and correctness under edge cases. It is commonly asked in the Coding & Algorithms domain because it measures practical application-level implementation and the ability to analyze time and space complexity rather than purely conceptual proof.
Two Sigma
Sep 6, 2025, 12:00 AM
Machine Learning Engineer
Take-home Project
Coding & Algorithms
0
0
- Tree partitioning for minimum difference: Given a rooted tree as an array parent of length n (parent[i] gives the parent of node i, and parent[root] = -
- and an integer array inputs of length n giving each node's weight, cut exactly one edge to split the tree into two connected components. Return the minimum possible absolute difference between the sums of inputs in the two components. Example: parent = [-1, 0, 0, 1, 1, 2], inputs = [1, 2, 2, 1, 1, 1] -> 0 by cutting the edge between nodes 0 and 1 (components {0,2,5} sum to 4 and {1,3,4} sum to 4). Describe your algorithm and its time/space complexity.
- IPO share allocation with round-robin at price tiers: You are given an integer S (total shares to allocate) and a list of bids, where each bid is a tuple (bidder_id, shares_requested, price, timestamp). Process bids by price in descending order. For a price group with a single bidder, allocate min(S, shares_requested) to that bidder. For a price group with multiple bidders, allocate one share per turn in round-robin order among bidders sorted by ascending timestamp; remove a bidder from the rotation once they receive shares_requested; continue until either all bidders in the current price group are fulfilled or S becomes 0, whichever comes first. If S remains after finishing a price group, move to the next lower price group and repeat. Return a list of integers representing, in the same order as the input bids, how many shares each bid receives. State edge cases you would handle and the time/space complexity.