Design a Time Map (TreeMap/Sorted Map)
Design a data structure that stores a key-value pair and a timestamp. Retrieve the value for a key at a given timestamp (the latest value less than or equal to the given timestamp).
Why Interviewers Ask This
Google asks this to evaluate your ability to balance time complexity with space efficiency in real-world scenarios. They specifically test if you can design a hybrid structure combining hash maps for O(1) key access and sorted lists or binary search for timestamp queries, demonstrating mastery of data organization under strict performance constraints.
How to Answer This Question
1. Clarify requirements: Confirm if timestamps are strictly increasing and if the map needs to handle duplicate keys with different times. 2. Propose the core structure: Suggest using a Hash Map where each key points to a list of (timestamp, value) pairs. 3. Optimize retrieval: Explain that since insertions maintain chronological order, you can use Binary Search on the list to find the largest timestamp less than or equal to the target in O(log N) time. 4. Analyze trade-offs: Discuss why linear search is inefficient for large datasets and how this approach scales better than a full TreeMap for this specific read-heavy pattern. 5. Implement edge cases: Briefly mention handling scenarios where no valid timestamp exists before the query time.
Key Points to Cover
- Explicitly choosing a HashMap combined with an ArrayList for optimal write and read performance
- Recognizing that the list remains sorted naturally upon sequential insertion
- Applying Binary Search (specifically upper_bound logic) to achieve logarithmic retrieval time
- Handling the edge case where no valid timestamp exists prior to the query
- Demonstrating clear understanding of Big-O notation for both operations
Sample Answer
To solve this, I would design a TimeMap class using a HashMap to store keys, where each entry maps to an ArrayList of objects containing both the timestamp and the value. Since the problem implies we often append new ver…
Common Mistakes to Avoid
- Using a standard TreeMap for all data which forces O(log N) insertion instead of O(1)
- Implementing a linear scan through the list for every retrieval query causing TLE on large inputs
- Failing to clarify if timestamps are guaranteed to be monotonically increasing before coding
- Ignoring the scenario where the query timestamp is smaller than the earliest stored timestamp
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.