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
Python's list and collections.deque already cover the common needs with less memory and faster access, because they are built in and stored compactly. A hand-made node needs one object per value. Linked lists are mostly an interview topic that tests reference handling.
items[i] in O(1)?The nodes are separate objects in different places in memory. Only the links tell you where the next one is, so you must follow i links from the head. A list stores references in a block, so it can compute the position directly.
Lesson: The Node Class: Build and TraverseThe empty list (head is None), a list with one node, and operations that touch the head or the last node. Many bugs come from calling .next on None, so decide what the function should do for those inputs before writing the loop.
A dummy node is a throwaway node placed before the head. It means the head has a previous node like all others, so inserting or deleting at the front needs no special case. You return dummy.next at the end.
push_front return the new head?Python passes object references by value, so assigning to head inside the function does not change the caller's variable. The function returns the new head, and the caller writes head = push_front(head, x).
list.insert(i, x) shifts every later item, so it is O(n) even if you know i. A linked list needs O(1) once you hold the previous node, but reaching it costs O(n). In practice the Python list is usually faster, because it is compact.
Move a slow pointer one step and a fast pointer two steps. When fast reaches the end, slow stands in the middle. For an even length it ends on the second middle unless you start fast one node ahead.
Lesson: Reverse, Middle and Cycle DetectionA set of visited nodes is easy and also O(n) in time, but it stores every node, so it uses O(n) space. Fast and slow uses two variables. The set version is fine when memory is not a concern and you want simple code.
Lesson: Reverse, Middle and Cycle DetectionAfter you point node.next at prev, nothing refers to the rest of the list, so you lose it and cannot continue. Saving nxt = node.next first, or using a tuple assignment that reads the old value, avoids that.
Move a lead pointer n nodes ahead of a trail pointer, both starting at a dummy node. Then move both until lead reaches the last node. The trail pointer is now just before the node to delete. The dummy node covers the case of deleting the head.
Lesson: Merge Lists and Classic Interview ProblemsMerge sort. It needs only the middle (found with slow and fast pointers) and relinking nodes, not random access. It runs in O(n log n) time, and a version that merges nodes in place uses only O(log n) space for the recursion. Quick sort and heap sort need indexes.
Lesson: Merge Lists and Classic Interview ProblemsA dummy node is a placeholder before the head, so the head needs no special case. It helps in merging, removing nodes, and any problem where the head of the result is not known until the loop ends. Return dummy.next.
Use a dummy node when the head may change or be removed. Use two pointers when you need the middle, a cycle, or a position counted from the end. Many problems use both, like removing the n-th node from the end.
Lesson: Linked Lists CheckpointAn empty list, a single node, changing or removing the head, working with the last node, and lists of two nodes. Calling .next on None is the commonest crash, so check node before using node.next.
append and pop() work on the end of the list and take O(1) time on average. No other item moves, so there is no need for a special class. The only care needed is to check for an empty list before you pop or peek.
insert(0, x) and pop(0) shift every other item, so each call is O(n). A loop of n pushes then costs O(n squared). Keep the top at the end.
Push, pop and peek are O(1) time. A stack holding n items uses O(n) space. A loop that pushes and pops each item once costs O(n) time in total.
Lesson: Stacks with a List: Push, Pop and PeekPostfix puts the operator after its operands, such as 3 4 +. It needs no brackets or precedence rules, and one left to right pass with a stack evaluates it in O(n).
An empty text, which is valid; a single closer; a single opener; interleaved types such as ([)]; and text with letters between the brackets.
A stack whose values stay sorted in one direction. Before pushing a new item you pop the items that would break the order. It answers nearest greater or smaller questions in O(n).
Lesson: Monotonic Stack: Next Greater Element and Largest RectangleKeep bars with rising heights. A lower bar ends every taller bar on top. For each ended bar, the width runs from its start to the current index, and the area is height times width. A sentinel 0 at the end flushes the rest.
Lesson: Monotonic Stack: Next Greater Element and Largest RectangleTime is O(n) because every item is pushed and popped once. Space is O(n) in the worst case, such as a strictly falling list where nothing is ever popped.
Lesson: Monotonic Stack: Next Greater Element and Largest RectangleA list is an array. Removing the first item shifts all the others, so each call is O(n) and draining the queue is O(n squared). A deque is a linked block structure that removes from the ends without shifting.
Lesson: Queues with deque, and Why Not list.pop(0)Print jobs, customer support tickets, round robin scheduling, buffering messages and breadth first search, which visits nodes level by level.
Lesson: Queues with deque, and Why Not list.pop(0)Use an inbox and an outbox. Push on the inbox. To pop or peek, if the outbox is empty move all inbox items over, which reverses them, then use the outbox top. Never move while the outbox has items.
Lesson: Queue with Stacks and Other Design ProblemsKeep a second stack with the minimum so far at every depth, or push pairs of value and minimum. Push adds a new minimum, pop removes from both, and get_min reads the top. Space is O(n).
A circular queue stores items in a fixed array with a head index and a size. Indexes wrap with %, so freed cells are reused and no item is ever shifted. It is common for fixed buffers.
list.pop(0) shifts every item and costs O(n). deque.popleft() costs O(1), so draining n items is O(n) and not O(n squared).
pop() and stack[-1] raise IndexError. Guard with if stack: before reading, and decide what the answer is for an empty input, such as an empty text being valid.
It is deterministic, so equal keys give equal numbers. It is fast. It spreads keys evenly, so buckets stay short.
Lesson: Hash Functions, Buckets and a Small MapIf a key changed after it was stored, its hash would change and the map would search the wrong bucket. Immutable types such as int, str and tuple keep their hash for life.
Lesson: Hash Functions, Buckets and a Small MapIf all keys land in one bucket, lookup scans every key, which is linear time. A good hash function and resizing make this very unlikely.
Lesson: Hash Functions, Buckets and a Small MapChaining is simple, and deletes are easy, but it uses extra list objects. Open addressing keeps everything in one array, which is cache friendly, but needs tombstones and slows down as the table fills.
Lesson: Collisions, Chaining and ProbingThe length of the chain, or the length of the probe run. Both depend on the load factor and on how evenly the hash spreads keys.
Lesson: Collisions, Chaining and ProbingIt is keys divided by slots. It sets the average chain length or probe run. A low load factor means fast lookups but more memory. A high one saves memory but slows lookups.
Lesson: Resizing, Average Cost and How dict and set RelateResizes happen after the table doubles, so over n inserts the total resize work is about 2n. That makes the amortized cost per insert constant.
Lesson: Resizing, Average Cost and How dict and set RelateBoth are hash tables with hashable keys. A set stores keys only. Dict keys also support set operations like intersection.
Lesson: Resizing, Average Cost and How dict and set RelateUse a hash map from key to node and a doubly linked list ordered by use. Get and put move the node to the front. When over capacity, drop the node at the back and delete its key from the map.
Lesson: Design Problems and the LRU CacheKeep a list of values and a dict from value to list position. Delete by moving the last value into the freed place. Pick by choosing a random list index.
Lesson: Design Problems and the LRU CacheUnhashable keys are refused with a TypeError. Heavy collisions push operations towards linear time, so design problems should use keys with well-spread hashes, such as integers or tuples.
Lesson: Design Problems and the LRU CacheChaining keeps a list per slot and is simple to delete from. Probing stores keys in the array, is cache friendly, but clusters and needs tombstones.
Lesson: Hash Tables from Scratch CheckpointA dictionary maps keys to nodes of a doubly linked list ordered by use. Get and put move the node to the front, and an overflow removes the node at the back. In Python, OrderedDict does the same.
Insertion sort: it is stable, adaptive and fast on small or nearly sorted lists, and it is used inside real hybrid sorts for tiny pieces. Selection sort only makes sense when swaps are very costly. Bubble sort is mainly for teaching.
Lesson: Bubble, Selection and Insertion SortIts swap moves the smallest value across many items. With [(a, 3), (b, 3), (c, 1)] the first swap puts c in front and a at the end, so a ends up after b although it came first.
Lesson: Bubble, Selection and Insertion SortNo. sorted() and list.sort() use Timsort: stable, O(n log n) in the worst case and O(n) on sorted data, written in C. Hand-written simple sorts are for learning and for interview questions.
It guarantees O(n log n) and is stable, and it works well on linked lists and on data too big for memory, because it reads sorted runs in order. Quick sort is usually faster in memory but has an O(n squared) worst case and is not stable.
Lesson: Merge Sort and Counting InversionsIt takes the left value when the two are equal (<=). Left items came first in the input, so taking them first keeps equal items in their original order, which makes the sort stable.
Use a min-heap holding the front item of each list, pop the smallest, and push the next item from that list. That costs O(n log k) time. In Python, heapq.merge(*lists) does exactly this.
Pick a random pivot or the median of three values. Also use a three-way partition so many equal values are not split again. With a random pivot no input can force O(n squared) reliably.
Lesson: Quick Sort, Partitioning and QuickselectPartition around a pivot. If the pivot index equals k, it is the answer; if k is smaller, continue in the left side; otherwise continue in the right side with an adjusted k. The average cost is O(n) and the worst case O(n squared).
Lesson: Quick Sort, Partitioning and QuickselectIt splits the list into smaller, equal and larger groups. With many duplicates the equal group is finished at once, and it solves the sort-colours problem with 0, 1 and 2 in one pass.
Lesson: Quick Sort, Partitioning and QuickselectCount how often each value appears in a list indexed by the value, turn the counts into positions, and write the values out. Time is O(n + k) and space O(k), where k is the range size, so it is a poor fit when k is much larger than n.
Lesson: Counting Sort and Bucket SortWhen many values land in the same bucket, for example when the data is clustered. In the worst case one bucket holds everything and the cost is that of the inner sort, such as O(n log n), or O(n squared) with insertion sort.
Lesson: Counting Sort and Bucket SortUse counting sort: a list of 101 counters and one pass over the data, O(n) time. In Python, Counter gives the counts and a loop over range(101) writes the result.
You can sort by several keys by sorting repeatedly, from the least important key to the most important one. Equal items keep their previous order, so the earlier sorts act as tie breakers.
Lesson: Timsort and Choosing a Sort in PythonHow large is the input, are the values integers in a small range, is it nearly sorted, must equal items keep their order, and is extra memory limited. Each answer points to a different algorithm.
Lesson: Timsort and Choosing a Sort in PythonOnly for comparison sorts, which can be shown to need that many comparisons in the worst case. Counting, bucket and radix sort avoid it by using the values themselves, under conditions on the data.
Lesson: Timsort and Choosing a Sort in PythonMerge sort is O(n log n) always, stable, and needs O(n) extra space. Quick sort is O(n log n) on average, O(n squared) at worst, in place, and not stable. In memory quick sort is usually faster, while merge sort suits linked lists and external data.
Lesson: Sorting Algorithms CheckpointBefore merging two sorted halves, move a pointer over the right half for each left value to count right values with 2 * right < left. Both halves are sorted, so the pointer only moves forward and the count costs O(n) per level.
Lesson: Sorting Algorithms CheckpointDepth of a node is the number of links from the root down to it. Height of a node is the number of links on the longest path from it down to a leaf. The height of the tree is the height of the root. Some books count nodes instead of links, so state which you use.
Lesson: Binary Tree Terms, TreeNode and Level-Order InputThe values are listed row by row, from left to right, and a missing child is written as null. The children of a null item are not listed. This is the format used in most coding tests.
Lesson: Binary Tree Terms, TreeNode and Level-Order InputEach lesson has quizzes, practice and more interview questions on the same topic.
Open the first lesson