Time Based Key-Value Store

📋

Problem

Imagine you are building a caching system that stores values with timestamps and you need to retrieve the most recent value for a key at any given time.

Design a time-based key-value data structure that supports two operations: set(key, value, timestamp) and get(key, timestamp). The set operation stores the key and value, along with the given timestamp. The get operation retrieves the value such that set was called previously with timestamp_prev <= timestamp. If there are multiple such values, return the one with the largest timestamp_prev. If there is no such value, return an empty string "".

1 ≤ number of set/get operations ≤ 10^5All timestamps for set operations are strictly increasing for the same keyKeys and values are strings of lowercase lettersTimestamps are positive integers

Edge cases: get on a key that was never set → returns ""get with timestamp earlier than any set timestamp → returns ""multiple sets with same key but increasing timestamps → returns correct latest value

</>

IDE

class TimeMap: def set(self, key: str, value: str, timestamp: int) -> None: pass def get(self, key: str, timestamp: int) -> str: passclass TimeMap { public void set(String key, String value, int timestamp) { // implementation } public String get(String key, int timestamp) { // implementation return ""; } }class TimeMap { public: void set(string key, string value, int timestamp) { // implementation } string get(string key, int timestamp) { // implementation return ""; } };class TimeMap { set(key, value, timestamp) { // implementation } get(key, timestamp) { // implementation return ""; } }

class TimeMap:
    def __init__(self):
        # Write your solution here
        pass
    def set(self, key: str, value: str, timestamp: int) -> None:
        pass
    def get(self, key: str, timestamp: int) -> str:
        pass

class TimeMap {
    public TimeMap() {
        // Write your solution here
    }
    public void set(String key, String value, int timestamp) {
        // Write your solution here
    }
    public String get(String key, int timestamp) {
        // Write your solution here
        return "";
    }
}

#include <string>
using namespace std;

class TimeMap {
public:
    TimeMap() {
        // Write your solution here
    }
    void set(string key, string value, int timestamp) {
        // Write your solution here
    }
    string get(string key, int timestamp) {
        // Write your solution here
        return "";
    }
};

class TimeMap {
    constructor() {
        // Write your solution here
    }
    set(key, value, timestamp) {
        // Write your solution here
    }
    get(key, timestamp) {
        // Write your solution here
        return "";
    }
}

Common Bugs to Avoid

Wrong: "bar" for get("foo", 0)Returning value for timestamp earlier than any set timestamp instead of empty string.✅ Add check in get to return "" if query timestamp < smallest stored timestamp.

Wrong: "bar" for get("foo", 2) when set timestamps are 1 and 3Returning first timestamp <= query instead of largest timestamp <= query (greedy trap).✅ Use binary search to find rightmost timestamp <= query timestamp.

Wrong: "" for get("foo", 5) when last set timestamp is 3Returning empty string for timestamp greater than max stored timestamp.✅ Return value corresponding to max timestamp if query timestamp > max timestamp.

Wrong: TLE on large inputUsing linear search for get operations causing O(n) per query.✅ Implement binary search on timestamps for O(log n) get queries.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Ensure your binary search logic is robust and handles all boundary cases.

Optimize your get method to use binary search for large input efficiency.

t1_01basic

Input"set(\"foo\", \"bar\", 1)\nget(\"foo\", 1)\nget(\"foo\", 3)\nset(\"foo\", \"bar2\", 4)\nget(\"foo\", 4)\nget(\"foo\", 5)"

Expected"\"bar\"\n\"bar\"\n\"bar\"\n\"bar2\"\n\"bar2\""

⏱ Performance - must finish in 2000ms

At timestamp 1, 'foo' is set to 'bar'. Getting at timestamp 1 returns 'bar'. Getting at timestamp 3 returns 'bar' because the closest timestamp <= 3 is 1. Then at timestamp 4, 'foo' is updated to 'bar2'. Getting at timestamp 4 returns 'bar2'. Getting at timestamp 5 also returns 'bar2' as it's the latest before or at 5.

💡 Think about storing values with their timestamps for each key.

💡 Use binary search on the timestamps list to find the closest timestamp <= query timestamp.

💡 Implement get by searching timestamps with bisect or equivalent to find the right value efficiently.

Why it failed: Failed to return correct value for get queries at various timestamps. Likely linear search without stopping early or incorrect binary search. Fix by implementing binary search to find largest timestamp <= query timestamp.

✓ Correctly returns values for all get queries using timestamp-based retrieval.

t1_02basic

Input"set(\"key1\", \"val1\", 5)\nset(\"key1\", \"val2\", 10)\nget(\"key1\", 5)\nget(\"key1\", 7)\nget(\"key1\", 10)\nget(\"key1\", 15)"

Expected"\"val1\"\n\"val1\"\n\"val2\"\n\"val2\""

⏱ Performance - must finish in 2000ms

Set 'key1' at timestamp 5 to 'val1' and at 10 to 'val2'. Gets at 5 and 7 return 'val1' (closest <= timestamp). Gets at 10 and 15 return 'val2'.

💡 Remember timestamps are strictly increasing for each key.

💡 Binary search can quickly find the right timestamp to return the value.

💡 Check edge cases where timestamp equals or is between stored timestamps.

Why it failed: Incorrect value returned for get queries between or at timestamps. Possibly using linear search without proper boundary checks. Fix by using binary search with correct boundary conditions.

✓ Correctly handles multiple sets and returns expected values for get queries.

t2_01edge

Input"get(\"nonexistent\", 10)"

Expected"\"\""

⏱ Performance - must finish in 2000ms

Getting a key that was never set returns empty string.

💡 Check if the key exists before searching timestamps.

💡 Return empty string if key not found.

💡 Add a guard clause at the start of get to handle missing keys.

Why it failed: Returned non-empty string for a key never set. Fix by checking key existence before searching timestamps in get method.

✓ Correctly returns empty string for keys never set.

t2_02edge

Input"set(\"a\", \"x\", 5)\nget(\"a\", 1)"

Expected"\"\""

⏱ Performance - must finish in 2000ms

Getting a timestamp earlier than any set timestamp returns empty string.

💡 Check if any stored timestamp is <= query timestamp.

💡 If none found, return empty string.

💡 Use binary search to detect if query timestamp is less than smallest stored timestamp.

Why it failed: Returned a value for a timestamp earlier than any set timestamp. Fix by returning empty string when no timestamp <= query timestamp exists.

✓ Correctly returns empty string for timestamps earlier than any set timestamp.

t2_03edge

Input"set(\"k\", \"v1\", 1)\nset(\"k\", \"v2\", 2)\nset(\"k\", \"v3\", 3)\nget(\"k\", 3)"

Expected"\"v3\""

⏱ Performance - must finish in 2000ms

Multiple sets with same key but increasing timestamps return the latest value at exact timestamp.

💡 Ensure timestamps are stored in order and binary search returns exact match if exists.

💡 Check boundary conditions when timestamp equals stored timestamp.

💡 Return value corresponding to exact timestamp if found.

Why it failed: Returned incorrect value for exact timestamp match. Fix by checking for exact timestamp match in binary search before returning closest smaller timestamp.

✓ Correctly returns value for exact timestamp match.

t3_01corner

Input"set(\"foo\", \"bar\", 1)\nset(\"foo\", \"bar2\", 2)\nset(\"foo\", \"bar3\", 3)\nget(\"foo\", 2)"

Expected"\"bar2\""

⏱ Performance - must finish in 2000ms

Tests greedy approach trap: must not return first timestamp <= query but the largest timestamp <= query.

💡 Beware of returning first timestamp <= query instead of largest.

💡 Use binary search to find rightmost timestamp <= query.

💡 Use bisect_right - 1 or equivalent to get largest valid timestamp.

Why it failed: Returned earliest timestamp value <= query instead of largest. Fix by using binary search to find rightmost timestamp <= query.

✓ Correctly returns value for largest timestamp <= query.

t3_02corner

Input"set(\"key\", \"val1\", 1)\nset(\"key\", \"val2\", 3)\nget(\"key\", 2)"

Expected"\"val1\""

⏱ Performance - must finish in 2000ms

Tests off-by-one error in binary search boundaries for timestamps between stored values.

💡 Check binary search mid calculation and boundary updates.

💡 Ensure search narrows correctly to find largest timestamp <= query.

💡 Adjust low/high pointers carefully to avoid skipping valid timestamps.

Why it failed: Returned empty or wrong value for timestamp between stored timestamps. Fix binary search boundaries to correctly find largest timestamp <= query.

✓ Correctly handles timestamps between stored values.

t3_03corner

Input"set(\"a\", \"x\", 1)\nset(\"a\", \"y\", 2)\nset(\"a\", \"z\", 3)\nget(\"a\", 4)"

Expected"\"z\""

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack style unbounded vs 0/1 constraint: must not return value for timestamp > max stored timestamp if none exists.

💡 Remember timestamps are strictly increasing and get returns latest <= query.

💡 Check if query timestamp is greater than max stored timestamp and return last value.

💡 Do not return empty string if query timestamp exceeds max timestamp.

Why it failed: Returned empty string for timestamp greater than max stored timestamp. Fix by returning value of max timestamp if query timestamp > max timestamp.

✓ Correctly returns last value for timestamps greater than max stored timestamp.

t4_01performance

Input{"operations":[{"op":"set","key":"key0","value":"val0","timestamp":1},{"op":"set","key":"key1","value":"val1","timestamp":2},{"op":"set","key":"key2","value":"val2","timestamp":3},{"op":"set","key":"key3","value":"val3","timestamp":4},{"op":"set","key":"key4","value":"val4","timestamp":5},{"op":"set","key":"key5","value":"val5","timestamp":6},{"op":"set","key":"key6","value":"val6","timestamp":7},{"op":"set","key":"key7","value":"val7","timestamp":8},{"op":"set","key":"key8","value":"val8","timestamp":9},{"op":"set","key":"key9","value":"val9","timestamp":10}],"get_queries":[]}

Expectednull

⏱ Performance - must finish in 2000ms

Performance test with 10 set operations (can be scaled to 10^5 in real environment). Must complete in O(log n) per get and O(1) per set.

💡 Brute force linear search on timestamps will time out for large inputs.

💡 Use binary search on sorted timestamps for efficient get operations.

💡 Store timestamps and values in arrays per key for O(1) append and O(log n) search.

Why it failed: Solution times out due to linear search on timestamps for get operations. Fix by implementing binary search to achieve O(log n) get complexity.

✓ Solution runs within time limits using binary search for get operations.

Practice

1. Consider the following Python function that checks if a continuous subarray sum is a multiple of k. What is the return value when called with nums = [1, 2, 3] and k = 5?

easy

A. True

B. False

C. Raises an exception due to modulo by zero

D. Returns True only if k is negative

Solution

1. Step 1: Trace prefix sums modulo k for nums=[1,2,3], k=5

   Prefix sums: 1, 3, 6; modulo 5: 1, 3, 1.

2. Step 2: Check remainder_map updates and subarray length condition

   At i=0, remainder 1 stored; at i=1, remainder 3 stored; at i=2, remainder 1 found again with distance 2 (2 - 0), which is >1, so return True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Subarray [2,3] sums to 5, divisible by k=5 [OK]

Hint: Check remainder repeats with index difference >1 [OK]

Common Mistakes:

• Forgetting to check subarray length >1
• Miscomputing modulo with negative k
• Returning True for single element subarrays

2. You are given an integer array and a number k. You need to find the length of the longest contiguous subarray whose sum is divisible by k. Which of the following approaches guarantees an optimal solution in O(n) time?

easy

A. Use a nested loop to check all subarrays and verify divisibility by k.

B. Use dynamic programming to store the maximum length subarray ending at each index with sum divisible by k.

C. Use a sliding window that expands and contracts based on the current sum modulo k.

D. Use prefix sums and a hash map to store the earliest index of each remainder modulo k.

Solution

1. Step 1: Understand the problem constraints

   We want the longest subarray with sum divisible by k. Checking all subarrays with nested loops is O(n^2) and inefficient.

2. Step 2: Recognize prefix sum + remainder pattern

   Using prefix sums modulo k, if two prefix sums have the same remainder, the subarray between them is divisible by k. Storing earliest indices of remainders in a hash map allows O(n) solution.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix sums + hash map is classic for subarray sum modulo problems [OK]

Hint: Prefix sums + remainder hash map -> O(n) solution [OK]

Common Mistakes:

• Thinking sliding window works for modulo sums
• Assuming DP is needed for this problem
• Believing brute force is acceptable for large inputs

3. Consider the following Python code implementing the optimal bucket sort approach for top K frequent elements. What is the value of res just before the function returns when called with nums = [1,2,2,3] and k = 2?

easy

A. [1, 2]

B. [2, 1]

C. [2, 3]

D. [3, 2]

Solution

1. Step 1: Calculate frequency map for nums=[1,2,2,3]

   freq = {1:1, 2:2, 3:1}, max_freq = 2

2. Step 2: Fill buckets and collect top k=2 elements

   buckets = [[], [1,3], [2]]; iterate from freq=2 down: add 2, then freq=1 add 1; res = [2,1]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Order depends on bucket insertion; here 2 appears before 1 [OK]

Hint: Trace buckets from highest frequency down [OK]

Common Mistakes:

• Confusing order of elements in buckets
• Assuming sorted order inside buckets
• Off-by-one in frequency indexing

4. What is the time complexity of the optimal prefix sum + hash map solution for finding the longest contiguous subarray with equal number of 0s and 1s, given an input array of length n?

medium

A. O(n^2) because of nested loops to check subarrays

B. O(n log n) due to sorting prefix sums

C. O(n) because each element is processed once with constant-time hash map operations

D. O(n) for prefix sums but O(n^2) for hash map lookups

Solution

1. Step 1: Identify loop structure

   The algorithm iterates over the array once, performing O(1) operations per element.

2. Step 2: Analyze hash map operations

   Hash map lookups and insertions are average O(1), so total is O(n).

3. Step 3: Why O(n) because each element is processed once with constant-time hash map operations is incorrect

   Although each element is processed once, hash map operations can degrade in worst case, but average case is O(1). However, O(n log n) due to sorting prefix sums mentions sorting prefix sums which is not done in this algorithm.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Single pass + O(1) map ops -> O(n) time [OK]

Hint: Hash map lookups are average O(1), no nested loops [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming sorting is needed
• Thinking hash map lookups cost O(n)

5. Suppose the input array can contain multiple values beyond 0 and 1, but you want to find the longest contiguous subarray where the count of two specific values (say, x and y) are equal. Which modification to the prefix sum + hash map approach correctly handles this generalized problem?

hard

A. Transform array by replacing x with +1, y with -1, and ignore other values; then apply prefix sum + hash map

B. Sort the array first to group x and y, then apply prefix sum + hash map

C. Apply the original algorithm directly without changes since it works for any values

D. Use a hash map keyed by the difference of counts of x and y seen so far, updating prefix sums accordingly

Solution

1. Step 1: Understand problem generalization

   We want longest subarray where counts of x and y are equal, ignoring other values.

2. Step 2: Modify prefix sum logic

   Track difference of counts of x and y as prefix sum; use hash map keyed by this difference to find longest subarray.

3. Step 3: Why other options fail

   Transform array by replacing x with +1, y with -1, and ignore other values; then apply prefix sum + hash map ignores other values which may break continuity; Apply the original algorithm directly without changes since it works for only 0/1; Sort the array first to group x and y, then apply prefix sum + hash map sorting breaks subarray order.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tracking count difference with hash map generalizes prefix sum approach [OK]

Hint: Track difference of counts for x and y with hash map [OK]

Common Mistakes:

• Ignoring other values breaks subarray continuity
• Applying original code without changes
• Sorting breaks contiguous subarray property