1) 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] = - 1) 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. 2) 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.

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.

How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Two Sigma.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Two Sigma during technical interviews.

Solve tree partition and IPO allocation | Two Sigma Interview Question

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.

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.

Solve tree partition and IPO allocation

Quick Overview

Comments (0)

Solve tree partition and IPO allocation

Quick Overview

Comments (0)