Implement a min-heap column allocator
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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:
1) Design a streaming API with addPost(h) and peekMinColumn() using the same rule.
2) How would you extend the design to support removal of an arbitrary post and updates to a post's height?
3) 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?
4) How would you handle tie-breaking, stability, and potential 64-bit overflow?
Quick Answer: 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` (the 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 the posts in order. For each post, place it into the column with the **smallest current total height**, breaking ties by the **smallest column index**. After placement, that column's total height increases by the post's height.
Implement `assignPosts(k, posts)` to return an array giving the **column index chosen for each post**, in order.
The intended approach supports **O(log k)** time per insertion by maintaining a binary min-heap of `(currentHeight, columnIndex)` pairs. Popping the minimum yields the target column; pushing back the updated height keeps the heap ordered. Including the column index as the secondary sort key makes the smallest-index tie-break fall out automatically.
Example: `k = 3`, `posts = [1, 2, 3, 4, 5]`.
- Post 1 (h=1) → all columns at 0, pick index 0. Heights: [1,0,0]
- Post 2 (h=2) → min is index 1 at 0. Heights: [1,2,0]
- Post 3 (h=3) → min is index 2 at 0. Heights: [1,2,3]
- Post 4 (h=4) → min is index 0 at 1. Heights: [5,2,3]
- Post 5 (h=5) → min is index 1 at 2. Heights: [5,7,3]
- Result: `[0, 1, 2, 0, 1]`
Constraints
- 1 <= k <= 100000
- 0 <= len(posts) <= 1000000
- 1 <= posts[i] (each post height is a positive integer)
- Column total heights can grow large; use 64-bit integers to avoid overflow when sums approach 2^63.
Examples
Input: (3, [1, 2, 3, 4, 5])
Expected Output: [0, 1, 2, 0, 1]
Explanation: Round-robin fills the three empty columns first (indices 0,1,2), then index 0 (total 1) is smallest, then index 1 (total 2).
Input: (1, [5, 3, 8])
Expected Output: [0, 0, 0]
Explanation: With a single column, every post goes to index 0.
Hints
- You only ever need the column with the smallest current total height — a structure that supports fast extract-min is the natural fit. A binary min-heap gives O(log k) per operation.
- Store each heap entry as a pair (currentHeight, columnIndex). Because tuples/pairs compare lexicographically, equal heights automatically break ties toward the smaller column index — no extra logic needed.
- For each post: pop the minimum to learn the chosen column, record that index, then push the same column back with its height increased by the post's height.
- Initialize the heap with all k columns at height 0 up front (heapify is O(k)), rather than inserting them one at a time.