Design a Tiered Expiring Item Store

Question

Design a tiered expiring item store that allows items to be stored and retrieved based on specific expiration and priority rules.

Codemia · Accepted Answer

To design a tiered expiring item store, we need to define the following requirements:
1. **Storage Structure**: The store should be organized into tiers, where each tier can hold items that have a specific expiration time.
2. **Item Attributes**: Each item should have a weight, a timestamp for when it was added, and a level indicating its tier.
3. **Retrieval Logic**: When retrieving items, the system should prioritize items with the highest weight and ensure they are not expired. Additionally, it should only retrieve from levels that have at least 50% of their capacity remaining.

The design will consist of a class `TieredItemStore` with the following methods:
- `__init__`: Initializes the store with a defined number of tiers and their capacities.
- `store(item)`: Adds an item to the appropriate tier based on its level and timestamp.
- `retrieve()`: Retrieves items from the highest tier down, prioritizing by weight while checking for expiration and capacity constraints.

The `store` method will check the item's level and add it to the corresponding tier's list. The `retrieve` method will iterate through the tiers from highest to lowest, filtering out expired items and ensuring that the remaining capacity is sufficient. Items will be sorted by weight before retrieval to ensure the highest priority items are returned first.

This design is efficient for a moderate number of items, but as the store scales, we may need to consider more advanced data structures like heaps for prioritized retrieval. Additionally, we could implement a background process to clean up expired items to maintain performance.

Here is a basic implementation of the `TieredItemStore` class:
```python
import time

class TieredItemStore:
    def __init__(self, tiers):
        self.tiers = {level: [] for level in range(tiers)}

def store(self, item, level):
        timestamp = time.time()
        self.tiers[level].append((item, timestamp))

def retrieve(self):
        items = []
        for level in sorted(self.tiers.keys(), reverse=True):
            for item, timestamp in self.tiers[level]:
                if time.time() - timestamp < EXPIRATION_TIME:
                    items.append(item)
        return sorted(items, key=lambda x: x.weight, reverse=True)
```
This code initializes a store with a specified number of tiers, allows items to be stored with a timestamp, and retrieves non-expired items sorted by weight.

Design a Tiered Expiring Item Store

Optiver

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Optiver Software Engineer Interview Guide

Related Questions

Design a scalable Search System

Design a Video Streaming for Rippling

Design a Load Balancing Service

Design a Image Processing Service

Build a high-throughput Image Processing Pipeline