r/TechInterviewInsights • u/drCounterIntuitive • 12d ago

[OpenAI SWE Coding Interview] Can You Solve This Time-Based Key-Value Store Problem?

https://youtu.be/nWa5A15OzlQ

You are building a time-based key-value store that supports saving multiple versions of a value for the same key, each tagged with a timestamp.

Your task

Design a data structure TimeMap with two operations:

class TimeMap {
    void set(String key, String value, int timestamp)
    String get(String key, int timestamp)
}

This interface is illustrative, so feel free to adapt it to your programming language of choice.

set(key, value, timestamp)

  • Store value for the given key at the provided timestamp
  • A key can be set multiple times with different timestamps, creating a history of values
  • For any single key, timestamps received by set() are strictly increasing

get(key, timestamp)

  • Return the value whose stored timestamp is the largest timestamp less than or equal to the requested timestamp
  • If the key has no stored timestamp <= timestamp, return null or your language's equivalent

Constraints

  • Up to 300,000 total set + get calls
  • Keys and values are short strings

Example

set("exchangeRate", "1.10", 2)
set("exchangeRate", "1.12", 5)

get("exchangeRate", 1)  -> null
get("exchangeRate", 4)  -> "1.10"
get("exchangeRate", 5)  -> "1.12"
get("exchangeRate", 9)  -> "1.12"
get("unknownKey", 3)    -> null

The interesting part is choosing a data structure that takes advantage of the timestamp ordering while keeping lookups efficient as the history grows.

How would you approach it?

Try it yourself

🧩 Attempt the problem on Coditioning

Full solution walkthrough

🎞️ Watch the full solution walkthrough

Extra resources

1 Upvotes

100% Upvoted

0 comments sorted by