Mock 6 — Full 90-Min Interview (90 min)

# Mock 6 — Full 90-Min Interview ## The brief Simulates a real 90-minute coding interview. Three problems of mixed difficulty. Goal: solve as many as possible, with optimal complexity, narrating throughout. ## Problem 1 — Valid Parentheses (Easy, ~10 min) Given a string of brackets `()`, `{}`, `[]`, determine if it's valid. ``` "()" → True "()[]{}" → True "(]" → False ``` ### Solution ```python def is_valid(s): stack = [] pairs = {')': '(', ']': '[', '}': '{'} for ch in s: if ch in '([{': stack.append(ch) elif ch in ')]}': if not stack or stack.pop() != pairs[ch]: return False return not stack ``` Stack-based matching. Edge case: stack must be empty at end. ## Problem 2 — Top K Frequent Elements (Medium, ~25 min) Given an array and k, return the k most frequent elements. ``` nums = [1,1,1,2,2,3], k = 2 → [1, 2] ``` ### Approach 1. Count frequencies with Counter. 2. Build heap of (negative_count, value) of size k, OR use bucket sort. ### Solution (heap) ```python from collections import Counter import heapq def top_k_frequent(nums, k): counts = Counter(nums) return heapq.nlargest(k, counts, key=counts.get) ``` O(N log K). ### Bucket-sort variant (O(N)) ```python def top_k_frequent_bucket(nums, k): counts = Counter(nums) buckets = [[] for _ in range(len(nums) + 1)] for val, cnt in counts.items(): buckets[cnt].append(val) result = [] for i in range(len(buckets) - 1, -1, -1): for v in buckets[i]: result.append(v) if len(result) == k: return result ``` Counts are bounded by N; bucket sort is O(N). ## Problem 3 — Trapping Rain Water (Hard, ~40 min) Given heights of bars, compute how much water can be trapped between them. ``` [0,1,0,2,1,0,1,3,2,1,2,1] → 6 units ``` ### Approach script 1. State: "Sum of water above each bar." 2. Brute: "For each bar, find max on left and max on right. Water at i = min(leftMax, rightMax) - height[i]. O(N²)." 3. Optimization 1 (precompute): "Precompute leftMax and rightMax arrays in two passes. O(N) time, O(N) space." 4. Optimization 2 (two pointers): "Maintain leftMax and rightMax as you walk from both ends. Move whichever side is smaller. O(N) time, O(1) space." ### Solution (two pointers) ```python def trap(height): if not height: return 0 left, right = 0, len(height) - 1 left_max = right_max = 0 water = 0 while left = left_max: left_max = height[left] else: water += left_max - height[left] left += 1 else: if height[right] >= right_max: right_max = height[right] else: water += right_max - height[right] right -= 1 return water ``` Subtle. If stuck, code the O(N) space version first; optimize after. ## Time management - 0:00-0:10 → Problem 1 - 0:10-0:35 → Problem 2 - 0:35-1:15 → Problem 3 - 1:15-1:30 → Buffer / cleanup / tests If you get stuck on problem 3, fall back to the brute force; don't lose points by leaving it blank. ## Self-rubric - [ ] Problem 1: solved < 10 min - [ ] Problem 2: O(N log K) or O(N) solution - [ ] Problem 3: at least the O(N) space solution; bonus for O(1) two-pointer - [ ] Narrated throughout (didn't go silent) - [ ] Tested each solution against the given examples - [ ] If stuck, articulated where and tried alternatives ## Deliverables - Solutions. - A `RETRO.md`: - Final score (problems fully solved). - Where you lost time. - Three things to drill more before the next mock. ## What you'll learn This mock simulates real interview conditions: - Mixed difficulty under time pressure. - The hard problem is meant to challenge — partial credit (brute → optimized) is valuable. - Narration matters: interviewers judge approach + communication, not just final code. - Pacing: don't sink all 90 min into problem 3 if 1 and 2 aren't solid. Real interviews are noisier than mocks (interviewer hints, follow-up questions). But the technical skill you're drilling here is the bottleneck.