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.

Assign Pins to Shortest Columns | Pinterest Coding Question

Assign Pins to Shortest Columns

Company: Pinterest

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of pins, where each pin has a height, and a fixed number of columns in a masonry-style layout. Process the pins in their original order. For each pin, append it to the column whose current total height is the smallest. After appending the pin, that column's total height increases by the pin's height. If multiple columns have the same minimum height, choose the column with the smallest index. Design and implement a function that returns the final assignment of pins to columns, or the final total height of each column. Also analyze the time and space complexity. Example: ```text heights = [5, 2, 4, 7, 1] numColumns = 3 Initial column heights: [0, 0, 0] Pin 5 -> column 0, heights become [5, 0, 0] Pin 2 -> column 1, heights become [5, 2, 0] Pin 4 -> column 2, heights become [5, 2, 4] Pin 7 -> column 1, heights become [5, 9, 4] Pin 1 -> column 2, heights become [5, 9, 5] Final column heights: [5, 9, 5] ```

Quick Answer: This question evaluates understanding of greedy assignment strategies and data structures for maintaining and updating minimums in an online allocation problem, while also testing load-balancing reasoning and analysis of time and space complexity.

You are given a list of non-negative integers `heights`, where each value is the height of a pin, and a positive integer `numColumns`, the number of columns in a masonry-style layout. Process the pins in their original order. For each pin, place it into the column whose current total height is smallest. If multiple columns share the same minimum height, choose the column with the smallest index. In this problem, return the final total height of every column after all pins have been placed.

Constraints

1 <= numColumns <= 2 * 10^5
0 <= len(heights) <= 2 * 10^5
0 <= heights[i] <= 10^9

Examples

Input: ([5, 2, 4, 7, 1], 3)

Expected Output: [5, 9, 5]

Explanation: Pins are assigned in order to the current shortest column: 5->0, 2->1, 4->2, 7->1, 1->2. Final heights are [5, 9, 5].

Input: ([], 4)

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

Explanation: With no pins to place, all columns remain at height 0.

Input: ([3, 1], 5)

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

Explanation: The first pin goes to column 0, the second to column 1, and the remaining columns stay unused.

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

Expected Output: [4, 4]

Explanation: After two pins the columns are tied at [2, 2]. The third pin goes to column 0 because of the smaller index tie-break, and the fourth goes to column 1.

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

Expected Output: [6]

Explanation: With only one column, every pin must go into that column, so the total is 1 + 3 + 2 = 6.

Input: ([0, 5, 0, 2], 2)

Expected Output: [5, 2]

Explanation: Zero-height pins still follow the same shortest-column rule and can preserve ties. The final column totals are [5, 2].

Hints

You need to repeatedly find the column with the smallest current total height, breaking ties by smaller index.
A min-heap storing pairs like `(currentHeight, columnIndex)` lets you update the shortest column efficiently.

Quick Overview

This question evaluates understanding of greedy assignment strategies and data structures for maintaining and updating minimums in an online allocation problem, while also testing load-balancing reasoning and analysis of time and space complexity.