Hash Table (Mid)

Two Sum

Hashmap value → index

1. For each x, compute target - x

2. If exists in map → return indices

3. Else store x → i

   O(n)

Ransom Note

Char frequency count:

1. Count chars in magazine

2. For each char in ransomNote, decrement

3. If any count < 0 → false

   Can use array of size 26

Group Anagrams

Hash by normalized key:

1. Sort string OR use 26-char frequency tuple

2. Map key → list of strings

3. Return all groups

Insert Delete GetRandom O(1) (LC380)

Use array + hashmap

1. Map: value → index

2. Insert → append to array, store index

3. Remove → swap with last element, pop

4. Update hashmap

5. GetRandom → random index from array

   All ops O(1)

First Missing Positive (H)

Index placement trick:

1. While 1 <= x <= n and not in correct position → swap to x-1

2. After pass, first index i where nums[i] != i+1 → answer i+1

3. Else return n+1

   In-place, O(n)

LRU Cache

Hashmap + Doubly Linked List:

1. Map key → node

2. DLL keeps order (most recent at front)

3. Get → move node to front

4. Put → insert/update at front

5. If over capacity → remove tail

   All ops O(1)

All O(1) Data Structure (AllOne) (H)

Hashmap + Doubly Linked List of counts:

1. Map key → node (node stores count)

2. DLL stores buckets of same count

3. Inc/Dec → move key to next/prev count bucket

4. Remove empty buckets

5. Head = min, Tail = max

   All ops O(1)

Design and Implement LFU Cache (H)

Hashmap + frequency lists:

1. Map key → (value, freq)

2. Map freq → DLL of keys

3. Track minFreq

4. Get → increase freq, move key to next freq list

5. Put → if full, evict from minFreq list (LRU within same freq)

6. Insert new key with freq = 1

   All ops O(1)