Loading...
Loading...
Loading...
Python interview guide
Arrays, linked lists, trees, graphs, sorting, searching and complexity. Every answer is short enough to say aloud, and every question links to the lesson that teaches it.
61 questionsLast updated
A binary tree has no rule about values. A binary search tree keeps every value in the left subtree smaller and every value in the right subtree larger than the node. That rule makes searching fast when the tree is balanced.
Lesson: Binary Tree Terms, TreeNode and Level-Order InputTime is O(n), since each node is visited once. Extra space is O(h) for the call stack or the explicit stack, where h is the height. That is O(log n) for a balanced tree and O(n) for a tree that is a chain.
Lesson: Preorder, Inorder and Postorder TraversalsWhen a node needs results from both children before it can finish. Examples are the size or height of a subtree, the total of a folder, and deleting a tree.
Lesson: Preorder, Inorder and Postorder Traversalsyield from doing in a recursive traversal?It passes on every value that a recursive call produces. It makes a lazy traversal that makes values one at a time, so you can stop early without building a full list.
Lesson: Preorder, Inorder and Postorder TraversalsAt the start of each round the queue holds exactly one row, so record its values and then replace the queue by the children of those nodes. The classic version reads len(queue) first and takes that many nodes.
Lesson: Level-Order Traversal with dequeBuild the rows and take the last node of each row. Another way is a depth-first search that visits the right child first and records the first node seen at each new depth.
Lesson: Level-Order Traversal with dequeBFS needs O(w) space for the widest row, which can be about n/2 for a full tree. DFS needs O(h) for the height, which is small for a balanced tree but O(n) for a chain. Which is smaller depends on the shape.
Lesson: Level-Order Traversal with dequeCompute heights bottom-up. At each node the longest path that bends there equals the left height plus the right height, so update a best value with it and return the usual height. One pass visits each node once.
Lesson: Height, Diameter and BalanceA balanced tree with n nodes has height about log n, so search, insert and delete in a search tree take O(log n). A chain has height n and the same operations take O(n).
Lesson: Height, Diameter and BalanceTake the middle value as the root, build the left subtree from the values before it and the right subtree from the values after it. Each half is about the same size, so the height is about log n. Slicing copies lists, so pass index bounds if copying matters.
Lesson: Height, Diameter and BalanceThe values show which way to go. While p and q are both smaller than the node, go left. While both are larger, go right. The first node that splits them is the answer. It takes O(h) time and O(1) space with a loop.
Lesson: Paths, Lowest Common Ancestor and Building from TraversalsWhen one mutable list is shared by all calls. Append the value before the calls on the children and pop it afterwards, and store a copy of the list at a leaf. Passing a new string or tuple to each call needs no undoing.
Lesson: Paths, Lowest Common Ancestor and Building from TraversalsCompute for each node the best gain going down one side, ignoring negative gains. The best path that bends at the node is its value plus both gains, which updates the global best. Return the value plus the larger gain to the parent. Time is O(n).
Lesson: Paths, Lowest Common Ancestor and Building from TraversalsPass a low and a high bound down the recursion, and require every value to lie strictly between them. Comparing with the parent only is not enough. Checking that inorder is strictly increasing also works. Both are O(n).
Lesson: Binary Trees CheckpointRaise sys.setrecursionlimit when the depth is moderate, or use an explicit stack or a level-order loop. Interview tests usually have balanced or small trees, but contest tests may contain a chain.
Lesson: Binary Trees CheckpointIt is O(h) for height h. A balanced tree has h near log n, so search is O(log n). Keys inserted in sorted order give a chain with h = n, so search is O(n).
Lesson: The BST Rule, Search and InsertThe loop is better in Python: it uses O(1) space and cannot hit the recursion limit. A recursive version is shorter and reads like the rule, but uses O(h) stack and fails on a chain deeper than about 1000.
Lesson: The BST Rule, Search and InsertA dict has fast lookup but no order. A sorted list has order but costs O(n) per insert. A BST keeps order and, when balanced, searches and inserts in O(log n), so it suits floor, ceiling and range queries.
Lesson: The BST Rule, Search and InsertIt is the smallest key larger than the deleted key. So it is larger than everything in the left subtree and not larger than anything else in the right subtree, and the BST rule still holds.
Lesson: Delete a Key from a BSTTime is O(h): one walk to the node and one more to the successor. A recursive version uses O(h) stack space. A balanced tree has h near log n.
Lesson: Delete a Key from a BSTAt every node, everything in the left subtree is smaller and everything in the right subtree is larger. Visiting left, node, right then lists smaller keys, the node, then larger keys. Proof by induction on the subtrees.
Lesson: Validate a BST and Sorted Output with InorderChecking only that the left child is smaller and the right child is larger than the node. It misses a key deeper in a subtree that breaks the rule against a higher ancestor.
Lesson: Validate a BST and Sorted Output with InorderRecursion fails near 1000 levels. Use an explicit stack for an iterative inorder, and compare each key with the previous one.
Lesson: Validate a BST and Sorted Output with InorderFloor is the largest key at most x and ceiling is the smallest key at least x. Walk down as in search. When the key is below x remember it and go right. When it is above x, for ceiling remember it and go left. O(h) time, O(1) space.
Lesson: Kth Smallest, Floor, Ceiling and Range QueriesMirror the walk: visit right, node, left. Or use the (n - k + 1)th smallest if the size is known.
Lesson: Kth Smallest, Floor, Ceiling and Range QueriesSubtrees entirely outside the range are skipped. The nodes visited either match or lie on the paths down to the range boundaries, so there are at most 2h of those plus the m matches.
Lesson: Kth Smallest, Floor, Ceiling and Range QueriesTake the middle key as the root and build the left subtree from the left half and the right subtree from the right half, recursively. It takes O(n) time. Use index bounds instead of slices to avoid copying.
Lesson: Balance, and Sorted Collections in Pythoninsort, and is it a problem?The search is O(log n) but the insert shifts items, so it is O(n). The shift is a fast memory copy, so it is fine up to many thousands of items. Beyond that, use a balanced structure.
Lesson: Balance, and Sorted Collections in PythonOn a list, bisect finds the position in O(log n) and a slice gives the range. On a balanced BST, the same queries are O(log n) plus the output, and inserts are also O(log n).
A dict gives O(1) lookup but no order. A sorted list gives order and O(log n) search but O(n) insert. A balanced BST gives order and O(log n) for search, insert and delete.
Lesson: Binary Search Trees CheckpointO(n), when the tree is a chain, for example after inserting sorted keys. Avoid it by building from sorted keys with the middle as root or by using a self-balancing tree.
Lesson: Binary Search Trees CheckpointA heap is a complete tree, so every level is full except maybe the last. That makes the position of a parent and children pure arithmetic: children of i at 2i + 1 and 2i + 2, parent at (i - 1) // 2. It saves memory and is cache friendly.
Lesson: How a Heap Works: Sift Up and Sift DownSifting down costs the height of a node. Half the nodes are leaves and cost nothing, a quarter cost one step, an eighth cost two, and so on. The sum of those costs is proportional to n.
Lesson: How a Heap Works: Sift Up and Sift DownWhen you only need the smallest or largest few values, or the data keeps changing. Sorting costs O(n log n) once and is slow to keep up to date. A heap keeps the smallest ready with O(log n) per change.
Lesson: How a Heap Works: Sift Up and Sift Downheapq has only a min-heap. Push the negated value and negate when you read it. For non-numbers push a tuple with a negated key, such as (-count, word). Or write a small class with a reversed __lt__.
Tuples compare item by item. If the priority ties, Python compares the next item. If that item is a dict or custom object, it raises a TypeError. A counter in the middle is always unique, so it stops the comparison, and it makes equal priorities first in, first out.
Lesson: Top K, Merging Sorted Lists and Max HeapsKeep the lower half in a max-heap and the upper half in a min-heap, with sizes equal or the lower one larger by one. After each add, the median is the top of the lower heap, or the average of both tops. Add is O(log n) and read is O(1).
Lesson: Running Median with Two HeapsPush it into the lower max-heap, pop the largest of the lower heap and push that into the upper min-heap. If the upper heap now has more items, move its smallest back to the lower heap. This keeps every lower value at most every upper value, and the sizes balanced.
Lesson: Running Median with Two HeapsCompare it with a slow version that sorts a copy and reads the middle, over many random inputs with a fixed seed. Also try one value, two equal values, negative numbers, and an even count to check the average.
Lesson: Running Median with Two HeapsEach costs O(L) for a word or prefix of length L, independent of how many words are stored. Space is O(total letters) in the worst case, and less when words share prefixes.
Lesson: Tries: Insert and SearchA dictionary from letter to child works well, and a node class with children and is_end is clearer. For only lowercase letters, a list of 26 children is faster but uses more memory per node.
Walk to the node for the typed prefix in O(L). Then run a depth-first search below it, visiting children in sorted order, and collect nodes with the word-end flag. Stop early once you have enough suggestions.
Lesson: Prefix Search and Word ProblemsInsert all words with counters. For each word, walk from the root and stop at the first node whose count is 1. The letters up to that node are the shortest prefix no other word shares.
Lesson: Prefix Search and Word ProblemsWalk a trie from the root while the node has exactly one child and no word ends there. In Python, zip(*words) with a loop that stops at the first column that differs is shorter, and both are O(total letters).
The heap never holds more than k items, so each push and pop costs O(log k). It runs once for each of n values. A full sort costs O(n log n) and needs all values in memory.
Lesson: Heaps and Tries Checkpointsearch and starts_with in a trie?Both walk the letters. search also needs the last node to have the word-end flag, so it rejects a plain prefix. starts_with only needs the walk to succeed.
Use defaultdict(list) and, for every pair (a, b), append b to graph[a] and a to graph[b]. It takes O(n + m) time. For a directed graph append only to graph[a].
They never appear as keys. Loop over range(n) when the node count is known, or add every node when reading the input, so isolated nodes still get visited and counted.
A sparse graph has far fewer edges than the possible n squared, often about n to a few times n. A dense graph has close to n squared edges. The choice of storage depends on this.
Lesson: Graph Terms and Adjacency ListsIf you mark it only when you remove it, the same node can be queued several times by different neighbours. That wastes time and on dense graphs can make the queue much larger.
Lesson: BFS and Shortest Path by Number of Edgesdeque and not a list in BFS?deque.popleft() is O(1). list.pop(0) is O(n) because it shifts all items, which makes BFS O(n squared) on large inputs.
BFS uses a queue and visits nodes level by level, so it finds the fewest edges in an unweighted graph. DFS uses a stack or recursion and goes deep first, which suits path existence, components, cycles and backtracking. Both are O(n + m).
Lesson: DFS: Recursive and IterativeWithout it, a cycle makes the search go round forever, and nodes joined by several paths are visited many times. With it every node is processed once, giving O(n + m).
Lesson: DFS: Recursive and IterativeIt means marking a node as part of the current path, exploring from it, then removing the mark so other paths can use the node. It lists all paths but can take exponential time.
Lesson: DFS: Recursive and IterativeEach cell is a node and its neighbours are found with a list of direction steps such as (1, 0), (-1, 0), (0, 1), (0, -1), keeping only cells inside the grid. No adjacency list is built.
Lesson: Connected Components and Grid ProblemsFlood fill changes one component starting from a given cell. Number of islands counts all components in the grid. Both use the same search.
Lesson: Connected Components and Grid ProblemsRun DFS or BFS and keep the parent of each node. If a neighbour is already seen and is not the parent, there is a cycle. Run it from every unseen node. Time is O(n + m). A shortcut: a forest with c components has n minus c edges, so more than that means a cycle.
Lesson: Cycle Detection: Undirected and DirectedUse DFS with three states: new, on the current path, finished. An edge to a node on the current path is a cycle. Or run Kahn's topological sort: if fewer than n nodes can be removed, there is a cycle. Both are O(n + m).
Lesson: Cycle Detection: Undirected and DirectedUse Kahn's method, which uses a queue and has no recursion. Or write DFS with an explicit stack that tracks which nodes are on the current path.
Lesson: Cycle Detection: Undirected and DirectedThe nodes are cells and the neighbours come from direction steps with a bounds check, so no adjacency list is stored. The search code is otherwise the same, and the cost is O(rows times columns).
Lesson: Graphs Basics CheckpointMarking nodes late, so they enter the queue twice; forgetting isolated nodes; skipping the grid bounds check; using recursion on deep graphs; and treating directed edges as undirected.
Lesson: Graphs Basics CheckpointEach lesson has quizzes, practice and more interview questions on the same topic.
Open the first lesson