Design In-Memory Database — Multi-Field Filtering

Problem Statement#

Design a simplified in-memory database supporting record-level operations: set(key, field, value) sets a field in a key's record; get(key, field) returns the field value or ""; delete(key, field) removes a field and returns true if it existed; scan(key) returns all fields and values sorted by field name; scanByRank(key, field, rank) returns the top rank entries sorted by field value descending.

Constraints:

• 1 <= key, field, value length <= 20
• At most 10^3 calls to each operation
• Values for scanByRank are numeric strings

Input:  set("a","b","100"), set("a","c","50"), scan("a")
Output: ["b(100)", "c(50)"]

Input:  set("a","b","100"), set("a","c","50"), scanByRank("a","b",1)
Output: ["b(100)"]

Why This Problem Matters#

This problem models the core of Redis hashes (HSET, HGET, HDEL, HGETALL) combined with sorted set ranking. Redis is used at virtually every FAANG company as the primary in-memory cache and data structure server. Understanding how to implement nested hashmaps with sorted access patterns is foundational to backend engineering.

Amazon asks this problem to evaluate whether candidates can design data store abstractions from first principles. The combination of a hashmap for O(1) field access with sorted iteration for scan queries mirrors how columnar databases, document stores, and key-value engines handle mixed workloads.

LeetCode's own contest scoring system uses a similar structure: each user's submission history is a record, score is a field, and the leaderboard scan is a scanByRank equivalent. Understanding this abstraction generalises to building any ranked entity store.

The Core Insight#

Use a two-level nested hashmap: outer map keyed by key, inner map keyed by field with string value. For scan, sort the inner map's items by field name. For scanByRank, sort by numeric value descending, then field name ascending for ties.

Java's TreeMap provides automatic field-name ordering for scan at O(log N) per insert. Python's defaultdict(dict) with sorted() at query time is simpler. The critical insight is that O(N log N) sorting at query time is acceptable given the constraint of at most 1000 records per key.

The output format "field(value)" must be produced by string concatenation—a common source of bugs if forgotten.

Visual Dry Run#

Solution (Optimal)#

from collections import defaultdict
 
class InMemoryDatabase:
    def __init__(self):
        self.db = defaultdict(dict)
 
    def set(self, key: str, field: str, value: str) -> None:
        self.db[key][field] = value
 
    def get(self, key: str, field: str) -> str:
        return self.db[key].get(field, "")
 
    def delete(self, key: str, field: str) -> bool:
        if key in self.db and field in self.db[key]:
            del self.db[key][field]
            return True
        return False
 
    def scan(self, key: str) -> list:
        if key not in self.db:
            return []
        return sorted(f"{k}({v})" for k, v in self.db[key].items())
 
    def scanByRank(self, key: str, field: str, rank: int) -> list:
        if key not in self.db:
            return []
        items = sorted(
            self.db[key].items(),
            key=lambda x: (-int(x[1]), x[0])
        )
        return [f"{k}({v})" for k, v in items[:rank]]

class InMemoryDatabase {
    constructor() {
        this.db = new Map();
    }
 
    set(key, field, value) {
        if (!this.db.has(key)) this.db.set(key, new Map());
        this.db.get(key).set(field, value);
    }
 
    get(key, field) {
        return this.db.get(key)?.get(field) ?? "";
    }
 
    delete(key, field) {
        if (this.db.has(key) && this.db.get(key).has(field)) {
            this.db.get(key).delete(field);
            return true;
        }
        return false;
    }
 
    scan(key) {
        const r = this.db.get(key);
        if (!r) return [];
        return [...r.entries()]
            .sort((a, b) => a[0].localeCompare(b[0]))
            .map(([k, v]) => `${k}(${v})`);
    }
 
    scanByRank(key, field, rank) {
        const r = this.db.get(key);
        if (!r) return [];
        return [...r.entries()]
            .sort((a, b) => Number(b[1]) - Number(a[1]) || a[0].localeCompare(b[0]))
            .slice(0, rank)
            .map(([k, v]) => `${k}(${v})`);
    }
}

Time: O(N log N) for scan and scanByRank where N is fields per key; O(1) for set, get, delete
Space: O(K * N) — K keys each with N fields

Common Mistakes#

• Forgetting the output format: "field(value)" not "field: value" or [field, value]
• In scanByRank, sorting by string value rather than numeric: "9" > "10" lexicographically but not numerically
• In delete, returning true even when the field did not exist—must check existence before deleting
• Not handling missing keys in scan—returning None instead of an empty list
• In scan, sorting the output strings directly works because "field(value)" sorts by field name first, but this breaks if field names contain parentheses

Interview Tips#

• Clarify the output format upfront—"field(value)" is easy to forget and causes wrong answers
• For scanByRank, explicitly mention the tie-breaking rule: same numeric value, sort by field name ascending
• Discuss the Java TreeMap optimisation: O(log N) per insert vs O(N log N) per scan, better when scans are frequent
• Connect to Redis: set=HSET, get=HGET, delete=HDEL, scan=HGETALL+sort, scanByRank=ZREVRANGEBYSCORE

Follow-up Questions#

• How would you support transactions (set multiple fields atomically)? (Write-ahead log + rollback on failure; or use a copy-on-write approach)
• How would you persist this database to disk? (Serialize to JSON/binary on every write, or append-only log with periodic snapshots)
• How would you support indexing on field values for fast scanByRank? (Maintain a sorted secondary index per field; update it on every set and delete)
• What if values could be floats or strings, not just integers? (Store as strings but parse as needed; sort with a type-aware comparator)
• How would you support expiry on keys or fields (TTL)? (Store expiry timestamp alongside value; check and prune on access)

Key Takeaways#

• Use a two-level nested hashmap: outer keyed by record key, inner keyed by field name
• set, get, delete are all O(1); scan and scanByRank are O(N log N) where N is fields per key
• scanByRank sorts by numeric value descending, then field name ascending for ties—parse values as integers before comparing
• Output format is "field(value)" concatenated as a string—a common source of bugs
• Java's TreeMap for the inner map gives automatic field-name ordering for scan without sorting at query time
• This design mirrors Redis HASH commands (HSET, HGET, HDEL, HGETALL) with added ranking capability
• Always return an empty list (not None or null) for missing keys in scan and scanByRank