Quick Overview

Implement indexed get and insert in an unrolled linked list, preserving block capacity, occupancy, sequence order, and split behavior.

Implement Get and Insert in an Unrolled Linked List

Company: Indeed

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an unrolled linked list: an ordered sequence stored in linked blocks, where each block contains up to `capacity` integers. Support indexed `get` and indexed `insert` while preserving the sequence order. Implement `unrolled_list(operations: int[][], capacity: int) -> int[]`. The list starts empty. Operations are: - `[0, index, value]`: insert `value` before the element currently at `index`; `index == size` appends. Return the new sequence size for this operation. - `[1, index]`: return the current element at `index`. Return one integer per operation. ### Constraints & Assumptions - `2 <= capacity <= 64`; there are at most 20,000 operations. - Values are signed 32-bit integers. All indices are valid at the time of the operation: insertion uses `0 <= index <= size`, and get uses `0 <= index < size`. - Blocks are linked in sequence order. Every nonempty block has at most `capacity` values. - Except for the final block, maintain at least `floor(capacity / 2)` values per block. No deletion is required. - When inserting into a full block, split its values into two contiguous blocks and preserve their order. The exact split point may vary as long as capacity and occupancy requirements hold. - The operation encoding, capacity bound, occupancy convention, and returned insertion size are explicit practice choices for the reported get/insert task. - Implement the block-based representation rather than storing the entire sequence in one flat resizable array. Output depends only on sequence semantics, so structural invariants also require code review. ### Examples ```text capacity = 3 operations = [[0,0,10],[0,1,30],[0,1,20],[1,1],[0,0,5],[1,3]] result = [1,2,3,20,4,30] ``` ```text capacity = 2 operations = [[0,0,7],[0,0,8],[0,1,9],[1,0],[1,1],[1,2]] result = [1,2,3,8,9,7] ``` ```hint Locate a block and an offset Subtract each block's element count while searching by index. At the insertion boundary, preserve which side of the existing element receives the new value, including append at the end. ```

Overview: Implement indexed get and insert in an unrolled linked list, preserving block capacity, occupancy, sequence order, and split behavior.

Implement an unrolled linked list: an ordered sequence stored in linked blocks, where each block contains up to `capacity` integers. Support indexed `get` and indexed `insert` while preserving the sequence order. Implement `unrolled_list(operations: int[][], capacity: int) -> int[]`. The list starts empty. Operations are: - `[0, index, value]`: insert `value` before the element currently at `index`; `index == size` appends. Return the new sequence size for this operation. - `[1, index]`: return the current element at `index`. Return one integer per operation. ### Constraints & Assumptions - `2 <= capacity <= 64`; there are at most 20,000 operations. - Values are signed 32-bit integers. All indices are valid at the time of the operation: insertion uses `0 <= index <= size`, and get uses `0 <= index < size`. - Blocks are linked in sequence order. Every nonempty block has at most `capacity` values. - Except for the final block, maintain at least `floor(capacity / 2)` values per block. No deletion is required. - When inserting into a full block, split its values into two contiguous blocks and preserve their order. The exact split point may vary as long as capacity and occupancy requirements hold. - The operation encoding, capacity bound, occupancy convention, and returned insertion size are explicit practice choices for the reported get/insert task. - Implement the block-based representation rather than storing the entire sequence in one flat resizable array. Output depends only on sequence semantics, so structural invariants also require code review. ### Examples ```text capacity = 3 operations = [[0,0,10],[0,1,30],[0,1,20],[1,1],[0,0,5],[1,3]] result = [1,2,3,20,4,30] ``` ```text capacity = 2 operations = [[0,0,7],[0,0,8],[0,1,9],[1,0],[1,1],[1,2]] result = [1,2,3,8,9,7] ``` ```hint Locate a block and an offset Subtract each block's element count while searching by index. At the insertion boundary, preserve which side of the existing element receives the new value, including append at the end. ```

Constraints

  • 2 <= capacity <= 64; at most 20000 operations.
  • The list starts empty; insert and get indices are valid at the time of each operation.
  • Inserted values are signed 32-bit integers.
  • Use linked blocks; completed operations keep each block at most capacity and every non-final block at least floor(capacity/2).
  • Return one integer per operation: new size after insert, or value after get.

Examples

Input: ([[0, 0, 10], [0, 1, 30], [0, 1, 20], [1, 1], [0, 0, 5], [1, 3]], 3)

Expected Output: [1, 2, 3, 20, 4, 30]

Explanation: The sequence becomes [5,10,20,30]; each insertion returns its new size.

Input: ([[0, 0, 7], [0, 0, 8], [0, 1, 9], [1, 0], [1, 1], [1, 2]], 2)

Expected Output: [1, 2, 3, 8, 9, 7]

Explanation: Interior insertion into the full block preserves [8,9,7].

Hints

  1. Locate a block and a local offset by subtracting preceding block sizes; handle insertion boundaries and append consistently.

Loading coding console...

Show the approach

Approach

Keep a singly linked chain of blocks, each holding a small array. Locate an index by subtracting whole block sizes. For insertion, an index equal to a block's length can be inserted at that block's end; this is the same sequence position as the next block's beginning. For get, equality instead advances to the next block. Append naturally reaches the last block.

Insert into the located block. If it now contains capacity + 1 values, cut it at floor((capacity + 1) / 2), move the suffix into a new linked block, and link that block before the old successor. The two contiguous pieces preserve sequence order. Each has at most capacity entries and at least floor(capacity / 2) entries. Every other block is unchanged, and insertions only increase occupancy. Starting from the empty list, these facts inductively establish the linked-block capacity and non-final occupancy invariants after every operation. A split may transiently hold capacity + 1 entries inside the operation; the completed operation restores the bound.

The concatenation of the block arrays is therefore always exactly the requested sequence. Indexed traversal finds its correct local offset, so get returns the requested value. A separate size counter increases exactly once per insert and supplies the insertion result. Empty streams, equal values, and signed endpoints require no special arithmetic. The C++ ownership vector owns separate linked nodes; it does not store the sequence as a flat array, and moving unique_ptr owners does not move the nodes.

For current size s and capacity C, minimum occupancy bounds the number of blocks by O(1 + s/C). Get takes O(1 + s/C); insertion takes O(1 + s/C + C) including shifting and splitting. With k operations the total upper bound is O(k + k^2/C + kC). Blocks hold O(k) values and links, and the returned results occupy O(k). Output comparison checks sequence behavior; linked storage and occupancy additionally need structural code review.

Time complexity:
O(k + k^2/C + kC) total for k operations and capacity C
Space complexity:
O(k) including linked blocks and returned results