Question 1

On average, what is the time complexity of looking up a value by key in a well-implemented hash table?

Accepted Answer

A hash table computes an index from the key's hash and jumps almost directly to the matching bucket, so a lookup does a roughly constant amount of work on average no matter how many entries are stored. O(log n) is the complexity of a lookup in a balanced binary search tree, not a hash table, and mixing the two up is a common slip. The O(1) average can degrade toward O(n) in the worst case if many keys collide into the same bucket, which is why hash quality and load factor matter, but that worst case is not what 'average case' is asking about here.

Question 2

You need to implement an LRU (least-recently-used) cache whose get and put operations both run in O(1) time. Which combination of data structures achieves this?

Accepted Answer

The hash map gives O(1) access to the node holding a given key, and the doubly linked list lets that node be unlinked and moved to the front (most recently used) or have the tail removed (least recently used) in O(1), because a doubly linked list can drop a node without scanning for its neighbors. A plain queue does not work on its own: a 'get' on an item buried in the middle needs to move it to the front, and a queue offers no O(1) way to do that. A BST keyed by timestamp would make both operations O(log n) rather than O(1).

Question 3

What is the time complexity of binary search on a sorted array of n elements?

Accepted Answer

Each comparison in binary search discards half of the remaining search space, so the number of comparisons needed to narrow down to a single element grows with log base 2 of n. O(n) is the complexity of a plain linear scan through an unsorted array, which is exactly the cost binary search avoids by relying on the array being sorted; without that sorted precondition, binary search is not even correct, let alone fast.

Question 4

What is the worst-case time complexity of quicksort when the pivot is chosen naively, such as always taking the first element?

Accepted Answer

If the pivot always turns out to be the smallest or largest of the remaining elements — which happens on already-sorted or reverse-sorted input when the pivot is always the first element — each partition step only peels off one element, giving roughly n nested passes over up to n elements each, for O(n^2) overall. O(n log n) is quicksort's average case and also its best case, which is a common point of confusion; randomizing the pivot or picking a median-of-a-few candidate is precisely what makes the O(n^2) worst case unlikely to show up in practice.

Question 5

Which data structure would you use to perform a level-order (breadth-first) traversal of a binary tree?

Accepted Answer

A queue's first-in-first-out order matches level-order traversal directly: a node's children are enqueued after the node itself is visited, so every node at the current depth gets dequeued and visited before any node at the next depth. A stack gives last-in-first-out order, which is what a depth-first traversal relies on instead — swapping a queue for a stack in this algorithm turns it into a form of DFS rather than BFS, even though the rest of the code can look almost identical.

Question 6

You compute the nth Fibonacci number iteratively, keeping only the previous two values in two variables as you loop up to n. What is the auxiliary space complexity?

Accepted Answer

Only two variables are kept alive no matter how large n gets, so the extra memory used does not grow with the input — that is O(1) auxiliary space. This differs from a naive recursive implementation without memoization, whose call stack depth grows to O(n) and whose time complexity is the far worse O(2^n) because of repeated recomputation of the same subproblems; the iterative version sidesteps both of those costs.

Question 7

Given an array of integers and a target value, how would you find the two numbers in the array that add up to the target? Walk through your approach and give its time and space complexity.

Accepted Answer

The brute-force approach checks every pair of numbers with a nested loop, which is O(n^2) time and O(1) extra space — correct, but it does far more work than necessary. A faster approach makes a single pass through the array while keeping a hash map (or hash set) of numbers already seen. For each number, first compute its complement (target minus the current number) and check whether that complement is already in the map; if it is, that pair is the answer. If not, add the current number to the map and continue. This works because a hash map gives an O(1) average-time way to ask 'have I seen this value before?' instead of rescanning the array for every element, which turns the overall approach into O(n) time. The trade-off against brute force is O(n) extra space for the map, since in the worst case nearly every number gets stored before the matching pair turns up. Two details matter for correctness: check the map for the complement before inserting the current number (otherwise a number could appear to pair with itself), and decide up front whether the problem wants the values themselves or their indices, since a hash map keyed by value alone loses index information if the array can contain duplicates.

Question 8

Explain how binary search works, and why the input array must be sorted for it to be correct. What happens if you run it on an unsorted array?

Accepted Answer

Binary search finds a target value in a sorted array by repeatedly narrowing a search window. It starts by looking at the middle element of the window: if that element equals the target, the search is done; if the target is smaller, the search continues only in the left half of the window (everything to the right, including the middle, is discarded); if the target is larger, it continues only in the right half. Because sortedness guarantees that everything to the left of a given element is less than or equal to it and everything to the right is greater than or equal to it, discarding half the window on each comparison is safe — the target, if present, is guaranteed to still be in the remaining half. That halving is also what gives binary search its O(log n) time complexity, since the window size shrinks by half on every step. If the array is not sorted, that guarantee disappears: the target could be anywhere in the half that gets thrown away, so the algorithm can report 'not found' for a value that is actually present, or find the wrong element, depending on the implementation. The array being sorted isn't an optimization binary search benefits from — it's a precondition the algorithm's correctness depends on entirely.

Question 9

How would you check whether a given string is a palindrome, ignoring case and any non-alphanumeric characters? Describe your approach and its time and space complexity.

Accepted Answer

One approach is to build a cleaned-up copy of the string first — lowercase it and strip out every character that isn't a letter or digit — and then compare that cleaned string to its own reverse. That's simple to reason about, but it costs O(n) extra space for the cleaned copy (and another O(n) if a second copy is made to reverse it). A more space-efficient approach uses two pointers, one starting at the left end of the original string and one at the right end, moving toward each other. At each step, advance the left pointer forward past any character that isn't alphanumeric, and advance the right pointer backward past any character that isn't alphanumeric; once both pointers sit on alphanumeric characters, compare them case-insensitively. If they differ, the string isn't a palindrome and the check can stop immediately. If they match, move both pointers one step further inward and repeat, until the pointers meet or cross. This two-pointer approach still runs in O(n) time, since each pointer moves through the string once, but it uses only O(1) extra space because it never builds a second string — it just reads the original one from both ends. The two-pointer version is generally preferred in an interview because it demonstrates the same idea with less memory, and it can short-circuit as soon as a mismatch is found.

Question 10

How would you determine whether a string of brackets — for example '{[()]}' — is balanced? Explain your approach and why a stack is the natural structure for it.

Accepted Answer

Scan the string left to right, one character at a time. Whenever an opening bracket is seen — '(', '[', or '{' — push it onto a stack. Whenever a closing bracket is seen, check the top of the stack: if the stack is empty, there's nothing for this closing bracket to match, so the string is unbalanced. Otherwise, pop the top element and check that it's the matching opening bracket for the closing bracket just seen (for example, a ')' must match a '(' that was just popped, not a '[' or '{'); if it doesn't match, the string is unbalanced. After processing every character, the string is balanced only if the stack ends up empty — a non-empty stack at the end means some opening brackets were never closed. A stack is the natural fit because bracket matching is inherently last-in-first-out: the bracket that was most recently opened is always the one that must be closed next, which is exactly the order a stack's push and pop operations enforce. Trying to solve this with, say, a running counter of open versus closed brackets would catch a simple count mismatch but would miss the case where the brackets are present in equal numbers but nested in the wrong order, like '([)]'. This approach runs in O(n) time, since each character is processed once, and O(n) space in the worst case, if the string is all opening brackets before any closing one.

Question 11

Given a sentence, how would you reverse the order of the words (not the letters within each word) — for example turning 'the sky is blue' into 'blue is sky the'? Discuss at least two approaches and the trade-offs between them.

Accepted Answer

The most direct approach is to split the sentence into a list of words on whitespace, reverse the order of that list, and join the words back together with single spaces. If the splitting step treats any run of one or more spaces as a single separator, this also naturally handles messy input with leading, trailing, or repeated spaces between words, since those extra spaces just get discarded rather than preserved. This approach is O(n) time and O(n) space, since it builds an intermediate list of words and a new output string. A second approach, more relevant in languages that allow in-place mutation of a character array, avoids most of that extra space: reverse the entire character array first, which puts the words in the right order but spells each one backward, then walk through the reversed array a second time and reverse each individual word back to normal, using the spaces as word boundaries. That two-pass technique is still O(n) time but only O(1) extra space beyond the input itself, because it never allocates a second copy of the string. The trade-off is mostly about language and mutability: in languages where strings are immutable, such as Python or JavaScript, true in-place reversal isn't possible anyway, so the split-reverse-join approach is usually both simpler and about as efficient in practice; the in-place double-reversal trick earns its keep mainly in languages like C or Java's char arrays, where avoiding an extra allocation is meaningful.

Question 12

Explain what memoization means and why it changes the time complexity of computing the nth Fibonacci number from exponential to linear.

Accepted Answer

A naive recursive definition of fib(n) as fib(n-1) + fib(n-2) recomputes the same subproblems over and over: fib(n-1) and fib(n-2) each independently recurse down to fib(n-2) and fib(n-3) and so on, so the same value, say fib(3), gets recalculated from scratch many separate times across the recursion tree. Because each call branches into two further calls, the total number of calls grows roughly like 2^n, which is where the exponential time complexity comes from. Memoization fixes this by caching the result of each distinct subproblem the first time it's computed — typically in an array or hash map keyed by n — and checking that cache before doing any recursive work: if fib(k) has already been computed, its cached value is returned immediately instead of recursing again. Since there are only n distinct subproblems (fib(0) through fib(n)), and each one is now computed exactly once, with all of its repeat 'calls' turned into O(1) cache lookups, the total work drops to O(n) time. The trade-off is O(n) space for the cache, plus the recursion's own O(n) call stack depth. A bottom-up dynamic programming version — computing fib(0), fib(1), fib(2), and so on iteratively up to n, keeping only the last two values — achieves the same O(n) time without the recursion stack, and can even bring the space down to O(1) if the full table of past results isn't needed afterward.

Coding & DSA Interview Questions