Katkat
Back

Implement list and grid transformation tasks

eBaySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to simulate state-dependent transitions on a 2D grid and your skill in repartitioning data based on specific grouping constraints.

Problem Description

You are tasked with building a UI layout engine that processes a sequence of items and a grid display.

Part 1: List Repartitioning

You are given a list of strings where each string is either a 'Task' (starts with 'T'), 'User' (starts with 'U'), or 'System' (starts with 'S'). You must reorder the list such that all 'Tasks' come first, followed by 'Users', and finally 'Systems'. Within each category, the original relative order must be maintained (stable sort).

Part 2: Grid Gravity

You are given a grid represented as a list of lists of integers, where 0 represents an empty cell and any other integer represents an item. Implement a apply_gravity(grid) function that shifts all items downwards until they hit the bottom of the grid or another item. The gravity is applied simultaneously to all columns.

Function Signatures

def repartition_list(items: list[str]) -> list[str]:
    pass

def apply_gravity(grid: list[list[int]]) -> list[list[int]]:
    pass

Examples

Example 1: Repartitioning Input: ['U1', 'T1', 'S1', 'T2', 'U2'] Output: ['T1', 'T2', 'U1', 'U2', 'S1']

Example 2: Grid Gravity Input: [[0, 1], [0, 0], [2, 0]] Output: [[0, 0], [0, 0], [2, 1]] Explanation: The 1 in column 1 falls to the bottom row, resting on top of the implicit floor.

Constraints

  • List length: up to 10^5 elements.
  • Grid dimensions: M x N where M, N <= 500.
  • Time complexity should be O(N) for repartitioning and O(M*N) for gravity.

Hints

Hint 1

For the repartitioning, consider using three separate buckets or lists to collect items based on their prefix before joining them.

Hint 2

For gravity, process each column independently by collecting all non-zero elements and placing them at the bottom of a new column buffer.

Hint 3

Ensure you handle empty rows and columns correctly by filling the top of the grid with zeros after moving items down.

Follow-up questions

  • How would you modify the repartitioning logic if you needed to do it in-place with O(1) extra space?
  • If the grid contained 'blocks' of different sizes (e.g., 2x1 items), how would the gravity logic change?
  • What are the implications for cache locality if you represent the grid as a 1D array versus a list of lists?