Home/dsa/

Design

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Requirements

get(key): Return the value of the key if it exists, otherwise return -1.
put(key, value): Update or insert the value. If the cache reaches capacity, evict the least recently used item before inserting a new one.

Goal

All operations must run in $O(1)$ average time complexity.

Medium

Examples

Input: ["LRUCache", "put", "put", "get", "put", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2]]
Output: [null, null, null, 1, null, -1]

Approach 1

Level I: Brute Force (List of Pairs)

Intuition

Maintain a simple list or array of [key, value] pairs. For every get or put operation, we iterate through the list to find if the key exists. This established a baseline for why we need more optimized structures.

⏱ O(N) for both `get` and `put`.💾 O(Capacity).

Detailed Dry Run

Input: put(1,1), put(2,2), get(1)

Step	Operation	List State (Old to New)	Result
1	`put(1,1)`	`[[1,1]]`	null
2	`put(2,2)`	`[[1,1], [2,2]]`	null
3	`get(1)`	`[[2,2], [1,1]]`	1

java

import java.util.*;

class LRUCache {
    private List<int[]> list = new ArrayList<>();
    private int cap;

    public LRUCache(int capacity) { this.cap = capacity; }

    public int get(int key) {
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i)[0] == key) {
                int[] pair = list.remove(i);
                list.add(pair);
                return pair[1];
            }
        }
        return -1;
    }

    public void put(int key, int value) {
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i)[0] == key) {
                list.remove(i); break;
            }
        }
        if (list.size() == cap) list.remove(0);
        list.add(new int[]{key, value});
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3);
        System.out.println(cache.get(2)); // -1
    }
}

Approach 2

Level II: Intermediate (Built-in Ordered Map)

Intuition

Most modern languages provide data structures that maintain insertion order. We can leverage these (e.g., LinkedHashMap in Java, OrderedDict in Python, or the standard Map in JS which preserves key insertion order) to implement LRU with minimal code.

⏱ O(1) average for all operations.💾 O(Capacity).

Detailed Dry Run

Input: put(1,1), put(2,2), get(1)

Step	Operation	Map State (Keys)	LRU Logic
1	`put(1,1)`	`{1}`	Added 1
2	`put(2,2)`	`{1, 2}`	Added 2
3	`get(1)`	`{2, 1}`	Re-inserted 1 to end

java

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    public int get(int key) { return super.getOrDefault(key, -1); }
    public void put(int key, int value) { super.put(key, value); }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1); cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
    }
}

Approach 3

Level III: Optimal (HashMap + Deque)

Intuition

To achieve true $O(1)$ without relying on language-specific magic, we implement our own Doubly Linked List (DLL) and a HashMap. The DLL allows $O(1)$ removal and addition at both ends, while the HashMap provides $O(1)$ access to any node given its key.

⏱ O(1) strictly for all operations.💾 O(Capacity).

Detailed Dry Run

Input: put(1,1), put(2,2), get(1)

Step	Operation	DLL Structure (Head <-> Tail)	Map State
1	`put(1,1)`	`H <-> [1:1] <-> T`	`{1: node1}`
2	`put(2,2)`	`H <-> [2:2] <-> [1:1] <-> T`	`{1: n1, 2: n2}`
3	`get(1)`	`H <-> [1:1] <-> [2:2] <-> T`	`{1: n1, 2: n2}`

java

import java.util.*;

class LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    
    private Map<Integer, Node> map = new HashMap<>();
    private Node head, tail;
    private int capacity;

    public LRUCache(int cap) {
        capacity = cap;
        head = new Node(0, 0); tail = new Node(0, 0);
        head.next = tail; tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node); add(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) remove(map.get(key));
        if (map.size() == capacity) {
            map.remove(tail.prev.key);
            remove(tail.prev);
        }
        Node node = new Node(key, value);
        add(node); map.put(key, node);
    }

    private void add(Node node) {
        node.next = head.next; head.next.prev = node;
        head.next = node; node.prev = head;
    }

    private void remove(Node node) {
        node.prev.next = node.next; node.next.prev = node.prev;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1); cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3); System.out.println(cache.get(2)); // -1
    }
}

Design Tic-Tac-Toe

Design a Tic-Tac-Toe game that is played on an $n \times n$ grid. You may assume the following rules:

A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves will be allowed.
A player who succeeds in placing $n$ of their marks in a horizontal, vertical, or diagonal row wins the game.

Goal

move(row, col, player) must run in $O(1)$ time complexity.

Medium

Examples

Input: n = 3, move(0, 0, 1), move(0, 2, 2), move(2, 2, 1), move(1, 1, 2), move(2, 0, 1), move(1, 0, 2), move(2, 1, 1)
Output: 1

Approach 1

Level I: Brute-Force Grid Scan

Intuition

Maintain the actual $n \times n$ grid. For every move, scan the entire row, column, and two diagonals to check if all elements belong to the current player.

⏱ O(N) per move.💾 O(N^2).

Detailed Dry Run

Input: n=3, move(0,0,1)

Step	Move	Grid State	Result
1	`(0,0,1)`	`[[1,0,0],...]`	0 (No win yet)

java

import java.util.*;

class TicTacToe {
    private int[][] grid; private int n;
    public TicTacToe(int n) { grid = new int[n][n]; this.n = n; }
    public int move(int r, int c, int p) {
        grid[r][c] = p;
        boolean win = true;
        for (int i=0; i<n; i++) if (grid[r][i] != p) win = false;
        if (win) return p;
        win = true; for (int i=0; i<n; i++) if (grid[i][c] != p) win = false;
        if (win) return p;
        if (r == c) {
            win = true; for (int i=0; i<n; i++) if (grid[i][i] != p) win = false;
            if (win) return p;
        }
        if (r + c == n - 1) {
            win = true; for (int i=0; i<n; i++) if (grid[i][n-1-i] != p) win = false;
            if (win) return p;
        }
        return 0;
    }
    public static void main(String[] args) {
        TicTacToe game = new TicTacToe(3);
        System.out.println(game.move(0, 0, 1)); // 0
    }
}

Approach 2

Level II: Optimized Grid Scan

Intuition

Instead of re-scanning everything, we only check the specific row, column, and diagonals that the current move affected. This reduces the work from $O(N^2)$ to $O(N)$ .

⏱ O(N) per move.💾 O(N^2) to store the grid.

Detailed Dry Run

Input: n=3, move(1,1,1)

Scan	Elements	Result
Row 1	`[0,1,0]`	No Win
Col 1	`[0,1,0]`	No Win
Diag 1	`[1,1,0]`	No Win
Diag 2	`[0,1,0]`	No Win

java

class TicTacToe {
    private int[][] grid; private int n;
    public TicTacToe(int n) { this.grid = new int[n][n]; this.n = n; }
    public int move(int r, int c, int p) {
        grid[r][c] = p;
        if (checkRow(r, p) || checkCol(c, p) || checkDiag(r, c, p) || checkAntiDiag(r, c, p)) return p;
        return 0;
    }
    private boolean checkRow(int r, int p) { for(int i=0; i<n; i++) if(grid[r][i] != p) return false; return true; }
    private boolean checkCol(int c, int p) { for(int i=0; i<n; i++) if(grid[i][c] != p) return false; return true; }
    private boolean checkDiag(int r, int c, int p) {
        if (r != c) return false;
        for(int i=0; i<n; i++) if(grid[i][i] != p) return false;
        return true;
    }
    private boolean checkAntiDiag(int r, int c, int p) {
        if (r + c != n - 1) return false;
        for(int i=0; i<n; i++) if(grid[i][n-1-i] != p) return false;
        return true;
    }
}

Approach 3

Level III: Counter Arrays (Optimal)

Intuition

To achieve $O(1)$ time, we stop storing the grid entirely. Instead, we maintain count arrays for rows and columns, and two variables for the diagonals. For player 1, we add 1; for player 2, we subtract 1. If any count's absolute value reaches $n$ , we have a winner.

⏱ O(1) per move.💾 O(N) to store row/col/diag counts.

Detailed Dry Run

Input: n=3, move(0,0,1)

Step	Move	Rows Count	Cols Count	Diag	Result
1	`(0,0,1)`	`[1,0,0]`	`[1,0,0]`	1	0
2	`(1,1,1)`	`[1,1,0]`	`[1,1,0]`	2	0
3	`(2,2,1)`	`[1,1,1]`	`[1,1,1]`	3	1 (Win!)

java

import java.util.*;

class TicTacToe {
    private int[] rows, cols; private int diag, antiDiag, n;
    public TicTacToe(int n) { this.n = n; rows = new int[n]; cols = new int[n]; }
    public int move(int r, int c, int p) {
        int val = (p == 1) ? 1 : -1;
        rows[r] += val; cols[c] += val;
        if (r == c) diag += val;
        if (r + c == n - 1) antiDiag += val;
        if (Math.abs(rows[r]) == n || Math.abs(cols[c]) == n || Math.abs(diag) == n || Math.abs(antiDiag) == n) return p;
        return 0;
    }
    public static void main(String[] args) {
        TicTacToe game = new TicTacToe(3);
        System.out.println(game.move(0,0,1));
    }
}

Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using one or more queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Easy

Examples

Input: ["MyStack", "push", "push", "top", "pop", "empty"]\n[[], [1], [2], [], [], []]
Output: [null, null, null, 2, 2, false]

Approach 1

Level I: Two Queues (Push O(1))

Intuition

Maintain two queues. push is $O(1)$ to q1. For pop, we move all elements except the last one from q1 to q2, then the last one is the stack's top.

⏱ O(1) push, O(N) pop/top.💾 O(N).

Detailed Dry Run

Input: push(1), push(2), pop()\n| Step | Op | Q1 | Q2 | Result |\n| :--- | :--- | :--- | :--- | :--- |\n| 1 | push(1) | [1] | [] | null |\n| 2 | push(2) | [1, 2] | [] | null |\n| 3 | pop() | [] | [1] | 2 |

java

import java.util.*;\nclass MyStack {\n    private Queue<Integer> q1 = new LinkedList<>();\n    private Queue<Integer> q2 = new LinkedList<>();\n    private int top;\n    public void push(int x) { q1.add(x); top = x; }\n    public int pop() {\n        while (q1.size() > 1) { top = q1.poll(); q2.add(top); }\n        int res = q1.poll();\n        Queue<Integer> temp = q1; q1 = q2; q2 = temp;\n        return res;\n    }\n    public int top() { return top; }\n    public boolean empty() { return q1.isEmpty(); }\n}

Approach 2

Level II: Two Queues (Pop/Top O(1))

Intuition

To make pop and top $O(1)$ , we do the heavy lifting during push. When pushing x, we add it to q2, then move everything from q1 to q2, then swap names. This keeps q1 in LIFO order.

⏱ O(N) push, O(1) pop/top.💾 O(N).

Detailed Dry Run

Push(1), Push(2)

Op	Q1	Q2	Action
`push(1)`	`[1]`	`[]`	Simple add
`push(2)`	`[]`	`[2, 1]`	Add 2 to Q2, then move 1 from Q1 to Q2
`pop()`	`[1]`	`[]`	pop from Q1

java

class MyStack {
    private Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>();
    public void push(int x) {
        q2.add(x);
        while(!q1.isEmpty()) q2.add(q1.poll());
        Queue<Integer> temp = q1; q1 = q2; q2 = temp;
    }
    public int pop() { return q1.poll(); }
    public int top() { return q1.peek(); }
    public boolean empty() { return q1.isEmpty(); }
}

Approach 3

Level III: One Queue (Optimal)

Intuition

The optimal implementation uses only one queue. For push, we add the element and rotate the queue $N-1$ times so the newly added element becomes the front of the queue.

⏱ O(N) push, O(1) pop/top.💾 O(N).

Detailed Dry Run

Queue: [1, 2] -> push(3) -> [1, 2, 3] -> Rotate 1: [2, 3, 1] -> Rotate 2: [3, 1, 2]

Step	Queue	Action
1	`[1,2]`	Initial
2	`[1,2,3]`	Add 3 to back
3	`[2,3,1]`	Poll 1, Add to back
4	`[3,1,2]`	Poll 2, Add to back
Result: 3 is at front (LIFO)

java

import java.util.*;
class MyStack {
    private Queue<Integer> q = new LinkedList<>();
    public void push(int x) {
        q.add(x);
        for (int i = 0; i < q.size() - 1; i++) q.add(q.poll());
    }
    public int pop() { return q.poll(); }
    public int top() { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}

Implement Queue using Stacks

Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Easy

Examples

Input: ["MyQueue", "push", "push", "peek", "pop", "empty"]\n[[], [1], [2], [], [], []]
Output: [null, null, null, 1, 1, false]

Approach 1

Level I: Two Stacks (Push O(N))

Intuition

When pushing an element, move all elements from the primary stack to a temporary stack, push the new element, then move everything back.

⏱ Push $O(N)$, Pop $O(1)$.💾 O(N).

Detailed Dry Run

Push(1), Push(2) -> S1: [2, 1] (top is 1)

java

import java.util.*;\nclass MyQueue {\n    Stack<Integer> s1 = new Stack<>(), s2 = new Stack<>();\n    public void push(int x) {\n        while(!s1.isEmpty()) s2.push(s1.pop());\n        s1.push(x);\n        while(!s2.isEmpty()) s1.push(s2.pop());\n    }\n    public int pop() { return s1.pop(); }\n    public int peek() { return s1.peek(); }\n    public boolean empty() { return s1.isEmpty(); }\n}

Approach 2

Level II: Two Stacks (Pop O(N))

Intuition

To make push $O(1)$ , just push to s1. For pop and peek, if s1 has elements, move everything to s2, remove/view the top, then move everything back to s1 to maintain order. This establishes a baseline for amortized optimization.

⏱ Push O(1), Pop/Peek O(N).💾 O(N).

Detailed Dry Run

Push(1), Push(2), Pop()

Op	S1	S2	Action
`push(1)`	`[1]`	`[]`
`push(2)`	`[1, 2]`	`[]`
`pop()`	`[]`	`[1, 2]`	Move S1 to S2, pop 1, move back
Result: 1

java

class MyQueue {
    Stack<Integer> s1 = new Stack<>(), s2 = new Stack<>();
    public void push(int x) { s1.push(x); }
    public int pop() {
        while(!s1.isEmpty()) s2.push(s1.pop());
        int res = s2.pop();
        while(!s2.isEmpty()) s1.push(s2.pop());
        return res;
    }
    public int peek() {
        while(!s1.isEmpty()) s2.push(s1.pop());
        int res = s2.peek();
        while(!s2.isEmpty()) s1.push(s2.pop());
        return res;
    }
    public boolean empty() { return s1.isEmpty(); }
}

Approach 3

Level III: Two Stacks (Amortized O(1))

Intuition

Use inStack for push and outStack for pop. Transfer only when outStack is empty. This way, each element is moved at most twice (once into inStack, once into outStack), leading to $O(1)$ amortized time.

⏱ Push $O(1)$, Pop amortized $O(1)$.💾 O(N).

Detailed Dry Run

Push(1), Push(2) -> In: [1, 2]. Pop() -> Move to Out: [2, 1]. Pop 1.

Op	In	Out	Action
`push(1)`	`[1]`	`[]`
`push(2)`	`[1, 2]`	`[]`
`pop()`	`[]`	`[2]`	Move S1 to S2, return 1
Result: 1

java

import java.util.*;
class MyQueue {
    Stack<Integer> in = new Stack<>(), out = new Stack<>();
    public void push(int x) { in.push(x); }
    public int pop() { peek(); return out.pop(); }
    public int peek() {
        if (out.isEmpty()) while(!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Medium

Examples

Input: hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301)
Output: 3, 4, 3

Approach 1

Level I: Queue of Timestamps

Intuition

Record every hit as a timestamp in a queue. For getHits, remove all timestamps from the front that are older than 300 seconds.

⏱ Hit: O(1), getHits: O(N).💾 O(N).

Detailed Dry Run

Queue: [1, 2, 3]. getHits(305) -> 1 is older than (305-300=5), so remove 1.

java

import java.util.*;\nclass HitCounter {\n    private Queue<Integer> q = new LinkedList<>();\n    public void hit(int t) { q.add(t); }\n    public int getHits(int t) {\n        while (!q.isEmpty() && t - q.peek() >= 300) q.poll();\n        return q.size();\n    }\n}

Approach 2

Level II: Map of Count by Second

Intuition

Instead of storing every hit, we store the total hit count for each unique second using a HashMap<Timestamp, Count>. This is more space-efficient if there are many hits at the same time.

⏱ Hit: O(1), getHits: O(300).💾 O(300) maximum.

Detailed Dry Run

hit(1), hit(1), hit(2) -> {1: 2, 2: 1}. getHits(301) -> Sum counts for keys > 1.

java

class HitCounter {
    private Map<Integer, Integer> map = new HashMap<>();
    public void hit(int t) { map.put(t, map.getOrDefault(t, 0) + 1); }
    public int getHits(int t) {
        int count = 0;
        for (int time : map.keySet()) if (t - time < 300) count += map.get(time);
        return count;
    }
}

Approach 3

Level III: Scalable Circular Array (Optimal)

Intuition

To handle large-scale systems with millions of hits, we use a fixed-size array of 300 buckets (one for each second). Each bucket stores the timestamp and hit count.

⏱ Hit: O(1), getHits: O(B) where B=300.💾 O(B).

Detailed Dry Run

Timestamp 301 maps to bucket 301%300 = 1. If old timestamp in bucket 1 was 1, we reset count. Else increment.

java

class HitCounter {\n    private int[] times = new int[300], hits = new int[300];\n    public void hit(int t) {\n        int idx = (t - 1) % 300;\n        if (times[idx] != t) { times[idx] = t; hits[idx] = 1; }\n        else hits[idx]++;\n    }\n    public int getHits(int t) {\n        int res = 0;\n        for (int i=0; i<300; i++) if (t - times[i] < 300) res += hits[i];\n        return res;\n    }\n}

Design Circular Queue

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

Medium

Approach 1

Level I: Array with Front/Rear Pointers

Intuition

Use a fixed-size array and two pointers, head and tail. Use modulo arithmetic to wrap around the array. We use a size variable to easily distinguish between empty and full states.

⏱ O(1) for all ops.💾 O(N).

Detailed Dry Run

Enqueue(1), Enqueue(2), Dequeue()...

Op	Array	Head	Tail	Size
`init(3)`	`[0,0,0]`	0	-1	0
`enq(1)`	`[1,0,0]`	0	0	1
`enq(2)`	`[1,2,0]`	0	1	2
`deq()`	`[1,2,0]`	1	1	1

java

class MyCircularQueue {
    private int[] q; private int head, tail, size, k;
    public MyCircularQueue(int k) { this.k = k; q = new int[k]; head = 0; tail = -1; size = 0; }
    public boolean enQueue(int val) {
        if (isFull()) return false;
        tail = (tail + 1) % k; q[tail] = val; size++; return true;
    }
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = (head + 1) % k; size--; return true;
    }
    public int Front() { return isEmpty() ? -1 : q[head]; }
    public int Rear() { return isEmpty() ? -1 : q[tail]; }
    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == k; }
}

Approach 2

Level II: Linked List Implementation

Intuition

Instead of an array, use a Doubly Linked List. This avoids modulo arithmetic but uses more memory for pointers. To make it 'circular' in memory, we can limit the number of nodes to k.

⏱ O(1) all ops.💾 O(k) where k is max size.

Detailed Dry Run

Head -> [1] <-> [2] <-> [3] <- Tail Enqueue(4) if size < k: Add new node after tail, move tail.

java

class MyCircularQueue {
    class Node { int val; Node next; Node(int v) { val = v; } }
    Node head, tail; int count, capacity;
    public MyCircularQueue(int k) { capacity = k; }
    public boolean enQueue(int value) {
        if (isFull()) return false;
        Node newNode = new Node(value);
        if (isEmpty()) head = tail = newNode;
        else { tail.next = newNode; tail = newNode; }
        count++; return true;
    }
    public boolean deQueue() {
        if (isEmpty()) return false;
        head = head.next; count--; return true;
    }
    public int Front() { return isEmpty() ? -1 : head.val; }
    public int Rear() { return isEmpty() ? -1 : tail.val; }
    public boolean isEmpty() { return count == 0; }
    public boolean isFull() { return count == capacity; }
}

Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Medium

Approach 1

Level I: Brute Force (Scan on getMin)

Intuition

Maintain a simple stack of elements. Every time getMin() is called, iterate through the entire stack to find the minimum element.

⏱ Push/Pop: O(1), getMin: O(N).💾 O(N).

Detailed Dry Run

Push(5), Push(3), getMin() -> Scan [5, 3] -> Min is 3.

java

class MinStack {
    private Stack<Integer> s = new Stack<>();
    public void push(int x) { s.push(x); }
    public void pop() { s.pop(); }
    public int top() { return s.peek(); }
    public int getMin() {
        int min = Integer.MAX_VALUE;
        for(int x : s) min = Math.min(min, x);
        return min;
    }
}

Approach 2

Level II: Two Stacks (Standard Optimality)

Intuition

Maintain a second stack to store the minimum value encountered so far for each element in the main stack. This ensures getMin() is $O(1)$ .

⏱ O(1) all ops.💾 O(N).

Detailed Dry Run

Push(5), Push(3) | Stack | MinStack | Action | | :--- | :--- | :--- | :--- | | [5] | [5] | | | [5, 3] | [5, 3] | 3 < 5, so push 3 | | pop() | [5] | both pop |

java

import java.util.*;
class MinStack {
    private Stack<Integer> s = new Stack<>(), min = new Stack<>();
    public void push(int x) { s.push(x); if(min.isEmpty() || x <= min.peek()) min.push(x); }
    public void pop() { if(s.pop().equals(min.peek())) min.pop(); }
    public int top() { return s.peek(); }
    public int getMin() { return min.peek(); }
}

Approach 3

Level III: Optimized Space (Single Stack with Min Delta)

Intuition

Store only the difference between the current value and the minimum value. This allows us to reconstruct the previous minimum when the current minimum is popped.

⏱ O(1) all ops.💾 O(1) auxiliary (excluding stack).

Detailed Dry Run

Push(x): store (x - min). If x < min, update min = x.

java

import java.util.*;\nclass MinStack {\n    private Stack<Long> s = new Stack<>();\n    private long min;\n    public void push(int val) {\n        if(s.isEmpty()) { s.push(0L); min = val; }\n        else { s.push(val - min); if(val < min) min = val; }\n    }\n    public void pop() {\n        long diff = s.pop();\n        if(diff < 0) min = min - diff;\n    }\n    public int top() {\n        long diff = s.peek();\n        return diff > 0 ? (int)(diff + min) : (int)min;\n    }\n    public int getMin() { return (int)min; }\n}

Design Add and Search Words

Design a data structure that supports adding new words and finding if a string matches any previously added string. The search string can contain letters or dots . where a dot can match any letter.

Complexity

addWord: $O(L)$ where $L$ is word length.
search: $O(26^L)$ in worst case due to wildcards, but typically fast with Trie pruning.

Medium

Examples

Input: addWord("bad"), addWord("dad"), search("pad"), search("bad"), search(".ad"), search("b..")
Output: false, true, true, true

Approach 1

Level I: Set of Words

Intuition

Store all added words in a HashSet. For search, if it contains no dots, do an $O(1)$ lookup. If it contains dots, iterate through all words in the set ( $O(N)$ ) and check if they match the pattern.

⏱ Add: O(L), Search: O(N * L).💾 O(N * L).

java

class WordDictionary {
    Set<String> set = new HashSet<>();
    public void addWord(String word) { set.add(word); }
    public boolean search(String word) {
        if (!word.contains(".")) return set.contains(word);
        for (String s : set) {
            if (s.length() != word.length()) continue;
            boolean match = true;
            for(int i=0; i<s.length(); i++) if(word.charAt(i) != '.' && word.charAt(i) != s.charAt(i)) { match = false; break; }
            if (match) return true;
        }
        return false;
    }
}

Approach 2

Level II: HashMap of Lengths

Intuition

Group words by their length in a HashMap<Integer, Set<String>>. When searching, we only check words of the exact same length as the input, significantly reduced the comparisons.

⏱ Add: O(L), Search: O(Words_of_Length_L).💾 O(N * L).

Detailed Dry Run

Add('bad', 'dad', 'pad'). Map: {3: ['bad', 'dad', 'pad']}. Search('.ad') checks only length 3 set.

java

class WordDictionary {
    Map<Integer, Set<String>> map = new HashMap<>();
    public void addWord(String word) {
        map.putIfAbsent(word.length(), new HashSet<>());
        map.get(word.length()).add(word);
    }
    public boolean search(String word) {
        if (!map.containsKey(word.length())) return false;
        for (String s : map.get(word.length())) {
            boolean match = true;
            for (int i=0; i<word.length(); i++) if (word.charAt(i) != '.' && word.charAt(i) != s.charAt(i)) { match = false; break; }
            if (match) return true;
        }
        return false;
    }
}

Approach 3

Level III: Trie (Prefix Tree) with DFS

Intuition

Use a Trie to store words. For exact matches, search is $O(L)$ . For dots, use DFS to explore all possible children at that level.

⏱ Add: O(L), Search: O(N) where N is total Trie nodes.💾 O(N).

java

class WordDictionary {
    class Node { Node[] children = new Node[26]; boolean isEnd; }
    private Node root = new Node();
    public void addWord(String word) {
        Node curr = root;
        for (char c : word.toCharArray()) {
            if (curr.children[c-'a'] == null) curr.children[c-'a'] = new Node();
            curr = curr.children[c-'a'];
        }
        curr.isEnd = true;
    }
    public boolean search(String word) { return dfs(word, 0, root); }
    private boolean dfs(String word, int i, Node node) {
        if (i == word.length()) return node.isEnd;
        char c = word.charAt(i);
        if (c == '.') {
            for (Node child : node.children) if (child != null && dfs(word, i+1, child)) return true;
            return false;
        }
        return node.children[c-'a'] != null && dfs(word, i+1, node.children[c-'a']);
    }
}

Design Underground System

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it takes to travel from one station to another.

Requirement

checkIn(id, stationName, t)
checkOut(id, stationName, t)
getAverageTime(startStation, endStation)

Medium

Examples

Input: ["UndergroundSystem","checkIn","checkOut","getAverageTime"]
[[],[45,"a",3],[45,"b",10],["a","b"]]
Output: [null,null,null,7.0]

Approach 1

Level I: Single HashMap with List (Brute Force)

Intuition

Store every check-in and check-out event in a single list or map. When asked for the average, iterate through ALL logged events to find matches. This is slow but memory-efficient for simple logs.

⏱ O(1) write, O(E) read where E is events.💾 O(E).

Detailed Dry Run

Logs: [(id:45, in:'a', out:'b', time:7), (id:46, in:'c', out:'b', time:10)]. Average('a','b') -> find first entry -> 7.

java

class UndergroundSystem {
    class Event { String start, end; int duration; Event(String s, String e, int d) { start = s; end = e; duration = d; } }
    Map<Integer, String[]> active = new HashMap<>();
    List<Event> history = new ArrayList<>();
    public void checkIn(int id, String s, int t) { active.put(id, new String[]{s, String.valueOf(t)}); }
    public void checkOut(int id, String s, int t) {
        String[] in = active.remove(id);
        history.add(new Event(in[0], s, t - Integer.parseInt(in[1])));
    }
    public double getAverageTime(String s, String e) {
        double sum = 0; int count = 0;
        for(Event ev : history) if(ev.start.equals(s) && ev.end.equals(e)) { sum += ev.duration; count++; }
        return sum / count;
    }
}

Approach 2

Level II: String Concatenation Keys

Intuition

Use simple string concatenation start+"->"+end as keys in a single HashMap. Store lists of travel durations and compute averages on the fly.

⏱ O(1) all ops, search is O(K) where K is number of trips.💾 O(N).

java

class UndergroundSystem {
    Map<Integer, Object[]> checkIn = new HashMap<>();
    Map<String, List<Integer>> trips = new HashMap<>();
    public void checkIn(int id, String s, int t) { checkIn.put(id, new Object[]{s, t}); }
    public void checkOut(int id, String s, int t) {
        Object[] cin = checkIn.get(id);
        String key = cin[0] + "->" + s;
        trips.putIfAbsent(key, new ArrayList<>());
        trips.get(key).add(t - (int)cin[1]);
    }
    public double getAverageTime(String start, String end) {
        List<Integer> list = trips.get(start + "->" + end);
        return list.stream().mapToInt(i->i).average().orElse(0.0);
    }
}

Approach 3

Level III: Two HashMaps

Intuition

Use checkInMap to store id -> (station, time). Use routeMap to store (start, end) -> (totalTime, count). Checkout triggers a look-up in checkInMap, calculates the duration, and updates routeMap.

⏱ O(1) for all operations.💾 O(P + S^2) where P is max active passengers, S is stations.

java

class UndergroundSystem {
    class CheckIn { String station; int time; CheckIn(String s, int t) { station = s; time = t; } }
    class Route { double total; int count; }
    Map<Integer, CheckIn> in = new HashMap<>();
    Map<String, Route> rMap = new HashMap<>();
    public void checkIn(int id, String s, int t) { in.put(id, new CheckIn(s, t)); }
    public void checkOut(int id, String s, int t) {
        CheckIn ci = in.remove(id);
        String key = ci.station + "," + s;
        Route rt = rMap.getOrDefault(key, new Route());
        rt.total += (t - ci.time); rt.count++;
        rMap.put(key, rt);
    }
    public double getAverageTime(String start, String end) {
        Route rt = rMap.get(start + "," + end);
        return rt.total / rt.count;
    }
}

Design Snake Game

Design a Snake game that is played on a device with screen size $height \times width$ . The snake is initially positioned at the top left corner $(0, 0)$ with a length of 1 unit.

Logic

Move the head.
Check boundaries and self-collision.
If head hits food, increase length (don't remove tail).
Otherwise, move forward (remove tail).

Medium

Examples

Input: SnakeGame(3, 2, [[1, 2], [0, 1]]), move("R"), move("D"), move("R"), move("U"), move("L"), move("U")
Output: 0, 0, 1, 1, 2, -1

Approach 1

Level II: Deque only (Body only scan)

Intuition

Maintain the body in a Deque. For collision check, iterate through the entire deque ( $O(N)$ ). This avoids the secondary HashSet but is slower for long snakes.

⏱ O(N) per move.💾 O(N).

java

class SnakeGame {
    Deque<Integer> body = new LinkedList<>();
    int[][] food; int foodIdx, w, h, score;
    public SnakeGame(int width, int height, int[][] food) {
        this.w = width; this.h = height; this.food = food; body.add(0);
    }
    public int move(String dir) {
        int head = body.peekFirst(), r = head / w, c = head % w;
        if (dir.equals("U")) r--; else if (dir.equals("D")) r++;
        else if (dir.equals("L")) c--; else if (dir.equals("R")) c++;
        if (r < 0 || r >= h || c < 0 || c >= w) return -1;
        int next = r * w + c;
        if (foodIdx < food.length && r == food[foodIdx][0] && c == food[foodIdx][1]) {
            foodIdx++; score++;
        } else body.removeLast();
        if (body.contains(next)) return -1;
        body.addFirst(next); return score;
    }
}

Approach 2

Level III: Deque + HashSet

Intuition

Use a Deque to store the coordinates of the snake's body (head at front, tail at back). Use a HashSet of encoded coordinates (r * width + c) for $O(1)$ self-collision check.

⏱ O(1) per move.💾 O(N + F) where N is snake length, F is food items.

java

class SnakeGame {
    Deque<Integer> body = new LinkedList<>();
    Set<Integer> set = new HashSet<>();
    int[][] food; int foodIdx, w, h, score;
    public SnakeGame(int width, int height, int[][] food) {
        this.w = width; this.h = height; this.food = food;
        body.add(0); set.add(0);
    }
    public int move(String dir) {
        int head = body.peekFirst(), r = head / w, c = head % w;
        if (dir.equals("U")) r--;
        else if (dir.equals("D")) r++;
        else if (dir.equals("L")) c--;
        else if (dir.equals("R")) c++;
        if (r < 0 || r >= h || c < 0 || c >= w) return -1;
        int next = r * w + c;
        int tail = body.peekLast();
        set.remove(tail); // Tail moves out, head can move in to old tail spot
        if (set.contains(next)) return -1;
        if (foodIdx < food.length && r == food[foodIdx][0] && c == food[foodIdx][1]) {
            set.add(tail); body.addLast(tail); foodIdx++; score++;
        }
        body.addFirst(next); set.add(next);
        return score;
    }
}

LFU Cache

Design a data structure that follows the constraints of a Least Frequently Used (LFU) cache.

Requirement

get(key): Return value if exists, update frequency.
put(key, value): Insert/update value. If at capacity, evict the least frequently used item. If there's a tie, evict the least recently used.

Hard

Examples

Input: ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Approach 1

Level I: Brute Force Scan

Intuition

Store entries in a List or Map. For every put at capacity, iterate through the entire collection to find the item with the minimum frequency and the oldest access time. This is $O(N)$ per operation but extremely simple.

⏱ O(N) for get and put.💾 O(Capacity).

Detailed Dry Run

Cache: {(A, f:2, t:1), (B, f:1, t:2)}. Put(C) evicts B because its frequency (1) is lower than A (2).

java

class LFUCache {
    class Node { int k, v, f, t; Node(int k, int v, int f, int t){this.k=k;this.v=v;this.f=f;this.t=t;} }
    Map<Integer, Node> map = new HashMap<>(); int cap, time = 0;
    public LFUCache(int c) { cap = c; }
    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        Node n = map.get(key); n.f++; n.t = ++time; return n.v;
    }
    public void put(int key, int value) {
        if(cap <= 0) return;
        if(map.containsKey(key)) { Node n = map.get(key); n.v = value; n.f++; n.t = ++time; }
        else {
            if(map.size() == cap) {
                int minF = Integer.MAX_VALUE, minT = Integer.MAX_VALUE, remK = -1;
                for(Node n : map.values()) if(n.f < minF || (n.f == minF && n.t < minT)) { minF = n.f; minT = n.t; remK = n.k; }
                map.remove(remK);
            }
            map.put(key, new Node(key, value, 1, ++time));
        }
    }
}

Approach 2

Level II: Priority Queue (O(log N))

Intuition

Use a PriorityQueue to store entries sorted by frequency, and then by access time (tie-breaker). While push and pop are $O(log N)$ , it is simpler to implement than the $O(1)$ DLL version.

⏱ O(log N) for get and put.💾 O(Capacity).

java

class LFUCache {
    class Node implements Comparable<Node> {
        int key, val, freq, time;
        Node(int k, int v, int f, int t) { key = k; val = v; freq = f; time = t; }
        public int compareTo(Node o) {
            return freq == o.freq ? time - o.time : freq - o.freq;
        }
    }
    Map<Integer, Node> map = new HashMap<>();
    PriorityQueue<Node> pq = new PriorityQueue<>();
    int cap, timer;
    public LFUCache(int capacity) { cap = capacity; }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        pq.remove(node); node.freq++; node.time = ++timer;
        pq.add(node); return node.val;
    }
    public void put(int key, int value) {
        if (cap <= 0) return;
        if (map.containsKey(key)) {
            Node node = map.get(key); pq.remove(node);
            node.val = value; node.freq++; node.time = ++timer;
            pq.add(node);
        } else {
            if (map.size() == cap) { Node rem = pq.poll(); map.remove(rem.key); }
            Node node = new Node(key, value, 1, ++timer);
            map.put(key, node); pq.add(node);
        }
    }
}

Approach 3

Level III: Map Frequency to Doubly Linked List

Intuition

Maintain a minFreq variable. Use one map for key -> node and another for freq -> DLL of nodes. When a key is accessed, move it from count DLL to count+1 DLL. If count DLL becomes empty and count == minFreq, increment minFreq. Eviction happens at freqMap[minFreq].tail.prev.

⏱ O(1) for all operations.💾 O(Capacity).

java

class LFUCache {
    class Node {
        int key, val, cnt;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; cnt = 1; }
    }
    class DLL {
        Node head, tail; int size;
        DLL() { head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; }
        void add(Node node) { node.next = head.next; head.next.prev = node; head.next = node; node.prev = head; size++; }
        void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; size--; }
    }
    Map<Integer, Node> map = new HashMap<>();
    Map<Integer, DLL> freqMap = new HashMap<>();
    int cap, minFreq, size;
    public LFUCache(int capacity) { cap = capacity; }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        update(node);
        return node.val;
    }
    public void put(int key, int value) {
        if (cap == 0) return;
        if (map.containsKey(key)) {
            Node node = map.get(key); node.val = value; update(node);
        } else {
            if (size == cap) {
                DLL minList = freqMap.get(minFreq);
                map.remove(minList.tail.prev.key);
                minList.remove(minList.tail.prev);
                size--;
            }
            Node node = new Node(key, value);
            map.put(key, node);
            DLL list = freqMap.getOrDefault(1, new DLL());
            list.add(node); freqMap.put(1, list);
            minFreq = 1; size++;
        }
    }
    private void update(Node node) {
        DLL oldList = freqMap.get(node.cnt);
        oldList.remove(node);
        if (node.cnt == minFreq && oldList.size == 0) minFreq++;
        node.cnt++;
        DLL newList = freqMap.getOrDefault(node.cnt, new DLL());
        newList.add(node); freqMap.put(node.cnt, newList);
    }
}

Insert Delete GetRandom O(1) - Duplicates allowed

Design a data structure that supports insert, remove, and getRandom in $O(1)$ time, where duplicates are allowed.

Strategy

Combine a List of values (for $O(1)$ random access) with a HashMap<Value, Set<Indices>> (for $O(1)$ removal).

Hard

Examples

Input: ["RandomizedCollection","insert","insert","insert","getRandom","remove","getRandom"]
[[],[1],[1],[2],[],[1],[]]
Output: [null, true, false, true, 1 or 2, true, 1 or 2]

Approach 1

Level I: Simple List with Linear Scan

Intuition

Maintain a simple ArrayList to store values. For insert, append to the end. For remove, find the first occurrence using a linear scan $O(N)$ and remove it. For getRandom, pick a random index in $O(1)$ .

⏱ Insert: O(1), Remove: O(N), GetRandom: O(1).💾 O(N).

Detailed Dry Run

List: [1, 1, 2]. Remove(1) -> Find index 0 -> List: [1, 2]. getRandom() picks 1 or 2 with equal prob.

java

class RandomizedCollection {
    List<Integer> list = new ArrayList<>();
    Random rand = new Random();
    public boolean insert(int val) {
        boolean exists = list.contains(val); list.add(val); return !exists;
    }
    public boolean remove(int val) {
        return list.remove((Integer)val);
    }
    public int getRandom() { return list.get(rand.nextInt(list.size())); }
}

Approach 2

Level II: Map of Count + Randomized Index

Intuition

Maintain a Map<Value, Frequency> and a List<Value>. When removing, find the first occurrence in the List and replace it with the last element. This is $O(N)$ for remove but $O(1)$ for others.

⏱ Insert: O(1), Remove: O(N), GetRandom: O(1).💾 O(N).

java

class RandomizedCollection {
    List<Integer> list = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    Random rand = new Random();
    public boolean insert(int val) {
        boolean res = !map.containsKey(val);
        map.put(val, map.getOrDefault(val, 0) + 1); list.add(val);
        return res;
    }
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int f = map.get(val); if (f == 1) map.remove(val); else map.put(val, f - 1);
        list.remove((Integer)val); // O(N) search
        return true;
    }
    public int getRandom() { return list.get(rand.nextInt(list.size())); }
}

Approach 3

Level III: HashMap of Sets + Array

Intuition

When removing an element, swap its last index from the Set with the last element in the Array. This allows $O(1)$ deletion from an array by overwriting the target with the last item and popping.

⏱ O(1) average for all operations.💾 O(N).

java

class RandomizedCollection {
    List<Integer> list = new ArrayList<>();
    Map<Integer, Set<Integer>> map = new HashMap<>();
    Random rand = new Random();
    public boolean insert(int val) {
        boolean exists = map.containsKey(val);
        if (!exists) map.put(val, new HashSet<>());
        map.get(val).add(list.size());
        list.add(val);
        return !exists;
    }
    public boolean remove(int val) {
        if (!map.containsKey(val) || map.get(val).isEmpty()) return false;
        int removeIdx = map.get(val).iterator().next();
        map.get(val).remove(removeIdx);
        int lastVal = list.get(list.size() - 1);
        list.set(removeIdx, lastVal);
        map.get(lastVal).add(removeIdx);
        map.get(lastVal).remove(list.size() - 1);
        list.remove(list.size() - 1);
        return true;
    }
    public int getRandom() { return list.get(rand.nextInt(list.size())); }
}

All O(1) Data Structure

Design a data structure that supports the following operations in $O(1)$ time:

Requirement

inc(key): Increments the count of key by one.
dec(key): Decrements the count of key by one.
getMaxKey(): Returns one of the keys with the maximum count.
getMinKey(): Returns one of the keys with the minimum count.

Hard

Examples

Input: ["AllOne","inc","inc","getMaxKey","getMinKey","inc","getMaxKey","getMinKey"]
[[],["hello"],["hello"],[],[],["leet"],[],[]]
Output: [null,null,null,"hello","hello",null,"hello","leet"]

Approach 1

Level I: Brute Force Map Scan

Intuition

Store keys and counts in a single HashMap<String, Integer>. For getMaxKey and getMinKey, iterate through the entire map to find the max/min. This is $O(1)$ for updates but $O(N)$ for queries.

⏱ Inc/Dec: O(1), GetMax/Min: O(N).💾 O(N).

Detailed Dry Run

Map: {'A': 2, 'B': 1}. getMaxKey() -> iterate -> find 'A'.

java

class AllOne {
    Map<String, Integer> map = new HashMap<>();
    public void inc(String key) { map.put(key, map.getOrDefault(key, 0) + 1); }
    public void dec(String key) {
        int c = map.getOrDefault(key, 0); if(c <= 1) map.remove(key); else map.put(key, c - 1);
    }
    public String getMaxKey() {
        String res = ""; int max = -1;
        for(Map.Entry<String, Integer> e : map.entrySet()) if(e.getValue() > max) { max = e.getValue(); res = e.getKey(); }
        return res;
    }
    public String getMinKey() {
        String res = ""; int min = Integer.MAX_VALUE;
        for(Map.Entry<String, Integer> e : map.entrySet()) if(e.getValue() < min) { min = e.getValue(); res = e.getKey(); }
        return res == "" ? "" : res;
    }
}

Approach 2

Level II: Map of Counts + Set of Keys (Lazy Removal)

Intuition

Use Map<String, Integer> keyCount and Map<Integer, Set<String>> countKeys. When incrementing, move the key from its current set to the set for count + 1. This is $O(1)$ but slightly slower than the DLL version due to hash operations.

⏱ O(1) average for all operations.💾 O(N).

java

class AllOne {
    Map<String, Integer> counts = new HashMap<>();
    Map<Integer, Set<String>> sets = new HashMap<>();
    int min = 0, max = 0;
    public void inc(String key) {
        // Lazy logic with counts and sets
    }
    public String getMaxKey() { /* return from max set */ return ""; }
    public String getMinKey() { /* return from min set */ return ""; }
}

Approach 3

Level III: HashMap + Doubly Linked List of Sets

Intuition

Use a HashMap to store key -> count. Use a DLL where each node represents a specific count and contains a Set of all keys with that count. This allows $O(1)$ movement between nodes when incrementing/decrementing.

⏱ O(1) for all operations.💾 O(N).

java

class AllOne {
    class Node { int cnt; Set<String> keys = new HashSet<>(); Node prev, next;
        Node(int c) { cnt = c; } }
    Node head, tail; Map<String, Integer> map = new HashMap<>();
    Map<Integer, Node> countMap = new HashMap<>();
    public AllOne() {
        head = new Node(0); tail = new Node(0); head.next = tail; tail.prev = head;
    }
    private void addNode(Node prevNode, Node newNode) {
        newNode.prev = prevNode; newNode.next = prevNode.next;
        prevNode.next.prev = newNode; prevNode.next = newNode;
    }
    private void removeNode(Node node) {
        node.prev.next = node.next; node.next.prev = node.prev;
    }
    public void inc(String key) {
        int oldCnt = map.getOrDefault(key, 0);
        map.put(key, oldCnt + 1);
        Node oldNode = countMap.get(oldCnt);
        Node newNode = countMap.getOrDefault(oldCnt + 1, new Node(oldCnt + 1));
        if (oldNode == null) { addNode(head, newNode); }
        else {
            oldNode.keys.remove(key);
            if (oldNode.keys.isEmpty()) { removeNode(oldNode); countMap.remove(oldCnt); }
            if (countMap.get(oldCnt + 1) == null) addNode(oldNode, newNode);
        }
        newNode.keys.add(key);
        countMap.put(oldCnt + 1, newNode);
    }
    public void dec(String key) {
        if (!map.containsKey(key)) return;
        int oldCnt = map.get(key);
        Node oldNode = countMap.get(oldCnt);
        oldNode.keys.remove(key);
        if (oldCnt == 1) map.remove(key);
        else {
            map.put(key, oldCnt - 1);
            Node newNode = countMap.getOrDefault(oldCnt - 1, new Node(oldCnt - 1));
            if (countMap.get(oldCnt - 1) == null) addNode(oldNode.prev, newNode);
            newNode.keys.add(key); countMap.put(oldCnt - 1, newNode);
        }
        if (oldNode.keys.isEmpty()) { removeNode(oldNode); countMap.remove(oldCnt); }
    }
    public String getMaxKey() { return tail.prev == head ? "" : tail.prev.keys.iterator().next(); }
    public String getMinKey() { return head.next == tail ? "" : head.next.keys.iterator().next(); }
}

Design Twitter

Design a simplified version of Twitter where users can post tweets, follow/unfollow others, and see the 10 most recent tweets in their news feed.

Core Operations

postTweet(userId, tweetId)
getNewsFeed(userId)
follow(followerId, followeeId)
unfollow(followerId, followeeId)

Scaling Hint

Pull strategy: When a user requests their feed, merge the $K$ recent tweets from themselves and everyone they follow using a Max-Heap.

Hard

Examples

Input: postTweet(1, 5), getNewsFeed(1), follow(1, 2), postTweet(2, 6), getNewsFeed(1), unfollow(1, 2), getNewsFeed(1)
Output: [[5], [6, 5], [5]]

Approach 1

Level I: Map of Lists (Brute Force Sort)

Intuition

Store each user's tweets in a Map<UserId, List<TweetId>>. For getNewsFeed, collect all tweets from the user and their followees into a single list, sort them by timestamp, and return the top 10.

⏱ Feed: O(N log N) where N is tweets of followed users. Other ops: O(1).💾 O(TotalTweets + TotalFollows).

Detailed Dry Run

User 1 follows 2. User 1 tweets: [T1]. User 2 tweets: [T2]. Feed: Sort([T1, T2]) -> [T2, T1].

java

class Twitter {
    private static int time = 0;
    class Tweet { int id, t; Tweet(int i, int tt){id=i; t=tt;} }
    Map<Integer, List<Tweet>> tweets = new HashMap<>();
    Map<Integer, Set<Integer>> follows = new HashMap<>();
    public void postTweet(int u, int t) {
        tweets.putIfAbsent(u, new ArrayList<>());
        tweets.get(u).add(new Tweet(t, time++));
    }
    public List<Integer> getNewsFeed(int u) {
        List<Tweet> all = new ArrayList<>(tweets.getOrDefault(u, new ArrayList<>()));
        if(follows.containsKey(u)) for(int f : follows.get(u)) all.addAll(tweets.getOrDefault(f, new ArrayList<>()));
        Collections.sort(all, (a, b) -> b.t - a.t);
        List<Integer> res = new ArrayList<>();
        for(int i=0; i<Math.min(10, all.size()); i++) res.add(all.get(i).id);
        return res;
    }
    public void follow(int f, int fe) { if(f!=fe) follows.computeIfAbsent(f, k->new HashSet<>()).add(fe); }
    public void unfollow(int f, int fe) { if(follows.containsKey(f)) follows.get(f).remove(fe); }
}

Approach 2

Level II: Global List + Filtering

Intuition

Maintain a single global list of all tweets. When getNewsFeed(userId) is called, iterate backwards through the list and pick the first 10 tweets that were posted by the user or their followees.

⏱ Feed: O(T) where T is total tweets in system. Other ops: O(1).💾 O(T + F).

java

class Twitter {
    class Tweet { int uid, tid; Tweet(int u, int t) { uid = u; tid = t; } }
    List<Tweet> allTweets = new ArrayList<>();
    Map<Integer, Set<Integer>> followers = new HashMap<>();
    public void postTweet(int uid, int tid) { allTweets.add(new Tweet(uid, tid)); }
    public List<Integer> getNewsFeed(int uid) {
        Set<Integer> followed = followers.getOrDefault(uid, new HashSet<>());
        followed.add(uid);
        List<Integer> res = new ArrayList<>();
        for (int i = allTweets.size() - 1; i >= 0 && res.size() < 10; i--) {
            if (followed.contains(allTweets.get(i).uid)) res.add(allTweets.get(i).tid);
        }
        return res;
    }
    public void follow(int f1, int f2) { followers.computeIfAbsent(f1, k -> new HashSet<>()).add(f2); }
    public void unfollow(int f1, int f2) { if (followers.containsKey(f1)) followers.get(f1).remove(f2); }
}

Approach 3

Level III: Map + Heap (Pull-based Feed)

Intuition

Keep a User class containing a Set of followees and a LinkedList of tweets. For getNewsFeed, push the first tweet of each user in the followee list into a Max-Heap (sorted by timestamp), and then standard merge-k-sorted-lists logic.

⏱ Feed: O(F log F) where F is number of followees. Other ops: O(1).💾 O(U + T) for Users and Tweets.

java

class Twitter {
    private static int timestamp = 0;
    class Tweet { int id, time; Tweet next; Tweet(int i, int t) { id = i; time = t; } }
    class User {
        int id; Set<Integer> followed; Tweet head;
        User(int i) { id = i; followed = new HashSet<>(); followed.add(i); }
    }
    Map<Integer, User> userMap = new HashMap<>();
    public void postTweet(int uid, int tid) {
        userMap.putIfAbsent(uid, new User(uid));
        User u = userMap.get(uid);
        Tweet t = new Tweet(tid, timestamp++);
        t.next = u.head; u.head = t;
    }
    public List<Integer> getNewsFeed(int uid) {
        if (!userMap.containsKey(uid)) return new ArrayList<>();
        PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.time - a.time);
        for (int followeeId : userMap.get(uid).followed) {
            User followee = userMap.get(followeeId);
            if (followee != null && followee.head != null) pq.add(followee.head);
        }
        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty() && res.size() < 10) {
            Tweet t = pq.poll(); res.add(t.id);
            if (t.next != null) pq.add(t.next);
        }
        return res;
    }
    public void follow(int f1, int f2) { userMap.putIfAbsent(f1, new User(f1)); userMap.putIfAbsent(f2, new User(f2)); userMap.get(f1).followed.add(f2); }
    public void unfollow(int f1, int f2) { if (userMap.containsKey(f1) && f1 != f2) userMap.get(f1).followed.remove(f2); }
}

Design Phone Directory

Design a Phone Directory that supports get, check, and release operations for a fixed set of $N$ numbers.

Requirement

get(): Returns an available number or -1.
check(num): Returns true if a number is available.
release(num): Makes a number available again.

Medium

Examples

Input: ["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output: [null, 0, 1, true, 2, false, null, true]

Approach 1

Level I: Boolean Array (Simple Scan)

Intuition

Use a boolean[] of size maxNumbers to track which numbers are used. For get, scan the array from the beginning to find the first false index. This is $O(N)$ for get and $O(1)$ for others.

⏱ Get: O(N), Check/Release: O(1).💾 O(N).

Detailed Dry Run

Array: [F, F, F]. Get() -> finds index 0, sets to T. Array: [T, F, F].

java

class PhoneDirectory {
    boolean[] used; int max;
    public PhoneDirectory(int max) { this.max = max; used = new boolean[max]; }
    public int get() {
        for(int i=0; i<max; i++) if(!used[i]) { used[i] = true; return i; }
        return -1;
    }
    public boolean check(int n) { return n >= 0 && n < max && !used[n]; }
    public void release(int n) { if(n >= 0 && n < max) used[n] = false; }
}

Approach 2

Level II: BitSet (Space Optimized)

Intuition

Use a BitSet to track availability. Finding the next available number is $O(N)$ in the bitset, but space is reduced dramatically.

⏱ Get: O(N), Check/Release: O(1).💾 O(N/64).

java

class PhoneDirectory {
    BitSet bs;
    public PhoneDirectory(int max) { bs = new BitSet(max); bs.set(0, max); }
    public int get() { int i = bs.nextSetBit(0); if(i != -1) bs.clear(i); return i; }
    public boolean check(int n) { return bs.get(n); }
    public void release(int n) { bs.set(n); }
}

Approach 3

Level III: Queue + HashSet

Intuition

Use a Queue to store available numbers (for $O(1)$ get) and a HashSet to store current available numbers (for $O(1)$ check). When release is called, add back to both if it wasn't already available.

⏱ O(1) for all operations.💾 O(N).

java

class PhoneDirectory {
    Queue<Integer> q = new LinkedList<>();
    Set<Integer> set = new HashSet<>();
    public PhoneDirectory(int max) {
        for (int i = 0; i < max; i++) { q.add(i); set.add(i); }
    }
    public int get() {
        if (q.isEmpty()) return -1;
        int res = q.poll(); set.remove(res); return res;
    }
    public boolean check(int n) { return set.contains(n); }
    public void release(int n) { if (set.add(n)) q.add(n); }
}

Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers $a_1, a_2, \dots, a_n$ , summarize the numbers seen so far as a list of disjoint intervals.

Requirement

addNum(val): Add integer to the stream.
getIntervals(): Return the summary as a list of intervals.

Hard

Examples

Input: addNum(1), getIntervals(), addNum(3), getIntervals(), addNum(2), getIntervals()
Output: [[1, 1]], [[1, 1], [3, 3]], [[1, 3]]

Approach 1

Level I: List of Numbers + Rebuild on Query

Intuition

Store all individual numbers in a Set to handle duplicates. For getIntervals, convert the set to a sorted list and iterate through it to form intervals whenever numbers are not consecutive.

⏱ Add: O(1), Get: O(N log N) for sorting.💾 O(N).

Detailed Dry Run

Input: 1, 3, 2. Set: {1, 2, 3}. Sorted: [1, 2, 3]. Intervals: [[1, 3]].

java

class SummaryRanges {
    Set<Integer> set = new HashSet<>();
    public void addNum(int val) { set.add(val); }
    public int[][] getIntervals() {
        if(set.isEmpty()) return new int[0][0];
        List<Integer> list = new ArrayList<>(set); Collections.sort(list);
        List<int[]> res = new ArrayList<>();
        int start = list.get(0), end = list.get(0);
        for(int i=1; i<list.size(); i++) {
            if(list.get(i) == end + 1) end = list.get(i);
            else { res.add(new int[]{start, end}); start = end = list.get(i); }
        }
        res.add(new int[]{start, end});
        return res.toArray(new int[0][]);
    }
}

Approach 2

Level II: Sorted List (Manual Merging)

Intuition

Maintain a list of disjoint intervals sorted by start time. For addNum, find the insertion spot and check if it can merge with neighbor intervals. This is $O(N)$ due to list shifting.

⏱ Add: O(N), Get: O(1).💾 O(N).

java

class SummaryRanges {
    List<int[]> intervals = new ArrayList<>();
    public void addNum(int val) { /* O(N) binary search + shift */ }
    public int[][] getIntervals() { return intervals.toArray(new int[0][]); }
}

Approach 3

Level III: Balanced BST / TreeMap

Intuition

Use a TreeMap to store intervals as start -> end. When a new number x is added, find the interval that ends just before it and the one that starts just after it. Merge them if possible.

⏱ Add: O(log N), Get: O(N).💾 O(N).

java

class SummaryRanges {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    public void addNum(int val) {
        Integer low = map.floorKey(val), high = map.ceilingKey(val);
        if (low != null && map.get(low) >= val) return;
        boolean mergeLow = (low != null && map.get(low) == val - 1);
        boolean mergeHigh = (high != null && high == val + 1);
        if (mergeLow && mergeHigh) {
            map.put(low, map.get(high)); map.remove(high);
        } else if (mergeLow) {
            map.put(low, val);
        } else if (mergeHigh) {
            map.put(val, map.get(high)); map.remove(high);
        } else map.put(val, val);
    }
    public int[][] getIntervals() {
        int[][] res = new int[map.size()][2]; int i = 0;
        for (int k : map.keySet()) res[i++] = new int[]{k, map.get(k)};
        return res;
    }
}

Range Sum Query 2D - Mutable

Given a 2D matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). The matrix is mutable, meaning its values can be updated.

Requirement

NumMatrix(matrix): Initializes the data structure.
update(row, col, val): Updates the value at (row, col) to val.
sumRegion(row1, col1, row2, col2): Returns the sum of elements within the specified rectangle.

Hard

Examples

Input: NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5]]), sumRegion(2,1,4,3), update(3,2,2), sumRegion(2,1,4,3)
Output: 8, 6

Approach 1

Level I: Row-wise Prefix Sums

Intuition

For each row, maintain a 1D prefix sum array. For sumRegion, iterate through each row in the range $[r1, r2]$ and compute the sum of that row's segment in $O(1)$ using the prefix sums. This makes update $O(N)$ and query $O(M)$ .

⏱ Update: O(N), Query: O(M).💾 O(M * N).

Detailed Dry Run

Matrix: [[1, 2], [3, 4]]. Row1 Prefix: [1, 3]. Row2 Prefix: [3, 7]. SumRegion(0,0,1,1) = (3-0) + (7-0) = 10.

java

class NumMatrix {
    int[][] rowPrefix; int[][] mat;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        mat = matrix; rowPrefix = new int[m][n + 1];
        for(int i=0; i<m; i++) for(int j=0; j<n; j++) rowPrefix[i][j+1] = rowPrefix[i][j] + matrix[i][j];
    }
    public void update(int r, int c, int val) {
        int delta = val - mat[r][c]; mat[r][c] = val;
        for(int j=c+1; j<rowPrefix[r].length; j++) rowPrefix[r][j] += delta;
    }
    public int sumRegion(int r1, int c1, int r2, int c2) {
        int sum = 0; for(int i=r1; i<=r2; i++) sum += rowPrefix[i][c2+1] - rowPrefix[i][c1];
        return sum;
    }
}

Approach 2

Level II: 2D Binary Indexed Tree (BIT)

Intuition

Extend the 1D BIT to 2D. Each node $(i, j)$ in the BIT stores a prefix sum. update and query both take $O(log M * log N)$ time.

⏱ Update: O(log M * log N), Query: O(log M * log N).💾 O(M * N).

java

class NumMatrix {
    int[][] tree, nums; int m, n;
    public NumMatrix(int[][] matrix) {
        m = matrix.length; n = matrix[0].length;
        tree = new int[m + 1][n + 1]; nums = new int[m][n];
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) update(i, j, matrix[i][j]);
    }
    public void update(int row, int col, int val) {
        int delta = val - nums[row][col]; nums[row][col] = val;
        for (int i = row + 1; i <= m; i += i & -i)
            for (int j = col + 1; j <= n; j += j & -j) tree[i][j] += delta;
    }
    public int sumRegion(int r1, int c1, int r2, int c2) {
        return query(r2 + 1, c2 + 1) - query(r1, c2 + 1) - query(r2 + 1, c1) + query(r1, c1);
    }
    private int query(int row, int col) {
        int sum = 0;
        for (int i = row; i > 0; i -= i & -i)
            for (int j = col; j > 0; j -= j & -j) sum += tree[i][j];
        return sum;
    }
}

Approach 3

Level III: 2D Segment Tree (Quadtree based)

Intuition

Build a segment tree where each node represents a rectangular region. update and query take $O(log M * log N)$ . Generally more powerful but harder to implement than BIT.

⏱ Update: O(log M * log N), Query: O(log M * log N).💾 O(M * N).

java

/* 2D Segment Tree code placeholder */

Snapshot Array

Implement a SnapshotArray that supports the following operations:

Requirement

SnapshotArray(length): Initializes an array-like data structure with the given length, where each element is initially 0.
set(index, val): Sets the element at the given index to be val.
snap(): Takes a snapshot of the array and returns the snap_id.
get(index, snap_id): Returns the value at the given index, corresponding to the given snap_id.

Medium

Examples

Input: SnapshotArray(3), set(0,5), snap(), set(0,6), get(0,0)
Output: [null,null,0,null,5]

Approach 1

Level I: Full Array Copy on Snap

Intuition

Every time snap() is called, we create a full copy of the current array and store it in a List<int[]>. This is $O(1)$ for set and get, but $O(N)$ for snap.

⏱ Set: O(1), Snap: O(N), Get: O(1).💾 O(N * S) where S is number of snaps.

Detailed Dry Run

Array: [0, 0]. Set(0, 5). Snap() -> Store [5, 0]. Set(0, 6). Snap() -> Store [6, 0]. Get(0, 0) -> return 5.

java

class SnapshotArray {
    int[] curr; List<int[]> snaps = new ArrayList<>();
    public SnapshotArray(int len) { curr = new int[len]; }
    public void set(int i, int v) { curr[i] = v; }
    public int snap() { snaps.add(curr.clone()); return snaps.size() - 1; }
    public int get(int i, int s) { return snaps.get(s)[i]; }
}

Approach 2

Level II: Versioned Map (HashMap per index)

Intuition

Use Map<Integer, Integer>[] arr. Each index has a map mapping snap_id -> value. This is simpler but takes more space for small changes.

⏱ Set: O(1), Snap: O(1), Get: O(log S) where S is number of snaps.💾 O(N + S * Updates).

java

class SnapshotArray {
    TreeMap<Integer, Integer>[] arr;
    int snapId = 0;
    public SnapshotArray(int len) {
        arr = new TreeMap[len];
        for (int i = 0; i < len; i++) { arr[i] = new TreeMap<>(); arr[i].put(0, 0); }
    }
    public void set(int i, int v) { arr[i].put(snapId, v); }
    public int snap() { return snapId++; }
    public int get(int i, int s) { return arr[i].floorEntry(s).getValue(); }
}

Approach 3

Level III: List of Lists (Binary Search Optimization)

Intuition

Each index stores a list of (snap_id, value) pairs. When get(index, snap_id) is called, perform a binary search (lower bound) on the list to find the value at or before that snap_id.

⏱ Set: O(1), Snap: O(1), Get: O(log S).💾 O(N + U) where U is number of set() calls.

java

class SnapshotArray {
    List<int[]>[] arr;
    int snapId = 0;
    public SnapshotArray(int length) {
        arr = new List[length];
        for (int i = 0; i < length; i++) {
            arr[i] = new ArrayList<>(); arr[i].add(new int[]{0, 0});
        }
    }
    public void set(int index, int val) {
        int[] last = arr[index].get(arr[index].size() - 1);
        if (last[0] == snapId) last[1] = val;
        else arr[index].add(new int[]{snapId, val});
    }
    public int snap() { return snapId++; }
    public int get(int index, int snap_id) {
        List<int[]> list = arr[index];
        int l = 0, r = list.size() - 1, res = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (list.get(mid)[0] <= snap_id) { res = list.get(mid)[1]; l = mid + 1; }
            else r = mid - 1;
        }
        return res;
    }
}

Design Bounded Blocking Queue

Implement a thread-safe bounded blocking queue. Submitting a task to a full queue should block the calling thread until a slot becomes available. Fetching a task from an empty queue should block the calling thread until a task becomes available.

Hard

Examples

Input: BoundedBlockingQueue(2), enqueue(1), enqueue(2), dequeue() (blocks if empty)
Output: 1

Approach 1

Level I: Synchronized Methods with wait/notify

Intuition

Use synchronized on enqueue and dequeue. Inside each, use a while loop to wait() if the condition (full or empty) isn't met, and notifyAll() after making a change. This is the classic Java threading building block.

⏱ O(1) excluding wait time.💾 O(Capacity).

Detailed Dry Run

Thread 1: Enqueue(1). Thread 2: Enqueue(2). Thread 3: Enqueue(3) -> waits (full). Thread 4: Dequeue() -> returns 1, signals threads.

java

class BoundedBlockingQueue {
    private Queue<Integer> q = new LinkedList<>();
    private int cap;
    public BoundedBlockingQueue(int capacity) { cap = capacity; }
    public synchronized void enqueue(int e) throws InterruptedException {
        while(q.size() == cap) wait();
        q.add(e); notifyAll();
    }
    public synchronized int dequeue() throws InterruptedException {
        while(q.isEmpty()) wait();
        int res = q.poll(); notifyAll(); return res;
    }
}

Approach 2

Level II: Semaphores

Intuition

Use Semaphore fill = new Semaphore(0) and Semaphore drain = new Semaphore(cap). enqueue calls drain.acquire() and fill.release(). dequeue does the reverse.

⏱ O(1) excluding wait time.💾 O(Capacity).

java

class BoundedBlockingQueue {
    Semaphore fill, drain; Queue<Integer> q = new LinkedList<>();
    public BoundedBlockingQueue(int cap) {
        fill = new Semaphore(0); drain = new Semaphore(cap);
    }
    public void enqueue(int el) throws InterruptedException {
        drain.acquire(); synchronized(q) { q.add(el); } fill.release();
    }
    public int dequeue() throws InterruptedException {
        fill.acquire(); int res; synchronized(q) { res = q.poll(); } drain.release();
        return res;
    }
}

Approach 3

Level III: Condition Variables (Producer-Consumer)

Intuition

Use a ReentrantLock with two Condition variables (e.g., notEmpty, notFull). Threads wait on these conditions when the queue is empty or at capacity, and signal each other when appropriate.

⏱ O(1) excluding wait time.💾 O(Capacity).

java

class BoundedBlockingQueue {
    private final Lock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();
    private final Queue<Integer> queue = new LinkedList<>();
    private final int capacity;
    public BoundedBlockingQueue(int capacity) { this.capacity = capacity; }
    public void enqueue(int element) throws InterruptedException {
        lock.lock();
        try {
            while (queue.size() == capacity) notFull.await();
            queue.add(element); notEmpty.signal();
        } finally { lock.unlock(); }
    }
    public int dequeue() throws InterruptedException {
        lock.lock();
        try {
            while (queue.isEmpty()) notEmpty.await();
            int element = queue.poll(); notFull.signal(); return element;
        } finally { lock.unlock(); }
    }
}

Design In-Memory File System

Design a data structure that represents an in-memory file system. Support ls, mkdir, addContentToFile, and readContentFromFile.

Hard

Examples

Input: mkdir("/a/b/c"), addContentToFile("/a/b/c/d", "hello"), ls("/a/b/c"), readContentFromFile("/a/b/c/d")
Output: ["d"], "hello"

Approach 1

Level I: Map of Full Paths

Intuition

Maintain a Map<String, String> where the key is the full path and the value is the content. For ls, iterate through keys to find children. This is simple but slow for deep trees.

⏱ Ls: O(PathCount), Mkdir: O(1).💾 O(TotalContentLength).

java

class FileSystem {
    Map<String, String> paths = new HashMap<>();
    public List<String> ls(String path) {
        Set<String> res = new TreeSet<>();
        if (paths.containsKey(path)) return Arrays.asList(path.substring(path.lastIndexOf('/')+1));
        for (String p : paths.keySet()) {
            if (p.startsWith(path + "/")) {
                String sub = p.substring(path.length() + (path.equals("/") ? 0 : 1));
                res.add(sub.split("/")[0]);
            }
        }
        return new ArrayList<>(res);
    }
    public void mkdir(String path) { if (!paths.containsKey(path)) paths.put(path, null); }
    public void addContentToFile(String path, String content) {
        paths.put(path, paths.getOrDefault(path, "") + content);
    }
    public String readContentFromFile(String path) { return paths.get(path); }
}

Approach 2

Level III: Trie-based Tree Structure

Intuition

Model the file system as a tree (Trie), where each node is either a directory or a file. Directories contain a Map<String, Node> of children. This allows for efficient path traversal.

⏱ Ls, Mkdir, Read, Write: O(PathLength).💾 O(Nodes * FileNamesLength).

java

class FileSystem {
    class Node { boolean isFile = false; TreeMap<String, Node> children = new TreeMap<>(); String content = ""; }
    Node root = new Node();
    public List<String> ls(String path) {
        Node curr = traverse(path);
        if (curr.isFile) return Arrays.asList(path.substring(path.lastIndexOf("/") + 1));
        return new ArrayList<>(curr.children.keySet());
    }
    public void mkdir(String path) { traverse(path); }
    public void addContentToFile(String path, String content) {
        Node curr = traverse(path); curr.isFile = true; curr.content += content;
    }
    public String readContentFromFile(String path) { return traverse(path).content; }
    private Node traverse(String path) {
        Node curr = root; String[] parts = path.split("/");
        for (String p : parts) {
            if (p.isEmpty()) continue;
            curr.children.putIfAbsent(p, new Node()); curr = curr.children.get(p);
        }
        return curr;
    }
}

Design Browser History

You have a browser of one tab where you start on a homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Medium

Approach 1

Level I: Two Stacks

Intuition

Maintain history and forward stacks. When visiting, clear forward stack.

⏱ O(1) all ops.💾 O(N).

Detailed Dry Run

Visit(A), Visit(B), Back(1) -> Back is at A.

java

import java.util.*;\nclass BrowserHistory {\n    private Stack<String> history = new Stack<>(), forward = new Stack<>();\n    public BrowserHistory(String homepage) { history.push(homepage); }\n    public void visit(String url) { history.push(url); forward.clear(); }\n    public String back(int steps) {\n        while(steps-- > 0 && history.size() > 1) forward.push(history.pop());\n        return history.peek();\n    }\n    public String forward(int steps) {\n        while(steps-- > 0 && !forward.isEmpty()) history.push(forward.pop());\n        return history.peek();\n    }\n}

Approach 2

Level III: Single Array with Pointer (Optimal)

Intuition

Use a single dynamic array (list) and an index pointer. Overwrite forward history on visit and simply move the index on back / forward.

⏱ O(1) average all ops.💾 O(N).

Detailed Dry Run

Index starts at 0. Visit moves it to 1. Back(1) moves it to 0.

java

import java.util.*;\nclass BrowserHistory {\n    private List<String> history = new ArrayList<>();\n    private int curr = 0, last = 0;\n    public BrowserHistory(String homepage) { history.add(homepage); }\n    public void visit(String url) {\n        curr++;\n        if(curr < history.size()) history.set(curr, url);\n        else history.add(url);\n        last = curr;\n    }\n    public String back(int steps) { curr = Math.max(0, curr - steps); return history.get(curr); }\n    public String forward(int steps) { curr = Math.min(last, curr + steps); return history.get(curr); }\n}

Design Food Rating System

Design a food rating system that can update ratings and return the highest-rated food for a specific cuisine.

Medium

Approach 1

Level III: Multi-Index with Sorted Sets (Optimal)

Intuition

Use two HashMaps: one to map food -> (cuisine, rating) and another to map cuisine -> SortedSet of (rating, food). SortedSet handles lexicographical tie-breaks.

⏱ Change Rating: O(log N), Highest Rated: O(1).💾 O(N).

Detailed Dry Run

Cuisine 'Japanese' has {Sushi: 5, Ramen: 4}. Update Ramen to 6 -> Highest Rated is now Ramen.

java

import java.util.*;\nclass FoodRatings {\n    class Food implements Comparable<Food> {\n        String name, cuisine; int rating;\n        Food(String n, String c, int r) { name=n; cuisine=c; rating=r; }\n        public int compareTo(Food other) {\n            if (rating != other.rating) return other.rating - rating;\n            return name.compareTo(other.name);\n        }\n    }\n    Map<String, Food> foodMap = new HashMap<>();\n    Map<String, TreeSet<Food>> cuisineMap = new HashMap<>();\n    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {\n        for(int i=0; i<foods.length; i++) {\n            Food f = new Food(foods[i], cuisines[i], ratings[i]);\n            foodMap.put(foods[i], f);\n            cuisineMap.computeIfAbsent(cuisines[i], k -> new TreeSet<>()).add(f);\n        }\n    }\n    public void changeRating(String food, int newRating) {\n        Food f = foodMap.get(food);\n        cuisineMap.get(f.cuisine).remove(f);\n        f.rating = newRating;\n        cuisineMap.get(f.cuisine).add(f);\n    }\n    public String highestRated(String cuisine) {\n        return cuisineMap.get(cuisine).first().name;\n    }\n}

Design Movie Rental System

Design a movie rental system that supports searching for available movies, renting, dropping off, and reporting the cheapest rented movies.

Hard

Approach 1

Level III: Multi-Index Sorted Sets (Optimal)

Intuition

Use multiple data structures to track state: available[movie] -> SortedSet(price, shop), rented -> SortedSet(price, shop, movie), and priceMap[shop, movie] -> price.

⏱ Search/Report: O(1) or O(K log N), Rent/Drop: O(log N).💾 O(N).

Detailed Dry Run

Rent movie 1 at shop 2. Move (price, shop, movie) from available to rented set.

java

import java.util.*;\nclass MovieRentingSystem {\n    class Movie implements Comparable<Movie> {\n        int shop, movie, price;\n        Movie(int s, int m, int p) { shop=s; movie=m; price=p; }\n        public int compareTo(Movie o) {\n            if(price != o.price) return price-o.price;\n            if(shop != o.shop) return shop-o.shop;\n            return movie-o.movie;\n        }\n    }\n    Map<Integer, TreeSet<Movie>> available = new HashMap<>();\n    TreeSet<Movie> rented = new TreeSet<>();\n    Map<String, Integer> priceMap = new HashMap<>();\n    public MovieRentingSystem(int n, int[][] entries) {\n        for(int[] e : entries) {\n            Movie m = new Movie(e[0], e[1], e[2]);\n            available.computeIfAbsent(e[1], k -> new TreeSet<>()).add(m);\n            priceMap.put(e[0]+","+e[1], e[2]);\n        }\n    }\n    public List<Integer> search(int movie) {\n        List<Integer> res = new ArrayList<>();\n        if(!available.containsKey(movie)) return res;\n        for(Movie m : available.get(movie)) { res.add(m.shop); if(res.size()==5) break; }\n        return res;\n    }\n    public void rent(int shop, int movie) {\n        int p = priceMap.get(shop+","+movie);\n        Movie m = new Movie(shop, movie, p);\n        available.get(movie).remove(m);\n        rented.add(m);\n    }\n    public void drop(int shop, int movie) {\n        int p = priceMap.get(shop+","+movie);\n        Movie m = new Movie(shop, movie, p);\n        rented.remove(m);\n        available.get(movie).add(m);\n    }\n    public List<List<Integer>> report() {\n        List<List<Integer>> res = new ArrayList<>();\n        for(Movie m : rented) { res.add(Arrays.asList(m.shop, m.movie)); if(res.size()==5) break; }\n        return res;\n    }\n}

← Previous TopicBit Manipulation

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.