Design a time-versioned key-value store and find common free time

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.

Time Versioned Key Value Store

Process set/get operations and return the outputs of get operations.

Examples

Example 1

Input: ([["set","foo","bar",1],["get","foo",1],["get","foo",3],["set","foo","baz",4],["get","foo",4],["get","foo",2]],)
Output: ['bar', 'bar', 'baz', 'bar']

Explanation: Gets return the latest value at or before the query timestamp.

Example 2

Input: ([["get","missing",5],["set","a","x",10],["get","a",9]],)
Output: ['', '']

Explanation: Missing keys or too-early timestamps return empty string.

Hints

1. Store timestamped values per key.
2. 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.

Examples

Example 1

Input: ([[[60,120]], [[30,90],[150,180]]], 0, 240)
Output: [[0, 30], [120, 150], [180, 240]]

Explanation: Free time is the complement of the union of busy intervals within the day.

Example 2

Input: ([[], []], 0, 10)
Output: [[0, 10]]

Explanation: If nobody is busy, the whole day is free.

Hints

1. Merge all busy intervals across people.
2. Common free time is the complement within the day bounds.