Katkat
Back

Implement Layer History and Grid Counting

FigmaMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question tests state management through a Command pattern implementation for undo/redo operations and spatial reasoning using depth-first search (DFS) to identify connected components in a 2D grid.

Part 1: Layer Editor State

Implement a LayerHistory class that manages the state of a document's layers. You must support add_layer(layer_id), remove_layer(layer_id), and undo()/redo() functionality. The system must support atomic batching, where multiple operations can be performed as a single unit that is undone or redone together.

class LayerHistory:
    def __init__(self):
        # Stores the state of active layers
        self.layers = set()
        
    def start_batch(self): pass
    def end_batch(self): pass
    def add_layer(self, layer_id): pass
    def remove_layer(self, layer_id): pass
    def undo(self): pass
    def redo(self): pass

Part 2: Grid Connectivity

Given a 2D grid represented by a list of lists where 1 represents land and 0 represents water, write a function count_connected_regions(grid) that returns the number of distinct islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Constraints

  • Grid dimensions: M x N where 1 <= M, N <= 500.
  • Time complexity for grid counting should be O(M * N).

Examples

Input:

[[1, 1, 0],
 [1, 0, 0],
 [0, 0, 1]]

Output: 2 (One island of size 3, one island of size 1).

Edge Cases

  • Empty grid.
  • Grid with all water or all land.
  • Disconnected components forming an 'L' shape.

Hints

Hint 1

For the LayerHistory, use two stacks to manage operations, ensuring that batching groups multiple commands into a single undoable block.

Hint 2

For the grid problem, use a recursive DFS or iterative BFS to traverse and mark visited cells to avoid double-counting.

Hint 3

Consider modifying the grid in-place to save memory during the traversal, or use a separate boolean matrix if the input must remain immutable.

Follow-up questions

  • How would you optimize the `LayerHistory` for a history of 100,000+ operations?
  • If the grid updates dynamically (e.g., land changes to water), how would you efficiently update the island count without re-scanning the entire grid?
  • How would you handle concurrent access to the `LayerHistory` if multiple users are editing the same document?