Quick Overview

This question evaluates a candidate's ability to design an object-oriented data structure with multiple prioritized eviction and expiration rules. It tests skills in coding and algorithms, specifically simulating TTL-based expiry alongside tiered, capacity-aware selection logic. Such multi-rule state machine problems are common in interviews to assess careful requirement tracking and practical implementation of layered constraints.

Multi-Level Warehouse Storage with Weighted Retrieval

Company: Ramp

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

## Multi-Level Warehouse Storage with Weighted Retrieval You are building the in-memory engine for an automated warehouse. The warehouse is a stack of horizontal **levels** (shelves), indexed from `0` at the **top** to `num_levels - 1` at the **bottom**. Each level can hold at most `capacity` items. Every item has an integer `weight` and is placed at an integer `timestamp` (a logical clock). An item **expires** once `ttl` time units have elapsed since it was stored: an item stored at time `t` is valid for a query at time `q` while `q < t + ttl`, and is expired (and must never be returned) once `q >= t + ttl`. Implement a class `Storage` with the methods below. ### Methods **`__init__(self, num_levels, capacity, ttl)`** Initialize an empty warehouse with `num_levels` levels, each able to hold `capacity` items, and the given item `ttl`. Assume `num_levels >= 1`, `capacity >= 1`, and `ttl >= 1`. **`store(self, item_id, weight, timestamp) -> int`** Place one item into the warehouse. - The item must be placed on the **topmost** level (smallest index) that currently has at least one free slot, counting only items that have not yet expired at this `timestamp`. - Return the index of the level on which the item was placed. - If every level is full of non-expired items, do not store the item and return `-1`. - You may assume each `item_id` passed to `store` is unique across the lifetime of the object, and that `timestamp` values are non-decreasing across successive calls. **`retrieve(self, timestamp) -> Optional[int]`** Select and remove exactly one item, returning its `item_id`. Apply these rules **in order**: 1. **Expire first.** On every level, remove all items that are expired at this `timestamp` (`timestamp >= stored_time + ttl`). Their slots become free and they can never be retrieved. 2. **Scan top to bottom.** Consider levels from index `0` downward. A level is a **candidate** only if, after step 1, it is still at least half full — that is, the number of valid items currently on it is at least `ceil(capacity / 2)`. 3. **Pick within the first candidate level.** From the topmost candidate level, choose the item with the **greatest `weight`**; break ties by the **smallest `item_id`**. Remove it from that level and return its `item_id`. 4. If no level qualifies, return `None`. ### Constraints & Notes - Levels are the primary ordering for retrieval (topmost eligible level wins); weight is only the selector **within** the chosen level. - "Half full" uses the level's `capacity`, not how many items it has ever held: a level with `c` valid items qualifies iff `c >= ceil(capacity / 2)`. - All `weight`, `timestamp`, and `ttl` values are non-negative integers; `weight` may repeat across items. - Expiration is evaluated lazily at the start of each `retrieve` (and when counting free slots in `store`); you are not required to evict expired items at any other time. ### Example ```text s = Storage(num_levels=2, capacity=2, ttl=10) s.store(1, weight=5, timestamp=0) # -> 0 (level 0 has space) s.store(2, weight=8, timestamp=0) # -> 0 (level 0 still has space) s.store(3, weight=3, timestamp=1) # -> 1 (level 0 now full) s.retrieve(timestamp=2) # -> 2 # No expirations (ttl=10). Level 0 has 2 valid items; ceil(2/2)=1, so it is a # candidate and is topmost. Highest weight on level 0 is item 2 (weight 8). s.retrieve(timestamp=2) # -> 1 # Level 0 now has 1 valid item; 1 >= ceil(2/2)=1, still a candidate. # Only item 1 remains there, so it is returned. s.retrieve(timestamp=2) # -> 3 # Level 0 has 0 items (0 < 1), not a candidate. Level 1 has 1 item # (1 >= 1), so item 3 is returned. s.retrieve(timestamp=2) # -> None (warehouse empty) ``` An expiry example: with `ttl=10`, an item stored at `timestamp=0` is still valid at `retrieve(timestamp=9)` but is treated as expired (removed, never returned) at `retrieve(timestamp=10)`.

Overview: This question evaluates a candidate's ability to design an object-oriented data structure with multiple prioritized eviction and expiration rules. It tests skills in coding and algorithms, specifically simulating TTL-based expiry alongside tiered, capacity-aware selection logic. Such multi-rule state machine problems are common in interviews to assess careful requirement tracking and practical implementation of layered constraints.

Read the full Ramp Software Engineer interview experience this question came from

Build the in-memory engine for an automated warehouse: a stack of horizontal **levels** indexed from `0` (top) to `num_levels - 1` (bottom), each holding at most `capacity` items. Every item has an integer `weight` and is stored at an integer `timestamp` (a logical clock). An item stored at time `t` is valid while `q < t + ttl` and is **expired** (never returned) once `q >= t + ttl`. Implement a class `Storage(num_levels, capacity, ttl)` with: - `store(item_id, weight, timestamp) -> int`: place the item on the **topmost** level with a free slot, counting only non-expired items. Return that level's index, or `-1` if every level is full of non-expired items. Each `item_id` is unique; `timestamp` values are non-decreasing. - `retrieve(timestamp) -> Optional[int]`: (1) remove all items expired at this `timestamp` on every level; (2) scan levels top to bottom, treating a level as a **candidate** only if it still holds at least `ceil(capacity / 2)` valid items; (3) from the topmost candidate, remove and return the item with the **greatest weight**, breaking ties by the **smallest item_id**; (4) return `None` if no level qualifies. **Console harness:** because the grader runs a single function, drive the class with `solution(operations, values)`. `operations[0]` is `"Storage"` (the constructor, whose args are `values[0]`); subsequent entries are `"store"` or `"retrieve"`. Return a list with one result per operation — `None` for the constructor, the `store`/`retrieve` return values otherwise.

Constraints

  • num_levels >= 1, capacity >= 1, ttl >= 1
  • All weight, timestamp, and ttl values are non-negative integers; weight may repeat across items
  • timestamp values are non-decreasing across successive calls
  • Each item_id passed to store is unique across the object's lifetime
  • An item stored at t is valid for query q while q < t + ttl; expired once q >= t + ttl
  • A level is a retrieval candidate iff it holds >= ceil(capacity / 2) valid items

Examples

Input: (['Storage', 'store', 'store', 'store', 'retrieve', 'retrieve', 'retrieve', 'retrieve'], [[2, 2, 10], [1, 5, 0], [2, 8, 0], [3, 3, 1], [2], [2], [2], [2]])

Expected Output: [None, 0, 0, 1, 2, 1, 3, None]

Explanation: Main example from the prompt.

Input: (['Storage', 'store', 'retrieve'], [[1, 1, 10], [1, 5, 0], [10]])

Expected Output: [None, 0, None]

Explanation: Item stored at t=0 is expired at t=10 (10 >= 0+10), so retrieve returns None.

Hints

  1. Track each item as (item_id, weight, timestamp) grouped per level. Expiration is lazy: only prune a level when you touch it (during store's free-slot count and at the start of retrieve).
  2. store scans levels from index 0 upward; place on the first level whose non-expired count is below capacity, else return -1.
  3. retrieve first expires everything, then finds the topmost level with >= ceil(capacity/2) = (capacity + 1) // 2 valid items, then selects max weight with smallest item_id as the tie-breaker.
  4. Level order dominates: a lower-index candidate always wins over a heavier item sitting on a level below it.

Loading coding console...