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. Given the following code snippet for flattening a multilevel doubly linked list, what is the value of curr.val after the first iteration of the outer while loop when the input list is: 1 - 2 - 3, where node 2 has a child list 4 - 5?

easy

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Initialize curr to head (node with val=1)

   First iteration: curr.val = 1, no child, so move to next node.

2. Step 2: After first iteration, curr moves to node with val=2

   Thus, after the first iteration, curr.val is 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   curr.val is 1 after first iteration of the loop [OK]

Hint: curr starts at head with val=1 and moves after processing [OK]

Common Mistakes:

• Assuming curr.val changes before moving
• Confusing iteration count with node value

2. You need to design a system that stores a fixed number of key-value pairs and supports fast retrieval and insertion. When the capacity is exceeded, the system must evict the least recently accessed item. Which data structure approach best guarantees O(1) time complexity for both retrieval and insertion while maintaining the eviction policy?

easy

A. Use a simple list to store keys in order of usage and a hash map for key-value pairs.

B. Use a queue to store keys and a hash map for values.

C. Use a hash map combined with a doubly linked list to track usage order.

D. Use a balanced binary search tree keyed by access timestamps.

Solution

1. Step 1: Understand the eviction policy

   The system must evict the least recently accessed item, which requires tracking usage order efficiently.

2. Step 2: Identify data structure supporting O(1) operations

   A hash map provides O(1) access to values, and a doubly linked list allows O(1) updates to usage order by moving nodes.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map + doubly linked list is the classic LRU cache design [OK]

Hint: LRU needs O(1) access and update of usage order [OK]

Common Mistakes:

• Using list causes O(n) removal
• Queue can't reorder on access
• BST adds O(log n) overhead

3. Consider the following Python code implementing an LRU Cache with capacity 2. After executing the sequence of operations below, what is the return value of cache.get(1)?

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

easy

A. 1

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys [2 (MRU), 1 (LRU)]. get(1) moves key 1 to MRU, order: [1,2]. put(3,3) evicts LRU key 2, cache: [3,1]. get(2) returns -1 (evicted). put(4,4) evicts LRU key 1, cache: [4,3].

2. Step 2: Evaluate get(1) after put(4,4)

   Key 1 was evicted, so get(1) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 1 evicted after put(4,4), so get(1) -> -1 [OK]

Hint: Remember to update usage order on get and evict LRU on put [OK]

Common Mistakes:

• Forgetting to move accessed node to front
• Evicting wrong node
• Returning wrong value after eviction

4. What is the average time complexity of search, insert, and erase operations in a skiplist with dynamic max level and probability tuning, assuming n elements?

medium

A. O(log n) average due to probabilistic multi-level structure

B. O(1) average due to direct indexing in arrays

C. O(log^2 n) because each level requires a separate traversal

D. O(n) because linked lists require linear traversal

Solution

1. Step 1: Understand skiplist structure

   Skiplist uses multiple levels with probabilistic promotion, reducing expected search path length to logarithmic in n.

2. Step 2: Analyze average operation cost

   Each operation traverses from top level down, with expected O(log n) steps due to geometric level distribution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Skiplist average complexity is well-known as O(log n) [OK]

Hint: Skiplist average complexity is logarithmic, not linear or constant [OK]

Common Mistakes:

• Assuming linear time due to linked list base
• Confusing traversal at each level as multiplicative
• Thinking arrays provide O(1) search in skiplist

5. Examine the following buggy code snippet for the MedianFinder class. Which line contains the subtle bug that can cause incorrect median calculation?

medium

A. Condition 'if self.low_size > self.high_size:' for balancing heaps

B. Line that pushes to high heap and increments high_size

C. Line that pushes to low heap and increments low_size

D. Condition 'elif self.high_size > self.low_size + 1:' for balancing heaps

Solution

1. Step 1: Understand balancing condition

   The heaps must be balanced so that their sizes differ by at most 1.

2. Step 2: Identify incorrect condition

   The condition 'if self.low_size > self.high_size:' moves an element from low to high even when sizes differ by only 1, causing imbalance.

3. Step 3: Correct condition

   The condition should be 'if self.low_size > self.high_size + 1:' to ensure size difference is more than 1 before balancing.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Balancing condition must check if low_size > high_size + 1 [OK]

Hint: Balance heaps only if size difference > 1 [OK]

Common Mistakes:

• Balancing heaps too aggressively
• Incorrect size difference checks