Design a time-versioned key-value store and find common free time
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Quick Answer: This question evaluates proficiency in designing time-versioned data structures and reasoning about interval-based scheduling, covering competencies in temporal data retrieval, state versioning, and computing common free time across multiple calendars.
Time Versioned Key Value Store
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([["set","foo","bar",1],["get","foo",1],["get","foo",3],["set","foo","baz",4],["get","foo",4],["get","foo",2]],)
Expected Output: ['bar', 'bar', 'baz', 'bar']
Explanation: Gets return the latest value at or before the query timestamp.
Input: ([["get","missing",5],["set","a","x",10],["get","a",9]],)
Expected Output: ['', '']
Explanation: Missing keys or too-early timestamps return empty string.
Hints
- Store timestamped values per key.
- Binary search for the rightmost timestamp <= query time.
Common Free Time
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[[60,120]], [[30,90],[150,180]]], 0, 240)
Expected Output: [[0, 30], [120, 150], [180, 240]]
Explanation: Free time is the complement of the union of busy intervals within the day.
Input: ([[], []], 0, 10)
Expected Output: [[0, 10]]
Explanation: If nobody is busy, the whole day is free.
Input: ([[[0,10]], [[10,20]]], 0, 20)
Expected Output: []
Explanation: Back-to-back busy intervals leave no gap.
Hints
- Merge all busy intervals across people.
- Common free time is the complement within the day bounds.