Implement Layer History and Grid Counting

The coding portion of this loop covered two independent tasks. Implement each cleanly, handle the edge cases, and analyze the time and space complexity. ### Constraints & Assumptions - **Task 1 (layer editor):** `id`s are unique (strings or integers). The `index` for `addLayer` and the `newIndex` for `moveLayer` are valid positions in the current ordering ($0 \le \text{index} \le n$ for insert, $0 \le \text{newIndex} < n$ for move). Batches are **not nested** (no `beginBatch()` while a batch is already open). Edits outside a batch each form their own history entry; edits inside a batch collapse into **one** atomic entry. `undo()` / `redo()` on an empty stack are no-ops. The number of layers fits comfortably in memory; favor correctness and clear semantics over micro-optimization. - **Task 2 (grid counting):** The grid has $R$ rows and $C$ columns of characters, each `'L'` (land) or `'W'` (water). Adjacency is **4-directional** (up/down/left/right) only — diagonals do **not** connect. The grid may be empty. You may mutate the grid in place if you wish. ### Clarifying Questions to Ask - Task 1: Can `beginBatch()` be called twice without an intervening `endBatch()`, and what should happen to an **empty** batch (no sub-edits before `endBatch`)? - Task 1: For `moveLayer`, is `newIndex` interpreted against the list **before** or **after** the element is removed from its old slot? - Task 1: Should `addLayer` with a duplicate `id`, or `removeLayer` / `moveLayer` of a missing `id`, raise an error or be a silent no-op? - Task 2: Is adjacency 4-directional or 8-directional (do diagonals connect)? - Task 2: Roughly how large can the grid get, and am I allowed to mutate it in place rather than allocate a separate `visited` structure? ### Part 1 — Layer editor with undo/redo and atomic batches Implement a `LayerEditor` that maintains an **ordered** list of layer IDs and supports: - `addLayer(id, index)` — insert a new layer at position `index`. - `removeLayer(id)` — remove an existing layer. - `moveLayer(id, newIndex)` — move a layer to a new position. - `undo()` — revert the most recent committed edit. - `redo()` — re-apply the most recently undone edit. - `beginBatch()` / `endBatch()` — treat every edit between them as **one** atomic history entry. Required semantics: applying a **new edit after an `undo()` clears the redo history**; `undo()` and `redo()` must restore the **exact** previous ordering of the list. ```hint Model the unit of history The hard part is not the list ops — it's deciding *what one undo entry is*. Settle on a single "committed edit" representation that one `undo()` can reverse and one `redo()` can re-apply. Then ask what that representation should hold: enough information to *recompute* the prior state (an inverse-operation log), or the prior state itself (a snapshot)? Both are defensible — weigh the time/space trade-off out loud. ``` ```hint What makes a batch one entry? A batch must produce exactly one history entry no matter how many sub-edits it contains. Think about where a sub-edit's record should go *while a batch is open* versus when it closes. If a single "edit" can hold multiple sub-ops, what must be true about the **order** in which you reverse them so the list comes back exactly right? And handle the awkward cases: an empty batch, and an `endBatch()` with no batch open. ``` #### What This Part Should Cover - A clear, single definition of a "committed edit" and an argument that one batch yields exactly **one** history entry. - Correct redo-clear-on-new-edit behavior and **exact** ordering restored by `undo`/`redo` (the reverse-order subtlety inside a batch). - Sensible handling of edge cases: empty stacks, empty batch, stray `endBatch`, missing/duplicate ids. - A stated time/space cost per operation (including `undo`/`redo` of a $k$-op edit). ### Part 2 — Count connected land regions Given a 2D grid of `'L'` (land) and `'W'` (water), count how many **connected land regions** exist, where two land cells belong to the same region iff they share a **side**. Provide an algorithm and analyze its time and space complexity. ```hint Reframe the problem Translate "region" into graph terms: if each land cell is a node, what are its edges, and what graph-theory object does a single region correspond to? Once you have that mapping, does this resemble a problem you already know? Whatever traversal you choose, decide up front how you'll guarantee you count each region exactly **once** as you scan the grid. ``` ```hint Don't recount, and watch the worst case When you start exploring a component, you need a way to never revisit its cells (and never start a second count inside it). What state records "already seen," and could you reuse the grid itself instead of allocating extra memory? For time: each cell is touched a constant number of times — reason from that to the bound. For space: the dominant term is whatever your traversal holds at once (frontier / stack / structure); pin down its worst case (think about an all-land grid). ``` #### What This Part Should Cover - Correct connected-components reasoning under the stated **4-directional** adjacency. - A flood-fill (BFS / DFS / union-find) that visits each cell once, with explicit visited-marking so no cell or region is recounted. - Handling of the empty grid and the in-place vs. separate-`visited` trade-off. - A justified $O(R \cdot C)$ time bound and a justified worst-case space bound. ### What a Strong Answer Covers These dimensions span both parts: - Clean, well-named interfaces and a stated handling of each edge case — not just code that happens to pass the happy path. - Complexity reported precisely in $O(\cdot)$ terms for every operation/algorithm. - A spoken design rationale: which representation/traversal you chose and **why**, including the alternative you rejected. ### Follow-up Questions - Task 1: How would you support **nested** batches, or a `redo()` that survives across batch boundaries? How does the design change if the history must persist to disk? - Task 1: If the layer list were huge, would you switch from whole-list snapshots to inverse-operation logging (or vice versa)? What's the trade-off? - Task 2: How would the solution change for **8-directional** adjacency, or for a grid too large to fit in memory (rows streamed one at a time)? - Task 2: If you must also return the **size of the largest** region, how do you extend the flood-fill?