Live Coding Round in Swift

Big O describes how an algorithm's running time or memory grows with the input size n, keeping only the fastest-growing term and dropping constants. In a coding round you state both, as in "O(n) time, O(n) extra space", because a faster solution often pays with memory. The ladder: O(1) for an index or a hash lookup, O(log n) for halving the range (binary search), O(n) for one pass, O(n log n) for a good sort, O(n²) for a loop inside a loop over the same data, O(2ⁿ) for trying every subset How to count: steps in sequence add and the biggest wins, so a sort followed by a pass is O(n log n); nested loops multiply; two independent inputs keep two letters: O(n + m), O(n · m) Library calls are not free: contains, firstIndex(of:), removeFirst() and String.count are O(n) each, so one of them inside a loop turns the loop into O(n²) Space: count what you allocate (a Set of seen values is O(n)) and the recursion depth: a recursive walk of a tree of height h holds h stack frames Average, worst, amortized: a Dictionary lookup is O(1) on average and O(n) in the worst case; append is amortized O(1) because the array occasionally moves into a buffer twice as big; say which one you mean In the round: name the brute force and its cost first, then the better solution and what it trades for the speed

Instead of comparing every element with every other one, remember what you have already seen in a hash-based Set or Dictionary. A lookup there is O(1) on average, so one pass over the input is enough, paid for with O(n) extra memory. Duplicates: seen.insert(x).inserted is false when x was already there, so the first false is the answer; Set(xs).count != xs.count is the one-liner, but it always builds the whole set Anagrams: count characters into [Character: Int] with counts[c, default: 0] += 1, then count them down for the second string; a.sorted() == b.sorted() is shorter but O(n log n) Two-sum: for each x, look up target - x in a value → index dictionary before inserting x, so an element never pairs with itself and [3, 3] with target 6 still works **Character is one visible character**: it compares by canonical equivalence, so an é typed as one scalar and as e plus a combining accent count as the same character; iterate the string with for c in s, never by integer index The worst case: O(n) per lookup needs many keys with colliding hashes; Swift seeds Hasher randomly per process, so crafted input cannot force it On sorted input: two pointers solve two-sum with O(1) extra memory

An Array already is a stack: append pushes and popLast() pops, both O(1). A queue also needs O(1) at the front, and removeFirst() shifts every remaining element down, so draining n items that way costs O(n²) in total. Pop safely: popLast() returns nil on an empty array, while removeLast() traps with "Can't remove last element from an empty collection"; in a live task the optional is the safer call Why the front is slow: an Array is one contiguous buffer whose first element sits at index 0, so removing it moves everything after it; insert(_:at: 0) costs the same Two-stack queue: push onto inbox; when outbox is empty, move all of inbox into it reversed and pop from its end. Each element is moved once, so dequeue is amortized O(1). Head index: alternatively, keep reading from a head index and compact the array once most of it has been consumed Library: the standard library has no queue; Deque from Apple's swift-collections package (import DequeModule) is a ring buffer with O(1) at both ends Typical tasks: a stack for brackets, undo, "next greater element" and iterative DFS; a queue for BFS and level-order traversal

A stack: push every opening bracket, and on a closing one pop and check that it is the matching opener. The string is balanced only if no check failed and the stack is empty at the end. One pass: O(n) time, O(n) memory in the worst case. Counting is not enough: one counter per bracket type accepts "([)]", where every count matches but the nesting is wrong; only a stack sees the order A closer with nothing open: in "())" the third character finds an empty stack; popLast() returns nil, which never equals the opener, so the function returns false instead of trapping as removeLast() would Leftover openers: "((" passes every step, and only the final isEmpty check rejects it Empty string: balanced; say it out loud, it is the first edge case the interviewer tries Other characters: in "f(x[0])" decide whether to skip them or reject the input; the code skips them The replace loop: deleting "()", "[]" and "{}" until nothing changes also works, but every pass copies the string: O(n²)

Walk both arrays with two indices, append the smaller of the two current elements and advance that index; when one array runs out, append the rest of the other. Every element is read once: O(n + m) time, plus O(n + m) for the result. Edge cases: one or both arrays empty, very different lengths, equal values in both arrays, every element of one array smaller than every element of the other Ties: <= takes the element from the first array, which keeps the merge stable; it matters when you merge records by a key rather than plain numbers The tail: result += a[i...] appends whatever is left in one call; when i == a.count the slice is simply empty, so no extra check is needed **reserveCapacity: the final size is known, so the result allocates once instead of growing several times; the Big O stays the same In place**: the LeetCode version hands you nums1 with spare room at the end; fill it from the back, largest first, so nothing unread is overwritten, with O(1) extra memory **Why not (a + b).sorted()**: it is the O((n + m) log(n + m)) baseline to mention; Swift's timsort-style sort happens to find the two sorted runs and only merge them, but the task checks that you can write the merge yourself

Extend Sequence, loop with for-in and build the result. Generic parameters (T, Result) let the output type differ from the element type, and a throws closure with a rethrows method means callers write try only when the closure they pass can throw. **Why Sequence, not Array**: the methods then work for Set, Dictionary, ranges and String too; Element is the protocol's associated type, so it needs no declaration Generics: myMap<T> turns [String] into [Int]; myReduce<Result> lets the accumulator be anything: a sum, a string, a dictionary **rethrows**: the method throws only if its closure does, so ["a"].myMap { $0.count } needs no try, exactly like the standard map Non-escaping by default: the closure runs only during the call, so it needs no @escaping, its context can stay on the stack, and callers need no [weak self] **reserveCapacity(underestimatedCount)**: saves regrowing the result; underestimatedCount is a lower bound, 0 for many sequences, so it is only a hint What the standard library does now: since Swift 6, map is declared with typed throws (throws(E)), so a closure that throws only ParseError keeps that type for catch; reduce still uses rethrows **reduce(into:)**: the variant that passes the accumulator inout does not copy a dictionary or array accumulator on every step

They replace the hand-written "look up, insert if missing, append" loop: Dictionary(grouping:by:) buckets elements by a key you compute, reduce(into:) folds into one dictionary that you mutate in place, and uniquingKeysWith: merges the values of repeated keys. Group anagrams: the key is what all anagrams share, the sorted letters: String(word.sorted()), O(k log k) per word of length k. Inside each group the words keep their input order. Output order: a Dictionary iterates in an order that changes between launches, because Swift seeds its hashing per process; sort the groups if the result must be deterministic, for example in a test **reduce(into:)**: the accumulator is inout, so counts[word, default: 0] += 1 updates one dictionary in place, O(n) for n words **The plain reduce trap**: its closure receives the accumulator as an immutable value, so to change it you copy it, and copy-on-write then duplicates the whole dictionary on every step: O(n²). On 40,000 words that took about 2 seconds in a Release build, against 2 ms with reduce(into:). **uniquingKeysWith: +**: builds the counts from (word, 1) pairs in one call; Dictionary(uniqueKeysWithValues:) instead traps on the first repeated key with "Duplicate values for key" **The default: subscript**: reads a missing key as 0 and writes the sum back during the same lookup, so there is no if let and no second hashing

s.index(s.startIndex, offsetBy: k) walks the string from the start on every call, because a Character can span several bytes, so the loop is O(n²): billions of steps for 100,000 characters, about 9 seconds in a Release build on a Mac. Move two String.Index values instead. Why there is no jump: a String.Index is a position in the UTF-8 storage, and "🇰🇿" or an é written with a combining accent is one Character but several bytes, so finding the k-th character means reading all the ones before it; even s.count is a full pass The fix: start at startIndex and index(before: endIndex), and step with formIndex(after:) and formIndex(before:); each step reads one character from where the index already is, so the whole check is O(n), about 1 ms here Shorter, also O(n): s.elementsEqual(s.reversed()); reversed() on a String is a lazy view, so nothing is copied When you need random access: let chars = Array(s) costs one pass and O(n) memory, and then chars[i] is O(1) Not the bytes: comparing s.utf8 from both ends is fast but wrong for any non-ASCII text: "éé" is a palindrome, its UTF-8 bytes are not How to catch it: a test with a 100,000-character input; unit tests on ten-letter words pass with both versions

sort() is a modified timsort: O(n log n) in the worst case, near O(n) on mostly sorted input, and documented as stable, so equal elements keep their order. For several keys, write one comparator that compares the primary key and falls back to the next only on a tie. How it works: it finds runs that are already sorted (reversing descending ones), extends short runs with insertion sort and merges neighbouring runs through a buffer of up to n/2 elements, so it needs O(n) extra memory; before Swift 5 it was an introsort, which is not stable **sort() and sorted()**: sort() reorders a var array in place; sorted() returns a new array from any Sequence, a Set included The comparator is a strict "goes before": return true only when the first argument must come strictly before the second; <= breaks the strict weak ordering the documentation requires, and the result is then unspecified Several keys: compare the primary key and return if it differs, otherwise compare the next; the tuple form (b.score, a.name) < (a.score, b.name) packs the same rule into one line, because tuples of up to six Comparable elements compare left to right Names people see: < compares Unicode scalar values, not the locale's alphabet, so "Zoe" < "adam"; localizedStandardCompare(_:) sorts the way Finder does, ignoring case and putting file2 before file10 Foundation: sort(using:) with KeyPathComparators (iOS 15+) spells the keys out declaratively

Sort the slots by start, then sweep once: if a slot starts before the last merged slot ends, extend that one to the later of the two ends, otherwise start a new slot. Sorting costs O(n log n) and dominates the O(n) sweep. Whether touching slots merge depends on whether the ends are inclusive. Why sort first: after sorting, a slot can only overlap the last merged slot, never an earlier one, so one comparison per slot is enough; without sorting you compare every pair, O(n²) Touching slots are a question to ask: for meetings from 9 to 10 and from 10 to 11, half-open ranges fit better, and (9..<10).overlaps(10..<11) is false; closed ranges share the endpoint, so (1...3).overlaps(3...5) is true. The comparison is <= for closed slots and < for half-open ones. Keep the later end: in [1...10, 2...3] the result stays 1...10; taking the new slot's end instead shrinks it, the classic bug Edge cases: an empty list, a single slot, unsorted input, a slot nested inside another, everything collapsing into one Follow-ups: inserting one new slot into a list that is already merged is O(n) with no new sort; "how many rooms do these meetings need" sorts the starts and the ends separately and counts the overlap with two pointers Memory: O(n) for the sorted copy and the result

Both replace the nested loop with indices that only move forward. Two pointers close in on a sorted array from both ends; a sliding window keeps a contiguous range, growing its right edge and moving its left edge past whatever made the window invalid. Each index crosses the input once: O(n). Two pointers: on sorted input, a sum that is too small can only grow by moving the left index up, and one that is too big only shrinks by moving the right index down; the same shape removes duplicates in place, reverses an array and checks a palindrome Sliding window: fits "the longest or shortest contiguous subarray or substring such that…"; keep the window's state (a last-seen map, a count, a running sum) up to date as the edges move, instead of recomputing it Why O(n): left and right each go from 0 to n at most once, so there are at most 2n moves, although the code has a branch inside the loop **The prev >= left check**: a character last seen before the window starts is not a repeat inside it; without the check left jumps backwards on "abba" and the function returns 3 instead of 2 Swift strings: enumerated() gives offsets, which is all this arithmetic needs; to return the substring itself, keep String.Index values or work on Array(s), because a String has no integer subscript When it does not work: unsorted input for two-sum (sort it first, or use a dictionary) and a window over values that can be negative, where shrinking no longer helps; prefix sums handle that case

It mixes two conventions: hi = a.count is a half-open bound, but lo <= hi treats it as closed, so an empty array reads a[0] and traps; and when a[mid] is too small, lo = mid keeps mid in range, so once mid == lo nothing changes and the loop spins forever. Pick one invariant and keep it: half-open is the common choice: the answer lies in lo..<hi, the loop runs while lo < hi, and each branch either sets lo = mid + 1 (mid is ruled out) or hi = mid (mid stays a candidate); every iteration shrinks the range, and mid is always a valid index Which inputs show it: [] traps with "Index out of range"; in [1, 3, 5] a search for 4 or 7 hangs; a target that is present, or smaller than every element, returns correctly, which is why a quick test passes Overflow: Swift traps on integer overflow instead of wrapping, so (lo + hi) / 2 crashes when you search a numeric range near Int.max, as in "find the first bad version"; lo + (hi - lo) / 2 never overflows Lower bound, not equality: the fixed loop finds the first index whose element is not less than the target, so one function answers "is it there", "where would it be inserted" and "where do the duplicates start" Library: the standard library has no binary search; firstIndex(of:) is a linear scan, and partitioningIndex(where:) from swift-algorithms is the O(log n) version Cost: O(log n), about 20 comparisons for a million elements

Walk the list once, saving node.next before pointing it back at prev: O(n) time, O(1) memory. Freeing a long Node list is safe since Swift 5.7, which releases a chain of next links in a loop, but a deep tree or an indirect enum list still frees recursively and can crash. Order of the moves: save next, flip the link, advance; overwrite node.next first and the rest of the list loses its last strong reference, so ARC frees it on the spot Recursive reverse: shorter, but one stack frame per node, so a long list overflows your own call stack Why freeing used to crash: destroying an object releases its stored properties, so releasing the head released the second node inside the same call, and so on, one nested call per node; the classic fix was an owner whose deinit unlinks the nodes in a loop What Swift 5.7 changed: when a class has a stored property of its own type, the compiler generates a deinit that walks that chain in a loop; lists of millions of nodes free without a crash, whether the node class is final, open or generic What it does not cover: two links of the node's type (left and right), children kept in an array, and indirect enum cases. A tree that degenerated into a chain of about 7,000 levels already overflowed a 1 MB stack, the size of the iOS main thread, in a Release build. The fix there: tear the structure down in the owner's deinit with an explicit stack, detaching each node's children before letting the node go, as in the code

Depth-first goes down one branch before backing up, through recursion or an explicit stack; breadth-first visits the tree level by level. Max depth is a natural DFS: a node's depth is one more than its deeper subtree. Level order is BFS by definition. Three DFS orders: pre-order (node, left, right) to copy or serialize a tree; in-order (left, node, right) yields a BST's values sorted, which is how you validate a BST or find its k-th smallest; post-order (children first) for heights, sizes and bottom-up sums BFS without a slow queue: hold one level in an array and collect the next level into a second one; there is no removeFirst(), and the level boundaries come for free Picking one: BFS reaches the shallowest nodes first, so "minimum depth" or "the nearest node with X" can stop at the first match, while DFS has to visit everything; DFS holds O(h) nodes for a tree of height h, BFS up to the widest level Recursion depth: a balanced tree is about log₂ n deep, so recursion is fine; a BST built from sorted keys is a linked list in disguise, and recursing 100,000 levels overflows the stack, which is what the explicit-stack in-order is for Validating a BST: pass the allowed range down (min < node.val < max) or check that the in-order walk strictly increases; comparing a node only with its own children is the classic wrong answer Cost: every traversal visits each node once: O(n) time

A Dictionary from key to node finds an entry in O(1), and a doubly linked list keeps the nodes in order of use, so moving a node to the front and dropping the last one are O(1) pointer updates. A dictionary alone has no order, and an array of keys makes every touch O(n). **get is a write**: a hit moves the node to the front, so even reads change the cache; behind an actor or a lock, get needs exclusive access too **put: replace or insert at the front; past capacity, unlink the last node and remove it from the dictionary, which is why every node stores its own key Sentinels**: a dummy head and tail remove every nil check at the two ends of the list ARC: prev is weak; with two strong links every pair of neighbours is a retain cycle, and the nodes leak when the cache is gone Why not the shortcuts: Swift has no LinkedHashMap; OrderedDictionary from swift-collections keeps order, but removing a key from the middle is O(n) **NSCache is not LRU**: it evicts in an undocumented order, mostly under memory pressure, and countLimit is not a strict limit; use it for memory-sensitive caches, and this structure when the eviction order is the requirement Capacity: decide what 0 means; the code clamps it to 1

It is DP when the answer is built from answers to smaller versions of the same problem, and a plain recursion would solve the same subproblem many times. Write the recursion, cache it by its state (memoization), then fill the same states in a loop from the smallest up (bottom-up). How to spot it The task asks for a number of ways, a minimum or maximum, the longest something, or whether a target is reachable, and each choice leaves a smaller problem of the same shape: an index, an amount left, a cell of a grid Draw the recursion tree for a small input: the same arguments appear in several branches; with no repeats it is divide and conquer, like merge sort, and a memo buys nothing From recursion to a table Name the state and say the recurrence first: here best(i) is the most money from houses 0...i, and best(i) = max(best(i - 1), best(i - 2) + nums[i]); interviewers want to hear that before any code Memoization: the same recursion plus a cache keyed by the state; cost = number of states × work per state, here O(n) instead of O(2ⁿ). A nested function can capture and update a local memo. Bottom-up: the same states in increasing order, with no recursion and no stack-depth limit; the memo version is still n frames deep on its first call, which overflows the stack for large n Shrink the table: when a cell reads only the last one or two cells, keep two variables instead: O(1) memory Swift traps Int.max as "impossible" traps on the next + 1, because Swift arithmetic checks for overflow; use nil or a bound such as amount + 1 for i in 2...n traps with "Range requires lowerBound <= upperBound" when n < 2; iterate indices or pad the table Dense states 0..<n belong in an array, which skips hashing; a two-dimensional state goes into a flat array indexed by row * cols + col, or into a Hashable struct used as the key

Count the words into a dictionary in one O(n) pass, then pick the top k of the u distinct words: sort them all (O(u log u)), keep a min-heap of k entries (O(u log k)), or bucket them by count (O(n + u)). Swift has no heap built in: write a small one or use Heap from swift-collections. Counting split(whereSeparator: { !$0.isLetter }) returns Substrings that share the text's storage, so counting allocates no strings; convert only the k winners with String(_:) Lowercase the whole text once, not each word, so "The" and "the" count together The dictionary takes O(u) memory, which for natural text is far smaller than the text itself Picking the top k Sort: counts.sorted { $0.value > $1.value }.prefix(k) is the simplest and is fine for a few hundred thousand distinct words; say it first Min-heap of size k: the root is the weakest of the current top k, so one comparison rejects most words; a stronger word replaces the root and sifts down in O(log k). It has to be a min-heap: a max-heap finds the top k only after holding every word. Buckets: a count is at most n, so an array of word lists indexed by count, read from the top until k words are collected, gives O(n + u) Quickselect: O(u) on average, but O(u²) in the worst case, and it reorders the data in place Ties at the cut-off: add the word itself as a second key so the result is deterministic When the text does not fit in memory Stream it, send each word to one of several files by its hash so the same word always lands in the same file, count each file separately and merge the per-file top k lists. That is map-reduce at a small scale.

Treat the modules as a directed graph and run Kahn's algorithm: count each module's unbuilt dependencies, start with the modules at zero, and every time one is "built", decrement its dependents and add any that reach zero. Modules left over at the end sit on a cycle or depend on one. Cost: O(V + E): each module becomes ready once, and each dependency edge is decremented once Report the cycle, not just "cycle": the leftovers are the modules still waiting; to name the loop itself, follow their remaining edges from one leftover until a module repeats, and print Profile → Checkout → Profile DFS alternative: three states per module (not visited, on the current path, done); reaching a module on the current path is a cycle, while reaching a done one is just a shared dependency, a diamond. Emitting each module after its dependencies yields the build order directly. Determinism: Swift seeds hashing per process, so iterating a Dictionary visits keys in a different order on every launch; sort the keys, as the code does, so the same input always gives the same order in tests and builds Parallel builds: all modules that are ready at the same moment can build at once; processing the ready set wave by wave gives the build waves, and the longest chain sets the minimum build time Edge cases: a module that appears only as a dependency, a module that depends on itself (stuck forever, so it is reported), duplicate edges (counted and decremented twice, which still works), an empty graph