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
You are given two coding tasks.
## Task 1: Time-versioned key-value store
Design an in-memory data structure that supports:
- `set(key, value, timestamp)`: store the string `value` for string `key` at integer `timestamp`.
- `get(key, timestamp) -> value`: return the value associated with `key` at the largest stored timestamp `t` such that `t <= timestamp`. If there is no such timestamp (or `key` was never set), return an empty string.
**Notes / assumptions**
- Multiple `set` operations may occur for the same `key` at different timestamps.
- Timestamps are integers; you may assume `set` calls for a given key arrive in non-decreasing timestamp order unless stated otherwise.
## Task 2: Find time slots when everyone is available
You are given schedules for `N` people. Each person’s schedule is a list of **busy** time intervals during the day.
- Each busy interval is `[start, end)` with `start < end`.
- For each person, their busy intervals are non-overlapping and sorted by start time.
Return all time intervals (also as `[start, end)`) when **everyone is available** (i.e., when no one is busy). Only include intervals with positive length.
**Clarify in your solution**
- What overall day bounds apply (e.g., `[0, 24*60)` minutes) and how to handle availability outside provided busy intervals.
### Input / Output format (for Task 2)
- **Input:** `schedules: List[List[Interval]]`, where `schedules[i]` is person `i`’s busy intervals.
- **Output:** `List[Interval]` representing common free time intervals.
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
Process set/get operations and return the outputs of get operations.
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
Given each person busy intervals and day bounds, return positive-length intervals when nobody is busy.
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.
Hints
- Merge all busy intervals across people.
- Common free time is the complement within the day bounds.