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.
59 questionsLast updated
Count the in-degree of every node. Put the nodes with in-degree 0 in a queue. Pop a node, add it to the answer, and lower the in-degree of each neighbour. When a neighbour reaches 0, push it. If the answer has fewer than n nodes, there is a cycle. The time is O(V + E).
Lesson: Topological Sort: Kahn and DFSWith Kahn, check whether the answer has fewer than n nodes. With DFS, keep three states per node: not seen, in progress and done. Reaching a node that is in progress means a back edge, which is a cycle.
Lesson: Topological Sort: Kahn and DFSKahn is usually safer. It uses a loop, so there is no recursion limit problem on a long chain, and the cycle check is one comparison. DFS is shorter to write when recursion depth is small.
Lesson: Topological Sort: Kahn and DFSAttach the smaller tree below the larger one. Without it a sequence of unions can build a chain of length n, and find becomes O(n). With it, the height is at most log n even without compression.
Lesson: Union-Find with Path CompressionFor each edge, find the leaders of both ends. If they are equal, the ends are already connected, so this edge closes a cycle. Otherwise union them. It does not work for directed graphs, which need DFS or Kahn.
Lesson: Union-Find with Path CompressionKeep the best known distance to each node. Repeatedly take the unsettled node with the smallest distance from a min-heap, and relax its edges. With heapq the time is O((V + E) log V) and the space is O(V + E). It needs non-negative weights.
Lesson: Dijkstra: Shortest Paths with heapqheapq cannot lower the priority of an item that is already in the heap. So you push a new better pair and ignore the old pair when it is popped with d > dist[u]. The heap can hold up to E entries.
Keep a parent array and set parent[v] = u when dist[v] improves. After the run, follow parent from the target to the start and reverse the list.
Lesson: Dijkstra: Shortest Paths with heapqRun one more pass. If any edge can still be relaxed, a negative cycle is reachable from the start. To find nodes affected by it, mark the nodes relaxed in that pass and spread the mark along outgoing edges.
Lesson: Bellman-Ford and Floyd-Warshall in BriefEqual weights: BFS. Non-negative weights and one start: Dijkstra. Negative weights: Bellman-Ford. All pairs on a small graph: Floyd-Warshall. For all pairs on a big sparse graph with non-negative weights, run Dijkstra from each node.
Lesson: Bellman-Ford and Floyd-Warshall in BriefFor a connected, weighted, undirected graph it is a set of V - 1 edges that connects all nodes with the smallest total weight and has no cycle. It is not the same as the shortest path tree from Dijkstra.
Lesson: Minimum Spanning Tree: Kruskal and PrimStart from any node and keep a heap of edges that leave the tree. Pop the cheapest. If it reaches a new node, add the node and push its edges. With heapq it is O(E log V) time and O(V + E) space.
Lesson: Minimum Spanning Tree: Kruskal and PrimCount the edges kept. A connected graph gives exactly V - 1. Fewer means some nodes cannot be reached, and the result is a spanning forest, not a tree.
Lesson: Minimum Spanning Tree: Kruskal and PrimDirected: Kahn finishes with fewer than n nodes, or DFS finds a node that is still in progress. Undirected: Union-Find finds an edge whose two ends already share a leader, or DFS reaches a visited node that is not the parent.
Lesson: Graph Algorithms CheckpointKahn and DFS sort: O(V + E). Union-Find: almost O(1) per operation. Dijkstra: O((V + E) log V). Bellman-Ford: O(V * E). Floyd-Warshall: O(V cubed). Kruskal: O(E log E). Prim: O(E log V).
Lesson: Graph Algorithms CheckpointCoin change with coins 1, 3 and 4 and amount 6. Largest-first gives 4 + 1 + 1, three coins, but 3 + 3 uses two. Dynamic programming gives the right answer.
Lesson: What Makes a Problem Greedy, and When Greedy FailsTake any best answer that does not use the greedy choice. Swap the greedy choice in, show the answer is no worse, and repeat. This proves a best answer exists that starts with the greedy choice.
Lesson: What Makes a Problem Greedy, and When Greedy FailsGreedy commits to one choice per step and never reconsiders it. Dynamic programming stores the best answer for smaller subproblems and compares all choices. Greedy is faster and simpler but is correct for fewer problems.
Lesson: What Makes a Problem Greedy, and When Greedy FailsEarliest start can pick one very long request that blocks many short ones. Shortest length can pick a short request in the middle that overlaps two others that would fit together. Small counterexamples show both.
Lesson: Activity Selection and Job SequencingThe slot version is O(n squared) worst case with O(n) space. The heap version is O(n log n) time and O(n) space. A union-find on free hours can bring the slot version close to O(n log n) too.
Lesson: Activity Selection and Job SequencingSort by start. Keep a result list. For each interval, if its start is at or before the last result end, extend that end with max; otherwise append it as new. Time is O(n log n), space is O(n) for the output.
Lesson: Merge Intervals, Insert Interval and Meeting RoomsCopy the ranges that end before the new start. Merge each range that starts at or before the new end by taking the minimum start and maximum end. Then copy the remaining ranges.
Lesson: Merge Intervals, Insert Interval and Meeting RoomsRead the statement. For merging, many problems merge them, so use start <= last_end. For meetings, a room is usually free at the end time, so use ends[0] <= start. Say your assumption aloud in an interview.
Keep the farthest reachable index. At each index, if it is beyond the reach, return False; otherwise update the reach with i plus the jump. Any cell up to the reach can be reached, so the farthest reach is all the state you need.
Lesson: Jump Game, Gas Station and Reach ProblemsBecause the total is not negative, the stretch after the last restart never goes below zero, and the stretch before it has a total at least that bad, so the rest of the ring is covered by the surplus. The restart point is the only one that never dips below zero.
Lesson: Jump Game, Gas Station and Reach ProblemsWhen each cell has a cost or a choice that affects later options, such as minimum cost jump or jump with obstacles. Then dynamic programming or a heap tracks the options that greedy would discard.
Lesson: Jump Game, Gas Station and Reach ProblemsFinish time for the largest set of non-overlapping requests, and start time for merging and for rooms. The key is chosen so that one scan can decide each item.
Lesson: Greedy and Intervals CheckpointJump game, gas station and best single trade. Each carries one value, such as the farthest reach or a running tank, through one pass in O(n) time and O(1) space.
Lesson: Greedy and Intervals CheckpointMemoization is top-down: write the recursion and cache each result. Tabulation is bottom-up: fill a table from the base cases upward. Both compute each state once. Tabulation avoids recursion depth limits and often allows saving space.
Lesson: From Recursion to Memoization to a TableEach recursive call adds a stack frame and the default limit is about 1000. A function that goes n levels deep raises RecursionError. Use a loop, or raise the limit carefully with sys.setrecursionlimit.
Lesson: From Recursion to Memoization to a Tablelru_cache is the fastest way to write a correct solution when states are hashable arguments. A table is better when recursion would be very deep, when speed matters, or when the filling order allows reducing memory. In interviews, show you can write the table.
Lesson: From Recursion to Memoization to a TableTaking the largest house first or every other house can block a better pair. For [3, 1, 1, 3] the best is the two 3s, which an alternate-house rule might miss. DP compares both choices at every house.
Lesson: Climbing Stairs, House Robber and Min CostKeep the table, then walk back from the last cell. At each cell see which choice gave the value, record it and jump to the cell it came from. This costs O(n) space, so use it only when the path is asked for.
Lesson: Climbing Stairs, House Robber and Min CostLet dp[a] be the fewest coins for amount a, with dp[0] = 0 and the rest infinity. For each amount try every coin c and take dp[a - c] + 1 when it is smaller. Return -1 if the last cell is still infinity. It takes O(amount x coins) time and O(amount) space.
Lesson: Coin Change and Counting WaysStore, for every amount, the coin that gave the best value. After filling the table, start at the target amount, record the stored coin, subtract it and repeat until you reach 0.
Lesson: Coin Change and Counting WaysA knapsack where each item can be used any number of times. Coin change is the standard example. Iterating amounts upward lets the same coin be reused in one pass; in the 0/1 knapsack the loop goes downward to avoid reuse.
Lesson: Coin Change and Counting WaysKeep a sorted list tails where tails[k] is the smallest last item of any rising run of length k + 1. For each item, binary search the first tail that is not smaller and replace it, or append when none exists. The length of tails is the answer.
Lesson: Longest Increasing Subsequence with bisectTo keep the rest strictly rising you keep a longest rising subsequence and remove the others, so the answer is n minus its length.
Lesson: Longest Increasing Subsequence with bisectLet dp[i] be True when the first i characters can be cut into dictionary words, with dp[0] = True. For each i check each j below i: if dp[j] is True and s[j:i] is a word, set dp[i] True. Put the words in a set. Time is O(n^2) with slicing and space is O(n).
Lesson: Word Break and Decode WaysUse the same table but set dp[0] = 1 and add dp[j] when s[j:i] is a word. To list the sentences instead, use memoized recursion over the start position and combine the results; the output itself can be exponential.
Lesson: Word Break and Decode WaysBoth look at the last piece or coin that ends the current state and combine the answers of the smaller state. In coin change the piece is a coin of some value; in word break it is a word of some length.
Lesson: Word Break and Decode WaysRecursion: the fewest coins for a is the minimum over coins c of 1 plus the fewest for a - c. It repeats work, so cache it or fill dp from 0 up. dp[0] = 0, the rest start at infinity. Time O(amount x coins), space O(amount).
Lesson: Dynamic Programming 1D CheckpointState that both are valid. Memoization is quick to write from the recursion; the table avoids recursion depth limits in Python and often allows saving space. Offer to convert one to the other.
Lesson: Dynamic Programming 1D Checkpoint[[0] * n] * m.The outer * repeats the same inner list object m times, so all rows are one list seen m times. Changing one cell changes every row. Use [[0] * n for _ in range(m)], which builds a new list for each row.
With no blocked cells, the routes are the number of ways to choose which moves go down: math.comb(m + n - 2, m - 1). As soon as cells are blocked or have costs, you need the table.
Lesson: Grid Paths and Minimum Path SumKeep the whole cost table. Start at the bottom-right cell and step to whichever neighbour (above or left) has the smaller best value, until you reach the start. Reverse the collected cells. This needs the full table, not one row.
Lesson: Grid Paths and Minimum Path Sumtable[i][w] is the best value using the first i items with capacity w. The rule is table[i][w] = max(table[i - 1][w], value[i] + table[i - 1][w - weight[i]]), and the second option only exists when the item fits.
Lesson: 0/1 Knapsack and Subset SumIf the total is odd, the answer is no. Otherwise run subset sum for total / 2. A True at that cell means one half exists and the other half is the rest.
Lesson: 0/1 Knapsack and Subset SumStore reachable sums as bits of one integer, with sums |= sums << x for each number x. Python integers are unbounded, so it is short and fast, but it only answers yes or no and cannot rebuild the chosen numbers.
Lesson: 0/1 Knapsack and Subset SumA substring is a contiguous piece. A subsequence keeps the order but may skip letters. "ace" is a subsequence of "abcde" but not a substring. Longest common substring uses a table where a mismatch resets the cell to 0.
Lesson: Longest Common Subsequence and Edit DistanceKeep the whole table and walk back from the bottom-right corner. At each cell, decide which neighbour gave the value. Collect the letters or edits, then reverse them. Two-row versions cannot do this.
Lesson: Longest Common Subsequence and Edit DistanceUse a range: pal[i][j] says whether s[i..j] is a palindrome, or lps[i][j] holds the longest palindromic subsequence inside s[i..j]. Both read the range just inside, [i + 1, j - 1], or one end shorter.
Lesson: Palindrome and Interval DPBoth are O(n squared) time. The table uses O(n squared) space. Expanding around 2n - 1 centres needs O(1) extra space and is usually shorter to write, so interviewers often expect it. Manacher algorithm gives O(n) but is rarely required.
Lesson: Palindrome and Interval DPA cell for range [i, j] needs shorter ranges, so loop by increasing length or loop i from the end and j from i upwards. A wrong order reads cells still holding their starting value, usually zero, and gives wrong answers without an error.
Lesson: Palindrome and Interval DPA bitmask stores a set of up to about 20 items as one integer, one bit per item. It lets a list or table be indexed by a set, so states such as "which jobs are used" become array positions.
Lesson: Bitmask DP in BriefThe state is (visited set, last city). dp[mask][last] is the shortest path from the start through mask ending at last. Each state tries n next cities, so it is O(2^n x n squared) time, far better than n factorial for moderate n.
Lesson: Bitmask DP in BriefStart with sub = mask and repeat sub = (sub - 1) & mask until sub is 0, handling sub = 0 separately if needed. It visits each submask once, and over all masks the total is 3 to the power n.
Lesson: Bitmask DP in BriefCheck what each cell means, the base cases (empty prefix, first row, range of length one), the fill order, the answer cell, and the size. Then run the smallest input and one case where the answer is zero or impossible.
Lesson: 2D Dynamic Programming CheckpointGrid: moves on cells with costs. Knapsack: items taken once with a limit. String DP: two sequences compared by prefix. Interval DP: merging, cutting or nested structure on a range. Bitmask: few items and a state of which are used.
Lesson: 2D Dynamic Programming CheckpointEach lesson has quizzes, practice and more interview questions on the same topic.
Open the first lesson