Mock 1 — Arrays, Strings, Hashmaps (45 min)

# Mock 1 — Arrays, Strings, Hashmaps ## The brief Three problems. 45 minutes total. Goal: solve all three with optimal complexity and narrate your thinking. ## Problem 1 — Two Sum (Easy, ~10 min) Given an array of integers `nums` and an integer `target`, return indices of the two numbers that sum to `target`. Exactly one solution exists; you can't use the same element twice. ``` Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] # 2 + 7 = 9 ``` ### Approach script 1. State the problem back: "Given array and target, find indices of pair summing to target." 2. Brute force: "Nested loops — O(N²)." 3. Optimization: "I'll use a hashmap: as I scan, check if the complement (target - current) is already seen. If yes, return both indices. O(N) time, O(N) space." 4. Code it. 5. Test with the example. 6. Discuss edge cases: duplicate target = 2 * num, empty array, etc. ### Solution ```python def two_sum(nums, target): seen = {} for i, x in enumerate(nums): if target - x in seen: return [seen[target - x], i] seen[x] = i return [] ``` ## Problem 2 — Longest Substring Without Repeating Characters (Medium, ~15 min) Given a string `s`, find the length of the longest substring without repeating characters. ``` Input: "abcabcbb" Output: 3 # "abc" Input: "bbbbb" Output: 1 # "b" ``` ### Approach script 1. State: "Find longest run of distinct chars." 2. Brute: "For each starting position, expand while distinct — O(N²)." 3. Optimization: "Sliding window. Expand right; when we see a duplicate, shrink left past the previous occurrence. Use hashmap of char → last index. O(N) time, O(min(N, alphabet)) space." 4. Code it. 5. Test "abcabcbb" → trace through. ### Solution ```python def length_of_longest_substring(s): last = {} start = 0 best = 0 for i, ch in enumerate(s): if ch in last and last[ch] >= start: start = last[ch] + 1 last[ch] = i best = max(best, i - start + 1) return best ``` ## Problem 3 — Group Anagrams (Medium, ~15 min) Given a list of strings, group anagrams together. ``` Input: ["eat","tea","tan","ate","nat","bat"] Output: [["eat","tea","ate"],["tan","nat"],["bat"]] ``` ### Approach script 1. State: "Group strings by anagram class." 2. Insight: "Two strings are anagrams iff their sorted forms are identical." 3. Plan: "For each string, compute a key (sorted tuple). Group by key in a hashmap. Return values." 4. Complexity: "O(N · K log K) where K is max string length. O(N · K) space." 5. Code it. 6. Discuss alternative key: char frequency tuple — same complexity, different implementation. ### Solution ```python from collections import defaultdict def group_anagrams(strs): groups = defaultdict(list) for s in strs: key = tuple(sorted(s)) groups[key].append(s) return list(groups.values()) ``` ## Self-rubric - [ ] All 3 solved correctly - [ ] Optimal complexity for each - [ ] Narrated approach BEFORE coding - [ ] Tested with examples - [ ] Discussed at least one edge case per problem - [ ] Total time ≤ 45 min ## Deliverables - Your solutions (Python or any language). - A `NOTES.md` with: - Where you got stuck and how you recovered. - Two things you'd practice more based on this mock.