Field Layout: getOffset and insert
Company: Jane Street
Role: Frontend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
An object's binary layout is defined by an **ordered list of fields**. Each field has a unique name and a size in bytes. Fields are packed contiguously starting at byte offset `0`, in list order: the first field starts at offset `0`, and each subsequent field starts where the previous one ends.
For example, the field list `(foo, 3), (bar, 6), (baz, 2)` produces this layout:
| Field | Size (bytes) | Occupies byte range |
|---|---|---|
| `foo` | 3 | `[0, 3)` |
| `bar` | 6 | `[3, 9)` |
| `baz` | 2 | `[9, 11)` |
Implement a class `FieldLayout` that supports the following operations:
- `FieldLayout(fields)` — initialize the layout from a list of `(name, size)` pairs, in order.
- `getOffset(name)` — return the starting byte offset of the field `name`.
- `insert(name, size, index)` — insert a new field with the given name and size at position `index` in the **field order** (0-based; this is a position in the list of fields, **not** a byte offset). All fields at position `index` and later shift toward the end, and their byte offsets increase by `size`.
## Example
Starting from `(foo, 3), (bar, 6), (baz, 2)`:
```text
getOffset("bar") -> 3
insert("qux", 2, 1) -> layout becomes foo[0,3), qux[3,5), bar[5,11), baz[11,13)
getOffset("bar") -> 5
getOffset("baz") -> 11
insert("end", 4, 4) -> appended at the end: end[13,17)
getOffset("end") -> 13
getOffset("foo") -> 0
```
## Constraints
- `1 <= initial number of fields <= 10^5`
- `1 <= total number of getOffset and insert calls <= 10^5`
- `1 <= size <= 10^4` for every field
- Field names are unique non-empty strings; `getOffset` is only called with the name of a field that exists in the layout.
- For every `insert`, `0 <= index <= current number of fields` (inserting at `index == current number of fields` appends to the end).
- Offsets fit in a 64-bit integer.
Quick Answer: This question evaluates a candidate's ability to model and maintain ordered field layouts by computing and updating byte offsets, testing competencies in dynamic sequence data structures, cumulative offset tracking, and efficient update/query operations.
An object's binary layout is defined by an **ordered list of fields**. Each field has a unique name and a size in bytes. Fields are packed contiguously starting at byte offset `0`, in list order: the first field starts at offset `0`, and each subsequent field starts where the previous one ends.
For example, the field list `(foo, 3), (bar, 6), (baz, 2)` produces this layout:
| Field | Size (bytes) | Occupies byte range |
|---|---|---|
| `foo` | 3 | `[0, 3)` |
| `bar` | 6 | `[3, 9)` |
| `baz` | 2 | `[9, 11)` |
Because the grader drives a single entry point, implement the class as a **simulation function** `solution(fields, operations)`:
- `fields` is the initial layout: a list of `[name, size]` pairs, in field order.
- `operations` is a list of operations to apply in order. Each operation is one of:
- `["getOffset", name]` — return the starting byte offset of field `name`.
- `["insert", name, size, index]` — insert a new field `[name, size]` at position `index` in the **field order** (0-based; a position in the list of fields, **not** a byte offset). All fields at position `index` and later shift toward the end, and their byte offsets increase by `size`. `index == current number of fields` appends to the end.
Return a list aligned with `operations`: the integer offset for each `getOffset`, and `None` (a placeholder) for each `insert`.
## Example
Starting from `(foo, 3), (bar, 6), (baz, 2)`:
```text
getOffset("bar") -> 3
insert("qux", 2, 1) -> layout becomes foo[0,3), qux[3,5), bar[5,11), baz[11,13)
getOffset("bar") -> 5
getOffset("baz") -> 11
insert("end", 4, 4) -> appended at the end: end[13,17)
getOffset("end") -> 13
getOffset("foo") -> 0
```
So for `operations = [["getOffset","bar"], ["insert","qux",2,1], ["getOffset","bar"], ["getOffset","baz"], ["insert","end",4,4], ["getOffset","end"], ["getOffset","foo"]]`, the result is `[3, None, 5, 11, None, 13, 0]`.
Constraints
- 1 <= initial number of fields <= 10^5
- 1 <= total number of getOffset and insert calls <= 10^5
- 1 <= size <= 10^4 for every field
- Field names are unique non-empty strings; getOffset is only called with the name of a field that exists in the layout.
- For every insert, 0 <= index <= current number of fields (index == current number of fields appends to the end).
- Offsets fit in a 64-bit integer.
Examples
Input: ([['foo',3],['bar',6],['baz',2]], [['getOffset','bar'],['insert','qux',2,1],['getOffset','bar'],['getOffset','baz'],['insert','end',4,4],['getOffset','end'],['getOffset','foo']])
Expected Output: [3, None, 5, 11, None, 13, 0]
Explanation: The worked example. getOffset(bar)=3 initially. After insert(qux,2,1) the layout is foo[0,3), qux[3,5), bar[5,11), baz[11,13); now bar starts at 5 and baz at 11. insert(end,4,4) appends end[13,17), so getOffset(end)=13 and getOffset(foo)=0.
Input: ([['a',5],['b',10]], [['getOffset','a'],['getOffset','b'],['insert','z',7,0],['getOffset','z'],['getOffset','a'],['getOffset','b']])
Expected Output: [0, 5, None, 0, 7, 12]
Explanation: Insert at index 0 pushes everything right. Initially a[0,5), b[5,15). After insert(z,7,0): z[0,7), a[7,12), b[12,22), so z=0, a=7, b=12.
Input: ([['only',4]], [['getOffset','only']])
Expected Output: [0]
Explanation: Single field starts at offset 0.
Input: ([['x',1],['y',2]], [])
Expected Output: []
Explanation: No operations, so the result list is empty.
Input: ([['p',2]], [['insert','q',3,1],['insert','r',1,0],['getOffset','r'],['getOffset','p'],['getOffset','q']])
Expected Output: [None, None, 0, 1, 3]
Explanation: Start p[0,2). insert(q,3,1) appends q[2,5). insert(r,1,0) prepends r[0,1), shifting p to [1,3) and q to [3,6). So r=0, p=1, q=3.
Hints
- The starting offset of a field is the sum of the sizes of all fields before it in the field order — a prefix sum over the size list.
- insert's index is a position in the field ordering, not a byte offset. Splice the new [name, size] into the list at that index; everything at or after it shifts one slot right and its byte offset grows by the inserted size automatically.
- Keep names and sizes in parallel lists (plus a name->index map for O(1) getOffset lookups). Inserting at index == len appends to the end.
- For the scale in the constraints, a Fenwick tree (BIT) over the sizes gives O(log n) prefix sums, and an order-statistics structure keeps insert at O(log n) — but a straightforward list simulation is enough to pass the console tests.