Implement a min-heap column allocator
PinterestSoftware Engineer · Technical ScreenLast updated
This question evaluates a candidate's competency in data structures (priority queues/min-heaps), online algorithm design for stream processing, and complexity and memory analysis.
You are given an integer k (number of columns) and an array posts of positive integers where posts[i] is the height of the i-th post. All columns start with total height 0. Process posts in order; for each post, place it into the column with the smallest current total height (break ties by the smallest column index). After placement, that column's height increases by the post's height. Implement assignPosts(k, posts) to return either the column index chosen for each post or the final total height of each column. Describe the data structures and algorithms you would use to support O(log k) time per insertion. Analyze the time and space complexity. Follow-ups:
- Design a streaming API with addPost(h) and peekMinColumn() using the same rule.
- How would you extend the design to support removal of an arbitrary post and updates to a post's height?
- If k is as large as 100,000 and posts has up to 1,000,000 items, what memory/layout choices and optimizations would you make?
- How would you handle tie-breaking, stability, and potential 64-bit overflow?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.