Time Based Key-Value Store

🎯

Time Based Key-Value Store

mediumHASH_MAPGoogleFacebookAmazon

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.

💡 This problem is about designing a data structure that stores multiple values for the same key but with different timestamps. Beginners often struggle because they try to store only one value per key or don't efficiently retrieve the closest timestamped value.

📋

Problem Statement

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

💡

Example

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

Output"bar" "bar" "bar2" "bar2"

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.

• 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
• set and get with large timestamps (up to 10^9) → should handle efficiently

⚠️

Common Mistakes

Not handling keys that were never set

get returns error or wrong value

✅ Check if key exists before accessing stored data

Using linear search instead of binary search for get

Slow performance, TLE on large inputs

✅ Use binary search on sorted timestamps

Incorrect binary search index adjustment

Returns wrong value or empty string incorrectly

✅ Carefully adjust index when binary search returns negative insertion point

Assuming timestamps are not strictly increasing

Binary search may fail or return incorrect results

✅ Use problem constraint that timestamps are strictly increasing or sort before search

Not breaking early in linear search brute force

Unnecessary iterations causing slowdowns

✅ Break loop once timestamp exceeds query timestamp

🧠

Brute Force (Linear Search on All Stored Values)

💡 This approach exists to understand the problem's baseline: storing all values and searching linearly. It helps grasp the problem's requirements before optimizing.

Intuition

Store all values for each key in a list with their timestamps. For get, scan all stored timestamps for the key and find the largest timestamp less than or equal to the query timestamp.

Algorithm

1. Maintain a dictionary mapping keys to a list of (timestamp, value) pairs.
2. For set operation, append the (timestamp, value) to the list for the key.
3. For get operation, iterate through the list for the key to find the largest timestamp <= query timestamp.
4. Return the corresponding value or empty string if none found.

💡 The main challenge is realizing that linear search is simple but inefficient for large inputs.

</>

Code

class TimeMap:
    def __init__(self):
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        values = self.store[key]
        res = ""
        for t, v in values:
            if t <= timestamp:
                res = v
            else:
                break
        return res

# Driver code
if __name__ == "__main__":
    tm = TimeMap()
    tm.set("foo", "bar", 1)
    print(tm.get("foo", 1))  # bar
    print(tm.get("foo", 3))  # bar
    tm.set("foo", "bar2", 4)
    print(tm.get("foo", 4))  # bar2
    print(tm.get("foo", 5))  # bar2

Line Notes

self.store = {}Initialize dictionary to store key to list of (timestamp, value)

if key not in self.store:Check if key is new to initialize list

self.store[key].append((timestamp, value))Append new timestamp-value pair preserving order

for t, v in values:Iterate over all stored pairs to find valid timestamp

if t <= timestamp:Update result if timestamp is valid and <= query

else:Break early since timestamps are in order and no further valid timestamps exist

import java.util.*;

class TimeMap {
    private Map<String, List<Pair>> store;

    public TimeMap() {
        store = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        store.putIfAbsent(key, new ArrayList<>());
        store.get(key).add(new Pair(timestamp, value));
    }

    public String get(String key, int timestamp) {
        if (!store.containsKey(key)) return "";
        List<Pair> values = store.get(key);
        String res = "";
        for (Pair p : values) {
            if (p.timestamp <= timestamp) {
                res = p.value;
            } else {
                break;
            }
        }
        return res;
    }

    private static class Pair {
        int timestamp;
        String value;
        Pair(int t, String v) {
            timestamp = t;
            value = v;
        }
    }

    // Driver code
    public static void main(String[] args) {
        TimeMap tm = new TimeMap();
        tm.set("foo", "bar", 1);
        System.out.println(tm.get("foo", 1)); // bar
        System.out.println(tm.get("foo", 3)); // bar
        tm.set("foo", "bar2", 4);
        System.out.println(tm.get("foo", 4)); // bar2
        System.out.println(tm.get("foo", 5)); // bar2
    }
}

Line Notes

store = new HashMap<>();Initialize map from key to list of pairs

store.putIfAbsent(key, new ArrayList<>());Create list if key not present

store.get(key).add(new Pair(timestamp, value));Add new timestamp-value pair to list

for (Pair p : values)Iterate over all pairs to find valid timestamp

if (p.timestamp <= timestamp)Update result if timestamp is valid and <= query

else { break; }Break early since timestamps are sorted

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> store;
public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        if (store.find(key) == store.end()) return "";
        string res = "";
        for (auto &p : store[key]) {
            if (p.first <= timestamp) {
                res = p.second;
            } else {
                break;
            }
        }
        return res;
    }
};

int main() {
    TimeMap tm;
    tm.set("foo", "bar", 1);
    cout << tm.get("foo", 1) << "\n"; // bar
    cout << tm.get("foo", 3) << "\n"; // bar
    tm.set("foo", "bar2", 4);
    cout << tm.get("foo", 4) << "\n"; // bar2
    cout << tm.get("foo", 5) << "\n"; // bar2
    return 0;
}

Line Notes

unordered_map<string, vector<pair<int, string>>> store;Map keys to vector of (timestamp, value) pairs

store[key].push_back({timestamp, value});Append new pair preserving order

for (auto &p : store[key])Iterate all pairs to find valid timestamp

if (p.first <= timestamp)Update result if timestamp is valid and <= query

else { break; }Break early since timestamps are sorted

class TimeMap {
    constructor() {
        this.store = new Map();
    }

    set(key, value, timestamp) {
        if (!this.store.has(key)) {
            this.store.set(key, []);
        }
        this.store.get(key).push([timestamp, value]);
    }

    get(key, timestamp) {
        if (!this.store.has(key)) return "";
        const values = this.store.get(key);
        let res = "";
        for (const [t, v] of values) {
            if (t <= timestamp) {
                res = v;
            } else {
                break;
            }
        }
        return res;
    }
}

// Driver code
const tm = new TimeMap();
tm.set("foo", "bar", 1);
console.log(tm.get("foo", 1)); // bar
console.log(tm.get("foo", 3)); // bar
tm.set("foo", "bar2", 4);
console.log(tm.get("foo", 4)); // bar2
console.log(tm.get("foo", 5)); // bar2

Line Notes

this.store = new Map();Initialize map from key to array of pairs

if (!this.store.has(key))Check if key exists to initialize array

this.store.get(key).push([timestamp, value]);Append new timestamp-value pair

for (const [t, v] of values)Iterate all pairs to find valid timestamp

if (t <= timestamp)Update result if timestamp is valid and <= query

else { break; }Break early since timestamps are sorted

⏱

Complexity

TimeO(n) per get in worst case

SpaceO(n) for storing all values

Each get operation scans all stored timestamps for the key, which can be up to n in worst case. Set is O(1).

💡 For n=100000, each get could scan 100000 entries, which is too slow for large inputs.

Interview Verdict: TLE / Use only to introduce problem

This approach is too slow for large inputs but helps understand the problem and correctness before optimizing.

🧠

Better Approach (Binary Search on Sorted Timestamp List)

💡 This approach improves get operation by using binary search on the sorted list of timestamps, making retrieval efficient.

Intuition

Since timestamps are strictly increasing for each key, store them in a sorted list. Use binary search to find the largest timestamp <= query timestamp.

Algorithm

1. Maintain a dictionary mapping keys to a list of (timestamp, value) pairs sorted by timestamp.
2. For set operation, append the (timestamp, value) pair (timestamps are strictly increasing).
3. For get operation, perform binary search on the timestamp list to find the rightmost timestamp <= query timestamp.
4. Return the corresponding value or empty string if none found.

💡 The key insight is leveraging the sorted order of timestamps to quickly find the correct value.

</>

Code

import bisect

class TimeMap:
    def __init__(self):
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = {'times': [], 'values': []}
        self.store[key]['times'].append(timestamp)
        self.store[key]['values'].append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        times = self.store[key]['times']
        values = self.store[key]['values']
        i = bisect.bisect_right(times, timestamp)
        if i == 0:
            return ""
        return values[i-1]

# Driver code
if __name__ == "__main__":
    tm = TimeMap()
    tm.set("foo", "bar", 1)
    print(tm.get("foo", 1))  # bar
    print(tm.get("foo", 3))  # bar
    tm.set("foo", "bar2", 4)
    print(tm.get("foo", 4))  # bar2
    print(tm.get("foo", 5))  # bar2

Line Notes

import bisectImport bisect module for binary search

self.store[key] = {'times': [], 'values': []}Store timestamps and values separately for efficient binary search

self.store[key]['times'].append(timestamp)Append timestamp preserving sorted order

i = bisect.bisect_right(times, timestamp)Find insertion point to the right of timestamp

if i == 0:No timestamp <= query timestamp found

return values[i-1]Return value corresponding to largest timestamp <= query

import java.util.*;

class TimeMap {
    private Map<String, List<Integer>> timesMap;
    private Map<String, List<String>> valuesMap;

    public TimeMap() {
        timesMap = new HashMap<>();
        valuesMap = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        timesMap.putIfAbsent(key, new ArrayList<>());
        valuesMap.putIfAbsent(key, new ArrayList<>());
        timesMap.get(key).add(timestamp);
        valuesMap.get(key).add(value);
    }

    public String get(String key, int timestamp) {
        if (!timesMap.containsKey(key)) return "";
        List<Integer> times = timesMap.get(key);
        List<String> values = valuesMap.get(key);
        int i = Collections.binarySearch(times, timestamp);
        if (i < 0) {
            i = -i - 2;
        }
        if (i < 0) return "";
        return values.get(i);
    }

    // Driver code
    public static void main(String[] args) {
        TimeMap tm = new TimeMap();
        tm.set("foo", "bar", 1);
        System.out.println(tm.get("foo", 1)); // bar
        System.out.println(tm.get("foo", 3)); // bar
        tm.set("foo", "bar2", 4);
        System.out.println(tm.get("foo", 4)); // bar2
        System.out.println(tm.get("foo", 5)); // bar2
    }
}

Line Notes

timesMap = new HashMap<>();Map key to list of timestamps

valuesMap = new HashMap<>();Map key to list of values

timesMap.get(key).add(timestamp);Append timestamp preserving order

int i = Collections.binarySearch(times, timestamp);Binary search for timestamp

if (i < 0) { i = -i - 2; }Adjust index to find largest timestamp <= query

if (i < 0) return "";No valid timestamp found

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class TimeMap {
    unordered_map<string, vector<int>> timesMap;
    unordered_map<string, vector<string>> valuesMap;
public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        timesMap[key].push_back(timestamp);
        valuesMap[key].push_back(value);
    }

    string get(string key, int timestamp) {
        if (timesMap.find(key) == timesMap.end()) return "";
        const vector<int> &times = timesMap[key];
        const vector<string> &values = valuesMap[key];
        int i = (int)(upper_bound(times.begin(), times.end(), timestamp) - times.begin()) - 1;
        if (i < 0) return "";
        return values[i];
    }
};

int main() {
    TimeMap tm;
    tm.set("foo", "bar", 1);
    cout << tm.get("foo", 1) << "\n"; // bar
    cout << tm.get("foo", 3) << "\n"; // bar
    tm.set("foo", "bar2", 4);
    cout << tm.get("foo", 4) << "\n"; // bar2
    cout << tm.get("foo", 5) << "\n"; // bar2
    return 0;
}

Line Notes

unordered_map<string, vector<int>> timesMap;Map key to vector of timestamps

unordered_map<string, vector<string>> valuesMap;Map key to vector of values

timesMap[key].push_back(timestamp);Append timestamp preserving order

int i = (int)(upper_bound(times.begin(), times.end(), timestamp) - times.begin()) - 1;Find rightmost timestamp <= query using upper_bound

if (i < 0) return "";No valid timestamp found

return values[i];Return value corresponding to found timestamp

class TimeMap {
    constructor() {
        this.store = new Map();
    }

    set(key, value, timestamp) {
        if (!this.store.has(key)) {
            this.store.set(key, {times: [], values: []});
        }
        this.store.get(key).times.push(timestamp);
        this.store.get(key).values.push(value);
    }

    get(key, timestamp) {
        if (!this.store.has(key)) return "";
        const {times, values} = this.store.get(key);
        let left = 0, right = times.length - 1;
        let res = "";
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (times[mid] <= timestamp) {
                res = values[mid];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}

// Driver code
const tm = new TimeMap();
tm.set("foo", "bar", 1);
console.log(tm.get("foo", 1)); // bar
console.log(tm.get("foo", 3)); // bar
tm.set("foo", "bar2", 4);
console.log(tm.get("foo", 4)); // bar2
console.log(tm.get("foo", 5)); // bar2

Line Notes

this.store = new Map();Initialize map from key to object with times and values arrays

this.store.get(key).times.push(timestamp);Append timestamp preserving order

let left = 0, right = times.length - 1;Initialize binary search boundaries

if (times[mid] <= timestamp)Check if mid timestamp is valid

res = values[mid];Update result with current valid value

left = mid + 1;Search right half for closer timestamp

⏱

Complexity

TimeO(log n) per get, O(1) per set

SpaceO(n) for storing all values

Binary search reduces get from linear to logarithmic time. Set remains constant time.

💡 For n=100000, get operations now take about 17 steps instead of 100000, making it efficient.

Interview Verdict: Accepted / Efficient for large inputs

This approach is optimal for the problem constraints and is the recommended solution in interviews.

🧠

Optimal Approach (Using Built-in Binary Search Utilities / Language Features)

💡 This approach leverages language-specific built-in binary search utilities to write clean and efficient code, reducing implementation errors.

Intuition

Use built-in binary search functions (like bisect in Python, Collections.binarySearch in Java, upper_bound in C++, or manual binary search in JS) to find the correct timestamp quickly.

Algorithm

1. Store timestamps and values separately for each key.
2. For set, append timestamp and value.
3. For get, use built-in binary search to find insertion point for query timestamp.
4. Return value at index before insertion point or empty string if none.

💡 This approach is a refinement of the previous one, focusing on clean code and reliability.

</>

Code

import bisect

class TimeMap:
    def __init__(self):
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = {'times': [], 'values': []}
        self.store[key]['times'].append(timestamp)
        self.store[key]['values'].append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        times = self.store[key]['times']
        values = self.store[key]['values']
        i = bisect.bisect_right(times, timestamp)
        if i == 0:
            return ""
        return values[i-1]

# Driver code
if __name__ == "__main__":
    tm = TimeMap()
    tm.set("foo", "bar", 1)
    print(tm.get("foo", 1))  # bar
    print(tm.get("foo", 3))  # bar
    tm.set("foo", "bar2", 4)
    print(tm.get("foo", 4))  # bar2
    print(tm.get("foo", 5))  # bar2

Line Notes

import bisectUse Python's built-in binary search for reliability and speed

self.store[key] = {'times': [], 'values': []}Separate lists for timestamps and values for efficient access

i = bisect.bisect_right(times, timestamp)Find insertion point to the right of timestamp

if i == 0:No timestamp <= query timestamp found

return values[i-1]Return value corresponding to largest timestamp <= query

import java.util.*;

class TimeMap {
    private Map<String, List<Integer>> timesMap;
    private Map<String, List<String>> valuesMap;

    public TimeMap() {
        timesMap = new HashMap<>();
        valuesMap = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        timesMap.putIfAbsent(key, new ArrayList<>());
        valuesMap.putIfAbsent(key, new ArrayList<>());
        timesMap.get(key).add(timestamp);
        valuesMap.get(key).add(value);
    }

    public String get(String key, int timestamp) {
        if (!timesMap.containsKey(key)) return "";
        List<Integer> times = timesMap.get(key);
        List<String> values = valuesMap.get(key);
        int i = Collections.binarySearch(times, timestamp);
        if (i < 0) {
            i = -i - 2;
        }
        if (i < 0) return "";
        return values.get(i);
    }

    // Driver code
    public static void main(String[] args) {
        TimeMap tm = new TimeMap();
        tm.set("foo", "bar", 1);
        System.out.println(tm.get("foo", 1)); // bar
        System.out.println(tm.get("foo", 3)); // bar
        tm.set("foo", "bar2", 4);
        System.out.println(tm.get("foo", 4)); // bar2
        System.out.println(tm.get("foo", 5)); // bar2
    }
}

Line Notes

int i = Collections.binarySearch(times, timestamp);Use built-in binary search for correctness and speed

if (i < 0) { i = -i - 2; }Adjust index to find largest timestamp <= query

if (i < 0) return "";No valid timestamp found

return values.get(i);Return value corresponding to found timestamp

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class TimeMap {
    unordered_map<string, vector<int>> timesMap;
    unordered_map<string, vector<string>> valuesMap;
public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        timesMap[key].push_back(timestamp);
        valuesMap[key].push_back(value);
    }

    string get(string key, int timestamp) {
        if (timesMap.find(key) == timesMap.end()) return "";
        const vector<int> &times = timesMap[key];
        const vector<string> &values = valuesMap[key];
        int i = (int)(upper_bound(times.begin(), times.end(), timestamp) - times.begin()) - 1;
        if (i < 0) return "";
        return values[i];
    }
};

int main() {
    TimeMap tm;
    tm.set("foo", "bar", 1);
    cout << tm.get("foo", 1) << "\n"; // bar
    cout << tm.get("foo", 3) << "\n"; // bar
    tm.set("foo", "bar2", 4);
    cout << tm.get("foo", 4) << "\n"; // bar2
    cout << tm.get("foo", 5) << "\n"; // bar2
    return 0;
}

Line Notes

int i = (int)(upper_bound(times.begin(), times.end(), timestamp) - times.begin()) - 1;Use C++ STL upper_bound to find insertion point efficiently

if (i < 0) return "";No valid timestamp found

return values[i];Return value corresponding to largest timestamp <= query

class TimeMap {
    constructor() {
        this.store = new Map();
    }

    set(key, value, timestamp) {
        if (!this.store.has(key)) {
            this.store.set(key, {times: [], values: []});
        }
        this.store.get(key).times.push(timestamp);
        this.store.get(key).values.push(value);
    }

    get(key, timestamp) {
        if (!this.store.has(key)) return "";
        const {times, values} = this.store.get(key);
        let left = 0, right = times.length - 1;
        let res = "";
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (times[mid] <= timestamp) {
                res = values[mid];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}

// Driver code
const tm = new TimeMap();
tm.set("foo", "bar", 1);
console.log(tm.get("foo", 1)); // bar
console.log(tm.get("foo", 3)); // bar
tm.set("foo", "bar2", 4);
console.log(tm.get("foo", 4)); // bar2
console.log(tm.get("foo", 5)); // bar2

Line Notes

let left = 0, right = times.length - 1;Initialize binary search boundaries

const mid = Math.floor((left + right) / 2);Calculate middle index

if (times[mid] <= timestamp)Check if mid timestamp is valid

res = values[mid];Update result with current valid value

left = mid + 1;Search right half for closer timestamp

right = mid - 1;Search left half if mid timestamp too large

⏱

Complexity

TimeO(log n) per get, O(1) per set

SpaceO(n) for storing all values

Using built-in binary search utilities ensures efficient and reliable get operations.

💡 This approach is the cleanest and most maintainable for interviews.

Interview Verdict: Accepted / Recommended for interviews

Using built-in utilities reduces bugs and improves code clarity, which is valued in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the binary search approach with built-in utilities in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) per get	O(n)	No	N/A	Mention only - never code
2. Binary Search on Sorted List	O(log n) per get	O(n)	No	N/A	Code if no built-in utilities
3. Optimal with Built-in Binary Search	O(log n) per get	O(n)	No	N/A	Preferred approach to code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem requirements and constraints.Describe the brute force approach and its limitations.Explain how timestamps being sorted enables binary search.Implement the binary search approach using built-in utilities.Test your code with edge cases and discuss complexity.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to design an efficient data structure, use binary search correctly, and write clean code.

Common Follow-ups

• What if timestamps are not strictly increasing? → Use balanced tree or sort before binary search.
• How to handle memory if many keys and values? → Use compression or external storage.

💡 These follow-ups test your ability to adapt the design to more complex or realistic scenarios.

🔍

Pattern Recognition

When to Use

1) Need to store multiple values per key with timestamps, 2) Queries ask for value at or before a timestamp, 3) Timestamps are sorted or can be sorted, 4) Efficient retrieval required

Signature Phrases

"get the value at the largest timestamp <= given timestamp""timestamps are strictly increasing"

NOT This Pattern When

Problems that require range sums or intervals but not exact timestamp retrieval

Similar Problems

Snapshot Array - similar versioning and retrieval by indexDesign Twitter - time-based retrieval of tweetsInsert Delete GetRandom O(1) - hash map design with extra constraints

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 two strings s and t. You need to determine if there exists a one-to-one character mapping from s to t such that replacing characters in s with their mapped characters produces t. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming to track substring isomorphisms

B. Greedy approach that maps characters as they appear without checking reverse mapping

C. Bidirectional hash map mapping that ensures one-to-one character correspondence

D. Brute force nested loops checking all character pairs for consistency

Solution

1. Step 1: Understand the problem constraints

   The problem requires a one-to-one mapping between characters of two strings, ensuring no two characters in s map to the same character in t and vice versa.

2. Step 2: Identify the approach that enforces bidirectional mapping

   Only the bidirectional hash map approach maintains two maps: one from s to t and another from t to s, ensuring the mapping is consistent and one-to-one.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bidirectional mapping prevents false positives like mapping "ab" to "aa" [OK]

Hint: One-to-one mapping requires bidirectional checks [OK]

Common Mistakes:

• Assuming single-direction mapping suffices
• Using DP which is unnecessary
• Relying on greedy without reverse check

3. You are given an unsorted array of integers and need to find the length of the longest sequence of consecutive integers that appear in the array. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use a hash set to store all numbers, then for each number that is the start of a sequence, count consecutive numbers forward.

B. Use dynamic programming to build the longest consecutive subsequence ending at each element.

C. Sort the array and then scan linearly to find the longest consecutive sequence.

D. Use a nested loop to check for consecutive sequences starting from each element.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the longest consecutive sequence in an unsorted array efficiently.

2. Step 2: Evaluate approaches

   Sorting then scanning is O(n log n), nested loops are O(n²), and DP is not straightforward here. Using a hash set to detect sequence starts and count forward achieves O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set membership checks are O(1), enabling linear time [OK]

Hint: Hash set start detection enables O(n) solution [OK]

Common Mistakes:

• Assuming sorting is optimal enough
• Trying DP which doesn't fit this problem
• Using nested loops leading to O(n²)

4. The following code attempts to implement the remove operation for the Insert Delete GetRandom data structure. Identify the line that contains a subtle bug causing incorrect behavior.

def remove(self, val: int) -> bool:
    if val not in self.pos:
        return False
    idx = self.pos[val]
    last_element = self.nums[-1]
    self.nums[idx] = last_element
    # BUG: Missing update of last_element's position in pos
    self.nums.pop()
    del self.pos[val]
    return True

medium

A. Missing line: updating self.pos[last_element] = idx after swap

B. Line: last_element = self.nums[-1]

C. Line: self.nums[idx] = last_element

D. Line: idx = self.pos[val]

Solution

1. Step 1: Understand swap-delete logic

   After swapping last element into idx, the hash map must update last_element's index.

2. Step 2: Identify missing update

   The code does not update self.pos[last_element] = idx, so pos points to old index, causing inconsistency.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without updating pos, getRandom or remove may fail [OK]

Hint: Always update hash map after swapping elements [OK]

Common Mistakes:

• Forgetting to update hash map after swap
• Assuming pop removes mapping automatically
• Updating wrong indices in hash map

5. Suppose the problem changes: now elements from the arrays can be reused multiple times in the intersection (i.e., unlimited reuse). Which modification to the algorithm correctly handles this new requirement?

hard

A. Use a hash map to count frequencies in one array and for each element in the other array, add it to intersection if count > 0 without decrementing counts.

B. Use the same two-pointer approach but do not increment pointers when elements match, allowing reuse.

C. Use a hash map to count frequencies in one array and for each element in the other array, add it to intersection and decrement count accordingly.

D. Sort both arrays and use two pointers, but reset pointers to zero after each match to allow reuse.

Solution

1. Step 1: Understand reuse requirement

   Elements can be reused unlimited times, so counts should not be decremented after matching.

2. Step 2: Evaluate modifications

   Two-pointer approach relies on moving pointers forward, so it cannot handle reuse without complex resets. Hash map counting without decrementing counts allows unlimited reuse correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash map frequency counting without decrement handles reuse correctly [OK]

Hint: Do not decrement counts to allow reuse [OK]

Common Mistakes:

• Not changing pointer logic for reuse
• Decrementing counts incorrectly
• Resetting pointers causing infinite loops