Implement a **round-robin selector** over a fixed list of service nodes, where each node can be toggled available or unavailable while you keep handing out the next available node in circular order. ## What to implement ```python def solution(nodes, operations): ... ``` - **`nodes`** — a list of `(node_id, status)` tuples describing the nodes, in their fixed order. `node_id` is a unique string; `status` is `1` (**available**) or `0` (**unavailable**). - **`operations`** — a list of operation tuples to process **in the given order**. Return a **list** containing one result for **each `pick` operation only**, in the order those picks were processed. ## Operations Process operations one at a time. There are two kinds: - **`('pick',)`** — Select and return the **next available node**, then record its result in the output list. Selection uses a **persistent round-robin pointer** (described below). - **`('set', node_id, status)`** — Update that node's availability to `status` (`1` = available, `0` = unavailable). This operation produces **no output**. Any empty/falsy operation in the list is ignored. ## Round-robin pointer rules - The pointer is an **index into the node list** and starts at index `0`. - A `pick` returns the node at the **smallest index `>=` the current pointer that is currently available**. If no available node exists at or after the pointer, the search **wraps around** and continues from index `0`, returning the first available node before the pointer. - After a successful pick of the node at index `idx`, advance the pointer to `(idx + 1) % len(nodes)`, so the next `pick` continues from just after the node just chosen. - The pointer **persists across picks** (and is unaffected by `set` operations except through availability changes). ## Return values for a pick - On success, append the chosen node's **`node_id`** (a string). - If **no node is currently available** (every node has status `0`, or there are no nodes at all), append **`-1`** (the integer). In this case the pointer is left unchanged. ## Notes & edge cases - Status is **numeric** (`0`/`1`); compare against these numeric constants rather than string-based checks. - If `nodes` is empty, every `pick` returns `-1`. - A `set` may change a node's status to a value it already has; this is a valid no-op update. ## Examples - `nodes = [('A', 0), ('B', 1)]`, `operations = [('pick',), ('pick',), ('pick',)]` → `['B', 'B', 'B']` (A is unavailable, so every pick returns B). - `nodes = [('A', 1), ('B', 1), ('C', 1)]`, `operations = [('pick',), ('pick',), ('set', 'B', 0), ('pick',), ('pick',), ('set', 'A', 0), ('set', 'C', 0), ('pick',)]` → `['A', 'B', 'C', 'A', -1]`. - `nodes = []`, `operations = [('pick',), ('pick',)]` → `[-1, -1]`. - `nodes = [('A', 1), ('B', 0), ('C', 1)]`, `operations = [('pick',), ('pick',), ('pick',)]` → `['A', 'C', 'A']` (B is skipped; after C the pointer wraps back to A). ## Constraints - `0 <= len(nodes) <= 200000` - `0 <= len(operations) <= 200000` - Each `node_id` is unique. - Each `status` is either `0` or `1`.

Implement a custom hash map called **DashMap** from scratch using **separate chaining**, then replay a sequence of operations against it and return the results. Write a function with this signature: ```python def solution(initial_capacity, operations): ... ``` ## What to build DashMap stores **string keys** mapped to **integer values**. Build it on top of an array of buckets, where each bucket is a list that holds every `(key, value)` pair whose key hashes to that slot. **Hash function (use exactly this).** For the current table `capacity`, the slot for a key is: ``` hash(key) = sum(ord(c) for c in key) % capacity ``` This deterministic hash makes collisions easy to produce. Because distinct keys can share the same slot, you must compare keys with **normal string equality** (`k == key`) when searching a bucket, so two different keys with the same hash still coexist correctly. **Capacity floor.** Treat the working capacity as at least `2` (i.e. `max(2, initial_capacity)`), so the table is never empty and you never take a modulus by `0`. ## Inputs - `initial_capacity` — a non-negative integer, the requested starting number of buckets (floored to a minimum of `2` as described above). - `operations` — a list of operation tuples to apply **in order**. Each operation is one of: - `('put', key, value)` — insert or update `key` with `value`. - `('get', key)` — look up `key`. - `('remove', key)` — delete `key`. - `('items',)` — snapshot all current entries. ## Operation semantics - **`('put', key, value)`** — If `key` already exists, overwrite its value in place (the size does not change). Otherwise, add a new `(key, value)` entry and increase the size. This operation produces **no value** in the result list. - **`('get', key)`** — Return the value mapped to `key`, or `None` if `key` is not present. - **`('remove', key)`** — If `key` exists, delete it and return `True`. If `key` is not present, return `False`. - **`('items',)`** — Return a list of all current live `(key, value)` pairs, each appearing **exactly once**, **sorted by key** in ascending order for deterministic output. ## Resizing After a **new** key is inserted by a `put` (not on an update of an existing key), check the load factor. Whenever ``` size > capacity * 0.75 ``` (strictly greater than `0.75`), **double the capacity** and **rehash** every existing entry into the larger table using the new capacity. Resizing only ever happens on growth from a `put`; `get`, `remove`, and `items` never trigger it. ## Return value Return a single list containing the result of each operation that produces an output, in the order those operations were applied. Concretely, append one entry per `get` (its value or `None`), one entry per `remove` (`True`/`False`), and one entry per `items` (the sorted list of pairs). `put` operations contribute nothing to this list. ## Example For `initial_capacity = 2` and operations: ``` [('put', 'ab', 1), ('put', 'ba', 2), ('get', 'ab'), ('get', 'ba'), ('items',)] ``` `'ab'` and `'ba'` hash to the same slot but must coexist. The function returns: ``` [1, 2, [('ab', 1), ('ba', 2)]] ``` ## Constraints - `0 <= initial_capacity <= 10000` - `0 <= len(operations) <= 20000` - Keys are strings of length `0` to `100`. - Values are integers.

Implement a fixed-capacity **in-memory cache** that supports **per-entry TTL (time-to-live) expiration** and **LRU (least-recently-used) eviction**. Implement the function: ```python def solution(capacity, operations): ``` - `capacity` is a non-negative integer: the maximum number of live entries the cache may hold. - `operations` is a list of operation tuples to process **in order**. Each tuple's first element is its kind (`'set'`, `'get'`, or `'keys'`), and every operation carries an integer timestamp. **Timestamps are non-decreasing** across the operation list. Return a **list** containing one result for each `'get'` and `'keys'` operation, in the order those operations occur. `'set'` operations produce **no** output. ## Recency model The cache tracks how recently each live key was used, from **least recently used (LRU)** to **most recently used (MRU)**: - A `'set'` makes its key the **most recently used** entry. - A **successful** `'get'` (the key is still live) also makes that key the **most recently used** entry. ## Expiration (applied before every operation) Before processing **any** operation at timestamp `now`, first **remove all expired entries**. - An entry created by `('set', key, value, ttl, time)` with `ttl is not None` expires at `time + ttl`. It is considered **expired (unavailable) at that exact instant** — i.e. an entry is removed once `now >= expiry_time`. - An entry whose `ttl` is `None` **never expires**. ## Operations **`('set', key, value, ttl, time)`** — Store (or overwrite) `key`. - `ttl` is either `None` (no expiration) or a **positive integer** (`>= 1`); if not `None`, the entry expires at `time + ttl`. - Storing or overwriting a key marks it as **most recently used**. - After the insert, if the number of live entries **exceeds** `capacity`, **evict the least recently used live entry**. - **Special case:** if `capacity <= 0`, the cache holds nothing — the key is **not** stored, and if it already existed it is removed. - A `'set'` appends nothing to the output list. **`('get', key, time)`** — Look up `key`. - If the key is still live, append its **value** to the output and mark the key as **most recently used**. - Otherwise, append `None`. **`('keys', time)`** — Append a **list of the currently live keys**, ordered from **least recently used to most recently used**. ## Constraints - `0 <= capacity <= 100000` - `0 <= len(operations) <= 100000` - Operation timestamps are non-decreasing. - `ttl` is either `None` or an integer `>= 1`. ## Examples Given `capacity = 2` and operations: ``` ('set', 'a', 1, None, 0) ('set', 'b', 2, None, 1) ('get', 'a', 2) -> 1 (a becomes most recently used; order is now b, a) ('set', 'c', 3, None, 3) -> evicts b (the LRU live entry) ('get', 'b', 4) -> None (b was evicted) ('keys', 4) -> ['a', 'c'] ``` Returns `[1, None, ['a', 'c']]`. Given `capacity = 2`: ``` ('set', 'x', 10, 2, 0) -> x expires at time 2 ('get', 'x', 1) -> 10 ('get', 'x', 2) -> None (expired exactly at time 2) ('keys', 2) -> [] ``` Returns `[10, None, []]`.