Implement a Level-Aware Expiring Inventory Store
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Implement an inventory store with levels, weights, timestamps, and expiration. `store` adds an item. `retrieve(timestamp)` returns and removes the highest-weight active item from the highest level where at least 50 percent of all items ever stored on that level are still active.
Implement:
```python
def process_inventory_operations(operations: list[list]) -> list[str]:
pass
```
Return one item id for each retrieve, or an empty string if none is eligible.
Overview: Practice a Optiver coding interview problem focused on implement a level-aware expiring inventory store. The prompt emphasizes edge cases, clean implementation, and verifiable test behavior without revealing the solution.
Process store and retrieve operations with level eligibility, expiration, and highest-weight retrieval.
Examples
Input: ([["store","a",1,5,0,None],["retrieve",1]],)
Expected Output: ["a"]
Explanation: Basic retrieval.
Input: ([["retrieve",1]],)
Expected Output: [""]
Explanation: Empty store.
Community answers
Answer by manishamehra2903
import heapq
from collections import defaultdict
def solution(operations):
if isinstance(operations, dict):
operations = operations.get("operations", [])
total = defaultdict(int) # ever stored per level
active = defaultdict(int) # currently active per level
items = {} # id -> (level, exp)
heaps = defaultdict(list) # level -> [(-weight, -time, id)]
expq = [] # [(exp_time, id)]
out = []
def expire(t):
while expq and expq[0][0] <= t:
e, i = heapq.heappop(expq)
it = items.get(i)
if it and it[1] == e: # still same item record
active[it[0]] -= 1
del items[i]
for op in operations:
if op[0] == "store":
_, i, lvl, w, t, ttl = op
expire(t)
exp = None if ttl is None else t + ttl
total[lvl] += 1
if exp is None or t < exp:
items[i] = (lvl, exp)
active[lvl] += 1
heapq.heappush(heaps[lvl], (-w, -t, i))
if exp is not None:
heapq.heappush(expq, (exp, i))
else:
t = op[1]
expire(t)
lvl = -1
for l, tot in total.items(): # could be heap-optimized, kept short here
if active[l] * 2 >= tot and active[l] > 0 and l > lvl:
lvl = l
if lvl < 0:
out.append("")
continue
h = heaps[lvl]
while h:
w, nt, i = h[0]
it = items.get(i)
if not it or it[0] != lvl or (it[1] is not None and t >= it[1]):
heapq.heappop(h)
else:
break
if not h:
out.append("")
continue
, , i = heapq.heappop(h)
l, _ = items.pop(i)
active[l] -= 1
out.append(i)
return out