Katkat

Assign Pins to Shortest Columns

PinterestSoftware Engineer · Technical Screen

Last updated

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 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:

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]