Time-Based Key-Value Store

Data Structures
Medium
Apple
60.9K views

Design a time-based key-value data structure that stores a key, value, and timestamp. The `get` operation must return the value set at the largest timestamp less than or equal to the given timestamp. Use a HashMap of Sorted Maps/Arrays.

Why Interviewers Ask This

Apple evaluates this question to assess a candidate's ability to design efficient data structures that balance read and write performance. It specifically tests understanding of hash maps for O(1) lookups combined with sorted collections or binary search for time-based retrieval. Interviewers want to see if you can handle temporal constraints while optimizing for the 'largest timestamp less than or equal' requirement without degrading system throughput.

How to Answer This Question

1. Clarify requirements: Confirm if timestamps are strictly increasing per key, as this simplifies the logic significantly. 2. Propose the core structure: Suggest a HashMap where keys map to a list or array of pairs (timestamp, value). 3. Discuss insertion strategy: Explain that since timestamps are monotonic, appending to the end of the list is an O(1) operation, avoiding expensive sorting. 4. Define retrieval logic: Describe using Binary Search on the list to find the target timestamp efficiently in O(log N) time, rather than linear scanning. 5. Analyze complexity: Explicitly state Time Complexity for set (O(1)) and get (O(log N)), and Space Complexity (O(N)). 6. Code implementation: Write clean code handling edge cases like missing keys or timestamps smaller than any stored entry.

Key Points to Cover

  • Explicitly stating that timestamps are monotonically increasing per key to justify O(1) appends
  • Choosing Binary Search over linear scan to achieve O(log N) retrieval time
  • Correctly handling edge cases where no valid timestamp exists in the history
  • Clearly articulating the separation of concerns between the HashMap layer and the Sorted List layer
  • Demonstrating awareness of how this structure scales with large volumes of historical data

Sample Answer

To solve this, I would first clarify that timestamps for a specific key are always inserted in increasing order. This assumption allows us to optimize our storage mechanism. I propose using a HashMap where each key point…

Common Mistakes to Avoid

  • Using a standard Map without a sorted container, forcing a linear scan that results in O(N) get complexity
  • Sorting the list upon every insertion instead of appending, which unnecessarily increases write time to O(N log N)
  • Failing to handle the case where the queried timestamp is earlier than all stored timestamps for that key
  • Confusing the global timestamp ordering with per-key ordering, leading to incorrect binary search logic

Sound confident on this question in 5 minutes

Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.

Try it free

Related Interview Questions

How do you implement a queue using two stacks?

Medium
Goldman Sachs

Find K Closest Elements (Heaps)

Medium
Meta

Convert Binary Tree to Doubly Linked List in Place

Hard
Microsoft
Browse all 166 Data Structures questionsBrowse all 54 Apple questions
Try this question free