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.