← OpenAI Interview InsightsSoftware Engineer

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

SeniorPrefer not to say
Jun 2026

Summary

System design round at OpenAI for a software engineer role, focused entirely on building an in-memory key-value store from scratch. The depth they expected was pretty serious, covering concurrency models, eviction policies, and complexity analysis all in one question.

Questions Asked (1)

Q1

Design and implement an in-memory key-value store with get, set, and delete operations. Then extend it to support TTL-based expiration, thread-safe concurrent access, and an eviction policy when the store hits a capacity limit. Walk through your data structures and analyze time and space complexity.

System DesignAlgorithms & Data StructuresTechnical Trade-offs
Author's notes

This question has a deceptively simple surface.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by designing a basic in-memory key-value store using a hash map, then incrementally add TTL, thread-safety, and eviction. For each extension, explain the data structures, concurrency mechanisms, and eviction policy, and analyze time and space complexity. Emphasize trade-offs and justify your choices.

Pro tip: Demonstrate awareness of real-world constraints: discuss how TTL expiration can be handled lazily or actively, and how eviction policies like LRU require additional data structures (e.g., doubly linked list) to achieve O(1) operations. Mention that thread-safety can be achieved with fine-grained locking or lock-free techniques, but be prepared to discuss the trade-offs.

1. Clarify requirements and constraints

Ask clarifying questions about expected load, consistency requirements, and whether TTL should be precise or approximate. Confirm the need for thread-safety and the desired eviction policy (e.g., LRU, LFU).

2. Design basic key-value store

Propose a hash map for O(1) average-case get, set, and delete. Discuss potential collisions and resizing, and analyze space complexity as O(n).

3. Extend with TTL-based expiration

Add a timestamp to each entry and implement lazy expiration on access or a background thread for active expiration. Discuss trade-offs between precision and overhead.

4. Ensure thread-safe concurrent access

Use locks (e.g., per-bucket or global) or lock-free data structures. Discuss read-write locks for read-heavy workloads and the impact on performance.

5. Implement eviction policy and analyze complexity

For LRU, combine a hash map with a doubly linked list to track access order, achieving O(1) operations. Analyze time and space complexity for all operations, including eviction overhead.

Key Points to Mention

  • Hash map provides O(1) average-case time complexity for basic operations, but worst-case O(n) with collisions.
  • TTL can be implemented with lazy expiration (check on access) or active expiration (background thread), each with trade-offs in precision and resource usage.
  • Thread-safety can be achieved with synchronized methods, read-write locks, or concurrent data structures like ConcurrentHashMap, but consider contention and scalability.
  • Eviction policies like LRU require additional data structures (e.g., doubly linked list) to maintain access order and achieve O(1) eviction.
  • Space complexity is O(n) for storing n entries, plus overhead for metadata (timestamps, pointers) and concurrency control.
  • Trade-offs: fine-grained locking improves concurrency but increases complexity; active expiration reduces stale reads but adds overhead.

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