29.2 · Linked lists, hash maps, trees, folders, logs and schedules
Problems built on pointers and recursion: reverse a list, design a hash map, read a tree from the side or the edge, walk folders, turn start/end events into timings, and find shared free time. Every program here was compiled and run.
Mental model. Draw the structure, name the invariant that each loop step keeps true, and test the empty case, one node and a skewed shape before you say it is done.
Lists, maps and trees
Pointer manipulation, designing a container and reading trees from different angles.
- Reverse a singly linked list in Swift, iteratively and recursively. What can go wrong with long lists?
Iteratively, walk the list with three references: prev (starts nil), cur and a saved next. For each node, remember its successor, point it back at prev, then… - Implement a hash map from scratch (get, set, remove), then extend it: what do you test and how does resizing work?
The core is an array of buckets; the key’s hash modulo the bucket count picks a bucket, and each bucket holds the entries that landed there (separate… - Given a binary search tree and a decimal target, find the value closest to the target. Why can you stop descending one side?
Use the search property: at each node compare the node’s distance to the target with the best so far, then go left if the target is smaller than the node’s… - Return the values you see when looking at a binary tree from its right side. How does a level-order walk give it, and what is the trap with a left-only branch?
The visible node at each depth is the last node of that level, so do a breadth-first traversal level by level and record the last value of each level. The… - Print the boundary of an N-ary tree counterclockwise: root, left edge, leaves left to right, right edge going up. How do you avoid printing a node twice?
Split the boundary into three disjoint parts and join them, so no node is printed twice. The left edge follows the first child down from the root and stops…
Files, logs and schedules
Recursion over folders, events turned into durations, and merged calendars.
- Recursively walk a folder tree to count files and bytes. Compare your own recursion with FileManager.enumerator, and name the hazards.
List a folder with contentsOfDirectory(at:includingPropertiesForKeys:), ask each item for .isDirectoryKey and .fileSizeKey, recurse into directories and add up… - Given function entry and exit events with timestamps, print the time spent in each function when it exits. How do you separate total time from self time, and handle recursion?
The events form a properly nested structure, so use a stack. On entry push the function name, its start time and a child total of 0. On exit pop the top: its… - Given two people’s busy intervals and working hours, find the time when both are free. How is it the merge-intervals problem in disguise?
“Both free” is “neither busy”, so combine both busy lists, sort by start, and merge overlapping ones (the sweep from the intervals question). The gaps between… - Find the longest run in a float array where adjacent chosen values differ by at most 1. Why must you ask “contiguous or may I skip elements?” first?
The wording hides two different problems, and asking is the first thing to do. If the run must be contiguous (a subarray), one pass suffices: extend the…