Snapshot Array

🎯

Snapshot Array

mediumDESIGNAmazonGoogleFacebook

Imagine you are building a version control system for an array where you can take snapshots and query historical values efficiently.

💡 This problem is about designing a data structure that supports efficient snapshots and queries on past states. Beginners often struggle because it requires combining data structure design with binary search to handle historical versions efficiently.

📋

Problem Statement

Design a SnapshotArray that supports the following interface: - SnapshotArray(int length): Initializes an array-like data structure with the given length. Initially, each element equals 0. - void set(index, val): Sets the element at the given index to be equal to val. - int snap(): Takes a snapshot of the array and returns the snap_id: the total number of times snap() has been called minus 1. - int get(index, snap_id): Returns the value at the given index, at the time the snapshot with snap_id was taken.

1 ≤ length ≤ 10^5At most 5 * 10^4 calls will be made to set, snap, and get.0 ≤ index < length0 ≤ snap_id < number of times snap() has been called0 ≤ val ≤ 10^9

💡

Example

Input"SnapshotArray snapshotArr = new SnapshotArray(3);\nsnapshotArr.set(0,5);\nint snap_id = snapshotArr.snap();\nsnapshotArr.set(0,6);\nint val = snapshotArr.get(0, snap_id);"

Outputsnap_id = 0 val = 5

We initialize an array of length 3 with all zeros. We set index 0 to 5. We take a snapshot (snap_id=0). Then we set index 0 to 6. When we get the value at index 0 for snap_id 0, it returns 5, the value at the time of the snapshot.

• Calling get on an index that was never set after initialization → returns 0
• Multiple sets on the same index before a snap → only the last set before snap is recorded
• Calling snap multiple times without any set in between → snapshots should be distinct
• Large number of snaps and sets on different indices → performance should remain efficient

⚠️

Common Mistakes

Storing full array snapshots on every snap()

Memory usage explodes and solution times out on large inputs

✅ Store only changes per index and use binary search for queries

Using linear search to find snapshot values in get()

get() becomes too slow for many snapshots, causing timeouts

✅ Use binary search on the sorted list of snapshots per index

Not handling multiple sets on the same index before snap() correctly

Duplicate entries for same snap_id cause incorrect get() results

✅ Overwrite the last entry if it has the current snap_id instead of appending

Not initializing each index with a default snapshot (-1, 0)

get() may fail or return incorrect values for indices never set

✅ Initialize each index with a default snapshot to represent initial zero values

Off-by-one errors in snap_id increments and returns

Returned snap_id or queried snap_id mismatches cause wrong results

✅ Return snap_id before incrementing it in snap(), and use consistent snap_id in set/get

🧠

Brute Force (Store Full Snapshots)

💡 This approach exists to build intuition by directly storing the entire array at each snapshot. It is simple but inefficient, helping beginners understand the problem's requirements before optimizing.

Intuition

Store a full copy of the array every time snap() is called. Then get() simply returns the value from the stored snapshot array.

Algorithm

1. Initialize the array with zeros.
2. On set(index, val), update the current array state.
3. On snap(), copy the entire current array and store it in a list of snapshots, then return the snap_id.
4. On get(index, snap_id), return the value at index from the snapshot array at snap_id.

💡 The main difficulty is realizing that storing full snapshots is straightforward but leads to huge memory and time costs.

</>

Code

class SnapshotArray:
    def __init__(self, length: int):
        self.arr = [0] * length
        self.snaps = []

    def set(self, index: int, val: int) -> None:
        self.arr[index] = val

    def snap(self) -> int:
        self.snaps.append(self.arr[:])
        return len(self.snaps) - 1

    def get(self, index: int, snap_id: int) -> int:
        return self.snaps[snap_id][index]

# Driver code
if __name__ == '__main__':
    snapshotArr = SnapshotArray(3)
    snapshotArr.set(0,5)
    snap_id = snapshotArr.snap()
    snapshotArr.set(0,6)
    print(snap_id)  # Output: 0
    print(snapshotArr.get(0, snap_id))  # Output: 5

Line Notes

self.arr = [0] * lengthInitialize the array with zeros for all indices

self.snaps = []Store all snapshots as full copies of the array

self.arr[index] = valUpdate the current array state at the given index

self.snaps.append(self.arr[:])Take a full snapshot by copying the current array

return len(self.snaps) - 1Return the snap_id which is the index of the last snapshot

return self.snaps[snap_id][index]Retrieve the value at index from the snapshot with snap_id

import java.util.*;

class SnapshotArray {
    private List<int[]> snaps;
    private int[] arr;

    public SnapshotArray(int length) {
        arr = new int[length];
        snaps = new ArrayList<>();
    }

    public void set(int index, int val) {
        arr[index] = val;
    }

    public int snap() {
        snaps.add(arr.clone());
        return snaps.size() - 1;
    }

    public int get(int index, int snap_id) {
        return snaps.get(snap_id)[index];
    }

    // Main method for testing
    public static void main(String[] args) {
        SnapshotArray snapshotArr = new SnapshotArray(3);
        snapshotArr.set(0, 5);
        int snap_id = snapshotArr.snap();
        snapshotArr.set(0, 6);
        System.out.println(snap_id); // Output: 0
        System.out.println(snapshotArr.get(0, snap_id)); // Output: 5
    }
}

Line Notes

arr = new int[length];Initialize array with zeros

snaps = new ArrayList<>();List to store snapshots as full array copies

arr[index] = val;Update current array state

snaps.add(arr.clone());Store a full copy of current array as snapshot

return snaps.size() - 1;Return the snap_id for the snapshot

return snaps.get(snap_id)[index];Retrieve value from snapshot at given index

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

class SnapshotArray {
    vector<vector<int>> snaps;
    vector<int> arr;
public:
    SnapshotArray(int length) {
        arr = vector<int>(length, 0);
    }

    void set(int index, int val) {
        arr[index] = val;
    }

    int snap() {
        snaps.push_back(arr);
        return (int)snaps.size() - 1;
    }

    int get(int index, int snap_id) {
        return snaps[snap_id][index];
    }
};

int main() {
    SnapshotArray snapshotArr(3);
    snapshotArr.set(0, 5);
    int snap_id = snapshotArr.snap();
    snapshotArr.set(0, 6);
    cout << snap_id << endl; // Output: 0
    cout << snapshotArr.get(0, snap_id) << endl; // Output: 5
    return 0;
}

Line Notes

arr = vector<int>(length, 0);Initialize array with zeros

snaps.push_back(arr);Store full copy of current array as snapshot

return (int)snaps.size() - 1;Return snap_id for the snapshot

arr[index] = val;Update current array state

return snaps[snap_id][index];Retrieve value from snapshot at given index

class SnapshotArray {
    constructor(length) {
        this.arr = new Array(length).fill(0);
        this.snaps = [];
    }

    set(index, val) {
        this.arr[index] = val;
    }

    snap() {
        this.snaps.push(this.arr.slice());
        return this.snaps.length - 1;
    }

    get(index, snap_id) {
        return this.snaps[snap_id][index];
    }
}

// Test code
const snapshotArr = new SnapshotArray(3);
snapshotArr.set(0, 5);
const snap_id = snapshotArr.snap();
snapshotArr.set(0, 6);
console.log(snap_id); // Output: 0
console.log(snapshotArr.get(0, snap_id)); // Output: 5

Line Notes

this.arr = new Array(length).fill(0);Initialize array with zeros

this.snaps = [];Store snapshots as full array copies

this.arr[index] = val;Update current array state

this.snaps.push(this.arr.slice());Take a full snapshot by copying current array

return this.snaps.length - 1;Return snap_id for the snapshot

return this.snaps[snap_id][index];Retrieve value from snapshot at given index

⏱

Complexity

TimeO(n * m) where n is length and m is number of snaps

SpaceO(n * m) due to storing full array copies for each snapshot

Each snap copies the entire array of length n, so with m snaps, total time and space grow linearly with both.

💡 For n=1000 and m=1000, this means 1,000,000 operations and large memory usage, which is impractical.

Interview Verdict: TLE / Memory Limit Exceeded for large inputs

This approach is too slow and memory-heavy for large inputs, but it helps understand the problem before optimizing.

🧠

Hash Map per Index with Linear Search

💡 This approach improves over brute force by storing only changes per index, but uses linear search to find the value at a snapshot, which is still inefficient for many snaps.

Intuition

For each index, keep a list of (snap_id, val) pairs representing changes. On get, search backwards linearly to find the latest snap_id ≤ requested snap_id.

Algorithm

1. Initialize a list of dictionaries or lists for each index to store (snap_id, val) pairs.
2. On set(index, val), record the value with the current snap_id (or pending snap_id).
3. On snap(), increment snap_id counter.
4. On get(index, snap_id), search backwards in the list for the largest snap_id ≤ requested snap_id and return its value.

💡 The challenge is managing the data structure per index and performing the backward search correctly.

</>

Code

class SnapshotArray:
    def __init__(self, length: int):
        self.length = length
        self.snap_id = 0
        self.data = [{} for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        self.data[index][self.snap_id] = val

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        while snap_id >= 0:
            if snap_id in self.data[index]:
                return self.data[index][snap_id]
            snap_id -= 1
        return 0

# Driver code
if __name__ == '__main__':
    snapshotArr = SnapshotArray(3)
    snapshotArr.set(0,5)
    snap_id = snapshotArr.snap()
    snapshotArr.set(0,6)
    print(snap_id)  # Output: 0
    print(snapshotArr.get(0, snap_id))  # Output: 5

Line Notes

self.data = [{} for _ in range(length)]Initialize a dictionary per index to store snap_id to val mappings

self.data[index][self.snap_id] = valRecord the value for the current snap_id at the index

self.snap_id += 1Increment snap_id on snap() call

while snap_id >= 0:Search backwards from requested snap_id to find latest value

if snap_id in self.data[index]:Check if value was set at this snap_id

return 0Return default 0 if no value found for any earlier snap_id

import java.util.*;

class SnapshotArray {
    private int snap_id;
    private Map<Integer, Integer>[] data;

    public SnapshotArray(int length) {
        snap_id = 0;
        data = new HashMap[length];
        for (int i = 0; i < length; i++) {
            data[i] = new HashMap<>();
        }
    }

    public void set(int index, int val) {
        data[index].put(snap_id, val);
    }

    public int snap() {
        snap_id++;
        return snap_id - 1;
    }

    public int get(int index, int snap_id) {
        while (snap_id >= 0) {
            if (data[index].containsKey(snap_id)) {
                return data[index].get(snap_id);
            }
            snap_id--;
        }
        return 0;
    }

    public static void main(String[] args) {
        SnapshotArray snapshotArr = new SnapshotArray(3);
        snapshotArr.set(0, 5);
        int snap_id = snapshotArr.snap();
        snapshotArr.set(0, 6);
        System.out.println(snap_id); // Output: 0
        System.out.println(snapshotArr.get(0, snap_id)); // Output: 5
    }
}

Line Notes

data = new HashMap[length];Initialize array of hash maps, one per index

data[index].put(snap_id, val);Store value for current snap_id at index

snap_id++;Increment snap_id on snap()

while (snap_id >= 0)Linear backward search for latest snap_id with value

if (data[index].containsKey(snap_id))Check if value exists for this snap_id

return 0;Return default 0 if no value found

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

class SnapshotArray {
    vector<unordered_map<int,int>> data;
    int snap_id;
public:
    SnapshotArray(int length) {
        data = vector<unordered_map<int,int>>(length);
        snap_id = 0;
    }

    void set(int index, int val) {
        data[index][snap_id] = val;
    }

    int snap() {
        return snap_id++;
    }

    int get(int index, int s_id) {
        while (s_id >= 0) {
            if (data[index].count(s_id))
                return data[index][s_id];
            s_id--;
        }
        return 0;
    }
};

int main() {
    SnapshotArray snapshotArr(3);
    snapshotArr.set(0, 5);
    int snap_id = snapshotArr.snap();
    snapshotArr.set(0, 6);
    cout << snap_id << endl; // Output: 0
    cout << snapshotArr.get(0, snap_id) << endl; // Output: 5
    return 0;
}

Line Notes

data = vector<unordered_map<int,int>>(length);Initialize vector of hash maps for each index

data[index][snap_id] = val;Store value for current snap_id at index

return snap_id++;Return current snap_id and then increment

while (s_id >= 0)Linear backward search for latest snap_id with value

if (data[index].count(s_id))Check if value exists for this snap_id

return 0;Return default 0 if no value found

class SnapshotArray {
    constructor(length) {
        this.snap_id = 0;
        this.data = Array.from({length}, () => new Map());
    }

    set(index, val) {
        this.data[index].set(this.snap_id, val);
    }

    snap() {
        return this.snap_id++;
    }

    get(index, snap_id) {
        while (snap_id >= 0) {
            if (this.data[index].has(snap_id)) {
                return this.data[index].get(snap_id);
            }
            snap_id--;
        }
        return 0;
    }
}

// Test code
const snapshotArr = new SnapshotArray(3);
snapshotArr.set(0, 5);
const snap_id = snapshotArr.snap();
snapshotArr.set(0, 6);
console.log(snap_id); // Output: 0
console.log(snapshotArr.get(0, snap_id)); // Output: 5

Line Notes

this.data = Array.from({length}, () => new Map());Initialize array of maps, one per index

this.data[index].set(this.snap_id, val);Store value for current snap_id at index

return this.snap_id++;Return current snap_id then increment

while (snap_id >= 0)Linear backward search for latest snap_id with value

if (this.data[index].has(snap_id))Check if value exists for this snap_id

return 0;Return default 0 if no value found

⏱

Complexity

TimeO(m * n) worst case for get due to linear search, where m is number of snaps

SpaceO(k) where k is number of set operations

Each set stores one entry. Get requires linear search backward over snap_ids, which can be slow if many snaps exist.

💡 For 50,000 snaps, get could take up to 50,000 steps, which is inefficient.

Interview Verdict: Accepted but inefficient for large number of snaps

Better than brute force but still slow for many snapshots; motivates binary search optimization.

🧠

Hash Map per Index with Binary Search (Optimal)

💡 This approach is the optimal solution combining efficient storage and fast queries by using binary search on snapshots per index.

Intuition

For each index, store a sorted list of (snap_id, val) pairs. On get, use binary search to find the largest snap_id ≤ requested snap_id to retrieve the value efficiently.

Algorithm

1. Initialize a list of lists for each index, starting with (snap_id=-1, val=0) to represent initial state.
2. On set(index, val), if last recorded snap_id is current snap_id, update value; else append (current snap_id, val).
3. On snap(), increment snap_id and return previous snap_id.
4. On get(index, snap_id), binary search in the list for the largest snap_id ≤ requested snap_id and return its value.

💡 The key is maintaining sorted snapshots per index and using binary search to quickly find the correct value.

</>

Code

import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.data = [[(-1, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        if self.data[index][-1][0] == self.snap_id:
            self.data[index][-1] = (self.snap_id, val)
        else:
            self.data[index].append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

# Driver code
if __name__ == '__main__':
    snapshotArr = SnapshotArray(3)
    snapshotArr.set(0,5)
    snap_id = snapshotArr.snap()
    snapshotArr.set(0,6)
    print(snap_id)  # Output: 0
    print(snapshotArr.get(0, snap_id))  # Output: 5

Line Notes

self.data = [[(-1, 0)] for _ in range(length)]Initialize each index with a default snapshot (-1, 0) for initial zero values

if self.data[index][-1][0] == self.snap_id:If last change is in current snap_id, overwrite it to avoid duplicates

self.data[index].append((self.snap_id, val))Otherwise append new (snap_id, val) pair

self.snap_id += 1Increment snap_id on snap()

i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1Binary search to find rightmost snap_id ≤ requested snap_id

return arr[i][1]Return the value corresponding to found snap_id

import java.util.*;

class SnapshotArray {
    private int snap_id;
    private List<List<int[]>> data;

    public SnapshotArray(int length) {
        snap_id = 0;
        data = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            List<int[]> list = new ArrayList<>();
            list.add(new int[]{-1, 0});
            data.add(list);
        }
    }

    public void set(int index, int val) {
        List<int[]> list = data.get(index);
        if (list.get(list.size() - 1)[0] == snap_id) {
            list.get(list.size() - 1)[1] = val;
        } else {
            list.add(new int[]{snap_id, val});
        }
    }

    public int snap() {
        snap_id++;
        return snap_id - 1;
    }

    public int get(int index, int snap_id) {
        List<int[]> list = data.get(index);
        int left = 0, right = list.size() - 1;
        int res = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid)[0] <= snap_id) {
                res = list.get(mid)[1];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        SnapshotArray snapshotArr = new SnapshotArray(3);
        snapshotArr.set(0, 5);
        int snap_id = snapshotArr.snap();
        snapshotArr.set(0, 6);
        System.out.println(snap_id); // Output: 0
        System.out.println(snapshotArr.get(0, snap_id)); // Output: 5
    }
}

Line Notes

list.add(new int[]{-1, 0});Initialize each index with default snapshot (-1, 0)

if (list.get(list.size() - 1)[0] == snap_id)Overwrite last value if same snap_id to avoid duplicates

list.add(new int[]{snap_id, val});Append new (snap_id, val) pair if different snap_id

snap_id++;Increment snap_id on snap()

while (left <= right)Binary search to find largest snap_id ≤ requested snap_id

res = list.get(mid)[1];Update result with value at mid if condition met

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

class SnapshotArray {
    vector<vector<pair<int,int>>> data;
    int snap_id;
public:
    SnapshotArray(int length) {
        data = vector<vector<pair<int,int>>>(length, vector<pair<int,int>>(1, {-1,0}));
        snap_id = 0;
    }

    void set(int index, int val) {
        if (data[index].back().first == snap_id) {
            data[index].back().second = val;
        } else {
            data[index].emplace_back(snap_id, val);
        }
    }

    int snap() {
        return snap_id++;
    }

    int get(int index, int s_id) {
        auto &arr = data[index];
        int left = 0, right = (int)arr.size() - 1;
        int res = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid].first <= s_id) {
                res = arr[mid].second;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
};

int main() {
    SnapshotArray snapshotArr(3);
    snapshotArr.set(0, 5);
    int snap_id = snapshotArr.snap();
    snapshotArr.set(0, 6);
    cout << snap_id << endl; // Output: 0
    cout << snapshotArr.get(0, snap_id) << endl; // Output: 5
    return 0;
}

Line Notes

data = vector<vector<pair<int,int>>>(length, vector<pair<int,int>>(1, {-1,0}));Initialize each index with default snapshot (-1, 0)

if (data[index].back().first == snap_id)Overwrite last value if same snap_id to avoid duplicates

data[index].emplace_back(snap_id, val);Append new (snap_id, val) pair if different snap_id

return snap_id++;Return current snap_id then increment

while (left <= right)Binary search to find largest snap_id ≤ requested snap_id

res = arr[mid].second;Update result with value at mid if condition met

class SnapshotArray {
    constructor(length) {
        this.snap_id = 0;
        this.data = Array.from({length}, () => [[-1, 0]]);
    }

    set(index, val) {
        const arr = this.data[index];
        if (arr[arr.length - 1][0] === this.snap_id) {
            arr[arr.length - 1][1] = val;
        } else {
            arr.push([this.snap_id, val]);
        }
    }

    snap() {
        return this.snap_id++;
    }

    get(index, snap_id) {
        const arr = this.data[index];
        let left = 0, right = arr.length - 1;
        let res = 0;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid][0] <= snap_id) {
                res = arr[mid][1];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}

// Test code
const snapshotArr = new SnapshotArray(3);
snapshotArr.set(0, 5);
const snap_id = snapshotArr.snap();
snapshotArr.set(0, 6);
console.log(snap_id); // Output: 0
console.log(snapshotArr.get(0, snap_id)); // Output: 5

Line Notes

this.data = Array.from({length}, () => [[-1, 0]]);Initialize each index with default snapshot (-1, 0)

if (arr[arr.length - 1][0] === this.snap_id)Overwrite last value if same snap_id to avoid duplicates

arr.push([this.snap_id, val]);Append new (snap_id, val) pair if different snap_id

return this.snap_id++;Return current snap_id then increment

while (left <= right)Binary search to find largest snap_id ≤ requested snap_id

res = arr[mid][1];Update result with value at mid if condition met

⏱

Complexity

TimeO(log m) per get, O(1) amortized per set and snap, where m is number of snaps

SpaceO(k) where k is number of set operations

Each set stores one entry. Snap is O(1). Get uses binary search on snapshots per index, making queries efficient.

💡 For 50,000 snaps, get takes about log2(50,000) ≈ 16 steps, which is very efficient.

Interview Verdict: Accepted and optimal for large inputs

This approach balances memory and speed, making it the best choice in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the optimal binary search approach is best. Brute force is only for explanation, and linear search is a stepping stone.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * m)	O(n * m)	No	Yes	Mention only - never code
2. Hash Map per Index with Linear Search	O(m) per get	O(k) where k is number of sets	No	Yes	Mention as intermediate improvement
3. Hash Map per Index with Binary Search	O(log m) per get	O(k)	No	Yes	Code this approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying requirements, then explain brute force, and progressively optimize. Practice coding and testing each approach.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding.Step 3: Discuss inefficiencies and propose storing only changes per index.Step 4: Explain how binary search optimizes get queries.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 3min → Approach discussion: 5min → Code: 10min → Testing & optimization: 7min. Total ~25min

What the Interviewer Tests

The interviewer tests your ability to design efficient data structures, use binary search, and handle edge cases correctly.

Common Follow-ups

• How would you optimize space if many indices are never set?
• Can you modify the data structure to support range queries?
• What if snap() is called very frequently without sets?
• How to handle concurrent set and snap calls in a multithreaded environment?

💡 These follow-ups test your ability to extend and adapt your design to real-world scenarios and constraints.

🔍

Pattern Recognition

When to Use

1) You need to maintain historical versions of data. 2) Queries ask for past states by snapshot or version id. 3) Updates happen between snapshots. 4) Efficient retrieval of past values is required.

Signature Phrases

take a snapshotget value at snap_idset value at index

NOT This Pattern When

Problems that only require current state updates without historical queries are not snapshot array pattern.

Similar Problems

Time Based Key-Value Store - similar versioned data retrievalRange Module - managing intervals with updates and queries

Practice

1. What is the time complexity of performing n operations (push, pop, increment) on the optimal CustomStack implementation that uses a lazy increment array?

medium

A. O(n * k), where k is the increment size

B. O(n + k), where k is the maximum increment size

C. O(n log n), due to increment propagation

D. O(n), total for all operations combined

Solution

1. Step 1: Analyze push and pop operations

   Each push and pop is O(1) amortized, as they add or remove one element.

2. Step 2: Analyze increment operation

   Increment only updates inc array at one index, O(1) per call. Propagation happens lazily during pop, each element's increment propagated once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All n operations combined run in O(n) total time [OK]

Hint: Lazy increments make all operations O(1) amortized, total O(n) [OK]

Common Mistakes:

• Assuming increment is O(k) per call
• Confusing total time with per-operation time

2. Consider the following buggy LFUCache get method. Which line contains the subtle bug that can cause incorrect eviction behavior?

def get(self, key: int) -> int:
    if key not in self.key_val_freq:
        return -1
    val, freq = self.key_val_freq[key]
    del self.freq_keys[freq][key]
    if not self.freq_keys[freq]:
        del self.freq_keys[freq]
        # BUG: missing update of min_freq here
    self.freq_keys[freq + 1][key] = None
    self.key_val_freq[key] = (val, freq + 1)
    return val

What is the bug?

medium

A. Missing update of min_freq after deleting freq_keys[freq]

B. Line deleting freq_keys[freq] when empty

C. Line deleting key from freq_keys[freq]

D. Line adding key to freq_keys[freq + 1]

Solution

1. Step 1: Identify the role of min_freq

   min_freq tracks the smallest frequency present in the cache, needed for correct eviction.

2. Step 2: Check frequency list deletion

   When freq_keys[freq] becomes empty and is deleted, if freq equals min_freq, min_freq must be incremented to freq + 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing min_freq update causes stale min_freq and wrong eviction [OK]

Hint: min_freq must update when freq list empties [OK]

Common Mistakes:

• Forgetting to update min_freq after freq list deletion
• Confusing key deletion with frequency list deletion
• Assuming min_freq updates automatically

3. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings? Assume merging two skylines of total length m takes O(m) time.

medium

A. O(n²)

B. O(n)

C. O(n log n)

D. O(n * w) where w is the width of the skyline

Solution

1. Step 1: Identify divide and conquer recurrence

   The algorithm splits buildings into halves recursively, then merges skylines in O(m) time where m is proportional to n.

2. Step 2: Solve recurrence and analyze merge cost

   Recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n). The width w does not affect complexity here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Divide and conquer with linear merge per level -> O(n log n) [OK]

Hint: Divide and conquer recurrence T(n)=2T(n/2)+O(n) -> O(n log n) [OK]

Common Mistakes:

• Confusing width w with n
• Assuming quadratic due to nested loops

4. Suppose the AllOne data structure is extended to allow keys to be reused after removal (i.e., keys can be reinserted after their count reaches zero). Which modification is necessary to maintain O(1) operations and correctness?

hard

A. Do nothing special; existing code handles reuse correctly

B. Maintain a separate reuse queue to track keys that can be reinserted

C. Reset key's count to zero and keep it in the data structure to track reuse

D. Ensure keys are fully removed from all buckets and mappings upon count zero, then treat reuse as new insertion

Solution

1. Step 1: Understand reuse implications

   Keys removed at count zero must be fully deleted to avoid stale references.

2. Step 2: Ensure reuse is treated as new insertion

   On reuse, key is inserted fresh with count 1, requiring clean removal previously.

3. Step 3: Confirm O(1) operations

   Full removal and fresh insertion maintain O(1) updates and correctness.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper removal prevents duplicates and stale buckets [OK]

Hint: Full removal before reuse ensures correctness and O(1) ops [OK]

Common Mistakes:

• Keeping keys with zero count in data structure causes bugs

5. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)