Meta·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

Jun 2026

Summary

Meta system design round for a software engineer role. The whole session was one massive question about building an in-memory key-field-value store, and it kept growing in scope every time I thought I was done.

Questions Asked (1)

Design and implement an in-memory key-field-value store with monotonic timestamps, supporting set, get, compareAndSet, compareAndDelete, scan, scanByPrefix, setWithTtl, compareAndSetWithTtl, and getWhen operations. Describe your data structures, expiration tracking, history tracking, and analyze time and space complexity.

System DesignAlgorithms & Data StructuresData Modeling

Author's notes

This thing started innocuous enough.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and assumptions, then propose a core data structure (e.g., nested hash maps) with auxiliary structures for TTL and history. Walk through each operation, explaining how timestamps ensure monotonicity and how versioning enables compare-and-set/delete. Finally, analyze time and space complexity, discussing trade-offs and potential optimizations.

Pro tip: Emphasize that monotonic timestamps must be strictly increasing per key to avoid conflicts, and consider using a logical clock or atomic counter. Also, mention that lazy expiration (on access) combined with a min-heap for TTL can balance performance and memory.

1. Clarify Requirements and Assumptions

Ask about expected scale, concurrency needs, persistence, and whether timestamps are per-key or global. Confirm that operations should be atomic and that TTL is in seconds/milliseconds.

2. Design Core Data Structures

Propose a nested map: Map<Key, Map<Field, ValueWithMetadata>> where ValueWithMetadata includes value, timestamp, and optional TTL. For history, maintain a list or tree of versions per field.

3. Implement Operations with Timestamps

For set/get, update/retrieve value and timestamp. For compareAndSet/Delete, check current timestamp matches expected before mutating. For scan/scanByPrefix, iterate over keys/fields efficiently.

4. Handle TTL and Expiration

Store expiration time per field. Use a min-heap or timing wheel for efficient expiration. On access, lazily remove expired entries; optionally run a background cleaner.

5. Analyze Complexity and Trade-offs

Discuss O(1) average for get/set, O(log n) for TTL heap operations, and O(k) for scans. Space is O(total fields + history). Mention trade-offs between eager vs lazy expiration and history retention.

Key Points to Mention

Monotonic timestamps: use a global atomic counter or per-key logical clock to ensure strictly increasing timestamps.
Versioning for compareAndSet/Delete: store a version or timestamp with each value; compare before mutating.
TTL implementation: store expiration time and use a min-heap or timing wheel for efficient expiration; lazy deletion on access.
History tracking: maintain a list of past values with timestamps for getWhen; consider memory trade-offs and pruning strategies.
Scan operations: use sorted structures (e.g., TreeMap) or maintain indexes for efficient prefix scans.
Concurrency: discuss locking (e.g., per-key locks) or lock-free approaches (e.g., CAS) for thread safety.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.