Data Structures and Algorithms Interview Questions

"I ask how many times the innermost line runs as the input grows, then drop constants and lower-order terms, because Big-O is about the growth rate, not exact counts. If I have a loop over n items and inside it another loop over n items, the inner line runs n times n, so it's O(n squared). If the inner loop only goes from i to n, it runs about half as often, but that's still O(n squared). A loop where n is halved each pass, like binary search, runs about log n times before it reaches one, so that's O(log n). Two loops one after the other are O(n) plus O(n), which is just O(n). I also state space separately: what extra memory I allocate and, for recursion, how deep the call stack gets."

"A dynamic array, like a Python list, keeps spare capacity. Most appends just write into the next free slot, which is constant time. When it's full, it allocates a bigger block and copies everything across, which is O(n) for that one call. The key is that it grows by a multiple, not by a fixed amount. If it doubles, then over n appends the copies add up to roughly n plus n over two plus n over four and so on, which is less than 2n. Spread over n appends, that's a constant per append, so we call it amortized O(1). If it grew by a fixed ten slots each time instead, the copying would add up to O(n squared) overall. I'd also say that amortized isn't a guarantee for each call, so in latency-sensitive code one slow append can still matter."

"I start from the limits, because they tell me the target. A million squared is a trillion basic steps, which would take far too long in any language. A million times log of a million is about twenty million, which is comfortable. Simple operations run somewhere in the tens to hundreds of millions per second, slower in Python, so with n around a million I need O(n) or O(n log n). If n were only a few thousand, O(n squared) would be fine and simpler to write. So out loud I'd say: the brute force is O(n squared), it won't handle a million items, and I'm aiming for n log n, which points to sorting, a heap or binary search, or O(n), which points to a hash map, two pointers or a single sweep. That stops me spending twenty minutes on a solution that was never going to pass."

"The brute force is two loops checking every pair, which is O(n squared) time and constant space. The wasted work is that for each number I scan the whole list for one specific partner, target minus that number. A hash map answers that in constant time on average. So I walk the list once, and for each number I compute the complement and check whether I've already seen it. If yes, I return the stored index and the current one. If not, I store the current number with its index and move on. Checking before storing means I never pair an element with itself, and duplicates like three plus three work because the first three is already in the map when I reach the second. That's O(n) time and O(n) space."

"A hash table is an array of slots. To store a key, I run it through a hash function and map the result to a slot index. A lookup does the same calculation, so it jumps straight to the right slot instead of searching. Two keys can land on the same slot, which is a collision. One fix is chaining, where each slot holds a small list. Another is open addressing, where you probe for another free slot, which is what Python's dict does. The table tracks how full it is, and past a threshold it grows and rehashes everything, so on average only a few keys compete for any slot. That's why lookups are average O(1). The worst case is O(n): with a poor hash function, or keys someone picked to collide, everything piles up in one place and a lookup becomes a linear scan."

"Brute force, I'd start at every index and extend to the right with a set until I hit a repeat, which is O(n squared). The waste is that after a repeat I restart from the next index and re-scan characters I already know are fine. So I use a sliding window. I keep a left edge and move the right edge forward one character at a time, and I store the last index where I saw each character. If the current character was last seen inside my window, I move the left edge to just past that position, because any window holding both copies is invalid. Now the window has no repeats, and I track the biggest length. Each character is handled once, so it's O(n) time, and space is O(k), where k is the number of distinct characters."

"Brute force is three loops, O(n cubed), plus a set of sorted tuples to remove repeated triplets. Sorting first changes things. I fix the first number at index i, and now I need two numbers after it that sum to minus that value. Because the array is sorted, I can use two pointers, one just after i and one at the end. If the sum is too small, I move the left pointer right to make it bigger; if it's too big, I move the right pointer left. That pair search is O(n), and I do it for each i, so O(n squared) overall, which outweighs the n log n sort. Duplicates are the tricky part: I skip i when it equals the previous value, and after a match I move the left pointer past equal values. Extra space is small apart from the output and the sort."

"An array stores items side by side, so reading index i is O(1). Inserting or deleting in the middle is O(n) because everything after it has to shift, while appending to a dynamic array is amortized O(1). A linked list stores nodes that point to the next one. Reaching the i-th item is O(n) because I walk from the head, but once I'm holding a node, inserting or removing next to it is O(1), just a few pointer changes. The catch people miss is that finding the node is usually O(n) anyway, and arrays are much friendlier to the CPU cache because the data is contiguous. So in practice I default to an array. I reach for a linked list when I keep inserting and removing at nodes I already have a reference to, like the recency order in an LRU cache."

"A simple brute force copies the values into an array and writes them back in reverse, which is O(n) time but O(n) extra space. I can do it in place with three pointers. I keep prev, starting at None, and current, starting at the head. At each step I first save current's next, because I'm about to overwrite it. Then I point current's next back at prev, move prev up to current, and move current to the saved next. When current is None, prev is the new head. That's O(n) time and O(1) extra space. The recursive version reverses the rest of the list first, then makes the next node point back at the current one. It's neat, but every node adds a stack frame, so it's O(n) space, and on a very long list Python would hit its recursion limit."

"The easy version keeps a set of nodes I've visited. If I reach a node twice, there's a cycle, and that node is where it starts. That's O(n) time and O(n) space. To get O(1) space I use two pointers: slow moves one step, fast moves two. If there's no cycle, fast runs off the end. If there is one, fast eventually catches slow inside the loop, because the gap between them closes by one each step, so they must meet. To find where the cycle starts, I put one pointer back at the head and leave the other at the meeting point, then move both one step at a time. They meet exactly at the start of the cycle, because the distance from the head to the start matches the distance from the meeting point forward to the start, give or take whole laps of the cycle."

"A tempting brute force is to keep deleting adjacent pairs like '()' until nothing changes, which works but can be O(n squared). The better fit is a stack, because brackets nest: the most recently opened one has to close first, which is last in, first out. I scan left to right. When I see an opener, I push it. When I see a closer, the stack must not be empty and its top must be the matching opener; if so I pop, and if not the string is unbalanced. At the end the stack must be empty, otherwise something was opened and never closed. A simple counter isn't enough once there are different bracket types, because '([)]' has the right counts in the wrong order. It's O(n) time and O(n) space in the worst case, like a string of only openers."

"A stack gives back the newest item and a queue the oldest, so I need to flip the order. The brute force pours the whole stack into the second one on every dequeue, pops the bottom item, and pours everything back, which is O(n) per dequeue. The better version gives the stacks fixed roles. Every enqueue pushes onto the in stack. Every dequeue pops from the out stack, and only when the out stack is empty do I move everything across from the in stack. That single move reverses the order, so the oldest item ends up on top. Each item is pushed and popped at most twice in its life, so over any run of operations the cost averages to O(1) each, even though one dequeue can take O(n). In real Python code I'd just use collections.deque, but this shows I understand both structures."

"A naive version keeps a plain list ordered by use, but finding an item and moving it is O(n). For O(1) I combine two structures. A hash map from key to node gives constant-time lookup. A doubly linked list keeps items in order of use, most recent at one end and least recent at the other. Because it's doubly linked and the map hands me the node, I can unlink it and move it to the recent end in O(1), and evicting is just removing the node at the old end. On get, I look up the node, move it to the recent end and return the value. On put, I insert or update at the recent end, and if I'm over capacity I remove the oldest node and delete its key from the map. In Python, OrderedDict is exactly that pairing, so I'd show it and offer to write the list by hand."

"A brute force would find the height, then for each depth run a walk that collects the nodes at that depth, which is O(n times h), and O(n squared) on a skewed tree. The natural fit is breadth-first search with a queue. I put the root in a deque. While the queue isn't empty, I read how many nodes are in it right now, and that's exactly one level. I pop that many from the left, record their values and push their children on the right. When that count is done, I've finished one level and add its list to the result. Each node enters and leaves the queue once, so it's O(n) time. Space is the widest level, which in a full tree is about half the nodes. I use a deque rather than a plain list, because popping from the front of a list is O(n)."

"The rule is that everything in the left subtree is smaller than the node and everything in the right subtree is larger, not just the direct children. For example, root 10, left child 5, and 5's right child 12. Twelve is bigger than 5, so a local check passes, but it sits in 10's left subtree, so the tree is invalid. A brute force checks, for every node, the largest value on its left and the smallest on its right, which is O(n squared) on a skewed tree. Instead I pass bounds down. The root can be anything. Going left, the node's value becomes the upper bound; going right, it becomes the lower bound. Every node must sit strictly inside its bounds. That's O(n) time and O(h) space, where h is the height. Another clean way is an in-order walk, checking that each value beats the previous one."

"The straightforward way is to find the path from the root down to each node, then walk both paths together and take the last node they share. That's O(n) time but it stores two paths. A single recursion does it in one pass. Each call returns the target it found in its subtree, or None. If the current node is one of the targets, it returns itself. Otherwise it asks both children. If both sides come back with something, the two nodes are split across this node, so it's the lowest common ancestor. If only one side found something, it passes that up. That's O(n) time and O(h) space for the stack. In a binary search tree I can use the ordering instead: starting at the root, if both values are smaller I go left, if both are bigger I go right, and the first node where they split, or that equals one of them, is the answer. That's O(h), with no recursion needed."

"The simplest answer is to sort in descending order and take position k minus one. That's O(n log n) and perfectly fine for small lists. When n is large and k is small, I use a min-heap of size k. A heap is a complete binary tree stored in an array where every parent is no bigger than its children, so the minimum is always at the top, and push and pop cost O(log) of the heap size. I push each number, and whenever the heap grows past k, I pop the smallest. At the end the heap holds the k largest numbers, and its top is the k-th largest. That's O(n log k) time and O(k) space, and it also works on a stream I can't hold in memory. A min-heap for the largest sounds backwards, but its minimum is exactly the item I want to throw out."

"The quick answer is to put everything in one list and sort it, which is O(n log n) and ignores that the inputs are already sorted. Merging the lists one at a time into a growing result is worse, up to O(n times k), because early items get copied again and again. The better way is a min-heap holding the front item of each list. I pop the smallest, add it to the output, and push the next item from the same list. The heap never holds more than k items, so each push and pop is O(log k), and each of the n items goes through once, giving O(n log k) time and O(k) extra space besides the output. I store tuples of value, list index and position, so ties break on the index, which matters when the items are linked-list nodes that Python can't compare."

"Both visit every reachable node and edge once, so with an adjacency list they're O(V plus E) time, plus O(V) space for the visited set. The difference is the order. BFS uses a queue and explores in rings: everything one edge away, then two edges away, and so on. That makes it the right choice for the shortest path when every edge costs the same, like the fewest moves on a grid or the fewest hops between two people in a network. DFS uses a stack or recursion and goes as deep as it can before backing up. I use it for cycle detection, topological sorting, counting connected components and backtracking. On memory, BFS can hold a very wide frontier, while DFS holds the current path, but recursive DFS on a deep graph can hit Python's recursion limit, so there I'd switch to an explicit stack."

"A naive version that searches from every land cell without remembering what it has seen repeats a lot of work. So I treat the grid as a graph where each land cell connects to its land neighbours up, down, left and right. The number of islands is then the number of connected components. I scan every cell. When I find land I haven't visited, I add one to the count and flood-fill from it with BFS, marking every connected land cell so I never count it again. Here I mark by flipping it to '0' in place, though I'd first ask whether I'm allowed to change the input; if not, I keep a visited set. Every cell is handled a constant number of times, so it's O(rows times columns) time, and the queue can grow that large in the worst case. I use an iterative BFS because recursion can hit Python's limit on a big all-land grid."

"I model it as a directed graph with an edge from each prerequisite to the course that depends on it. An order exists exactly when the graph has no cycle, and that order is a topological sort. The slow way is to keep scanning all the courses for one whose prerequisites are all done, which means up to V passes over the whole graph. Kahn's algorithm does it in one pass. I count the incoming edges for each course. Every course with zero goes in a queue, since nothing blocks it. I pop a course, add it to the order, and lower the count of every course that depends on it; any that reach zero join the queue. If the order ends up holding every course, that's my answer. If some are left over, they're waiting on each other in a cycle, so I return an empty list. It's O(V plus E) time and space."

"Dijkstra works on graphs whose edge weights are zero or more. I keep a best-known distance for each node, with the source at zero, and a min-heap of candidates. I pop the node with the smallest distance. Because no edge is negative, no other route can come back to it cheaper later, so that distance is final. Then I relax its edges: if the distance to this node plus the edge weight beats a neighbour's current best, I update it and push it onto the heap. Old heap entries that are out of date I simply skip when they're popped. With a binary heap that's O((V plus E) log V). With negative edges, the 'settled means final' guarantee breaks, because a path through a node I haven't finished could come back cheaper. Then I'd use Bellman-Ford, which is O(V times E) and also detects negative cycles. If all edges cost the same, plain BFS is enough."

"I look for two things. First, the question asks for a count, a minimum, a maximum or whether something is possible, over a series of choices. Second, when I write the brute-force recursion, the same subproblem comes up again and again. For the stairs, my last move was either one step or two, so ways of n equals ways of n minus one plus ways of n minus two. As plain recursion that's exponential, because it recomputes the same values over and over. Adding a cache so each n is computed once makes it O(n) time and O(n) space. Then I flip it bottom-up: start from the base cases and build upwards. Each value only needs the previous two, so I keep two variables, which gives O(n) time and O(1) space. That path from recursion to memo to table is how I approach any DP question."

"Greedy works for some coin systems but not all. With coins 1, 3 and 4 and an amount of 6, greedy takes 4, then 1, then 1, which is three coins, but 3 plus 3 is only two. The brute force tries every coin at every step, which is exponential, and it keeps solving the same smaller amounts. So I define best of a as the fewest coins that make amount a. Best of zero is zero. For any a, the last coin used was some coin c, so best of a is one plus the smallest best of a minus c over all coins that fit. I fill the table from 1 up to the amount. If an amount can't be made, it stays at infinity, and at the end I return minus one for that case. That's O(amount times the number of coins) time and O(amount) space."

"Each number is either in a subset or not, so there are 2 to the n subsets, and no approach can beat that, because the output itself is that big. One simple way is to count from zero to 2 to the n minus one and use each number's bits to pick items. Backtracking builds them with one shared path instead. Each call first records a copy of the current path. Then for each index from start onward, I add that number, recurse with start moved past it, and pop it off afterwards. That pop is the backtrack: it undoes the choice so the path is clean for the next option. Moving start forward means I never produce the same set in a different order. The cost is O(n times 2 to the n), since each subset takes up to n to copy. The classic bug is saving the path itself instead of a copy."

"A linear scan is O(n) and works on anything. If the array is sorted, binary search halves the range each step, so it's O(log n) time and O(1) space. The bugs come from being vague about the range, so I fix an invariant: if the target is in the array, it's between lo and hi, both inclusive. That means the loop runs while lo is less than or equal to hi. I take the middle, and if it's the target I return it. If the middle value is too small, the target must be to the right, so lo becomes mid plus one. If it's too big, hi becomes mid minus one. I always move past mid and never set lo or hi to mid itself, because that's what causes infinite loops when two elements are left. Then I check the edge cases out loud: empty array, one element, target at either end, and target missing."

"Both are divide and conquer. Merge sort splits the array in half, sorts each half and merges them. It's O(n log n) in every case and it's stable, meaning equal items keep their original order, but merging arrays needs O(n) extra space. Quicksort picks a pivot, moves smaller items to one side and larger to the other, then sorts each side. On average it's O(n log n), it sorts in place apart from the recursion stack, and it's usually fast in practice because it's cache-friendly. But with bad pivots, like always taking the first element of already sorted data, it drops to O(n squared); random or median-of-three pivots make that unlikely. It also isn't stable. So I'd pick merge sort when I need stability or a guaranteed time, or I'm sorting a linked list or data too big for memory, and quicksort for arrays in memory where extra space matters."

"At my last company we had a nightly job that checked incoming orders against a list of blocked customer IDs. It was fine in testing, but as the blocked list grew, the job slowed down until it started missing its window. I profiled it and saw almost all the time was on one line: checking whether an ID was in a list. That's a linear scan, and it ran once per order, so the whole job cost orders times blocked IDs. I changed the list to a set, built once at the start, which made each check constant time on average. The job went from most of an hour to a couple of minutes, and I added a test with a large list so it couldn't quietly slow down again. Since then, I ask how big each input can realistically get before I choose a structure, not just whether it works on the sample data."

"In my final-year project I needed to find, for each reading in a sensor log, the next reading that was higher. My first version checked every later reading for each one, which was O(n squared), and it crawled on the full data. I was stuck on how to do better, so I stopped coding and worked a tiny example by hand, eight numbers on paper. I noticed that the readings still waiting for a higher value were always in decreasing order, and each new reading settled them starting from the most recent one. That's a stack. So I kept a stack of indexes still waiting, and each new reading popped every smaller one and gave it its answer. Each index is pushed and popped once, so it became O(n). Now, when I'm stuck, I write the brute force, do a small case by hand, and ask which work I'm repeating."

"At my last company we had a report that found overlapping bookings. The original code compared every booking with every other one, which was O(n squared), and in a busy month with tens of thousands of bookings it ran for over an hour. The first suggestion was a bigger server. I measured it and saw the pair comparison was nearly all the time, so hardware would only buy a constant factor. Instead I sorted the bookings by start time, which is O(n log n), and swept through once, keeping a min-heap of end times for bookings still open. For each new booking I dropped the ones that had already ended, and anything left in the heap overlapped it. The report came down to under a minute. Before shipping, I ran the old and new versions on three months of real data and checked they flagged exactly the same bookings."

"I'd say the situation out loud rather than decide silently. Something like: I can code the O(n squared) brute force in about ten minutes and I'm confident it's right, or I can try the O(n) idea, which I'm less sure about. Would you rather see the working version first? Often the interviewer says go ahead with the brute force, and even without an answer, that's my default when the better idea isn't clear yet. A correct, tested solution with a clear explanation of how to improve it is worth more than half an optimal solution that doesn't run. Once it works, I use the remaining time to point at the wasted work, for example that it re-scans the array for every item, and sketch how a hash map would remove that. If the optimal idea is already clear to me, I skip the brute force and write it directly."

"I'd stay calm and treat it like any debugging job. First I re-read the code against the plan I described, line by line, because the bug is often where the code quietly differs from what I said, like a less-than that should be less-than-or-equal. Then I dry-run a small example out loud, writing down the variables after each step, so the interviewer can see exactly where my trace and the expected result split. If the normal case passes, I go through edge cases: an empty input, a single element, duplicates, negative numbers, and answers right at the start or end. Loop bounds and off-by-one errors are the usual suspects. When I find it, I explain why it was wrong, change just that one thing, and re-run the case that failed. What I'd avoid is changing several lines at random to see what sticks."