Assign Pins to Shortest Columns
PinterestSoftware Engineer · Technical ScreenLast 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]
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.