Interview Prep
Problems modelled on what technical interviews ask. Solve them in JavaScript, TypeScript, Python or SQL.
Difficulty
Topics
Language
solve(s) — convert a valid Roman numeral (1..3999) to an integer. The symbols are I=1 V=5 X=10 L=50 C=100 D=500 M=1000. Symbols are normally written largest to smallest and added, except in six subtractive cases (IV=4 IX=9 XL=40 XC=90 CD=400 CM=900) where a smaller symbol before a larger one is subtracted. Scan left to right: when a symbol is smaller than the one after it, subtract it, otherwise add it. Examples
solve(s) — return true if s can be built by repeating a shorter substring two or more times ("abab" is "ab" twice). Trying every divisor of the length is fine, but the failure table of KMP answers it in one pass: let n = s.length and b = lps[n - 1] (the longest border of the whole string). The string is periodic exactly when b > 0 and n is divisible by n - b (the length of the smallest period). Examples
solve(strs) — return the longest string that is a prefix of every string in strs (non-empty array), or "" if there is none. Take the first string as the candidate prefix and shrink it until each other string starts with it. Or compare column by column: the prefix ends at the first index where any string is shorter or disagrees with the first one. Either way is O(total characters). Examples
solve(s, t) — two strings of the same length are isomorphic if the characters of s can be replaced to get t, with a one-to-one mapping: every character of s always maps to the same character of t, and two different characters of s never map to the same character. One map is not enough: "ab" → "aa" is a valid function but not a valid bijection. Keep two maps (s → t and t → s), or compare the index of each character's first occurrence. Examples
Replace a positive integer by the sum of the squares of its digits, and repeat. If the process reaches 1 the number is happy; otherwise it loops forever in a cycle that never contains 1. solve(n) — return true when n (1 <= n < 2^31) is happy. The sequence cannot grow without bound (a 10-digit number maps to at most 810), so it either reaches 1 or repeats a value. Detect the repeat with a Set of seen values, or in O(1) space with Floyd's slow / fast pointers on the "next number" function. Examples
solve(columnNumber) — convert a positive column number (1 <= columnNumber < 2^31) to its spreadsheet title: 1 → "A", 26 → "Z", 27 → "AA", 28 → "AB", 702 → "ZZ", 703 → "AAA". It looks like base 26, but it is bijective: there is no digit for zero (A is 1, Z is 26). The usual n % 26 loop breaks on multiples of 26. The fix is to shift by one before each division: take the letter for (n - 1) % 26, then continue with floor((n - 1) / 26). Examples
solve(nums) — every value of nums appears twice except one, which appears once. Return that value in O(n) time and O(1) extra space — no Set, no counting map. XOR (^) is the tool: x ^ x = 0, x ^ 0 = x, and XOR is commutative and associative. XOR every value together and each pair cancels itself, leaving the single one. Examples
solve(n) — treat n (0 <= n < 2^32) as an unsigned 32-bit integer, reverse the order of its 32 bits and return the result, also as an unsigned number. Peel the lowest bit of n off with n & 1, push it onto the result with a left shift, and shift n right. Do it exactly 32 times, even if n runs out of ones early — the leading zeros of n become trailing zeros of the result. In JavaScript use >>> 0 (and >>> for the shifts) to stay unsigned. Examples
solve(n) — n is a 32-bit signed integer (-2^31 <= n < 2^31). Return true when n is a power of two (1, 2, 4, 8, …). Zero and negative numbers are not. No loops, no division, no logarithm: a single expression is enough. A power of two has exactly one set bit. n & (n - 1) clears the lowest set bit, so it is 0 only when there was a single one. Examples
solve(nums) — nums holds n distinct numbers taken from the range 0..n, so exactly one number of that range is missing. Return it in O(n) time and O(1) space. Two classic solutions: the sum n(n+1)/2 minus the sum of nums, or XOR. With XOR, combine every index 0..n with every value: each number present appears twice and cancels, and the missing one appears only as an index. Examples
solve(n) — return an array ans of length n + 1 where ans[i] is the number of 1 bits in i, for every 0 <= i <= n. Counting each number separately is O(n log n); do it in O(n) with dynamic programming. Shifting right drops the last bit: i >> 1 is a smaller number whose answer you already know, and the dropped bit is i & 1. So ans[i] = ans[i >> 1] + (i & 1). Examples
solve(n) — n is an integer with 0 <= n < 2^31. Return the number of 1 bits in its binary representation (its Hamming weight). Looping over all 31 bits works. Brian Kernighan's trick is faster: n & (n - 1) clears the lowest set bit, so the loop runs once per 1 bit instead of once per bit. Examples
solve(values) builds a singly linked list from values, reverses it by re-pointing the next links, and returns the values of the reversed list as an array. Do not copy the values into an array and reverse that — the point is to rewire the nodes in O(n) time and O(1) extra space. Walk the list with three references: prev (already reversed), cur (being processed) and next (saved before you overwrite cur.next). Examples
solve(values) builds a singly linked list from values and returns true when it reads the same forwards and backwards. An empty list is a palindrome. Copying the values into an array is O(n) space. Do better by combining two earlier ideas: find the middle with slow / fast pointers, reverse the second half in place, then walk the first half and the reversed second half together comparing values. Examples
solve(values) builds a singly linked list from values and returns the values from the middle node to the end, as an array. With two middle nodes (an even length) the second one is the middle. An empty list returns []. You are not allowed to measure the length first: find the middle in a single pass with a slow and a fast pointer. When the fast pointer (two steps at a time) falls off the end, the slow pointer (one step at a time) is exactly halfway. Examples
solve(nums) — nums is sorted in non-decreasing order and may contain negative numbers. Return the squares of every value, also sorted in non-decreasing order. Sorting the squares works in O(n log n), but the input order gives you more: the largest square is always at one of the two ends. Walk two pointers inward and fill the result from the back in O(n). Examples
solve(nums1, m, nums2, n) — nums1 has length m + n: its first m values are sorted and the last n slots are padding (zeros). nums2 holds n sorted values. Merge nums2 into nums1 so that nums1 is sorted, and return nums1. Fill nums1 from the back: the largest remaining value always belongs at the end, and writing there never overwrites a value you still need. Examples
solve(arr) — arr is a mountain: it has at least 3 values, strictly increases up to a single peak, then strictly decreases. Return the index of the peak. Run in O(log n) — a scan for the maximum is not the point. Look at the slope at mid: if arr[mid] < arr[mid + 1] you are still climbing, so the peak is to the right; otherwise it is at mid or to its left. Examples
solve(x) — return the square root of the non-negative integer x, rounded down to an integer. Do not use Math.sqrt, *0.5 or any built-in root: binary search the answer instead. You are not searching an array, you are searching the range 0..x for the largest r with r r <= x. The predicate "r * r is small enough" is true then false, which is exactly what binary search needs. Examples
solve(nums, target) — nums is sorted ascending with distinct values. Return the index of target if it is present, otherwise the index where it would have to be inserted to keep the array sorted. Run in O(log n). This is the lower bound: the first index whose value is >= target. Almost every binary-search variant is a lower bound in disguise, so write it with a half-open range [lo, hi) and never return early. Examples
solve(nums) — nums has a majority element: a value that appears more than n / 2 times. It is guaranteed to exist. Return it. Three solutions, three complexities — pick the best: | Approach | Time | Extra space | |---|---|---| | Count with a hash map | O(n) | O(n) | | Sort and take the middle | O(n log n) | O(1) or O(n) | | Boyer–Moore voting | O(n) | O(1) | Boyer–Moore keeps a candidate and a count. A matching value adds a vote, a different one cancels a vote, and when the count hits zero the next value becomes the candidate. The majority element outnumbers all the others combined, so it survives every cancellation. Examples
solve(nums) — you start on the first index; nums[i] is the maximum number of steps you can jump forward from index i. Return true if you can reach the last index. No search is needed: sweep left to right while tracking the farthest index reachable so far. If you ever stand on an index beyond that frontier, you are stuck. Examples
solve(grid) — a robot starts at the top-left cell of a grid and wants to reach the bottom-right cell. It can only move right or down. Cells with 1 are obstacles and cannot be entered; cells with 0 are open. Return the number of distinct paths. The number of ways to reach a cell is the sum of the ways to reach the cell above it and the cell on its left (or 0 if the cell is an obstacle). Only the previous row is needed, so a single array of size cols is enough. Examples
solve(grid) — grid holds non-negative numbers. Starting at the top-left cell, move only right or down to reach the bottom-right cell. Return the smallest possible sum of the numbers along a path (both end cells included). best[r][c] = grid[r][c] + min(best[r-1][c], best[r][c-1]) — each cell is reached from above or from the left, so the cheapest path to it extends the cheaper of the two. Examples
solve(s) — return how many substrings of s are palindromes. Substrings with different positions count separately, even when their text is identical. Same idea as the longest palindromic substring, but every successful expansion step adds one more palindrome to the count. Examples
solve(grid) — grid contains 1 (land) and 0 (water). An island is a group of land cells connected 4-directionally. Return the area (number of cells) of the largest island, or 0 if there is none. This is the sibling of graph-number-of-islands: same traversal, but the traversal returns a size instead of just marking cells. Examples
A grid of colors is a graph in disguise: each cell is a node connected to its 4 neighbours (up, down, left, right — not diagonals). solve(image, sr, sc, color) — starting at cell (sr, sc), recolor that cell and every cell connected to it through cells of the same original color. Return the new image; do not mutate the input. Examples If the new color equals the original one, return early — otherwise a naive search never marks anything as visited and loops forever.
Return true when a binary tree is a mirror of itself around its center: the left subtree must be the mirror image of the right subtree, in both shape and values. solve(levelOrder) receives the tree serialized level by level (null = no child); a builder is provided. Examples Hint on the shape of the answer: write a helper that compares two nodes at once, recursing on (a.left, b.right) and (a.right, b.left).
solve(levelOrder, target) — return true if the tree has a root-to-leaf path whose values add up to target. A leaf is a node with no children, so a path must end on a leaf: stopping at an inner node does not count. Examples Values can be negative, so you cannot prune a branch just because the running sum went past the target.
solve(levelOrder) receives a binary tree serialized level by level, with null for a missing child. A helper that builds the tree is already provided. Return the tree's maximum depth: the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0. This is the "hello world" of tree recursion: the answer for a node is built from the answers for its two subtrees. Examples
Mirror a binary tree: at every node, swap the left and right children. solve(levelOrder) builds the tree from a level-order array, inverts it and returns it serialized again with the provided toLevelOrder helper. Examples Swapping only the root's children is the classic mistake — the swap has to happen all the way down.
solve(levelOrder, p, q) — in a binary search tree with unique values, return the value of the lowest common ancestor of p and q. A node is a descendant of itself, and both values are guaranteed to be in the tree. Unlike a general binary tree, the ordering tells you where to go. No recursion is needed: walk down from the root in O(h) time and O(1) space. Examples (tree [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5])
solve(nums) receives a sorted array of unique numbers. Build a height-balanced binary search tree from it and return it serialized level by level with the provided toLevelOrder helper. To make the answer unique, use this rule: for the range lo..hi (inclusive) the root is the element at index Math.floor((lo + hi) / 2) — the lower middle when the range has an even length. Build the left subtree from the elements before it and the right subtree from the elements after it. Examples
Given an array temps of daily temperatures, return an array answer where answer[i] is the number of days you have to wait after day i to get a warmer temperature. If there is no warmer day, answer[i] is 0. The brute force (scan forward from every day) is O(n²). Get it to O(n) with a stack of indices whose temperatures are still waiting for a warmer day. Examples Constraints 1 <= temps.length <= 100000 "Warmer" means strictly greater — an equal temperature does not count.
Implement solve(a, b, op) where a and b are lists of values and op is one of: "union" → elements in a or b (or both) "intersection" → elements in both a and b "difference" → elements in a but not in b "symmetric_difference" → elements in a or b but not both Return the result as a sorted list (so the output is deterministic). Examples solve([1,2,3], [2,3,4], "union") → [1, 2, 3, 4] solve([1,2,3], [2,3,4], "intersection") → [2, 3] solve([1,2,3], [2,3,4], "difference") → [1] solve([1,2,3], [2,3,4], "symmetric_difference") → [1, 4]
Implement solve(str) that returns true when every opening bracket in str is closed by the correct matching bracket in the correct order, and false otherwise. Supported pairs: () [] {} Non-bracket characters are ignored. Examples Approach Use a stack: push each opening bracket; on a closing bracket, pop and verify the match. Return true only if the stack is empty at the end. Constraints Input may contain any Unicode characters; only ()[]{} matter. Do NOT use a counter — counters cannot detect interleaved mismatches like ([)].
A load balancer in front of servers with different capacities. Plain weighted round robin sends bursts to the heavy server (a a a a a b c); the smooth variant used by nginx spreads the picks out (a a b a c a a). solve(args, ops) builds new WeightedBalancer(servers) — args = [servers] where servers is a list of [name, weight] pairs in priority order — and replays ops: next() — return the name of the next server. Algorithm: every server has a current value starting at 0. On each call: add each server's weight to its current; pick the server with the largest current (on a tie, the one listed first); subtract the total weight of all servers from the picked server's current. Example — [["a",5],["b",1],["c",1]], seven calls to next():
A Merkle tree summarises a large data set in one root hash and lets you prove that a single item belongs to it with only O(log n) hashes. Git, Cassandra's anti-entropy repair and blockchains all rely on it. solve(args, ops) builds new MerkleTree(leaves) — args = [leaves], a non-empty list of strings — and replays ops: root() — the root hash. proof(index) — the proof for leaf index: a list of [siblingHash, side] pairs from the leaf level up to just below the root. side is "L" if the sibling sits on the left of the running hash, "R" if on the right. verify(leaf, proof, root) — true if hashing leaf and then combining it with each sibling of proof in order gives root. update(index, leaf) — replace a leaf, rebuild and return the new root. Construction (pinned). hash(text) is the 32-bit FNV-1a of the UTF-8 bytes (start 2166136261; per byte h ^= byte; h = h * 16777619 mod 2^32) written as 8 lowercase hex digits. A leaf node is hash(leaf). Each level pairs neighbours, and a parent is hash(leftHex + rightHex) — the concatenation of the two hex strings. If a level has an odd number of nodes, its last node is duplicated (paired with itself). Repeat until one node is left. Example — leaves = ["a","b","c"]
Scores go up and down, and the product needs "top K" and "my rank" at any time. solve(args, ops) builds new Leaderboard() and replays ops: add(player, delta) — add delta (may be negative) to the player's score; an unknown player starts at 0. Returns the player's new score. top(k) — return the ids of the k best players, best first. Fewer players than k is fine. rank(player) — the 1-based position of the player, or -1 for an unknown player. reset(player) — remove the player from the board. Returns nothing. Ordering is pinned: higher score first; on equal scores the smaller player id (plain string comparison) comes first. Players with equal scores therefore do not share a rank. A sort on every query is acceptable here. In production you would keep a sorted structure (balanced tree, skip list or Redis sorted set) so top and rank are O(log n) — be ready to say so. Example
Model a tiny file system as a tree of directories and files. solve(args, ops) builds new FileSystem() (an empty root /) and replays ops. Paths are absolute, start with / and use / as the separator; names contain no slash. ls(path) — if path is a directory, return the names of its entries (files and directories) in lexicographic order; if it is a file, return an array holding just the file's name. mkdir(path) — create the directory, including any missing parents. Nothing happens if it already exists. Returns nothing. addcontent(path, content) — create the file if needed (with any missing parent directories) and append content to it. Returns nothing. read(path) — return the full content of the file. Only valid operations are tested (no listing of a missing path, no reading a directory). Example
Type a few characters and get the three most popular completions — Google's search box in miniature. solve(args, ops) builds new Autocomplete(sentences, times) — args = [sentences, times]; times[i] is how many times sentences[i] has already been searched — and replays ops: input(c) — the user typed one character c: if c is "#", the sentence typed so far is submitted: add one to its count (create it with count 1 if new), reset the typed text and return []; otherwise append c to the typed text and return the top 3 known sentences that start with it, as an array. Ordering is pinned: higher count first; ties are sorted ascending by plain ASCII order of the whole sentence (so a space sorts before any letter). Return fewer than 3 if fewer match. Scanning every sentence per keystroke is fine here. At scale you would keep a trie whose nodes cache their best suggestions. Example — sentences = ["i love you","island","iroman","i love leetcode"], times = [5,3,2,2]
solve(s, numRows) — write s in a zigzag pattern on numRows rows, going down then diagonally up, then read the rows one after another. With "PAYPALISHIRING" on 3 rows: the answer is "PAHNAPLSIIGYIR". Do not draw the grid: keep one string per row, and move a row index down until it hits the last row, then up until it hits row 0, flipping direction at the edges. With a single row (or at least as many rows as characters) the string is unchanged. Examples
solve(s) — s is made of lowercase letters. Return true if it is a palindrome, or can become one after deleting at most one character. Walk two pointers inward from both ends. While the characters match, keep going. On the first mismatch you have exactly one chance: the answer is true if either s[left+1..right] or s[left..right-1] is a plain palindrome (skip the left character, or skip the right one). Checking both is O(n) overall. Examples
solve(s) — compress s by replacing every run of the same character with the character followed by the run length, but omit the length when it is 1. A run of 12 is written as the character then 12 (two digits). Return the compressed string. The compressed string is not replaced by the original when it is longer. Scan with two indices: start marks the beginning of the current run, and i walks to the end of it. When the character changes (or the string ends), emit the character and, if the run is longer than 1, its length. Examples
solve(path) — path is an absolute Unix-style path starting with /. Return its canonical form: one slash between directory names, no trailing slash (except for the root "/"); . means the current directory and is dropped; .. goes up one level (and does nothing at the root); several consecutive slashes count as one; any other name, including ..., is a normal directory name. Split on /, then process the pieces with a stack: ignore empty pieces and ., pop on .. (if the stack is not empty), push everything else. Join the stack back with /. Examples
solve(s) — a word is a run of non-space characters. Return the words of s in reverse order, joined by a single space, with no leading or trailing spaces. The input may contain leading, trailing or repeated spaces, which must not appear in the output. A string with no words returns "". The interview follow-up is to do it in place on a character array: reverse the whole string, then reverse each word back. Here, any correct approach is accepted — but be able to explain both. Examples
solve(s) — s is a DNA string over the letters A C G T. Return every 10-letter-long substring that occurs more than once in s, each listed once, in ascending alphabetical order. Collecting all substrings in a map works but stores many long strings. Since there are only four letters, encode each one in 2 bits (A=0, C=1, G=2, T=3): a 10-letter window is a 20-bit integer. Slide the window by shifting the integer left by 2, OR-ing in the new letter, and masking to 20 bits — a rolling hash with no collisions. Examples
solve(s, k) — s has uppercase letters. You may replace at most k characters with any other uppercase letter. Return the length of the longest substring that can be made of a single repeated letter. Use a sliding window. A window [left, right] is valid when window length - (count of its most frequent letter) <= k — the letters that are not the majority are the ones to replace. Expand right one step at a time; when the window becomes invalid, move left forward. You never need to shrink maxCount: a smaller count cannot produce a longer answer than the best one already seen. Examples
solve(haystack, needle) — return the index of the first occurrence of needle in haystack, or -1 if it does not occur. An empty needle returns 0. Do not use indexOf / find / includes. The naive double loop is O(n · m) on inputs like "aaaa…ab". Knuth–Morris–Pratt gets O(n + m) by never moving backwards in the haystack. First build the failure table lps[i]: the length of the longest proper prefix of needle[0..i] that is also a suffix of it. Then scan the haystack; on a mismatch, instead of restarting, fall back to lps[matched - 1] and reuse what you already matched. Examples
solve(s, p) — s and p contain lowercase letters. Return the start indices, in increasing order, of every substring of s that is an anagram of p (the same letters with the same counts, in any order). Slide a window of length p.length over s and keep 26 letter counts for it. Moving the window one step adds one letter and removes one, so you update the counts in O(1) and compare them with p's counts — O(26 · n) overall, no sorting of substrings. Examples