Oracle·Software Engineer·Onsite - System Design / Architecture·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Oracle system design round for a software engineer role, centered on building a stripped-down in-memory key-value store from scratch. The scope kept expanding mid-interview, which I wasn't fully ready for.

Questions Asked (1)

Design and implement a simplified in-memory store supporting SET and GET for string keys, list operations (push and remove), and per-key expiration. Walk through your data structure choices and time complexity, and explain how you'd handle concurrent access.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with a plain hash map and felt pretty confident until they asked about list operations.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (operations, expiration semantics, concurrency expectations) and then propose a design using a hash map for key-value storage, with lists as doubly linked lists or dynamic arrays, and expiration via lazy deletion plus a min-heap or timing wheel. Walk through time complexity for each operation and discuss concurrency using fine-grained locking or sharding, highlighting trade-offs.

Pro tip: Demonstrate awareness of real-world systems like Redis by mentioning how they handle expiration (e.g., active vs. passive) and concurrency (single-threaded event loop vs. multi-threaded), and relate your choices to those patterns.

1. Clarify Requirements

Ask about expected operations, data sizes, expiration precision, and concurrency needs to scope the design appropriately.

2. Choose Core Data Structures

Select a hash map for key-value storage, and for lists, choose between doubly linked lists (O(1) push/remove at ends) or dynamic arrays (O(1) amortized push, O(n) remove) based on access patterns.

3. Design Expiration Mechanism

Implement lazy expiration on access combined with a min-heap or timing wheel for active cleanup, ensuring O(log n) or O(1) expiration handling.

4. Analyze Time Complexity

For each operation (SET, GET, push, remove, expire), state the average and worst-case time complexity, justifying with the chosen data structures.

5. Address Concurrency

Discuss locking strategies (global lock, per-key locks, sharding) or lock-free approaches, and explain trade-offs between simplicity and scalability.

Key Points to Mention

Hash map provides O(1) average time for SET and GET, but worst-case O(n) with poor hash function; mention collision handling.
List operations: doubly linked list gives O(1) push/remove at both ends, but O(n) for arbitrary index; dynamic array gives O(1) amortized push and O(n) remove.
Expiration: lazy deletion avoids overhead but may leave expired keys; active expiration via min-heap gives O(log n) per expiration but requires cleanup thread.
Concurrency: coarse-grained locking is simple but limits throughput; fine-grained per-key locks or sharding improve concurrency but add complexity.
Consider memory overhead and trade-offs: e.g., min-heap adds O(n) space, but timing wheel can be more efficient for many timers.
Mention real-world systems like Redis: single-threaded event loop simplifies concurrency, but multi-threaded designs need careful synchronization.

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