29.1 · Arrays, strings and hashing: the warm-up problems, solved in Swift
Short problems that open many loops: pairs in an array, merging ranges, digit-by-digit arithmetic, permutations, brackets, splitting a string, sliding windows and an Array extension. Each one has the idea, the Swift version that was run, and the edge cases interviewers check.
Mental model. Say the brute force first, name what it repeats, and replace the repeated work with a dictionary, a sort or a moving window. Then walk the edge cases out loud (empty, one element, duplicates, negatives).
Hashing and sorting
Find pairs and merge ranges by remembering what you have seen, or by sorting first.
- Two-sum: given an array and a target, return the indices of two elements that add up to it. How do you get from O(n²) to O(n), and which edge cases do you test?
The brute force checks every pair, O(n²) time. The repeated work is “is there a partner for this element?”, and a dictionary answers that in O(1): walk the… - Merge overlapping intervals: [[1,3],[8,10],[2,6],[15,18]] becomes [[1,6],[8,10],[15,18]]. How do you do it, and when do touching intervals count as overlapping?
Sort by start, then sweep once. Keep an output list; for each interval, if its start is at or before the end of the last output interval they overlap, so… - Write an Array extension that removes every element that appears in a second array. What is the complexity, and what if the elements are only Equatable?
The naive version calls other.contains($0) inside filter: O(n × m). When Element: Hashable, build a Set(other) once (O(m)) and filter with O(1) lookups: O(n +…
Strings and digits
Work on characters, carries and brackets without converting to numbers.
- Add two non-negative numbers given as decimal strings, without converting them to integers. Why can you not just use Int, and how does the carry loop work?
Numbers longer than 19 digits overflow Int (and 15 or so digits lose precision in Double), which is the point of the exercise: do it the way you did at school.… - Given a string with brackets, remove the fewest parentheses to make it valid. How do you count them, and how do you build the fixed string?
Scan left to right keeping an open counter. An opening bracket increments it; a closing bracket with open > 0 pairs up and decrements; a closing bracket with… - Can a string be built by concatenating words from a list (words may repeat)? How do you answer yes or no, and how do you also return which words?
A recursive “try every first word” search repeats the same suffixes exponentially often. Make it dynamic programming over prefixes: reach[i] means the first i…
Orderings and windows
Permutations and moving windows.
- Next permutation: rearrange an array into the next lexicographically greater order, in place. Walk through the algorithm.
Three steps, O(n) time and O(1) memory. (1) Scan from the right for the first position i where a[i] < a[i+1]; everything to its right is in descending order… - When do you use a sliding window, and how do the fixed-size and variable-size versions differ?
Use a sliding window when the question is about a contiguous run of an array or string (a subarray or substring) and you can update an answer for the run in…