Question: Buildings: [ [2,9,10], [3,7,15], [5,12,12] ] = [left, right, height]. Output key points: [ [2,10], [3,15], [7,12], [12,0] ]

Why L6: Tests sweep line + custom heap + edge cases. Used in computational geometry, CAD, Amazon Robotics path planning.

Core Idea: Process Events
Scan left to right. Only points where max height changes matter. Happens at building start/end.

Step 1: Convert to Events
Start: (x, -height). Negative so taller comes first if x same.
End: (x, height).
For [2,9,10]: events = (2,-10), (9,10)

Step 2: Sweep with MaxHeap
Sort events by x. Walk through. Keep MaxHeap of active heights.
On start: add height. On end: remove height. If max changed, record [x, newMax].

The Trap: Heap Remove is O(N)
Use SortedDictionary<int,int> as multiset. Key=height, Value=count. Max = Last().Key.

C# Code:

public IList<IList<int>> GetSkyline(int[][] buildings) {
    var events = new List<(int x, int h)>();
    foreach(var b in buildings) {
        events.Add((b[0], -b[2]));
        events.Add((b[1], b[2]));
    }
    events.Sort((a,b) => a.x == b.x? a.h.CompareTo(b.h) : a.x.CompareTo(b.x));
    
    var result = new List<IList<int>>();
    var active = new SortedDictionary<int,int>();
    active[0] = 1;
    int prevMax = 0;
    
    foreach(var (x,h) in events) {
        if(h < 0) {
            int height = -h;
            active[height] = active.GetValueOrDefault(height) + 1;
        } else {
            active[h]--;
            if(active[h] == 0) active.Remove(h);
        }
        int currMax = active.Last().Key;
        if(currMax!= prevMax) {
            result.Add(new List<int>{x, currMax});
            prevMax = currMax;
        }
    }
    return result;
}

Time: O(N log N). Space O(N).

L6 Follow-ups:
1. 1 billion buildings? External sort. Stream events. Heap = O(#overlapping buildings).
2. Why not PriorityQueue? PQ can't delete middle. Need SortedDict O(log N) remove.

Reject If: Brute force O(N²). Can't explain -height. Forget ground level 0.

Question: Design LFU Cache. get(key), put(key,val). Evict least frequent. If tie, evict LRU. All O(1).

Why LRU is Easy, LFU is Hard:
LRU: One doubly linked list. Move to head on access. Evict tail. O(1).
LFU: You need frequency buckets. Evict from minFreq bucket. When frequency changes, move node between buckets. How to do O(1)?

Data Structure - 3 HashMaps + LinkedLists:
1. keyToVal: Dictionary<int,int>
2. keyToFreq: Dictionary<int,int>
3. freqToKeys: Dictionary<int, LinkedHashSet<int>> - freq → ordered set
4. minFreq: int - tracks current min for O(1) eviction

Why LinkedHashSet? DLL + HashSet. Add() to tail. Remove() O(1). First() = LRU within freq bucket.

Code:

public class LFUCache {
    int capacity;
    int minFreq;
    Dictionary<int,int> keyToVal = new();
    Dictionary<int,int> keyToFreq = new();
    Dictionary<int, LinkedHashSet<int>> freqToKeys = new();

    public LFUCache(int capacity) { this.capacity = capacity; }

    public int Get(int key) {
        if(!keyToVal.ContainsKey(key)) return -1;
        int freq = keyToFreq[key];
        freqToKeys[freq].Remove(key);
        if(freqToKeys[freq].Count == 0) {
            freqToKeys.Remove(freq);
            if(minFreq == freq) minFreq++;
        }
        keyToFreq[key] = freq + 1;
        if(!freqToKeys.ContainsKey(freq + 1))
            freqToKeys[freq + 1] = new LinkedHashSet<int>();
        freqToKeys[freq + 1].Add(key);
        return keyToVal[key];
    }

    public void Put(int key, int value) {
        if(capacity == 0) return;
        if(keyToVal.ContainsKey(key)) {
            keyToVal[key] = value;
            Get(key);
            return;
        }
        if(keyToVal.Count == capacity) {
            int evictKey = freqToKeys[minFreq].First();
            freqToKeys[minFreq].Remove(evictKey);
            keyToVal.Remove(evictKey);
            keyToFreq.Remove(evictKey);
        }
        keyToVal[key] = value;
        keyToFreq[key] = 1;
        if(!freqToKeys.ContainsKey(1)) freqToKeys[1] = new LinkedHashSet<int>();
        freqToKeys[1].Add(key);
        minFreq = 1;
    }
}

Critical Edge Case: When incrementing ONLY key in minFreq bucket, must increment minFreq. 90% miss this.

L6 Follow-ups:
1. Thread-safe 1M QPS? ConcurrentDictionary + stripe locks per freq bucket. Or ReaderWriterLockSlim.
2. Frequency overflow? int.MaxValue accesses. Periodically divide all freq by 2. Or use long.
3. Why not PriorityQueue? PQ update is O(N). Need O(1) update. Heap doesn't work.

Reject If: Using SortedDictionary scan for LRU = O(N). Not understanding minFreq update.

Question: nums1=[1,3], nums2=[2]. Median = 2.0. Find in O(log(min(M,N))).

Insight: Partition
Median splits array into left half ≤ right half.
Partition A at i, B at j such that len(left) = (M+N+1)/2
Condition: maxLeftA ≤ minRightB && maxLeftB ≤ minRightA

Binary Search on Smaller Array:
j = (M+N+1)/2 - i ensures left total correct.

Code:

public double FindMedianSortedArrays(int[] A, int[] B) {
    if(A.Length > B.Length) return FindMedianSortedArrays(B, A);
    int m = A.Length, n = B.Length;
    int low = 0, high = m;
    
    while(low <= high) {
        int i = (low + high)/2;
        int j = (m + n + 1)/2 - i;
        
        int maxLeftA = i == 0? int.MinValue : A[i-1];
        int minRightA = i == m? int.MaxValue : A[i];
        int maxLeftB = j == 0? int.MinValue : B[j-1];
        int minRightB = j == n? int.MaxValue : B[j];
        
        if(maxLeftA <= minRightB && maxLeftB <= minRightA) {
            if((m + n) % 2 == 0) {
                return (Math.Max(maxLeftA, maxLeftB) + Math.Min(minRightA, minRightB)) / 2.0;
            } else {
                return Math.Max(maxLeftA, maxLeftB);
            }
        } else if(maxLeftA > minRightB) {
            high = i - 1;
        } else {
            low = i + 1;
        }
    }
    throw new ArgumentException();
}

Why int.Min/MaxValue: Handles edge partition at start/end.

L6 Follow-ups:
1. 1B elements each? O(log 1B) = 30 steps. Fits memory.
2. One array on disk? Binary search in-memory array. Only fetch O(log N) from disk.
3. kth element instead? Same idea. Partition so left has k elements.

Reject If: You merge arrays. Can't derive j = (M+N+1)/2 - i. Forget int.MinValue crashes on [1,2], [3,4].

Question: N-ary tree. Each node: int val; List<Node> children; Serialize to string, deserialize back. Handle 100M nodes without stack overflow.

Why Binary Tree Method Fails: Binary: "1,2,#,3,#,#". For N-ary, you don't know how many children. "#" per null child = waste.

Optimal Encoding: val + numChildren + children
Example: 1 [3,2,4] → "1,3,3,2,5,0,6,0,0,2,0,4,0"
Read: 1 has 3 children. First child 3 has 2: 5,6. 5 has 0, 6 has 0. Back: 2 has 0, 4 has 0.

Iterative Ser to Avoid Stack Overflow:

public class Codec {
    public string Serialize(Node root) {
        if(root == null) return "";
        var sb = new StringBuilder();
        var stack = new Stack<Node>();
        stack.Push(root);
        while(stack.Count > 0) {
            var node = stack.Pop();
            sb.Append(node.val).Append(',');
            sb.Append(node.children.Count).Append(',');
            for(int i = node.children.Count - 1; i >= 0; i--)
                stack.Push(node.children[i]);
        }
        return sb.ToString();
    }
    
    public Node Deserialize(string data) {
        if(string.IsNullOrEmpty(data)) return null;
        var q = new Queue<string>(data.Split(','));
        return Dfs(q);
    }
    
    private Node Dfs(Queue<string> q) {
        int val = int.Parse(q.Dequeue());
        int count = int.Parse(q.Dequeue());
        var node = new Node(val);
        for(int i = 0; i < count; i++)
            node.children.Add(Dfs(q));
        return node;
    }
}

Why Iterative Ser but Recursive Deser: Ser iterative avoids stack overflow for depth 100K. Deser recursive OK because we control recursion depth = tree depth. If depth > 10K, use iterative deser too.

For 100M Nodes - Binary Format:
String = 2 bytes/char. 100M * 10 chars = 2GB. OOM.
Use BinaryWriter: 8 bytes per node = 800MB. Stream to file.

using var bw = new BinaryWriter(File.OpenWrite("tree.bin"));
void WriteBinary(Node n) {
    bw.Write(n.val);
    bw.Write(n.children.Count);
    foreach(var c in n.children) WriteBinary(c);
}

L6 Follow-ups:
1. 10TB tree? Stream. Read 8 bytes, create node, read count, loop. Process one subtree at a time.
2. Query without full deser? Add index: offset of each node. Or B-tree layout on disk.
3. Tree is skewed 1M deep? Iterative only. Recursion crashes.

Reject If: Use "#" for null. Recursion for ser crashes at depth 50K. Can't calculate 100M * 8 = 800MB.

Question: begin="hit", end="cog", wordList=["hot","dot","dog","lot","log","cog"]
Return ALL shortest transformation sequences: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

Why Pure BFS/DFS Fail: BFS finds one shortest path. Stops when it finds cog, misses other paths at same level.
DFS explores hit→hot→dot→lot→log→cog which is longer. TLE. Need shortest length first.

L6 Solution: BFS Build Graph + DFS Backtrack
Step 1: BFS - Find shortest level + build parents[word]. Remove words per level to prevent cycles.
Step 2: DFS - Backtrack from end to start using parent map.

Code:

public IList<IList<string>> FindLadders(string beginWord, string endWord, IList<string> wordList) {
    var dict = new HashSet<string>(wordList);
    if(!dict.Contains(endWord)) return new List<IList<string>>();
    
    var result = new List<IList<string>>();
    var parents = new Dictionary<string, List<string>>();
    var currLevel = new HashSet<string>{beginWord};
    bool found = false;
    
    while(currLevel.Count > 0 &&!found) {
        foreach(var w in currLevel) dict.Remove(w);
        var nextLevel = new HashSet<string>();
        
        foreach(var word in currLevel) {
            var chars = word.ToCharArray();
            for(int i = 0; i < chars.Length; i++) {
                char old = chars[i];
                for(char c = 'a'; c <= 'z'; c++) {
                    chars[i] = c;
                    string newWord = new string(chars);
                    if(dict.Contains(newWord)) {
                        if(newWord == endWord) found = true;
                        nextLevel.Add(newWord);
                        if(!parents.ContainsKey(newWord)) parents[newWord] = new List<string>();
                        parents[newWord].Add(word);
                    }
                }
                chars[i] = old;
            }
        }
        currLevel = nextLevel;
    }
    
    if(found) {
        var path = new List<string>{endWord};
        Dfs(endWord, beginWord, parents, path, result);
    }
    return result;
}

void Dfs(string word, string beginWord, Dictionary<string,List<string>> parents, 
         List<string> path, List<IList<string>> result) {
    if(word == beginWord) {
        var list = new List<string>(path);
        list.Reverse();
        result.Add(list);
        return;
    }
    if(!parents.ContainsKey(word)) return;
    foreach(var p in parents[word]) {
        path.Add(p);
        Dfs(p, beginWord, parents, path, result);
        path.RemoveAt(path.Count - 1);
    }
}

Time: O(N * 26 * L * P) N=words, L=len, P=paths. BFS = O(N*26*L). DFS = O(P*L).

L6 Optimization: Bidirectional BFS
Search from begin + end. Meet in middle. O(b^(d/2)) vs O(b^d). For 5 levels, 26^5 vs 26^2.5.

Reject If: Pure DFS. Don't remove words per level and get cycles. Can't explain BFS+DFS combo.

Question: 2D elevation map. Water flows off edges. Calculate total trapped.
Example: [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] → 4

Why 1D Method Fails: 1D: water = min(maxLeft, maxRight) - height. In 2D, water can flow 4 directions. "Wall" is lowest boundary point.

Key Insight: Process from Boundary Inward
Water level determined by shortest "wall" surrounding cell. Start from all boundaries. Always process lowest boundary first using MinHeap. Why? Water can't exceed lowest wall.

Algorithm - Dijkstra on Height:
1. Push all boundary cells into MinHeap (height, row, col). Mark visited.
2. Pop lowest cell. For each unvisited neighbor:
- Water trapped = max(0, currentHeight - neighborHeight)
- Push neighbor with height = max(currentHeight, neighborHeight) because neighbor becomes new "wall"
3. Sum all water.

Code:

public int TrapRainWater(int[][] heightMap) {
    int m = heightMap.Length, n = heightMap[0].Length;
    if(m < 3 || n < 3) return 0;
    
    var visited = new bool[m,n];
    var pq = new PriorityQueue<(int r, int c, int h), int>();
    
    for(int i = 0; i < m; i++) {
        pq.Enqueue((i, 0, heightMap[i][0]), heightMap[i][0]);
        pq.Enqueue((i, n-1, heightMap[i][n-1]), heightMap[i][n-1]);
        visited[i,0] = visited[i,n-1] = true;
    }
    for(int j = 1; j < n-1; j++) {
        pq.Enqueue((0, j, heightMap[0][j]), heightMap[0][j]);
        pq.Enqueue((m-1, j, heightMap[m-1][j]), heightMap[m-1][j]);
        visited[0,j] = visited[m-1,j] = true;
    }
    
    int water = 0;
    int[][] dirs = {new[]{0,1}, new[]{1,0}, new[]{0,-1}, new[]{-1,0}};
    
    while(pq.Count > 0) {
        var (r,c,h) = pq.Dequeue();
        foreach(var d in dirs) {
            int nr = r + d[0], nc = c + d[1];
            if(nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr,nc]) continue;
            visited[nr,nc] = true;
            water += Math.Max(0, h - heightMap[nr][nc]);
            int newWall = Math.Max(h, heightMap[nr][nc]);
            pq.Enqueue((nr, nc, newWall), newWall);
        }
    }
    return water;
}

Time: O(MN log MN) Each cell pushed/popped once. Heap ops log(MN). Space O(MN).

L6 Follow-ups:
1. 100K x 100K map? 10B cells. Heap 80GB. Divide-and-conquer: split tiles, process boundaries, merge.
2. Why not DFS from each cell? DFS O(4^MN). MinHeap ensures we process bottleneck first.
3. Memory optimization? Don't store height in tuple. Read from heightMap. Tuple = (r,c) only.

Reject If: You try 1D method. Use DFS. Can't explain why heap. Forget visited = infinite loop.

Question: Implement isMatch(s, p). . matches any char. * matches zero or more of preceding element.
isMatch("aab", "c*a*b") → true. Because c* = 0 c, a* = 2 a.

Why Recursion Explodes: For "aaaaaaaaaaaaab", "a*a*a*a*a*a*a*a*a*a*c", recursion tries all combinations. 2^N paths. TLE.

DP State Definition:
dp[i][j] = does s[0..i) match p[0..j)? i,j are lengths, not indices.
Base: dp[0][0] = true, empty matches empty.
dp[0][j] = true if p[0..j) is like a*b*c*

Transition - The Hard Part:
If p[j-1]!= '*': Must match current char.
dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.')

If p[j-1] == '*': Two choices:
1. Zero occurrence: Ignore x*. Check dp[i][j-2]
2. One or more: If s[i-1] matches p[j-2], consume s[i-1] and stay at p[j]. Check dp[i-1][j]
dp[i][j] = dp[i][j-2] || (match(s[i-1], p[j-2]) && dp[i-1][j])

Code - Bottom Up DP:

public bool IsMatch(string s, string p) {
    int m = s.Length, n = p.Length;
    var dp = new bool[m+1, n+1];
    dp[0,0] = true;
    
    for(int j = 2; j <= n; j++)
        if(p[j-1] == '*') dp[0,j] = dp[0,j-2];
    
    for(int i = 1; i <= m; i++) {
        for(int j = 1; j <= n; j++) {
            if(p[j-1] == '*') {
                dp[i,j] = dp[i,j-2];
                if(Match(s[i-1], p[j-2]))
                    dp[i,j] |= dp[i-1,j];
            } else {
                dp[i,j] = Match(s[i-1], p[j-1]) && dp[i-1,j-1];
            }
        }
    }
    return dp[m,n];
}

bool Match(char sc, char pc) => pc == '.' || sc == pc;

Time/Space: O(MN). Can optimize space to O(N) since only need prev row.

L6 Follow-ups:
1. Pattern 1M long? Space O(N) optimization. Keep 2 rows. Or compile to NFA.
2. Wildcard * vs Regex *? Wildcard * = any sequence. Regex a* = zero or more a's only.
3. Add + operator? a+ = one or more. dp[i][j] = match && (dp[i-1][j-1] || dp[i-1][j])

Reject If: You use Regex.IsMatch. You write recursion. Can't derive dp[i][j-2] || dp[i-1][j] for star.

Question: Design AWS DynamoDB. Requirements: 10M reads/sec, 1M writes/sec. 99.999999999% durability. Multi-AZ. Single-digit ms latency.

Step 1: Calculate Scale - L6 Must Do Math
10M TPS. Each request 1KB. = 10GB/s network. 1M writes * 3 replicas = 3M writes/sec to disk.
Single SSD: 200K IOPS. Need 3M / 200K = 15 SSDs minimum. Add 3x for headroom = 45 SSDs.
Data: 100TB. 3x replication = 300TB. With 10TB SSD = 30 nodes min. With partitions = 1000+ nodes.

Step 2: Partitioning - Consistent Hashing
Ring 0-2^128. Partition = hash range. Each node owns N partitions.
Key: partitionKey → MD5 → position on ring. Request routes to owner node.
Hot partition? Split partition. Move half to new node. Dynamo does auto-split at 10GB or 3000 RCU/WCU.

Step 3: Replication - Quorum R+W > N
N=3 replicas across 3 AZs. Write: W=2. Read: R=2. R+W=4 > N=3 → strong consistency.
Dynamo default: Eventually consistent R=1. Strong consistent R=W=2, costs 2x RCU.

Step 4: Write Path - PutItem
1. Client → Request Router. Hash partitionKey → find partition + nodes.
2. Router → Coordinator node. Coordinator = first node in preference list.
3. Coordinator writes to local commit log, then replicates to W-1 replicas.
4. Wait for W acks. Return 200. Async replicate to remaining N-W.
5. Hinted Handoff: If replica down, coordinator writes to temp node. Delivers later.

Step 5: Read Repair + Anti-Entropy
Read R replicas. If versions differ, return latest, async repair old replicas.
Merkle trees: Compare hash trees between replicas. Only sync diffs. Runs in background.

Step 6: Cost Model - L6 Owns Budget
10M RCU * $0.25 per million = $2.5M/month. 1M WCU * $1.25 = $1.25M/month.
Storage 100TB * $0.25/GB = $25K/month. Total ~$4M/month.
If customer wants $1M: Use S3+Athena. Dynamo wrong choice. L6 says no.

L6 Follow-ups:
1. Hot partition celebrity user? Write sharding: partitionKey = userId#001 to userId#100. Read scatter-gather.
2. Cross-region? Global Tables. Multi-master. Last-writer-wins via timestamp. Conflicts = app responsibility.
3. Why not SQL? SQL join across 1000 nodes = O(N²) network. NoSQL denormalize. Single query = single partition.

Reject If: You say "add cache". You don't calculate partitions. You forget R+W>N. You ignore cost.

Question: Design Uber Eats. 1M DAU. 100K restaurants. 500K drivers. Match order to driver in <3 min.

Step 1: Geo-Indexing - GeoHash vs QuadTree
GeoHash: Encode lat/lon to string. 9q8yy = 1km box. Nearby = same prefix.
Problem: Edge cases. 9q8yy adjacent to 9q8yv but prefix differs.
Solution: Check 8 neighbors. Or use H3 hexagons. Uber uses H3.

Step 2: Matching Algorithm
1. Order placed → Find restaurants in GeoHash 3km.
2. Restaurant accepts → Find drivers in GeoHash 5km with status=online.
3. Rank drivers: score = -ETA - detour + driver_rating*10
4. Dispatch to top 3. First accept wins. Timeout 30s → next batch.

Step 3: ETA Calculation
Can't call Google Maps 1M times/sec. Precompute.
OSRM: Open Source Routing Machine. Load OSM data. Contraction hierarchies.
ETA = driving_time(restaurant→customer) + pickup_time. Cache ETA for 5 min.

Step 4: Real-time Location - Kafka + Redis
Driver app sends location every 4s → Kafka driver-location.
Consumer updates Redis Geo: GEOADD drivers 12.34 56.78 driver123
Matching: GEORADIUS drivers 12.34 56.78 5 km → O(log N + M) where M=matches.

Step 5: Surge Pricing - Demand vs Supply
Per H3 cell per 5min: demand = orders, supply = idle_drivers.
surge = min(3.0, demand / supply). If surge > 1.5, increase price, notify drivers.

L6 Follow-ups:
1. Driver GPS spoofing? Cross-check cell tower + WiFi. Ban if >100km jump.
2. Restaurant overwhelmed? Circuit breaker. If prep_time > 45min, hide restaurant.
3. How to handle 10x spike on SuperBowl? Pre-warm capacity. Auto-scale matching service. Pre-position drivers via ML forecast.

Reject If: You store all drivers in SQL and SELECT with distance formula. You don't mention GeoHash/H3. No surge logic.