Part IV
DSA for Interviews
The coding problems interviews keep asking, grouped by topic. Each topic opens with a primer: the technique, the words that point to it, a Swift template. Each problem gives starter code and tests to paste into Xcode or a playground, then — hidden until you have tried — the cue, the approach in plain words, a compiled and tested Swift solution, the Swift trap and the follow-ups. Blind 75 at its core, plus the problems German loops (Zalando, Sixt, Delivery Hero, N26) are documented asking.
Start here
Arrays and hashing
- Arrays and hashing — the idea8 minTrade memory for speed by remembering what you've already seen, so each question about the past costs one lookup instead of another pass.
- 1Contains Duplicate15 minGiven a list of whole numbers, say whether any value appears in it more than once.
- 2Valid Anagram15 minGiven two words, say whether the second uses exactly the same letters as the first, the same number of times each.
- 3Two Sum25 minGiven a list of whole numbers and a target, return the positions of the two numbers that add up to it.
- 4Group Anagrams25 minGiven a list of words, gather together the ones that are made of exactly the same letters.
- 5Top K Frequent Elements25 minGiven a list of numbers and a count k, return the k values that appear most often.
- 6Encode and Decode Strings25 minTurn a list of strings into one single string, and back again, so that the round trip always returns exactly the original list.
- 7Longest Consecutive Sequence25 minGiven an unsorted list of whole numbers, find how long the longest unbroken run of consecutive values is.
Prefix sums
- Prefix sums — the idea8 minKeep a running total as you walk an array, so the sum of any stretch becomes the difference of two numbers you already have.
- 8Product of Array Except Self25 minFor each position in a list of whole numbers, return the product of all the other numbers, without using division.
- 9Subarray Sum Equals K25 minGiven a list of whole numbers and a target, count how many unbroken stretches of the list add up to exactly that target.
- 10Continuous Subarray Sum25 minGiven a list of whole numbers and a number k, say whether some stretch of at least two neighbouring entries adds up to a multiple of k.
Two pointers
- Two pointers — the idea8 minTwo positions walking through one array, usually toward each other, so that every step rules something out for good.
- 11Valid Palindrome25 minDecide whether a sentence reads the same forwards and backwards once you ignore case, spaces and punctuation.
- 12Two Sum II — Input Array Is Sorted25 minGiven a list of whole numbers already in ascending order and a target, find the two entries that add up to it, using no extra memory.
- 133Sum25 minGiven a list of whole numbers, find every distinct set of three entries that adds up to zero.
- 14Container With Most Water25 minGiven a row of vertical walls, pick the two that hold the most water between them.
- 15Sort Colors25 minRearrange an array of 0s, 1s and 2s so equal values sit together, in place and in one pass.
- 16Trapping Rain Water30 minGiven the heights of a row of bars, work out how much rain stays caught between them after a storm.
Sliding window
- Sliding window — the idea8 minA stretch of consecutive elements that grows on the right and shrinks on the left, so every stretch worth checking is seen in one pass.
- 17Best Time to Buy and Sell Stock25 minGiven a share's price on each day, find the most you could make by buying once and selling once later.
- 18Longest Substring Without Repeating Characters25 minFind the length of the longest run of consecutive characters in a string where no character appears twice.
- 19Longest Repeating Character Replacement25 minChange at most k letters in a string so that the longest possible stretch of one repeated letter appears, and return its length.
- 20Minimum Window Substring25 minFind the shortest stretch of a text that contains every character of a second string, counting repeats.
Stack
- Stack — the idea8 minHow to spot a problem where the most recent unfinished thing is always the next one to deal with, and the two shapes the code takes.
- 21Valid Parentheses25 minDecide whether a string made only of round, square and curly brackets closes every bracket correctly.
- 22Min Stack25 minBuild a stack of integers that can also report its smallest element at any moment, with every operation in constant time.
- 23Evaluate Reverse Polish Notation25 minCompute the value of an arithmetic expression written with each operator after the two numbers it applies to.
- 24Daily Temperatures25 minFor each day in a list of temperatures, count how many days you'd wait for a strictly warmer one.
- 25Decode String25 minExpand a compressed string in which a number followed by text in square brackets means that text repeated, with repeats allowed inside repeats.
Binary search
- Binary search — the idea9 minHow to spot a problem where each check can rule out half of what's left, and the two loop shapes that cover almost every version of it.
- 26Binary Search25 minFind the position of a target number in a sorted list of distinct numbers, or report that it isn't there, without checking every entry.
- 27Search in Rotated Sorted Array25 minFind a target in a list of distinct numbers that was sorted and then shifted around in a circle, in logarithmic time.
- 28Find Minimum in Rotated Sorted Array25 minFind the smallest number in a list of distinct numbers that was sorted and then shifted around in a circle, in logarithmic time.
- 29Koko Eating Bananas25 minFind the slowest steady eating speed that still finishes every pile of bananas within a given number of hours.
- 30Time Based Key-Value Store25 minBuild a key-value store that keeps every value a key has had over time and answers what the value was at any given moment.
Linked list
- Linked list — the idea8 minHow to rewire a chain of nodes safely, the two helpers that remove most special cases, and the Swift details that make lists different from arrays.
- 31Reverse Linked List15 minTurn a chain of nodes around so the last node comes first, by changing the links rather than the values.
- 32Merge Two Sorted Lists15 minCombine two linked lists that are each in ascending order into one ascending list, reusing their nodes.
- 33Linked List Cycle15 minDecide whether following the links of a list from its first node ever leads back to a node already visited.
- 34Add Two Numbers25 minTwo whole numbers are stored as linked lists of digits, ones digit first; return their sum stored the same way.
- 35Reorder List25 minRearrange a linked list in place so that it alternates first, last, second, second-to-last, and so on toward the middle.
- 36Remove Nth Node From End of List25 minDelete the node that sits a given number of places from the end of a linked list, walking the list only once.
- 37LRU Cache30 minDesign a fixed-size key-value store where reads and writes are constant time and, when full, it drops the entry that was used longest ago.
Trees
- Trees — the idea10 minHow to walk a tree depth-first and level by level, what a binary search tree promises, and where Swift's recursion runs out of stack.
- 38Invert Binary Tree20 minTurn a binary tree into its mirror image, so every left branch becomes a right branch and the other way round.
- 39Maximum Depth of Binary Tree20 minCount how many levels a binary tree has, from the root down to its deepest leaf.
- 40Same Tree20 minDecide whether two binary trees have exactly the same shape and the same value in every matching position.
- 41Subtree of Another Tree25 minDecide whether a small binary tree appears inside a bigger one as a complete branch, every descendant included.
- 42Lowest Common Ancestor of a Binary Search Tree25 minIn a binary search tree, find the deepest node that has both of two given values somewhere below it or is one of them.
- 43Binary Tree Level Order Traversal25 minList a binary tree's values row by row, top to bottom and left to right, one list per row.
- 44Validate Binary Search Tree25 minDecide whether a binary tree keeps the search-tree ordering at every node, not just between parents and children.
- 45Kth Smallest Element in a BST25 minFind the value that would be in position k if all the values of a binary search tree were sorted.
- 46Lowest Common Ancestor of a Binary Tree25 minIn a binary tree with no ordering, find the deepest node that has both of two given nodes somewhere below it or is one of them.
- 47Construct Binary Tree from Preorder and Inorder Traversal25 minRebuild a binary tree from two listings of its values, one written root-first and one written left-to-right.
- 48Binary Tree Maximum Path Sum30 minFind the largest total you can collect along any path between two nodes of a binary tree whose values may be negative.
- 49Serialize and Deserialize Binary Tree30 minTurn a binary tree into a single string and back again, so that the rebuilt tree is identical to the original.
Tries
- Tries — the idea7 minA tree of letters in which words that start the same share a path, so prefix questions cost the length of the prefix, not the number of words.
- 50Implement Trie (Prefix Tree)25 minBuild a word store that can add words, say whether an exact word was added, and say whether any added word starts with a given beginning.
- 51Design Add and Search Words Data Structure25 minBuild a word store whose search accepts a dot as a stand-in for any single letter.
Heap
- Heap — the idea10 minA structure that always hands you the smallest (or largest) item it holds, cheaply, even while items keep arriving.
- 52Kth Largest Element in an Array25 minGiven a list of numbers and a position k, return the number that would sit kth from the top if the list were sorted from largest to smallest.
- 53K Closest Points to Origin25 minGiven points on a flat grid and a count k, return the k points that lie nearest to the centre (0, 0).
- 54Task Scheduler25 minGiven a list of labelled jobs and a rest period that must pass between two jobs with the same label, find the shortest total time to finish them all.
- 55Merge K Sorted Lists35 minGiven several linked lists that are each already in ascending order, join them into one ascending linked list.
- 56Find Median from Data Stream35 minBuild an object that accepts numbers one at a time and can report, after any of them, the middle value of everything it has received.
Backtracking
- Backtracking — the idea10 minBuild every possible answer one choice at a time, undoing the last choice to try the next one, and stop early on branches that can't work.
- 57Subsets25 minGiven a list of different numbers, return every possible selection of them, from picking none to picking all.
- 58Permutations25 minGiven a list of different numbers, return every order in which they can be arranged.
- 59Combination Sum25 minGiven a set of different positive numbers and a target, list every way to reach the target by adding numbers from the set, where each number may be used as often as you like.
- 60Word Search25 minGiven a grid of letters and a word, say whether the word can be traced through the grid by stepping between side-by-side cells without using any cell twice.
Graphs
- Graphs — the idea10 minHow to see a grid, a web of references or a list of dependencies as nodes and edges, and the three walks that answer almost every question about them.
- 61Number of Islands25 minCount the separate patches of land on a map of land and water cells, where land touches land only up, down, left and right.
- 62Clone Graph25 minGiven one node of a web of objects that point at each other, build a completely separate copy of the whole web with the same shape.
- 63Rotting Oranges25 minRot spreads each minute from bad oranges to the fresh ones beside them; find how many minutes until none are fresh, or say it never happens.
- 64Pacific Atlantic Water Flow25 minOn a height map bordered by two oceans, find every cell from which rain could run downhill into both of them.
- 65Course Schedule25 minAn app is split into numbered modules, some of which must be built before others; decide whether every module can be built at all.
Intervals
- Intervals — the idea8 minHow to handle lists of start-and-end pairs — merging, inserting, trimming and counting overlaps — by sorting them first and sweeping once.
- 66Insert Interval25 minAdd one new range to a sorted list of separate ranges, joining it with any it overlaps, and keep the list sorted and separate.
- 67Merge Intervals25 minGiven ranges in any order, join every group that overlaps into one range and return the result sorted.
- 68Non-overlapping Intervals25 minRemove as few ranges as possible from a list so that the ones left never overlap, and return how many you removed.
- 69Meeting Rooms II25 minGiven a day's meetings as start and end times, find the smallest number of rooms that lets every meeting happen.
Greedy
- Greedy — the idea8 minHow to solve a problem in one pass by making the choice that looks best right now and never revisiting it, and how to tell when that is safe.
- 70Maximum Subarray25 minFind the largest total you can get by adding up a run of consecutive numbers from a list that may contain negatives.
- 71Jump Game20 minStanding on the first square of a row, where each square says how far you may jump from it, decide whether you can land on the last square.
1-D dynamic programming
- 1-D dynamic programming — the idea10 minAnswer a big question by answering a row of smaller copies of it, each one once, and building on the ones already answered.
- 72Climbing Stairs15 minCount the different orders of one-step and two-step moves that take you up a staircase of n steps.
- 73House Robber20 minPick amounts from a row of houses to collect the largest total, never taking from two houses next to each other.
- 74House Robber II20 minPick amounts from houses arranged in a circle to collect the largest total, never taking from two neighbours, where the first and last houses are neighbours too.
- 75Coin Change25 minGiven coin values you can use as often as you like, find the fewest coins that add up to an amount exactly, or report that no combination does.
- 76Maximum Product Subarray25 minFind the largest product you can get by multiplying a run of neighbouring numbers in an array that may hold negatives and zeros.
- 77Word Break25 minDecide whether a string with no spaces can be cut into pieces that are all words from a given list.
- 78Decode Ways25 minCount how many ways a string of digits can be read back as letters when A is 1, B is 2, and so on up to Z as 26.
- 79Longest Increasing Subsequence25 minFind how many numbers you can keep from an array, in their original order, so that each kept number is strictly bigger than the one before.
- 80Longest Palindromic Substring25 minReturn the longest run of consecutive characters in a string that reads the same forwards and backwards.
- 81Palindromic Substrings20 minCount how many runs of consecutive characters in a string read the same forwards and backwards, counting each position separately.
2-D dynamic programming
- 2-D dynamic programming — the idea8 minWhen one position isn't enough to describe a smaller question, describe it with two — a row and a column, or a place in each of two strings — and fill a grid of answers.
- 82Unique Paths20 minCount the routes from the top-left corner of a grid to the bottom-right corner when every move goes one square right or one square down.
- 83Longest Common Subsequence25 minFind how many characters two strings can share in the same order, when each string may skip characters freely.
Matrix
- Matrix — the idea8 minTreat a grid of numbers as rows of rows, walk it by row and column, and change it in place without a second copy.
- 84Set Matrix Zeroes25 minWherever a grid holds a 0, wipe that cell's whole row and whole column to 0, changing the grid you were given and using almost no extra memory.
- 85Spiral Matrix25 minRead every value of a rectangular grid in the order you meet them walking clockwise around its edge and then inward, ring by ring.
- 86Rotate Image25 minTurn a square grid of numbers a quarter turn clockwise, changing the grid you were given instead of building a new one.
Bit manipulation
- Bit manipulation — the idea10 minRead a whole number as the row of 1s and 0s the machine stores, and answer questions about it with a few operators that work on all those digits at once.
- 87Number of 1 Bits15 minGiven a non-negative whole number, say how many of the digits in its binary form are 1.
- 88Counting Bits15 minFor every whole number from 0 up to n, report how many 1s its binary form contains, in one list.
- 89Missing Number15 minA list holds all but one of the whole numbers from 0 to its own length, each at most once; find the one that isn't there.