How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Pinterest.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Pinterest during technical interviews.

Implement a min-heap column allocator | Pinterest Coding Question

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.

Input: (4, [])

Expected Output: []

Explanation: No posts to place, so the result is empty regardless of k.

Input: (2, [10, 10, 10, 10])

Expected Output: [0, 1, 0, 1]

Explanation: Equal heights keep tie-breaking to the smaller index, alternating 0,1,0,1 as columns stay balanced.

Input: (3, [5, 5, 5])

Expected Output: [0, 1, 2]

Explanation: All columns start at 0; ties go to the smallest index, filling 0 then 1 then 2.

Input: (2, [1, 100, 1, 1, 1])

Expected Output: [0, 1, 0, 0, 0]

Explanation: After post 2 (h=100) lands in column 1, column 0 stays far lighter, so the remaining small posts all go to column 0.

Input: (5, [7])

Expected Output: [0]

Explanation: Single post with all columns empty picks the smallest index, 0.

Input: (3, [2, 1, 1, 1])

Expected Output: [0, 1, 2, 1]

Explanation: Posts 1-3 fill columns 0,1,2 (heights 2,1,1). The 4th post sees columns 1 and 2 tied at 1, so it picks the smaller index, 1.

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.

Quick Overview

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.