Data Structures & Algorithms interview questions and answers

Question 1

What is an algorithm, and what is a data structure?

Accepted Answer

Answer: An algorithm is a step-by-step procedure that solves a problem or completes a task. Given an input, it produces the correct output in a finite number of steps. A recipe is an everyday algorithm. A data structure is a way of organising and storing data so it can be used efficiently. The right structure makes the operations you do most (search, insert, delete) fast. They work together: a good algorithm often depends on choosing the right data structure. Two Sum is O(n squared) with just an array, but O(n) once you add a hash map. Analogy: the algorithm is the plan of action; the data structure is how you lay out your materials so the plan is quick to carry out. In an interview: An algorithm is a finite step-by-step procedure from input to correct output. A data structure is how data is organised so operations on it are efficient. Picking the right structure is often what makes an algorithm fast.

Question 2

What is the difference between a linear and a non-linear data structure?

Accepted Answer

Answer: Linear: elements are arranged in a sequence, each with one element before it and one after (except the ends). You traverse them in one direction. Examples: array, linked list, stack, queue. Non-linear: elements are arranged hierarchically or as a network, so one element can connect to many others. There is no single straight path through all of them. Examples: trees (one parent, many children) and graphs (any node connects to any node). Linear structures are simpler and often more cache-friendly. Non-linear structures model relationships: a file system, an org chart, a road network, a social graph. Analogy: linear is a train: carriages in a line, one after another. Non-linear is a family tree or a map of cities: branches and connections in many directions. In an interview: Linear structures arrange elements in a single sequence you traverse one way: arrays, linked lists, stacks, queues. Non-linear structures are hierarchical or networked, where a node links to many others: trees and graphs, used to model relationships.

Question 3

What operations do you perform on a data structure, and which structures do not keep insertion order or allow duplicates?

Accepted Answer

Answer: The common operations on any structure are: insert, delete, search (find), traverse (visit every element), access (get by position or key), and sometimes sort. Order not guaranteed: a hash set and a hash map store items by a hash of the key, so iteration order is not the insertion order (Java's HashMap, Python's set). A graph has no inherent order either. If you need insertion order, use a LinkedHashMap, an ordered dict, or a list alongside. No duplicates: a set (and its key-only cousin, the keys of a map) stores each value at most once. Adding a value that is already present does nothing. Lists, arrays, and queues all allow duplicates. Analogy: a set is a guest list where a name can only appear once and the order does not matter. A list is a queue at a shop: duplicates fine, order is everything. In an interview: Every structure supports insert, delete, search, traverse, and access. Hash sets and hash maps do not preserve insertion order because they store by hash. Sets do not allow duplicates; lists, arrays, and queues do.

Question 4

What is a brute force algorithm?

Accepted Answer

Answer: Brute force is the most direct approach: try every possible option and check each one, with no cleverness. It is usually easy to write and obviously correct, but slow, often O(n squared), O(2 to the n), or worse. In an interview you almost always start here: state the brute force solution and its complexity out loud ("I could check every pair, that is O(n squared)"), then look for a faster approach. It shows you can always produce something that works. Example: to find a pair of numbers that sum to a target, brute force checks all pairs. To crack a 4-digit PIN, brute force tries 0000 to 9999. Analogy: trying every key on a big keychain until the door opens. It always works eventually; it is just not smart. In an interview: Brute force tries every possibility and checks it. It is simple and clearly correct but slow. I start with it in interviews to have a working baseline, then optimise from there.

Question 5

What is the difference between recursion and iteration?

Accepted Answer

Answer: Both repeat work, but differently. Recursion: a function calls itself with a smaller version of the problem, until it hits a base case that stops it. Each call is put on the call stack. It is often cleaner for problems that are naturally nested: trees, graphs, divide and conquer, backtracking. Iteration: a loop (for, while) repeats a block until a condition is met. It uses a fixed amount of memory (no growing call stack) and has no risk of a stack overflow. Any recursion can be rewritten as iteration (sometimes using your own explicit stack), and vice versa. Recursion trades memory and a small speed cost for readability on nested problems. Analogy: recursion is asking the person one step ahead of you for their answer and building on it, so the whole line has to wait for the front. Iteration is doing each step yourself in a loop. In an interview: Recursion has a function call itself on a smaller input until a base case, using the call stack, and reads well for nested problems like trees. Iteration uses a loop with constant extra memory and no stack-overflow risk. Each can be converted to the other.

Question 6

What is divide and conquer?

Accepted Answer

Answer: A strategy with three steps: divide the problem into smaller sub-problems of the same kind, conquer each sub-problem (usually by recursion), then combine the sub-answers into the full answer. It works when a problem splits cleanly and the sub-problems do not overlap. Splitting in half each time gives the classic O(n log n) or O(log n) running times. Examples: merge sort and quicksort (split the array, sort the halves, merge), binary search (halve the search range each step), and many geometry and matrix algorithms. Analogy: sorting a huge stack of papers by splitting it among helpers, each helper sorts their smaller pile, then you merge the sorted piles together. In an interview: Divide and conquer splits a problem into same-kind sub-problems, solves each recursively, and combines the results. It fits problems that split cleanly with non-overlapping parts, and halving each step gives O(n log n) or O(log n). Merge sort, quicksort, and binary search are the classics.

Question 7

What is a greedy algorithm?

Accepted Answer

Answer: A greedy algorithm builds a solution one step at a time, and at each step it takes the choice that looks best right now (the locally optimal choice), never reconsidering. It does not look ahead or backtrack. It is fast and simple, but it only gives the correct overall answer for problems with a special property (a 'greedy choice' property). For many problems greedy gives a wrong or merely-okay answer, and you need dynamic programming instead. Classic correct uses: making change with standard coin denominations (take the biggest coin that fits, repeat), Dijkstra's shortest path, Huffman coding, and interval scheduling (always pick the meeting that ends earliest). Analogy: hiking to the highest peak by always stepping toward the steepest upward slope. Works if there is one smooth hill; fails if you can get stuck on a small hill next to a bigger one. In an interview: A greedy algorithm makes the best-looking choice at each step and never revisits it. It is fast and correct only for problems with the greedy-choice property, like standard-coin change, Dijkstra, and interval scheduling. Otherwise you need dynamic programming.

Question 8

What is dynamic programming?

Accepted Answer

Answer: Dynamic programming (DP) solves a problem by breaking it into overlapping sub-problems, solving each sub-problem once, and storing the answer so you never recompute it. Two signs a problem is DP: it has optimal substructure (the best answer is built from best answers to sub-problems), and overlapping sub-problems (the same sub-problem comes up many times). Two styles: - Top-down (memoisation): normal recursion, but cache each result in a map or array. - Bottom-up (tabulation): fill a table from the smallest sub-problems up to the answer, with a loop. Naive Fibonacci recursion is O(2 to the n) because it recomputes; with DP it is O(n). Other examples: coin change (minimum coins), the knapsack problem, longest common subsequence (used by diff tools and spell checkers). Analogy: doing a big jigsaw by solving small corner sections once and writing down how they fit, so you never re-solve the same corner. In an interview: Dynamic programming breaks a problem into overlapping sub-problems, solves each once, and stores the result. It applies when the problem has optimal substructure and repeated sub-problems. You do it top-down with memoisation or bottom-up with a table. It turns exponential recursion into linear or polynomial time.

Question 9

What is backtracking?

Accepted Answer

Answer: Backtracking builds a solution one choice at a time, and as soon as a partial solution cannot possibly lead to a valid full solution, it undoes the last choice ('backtracks') and tries a different one. It is a smarter brute force: it prunes whole branches instead of exploring every combination. The shape is recursive: try a choice, recurse, and if that fails, undo the choice and try the next. Examples: solving a Sudoku (place a digit, recurse, erase it if it leads to a dead end), the N-Queens puzzle, generating all permutations or subsets, and finding a path through a maze. Analogy: exploring a maze by always keeping one hand on the wall. When you hit a dead end you walk back to the last junction and take a different turn, instead of teleporting to random spots. In an interview: Backtracking builds a solution incrementally and abandons a partial path the moment it cannot lead to a valid answer, undoing the last choice and trying another. It is brute force with pruning. Sudoku solvers, N-Queens, permutations, and maze pathfinding use it.

Question 10

What is Big-O notation, and why do we use it?

Accepted Answer

Answer: Big-O describes how the running time (or memory) of an algorithm grows as the input gets bigger. It ignores constants and small terms and keeps only the fastest-growing part. Why: real machines differ, and small inputs are always fast. What actually matters is how the cost scales when n goes from 1,000 to 1,000,000. If an algorithm is O(n) it roughly doubles when the input doubles. If it is O(n squared) it goes up four times. That difference decides whether something finishes in a second or an hour. We usually talk about the worst case, because that is the guarantee you can rely on. Analogy: Big-O is like comparing the shape of two curves, not their exact height. A flatter curve always wins once the input is large enough. In an interview: Big-O is the growth rate of cost as input grows, with constants dropped. I always state the worst case unless asked otherwise, and I compare algorithms by which curve wins for large n.

Question 11

What is the difference between time complexity and space complexity?

Accepted Answer

Answer: Time complexity is how the number of operations grows with input size. Space complexity is how much extra memory the algorithm needs, beyond the input itself, as the input grows. They often trade off. A hash map can turn an O(n squared) time solution into O(n) time, but it costs O(n) extra space. Sorting in place uses O(1) extra space; merge sort uses O(n) extra space for the temporary arrays. In interviews, give both. "This is O(n) time and O(n) space" is a complete answer. Analogy: time is how long the work takes, space is how big a desk you need to do it on. Often you can go faster by using a bigger desk. In an interview: Time is operation count growth, space is extra memory growth. I quote both, and I mention the trade-off when there is one, usually spending memory to save time.

Question 12

What does "amortised" time mean, for example pushing to a dynamic array?

Accepted Answer

Answer: Amortised time is the average cost per operation over a long run, even if a few individual operations are expensive. A dynamic array (ArrayList, Python list, vector) usually appends in O(1). But when it fills up, it allocates a bigger block (typically double the size) and copies everything over, which is O(n) for that one push. Because the array doubles, those expensive copies happen rarely and get rarer as the array grows. If you add up the cost of n pushes including the occasional big copy, it comes to about 2n total, which is O(1) per push on average. So we say append is amortised O(1). Analogy: like a phone bill that is mostly small but has a big charge once a year. Spread over the year, the monthly cost is still low. In an interview: Amortised means average per operation across many operations. Array append is amortised O(1): most pushes are cheap, the resize copies are rare because the capacity doubles, so the total stays linear.

Question 13

Two Sum: given an array and a target, return the indices of the two numbers that add up to the target. Give a brute force answer, then optimise.

Accepted Answer

Answer: Walk the array once, keeping a hash map of value to index. For each number, check if (target minus this number) is already in the map. If it is, you have the pair. If not, add the current number to the map. This is O(n) time and O(n) space. Brute force first: two nested loops trying every pair. That is O(n squared) time and O(1) space. It works but is slow for large arrays. The optimisation: instead of searching the rest of the array for the partner each time (the inner loop), remember what you have seen in a hash map so the lookup is O(1). One pass, done. Analogy: instead of asking 'is my partner somewhere ahead of me', write down everyone you have already met, then just check if your partner is on that list. In an interview: Brute force is the nested loop at O(n squared). The optimisation is a hash map of seen values so the partner lookup becomes O(1), giving one pass at O(n) time and O(n) space.

Question 14

How do you check if one string is a rotation of another? For example "erbottlewat" is a rotation of "waterbottle".

Accepted Answer

Answer: First check the two strings are the same length. Then check whether the second string appears inside (first string + first string). If it does, it is a rotation. Why it works: concatenating the original with itself contains every possible rotation of it as a substring. "waterbottlewaterbottle" contains "erbottlewat" starting at index 3. Time is O(n) if your substring search is linear, O(n squared) with a naive search. Space is O(n) for the doubled string. Analogy: if you write the word twice in a circle, every rotation of it is just a window sliding around that circle. Doubling the string flattens the circle out. In an interview: Check equal lengths, then check if b is a substring of a+a. Doubling a contains all its rotations, so one substring search settles it.

Question 15

How do you check if a string is a palindrome? Give more than one method.

Accepted Answer

Answer: The cleanest is the two-pointer method. Put one pointer at the start and one at the end. Compare the characters. If they differ, it is not a palindrome. If they match, move both pointers inward. Stop when they meet. O(n) time, O(1) space. Other methods: Reverse and compare: build the reversed string and check it equals the original. Simple, but O(n) extra space. Recursion: check the first and last characters match, then recurse on the middle. O(n) time but O(n) space for the call stack. In a real interview, mention that you would first decide whether to ignore case and non-letters. Analogy: two people reading the word from opposite ends toward the middle, checking they say the same letters at the same time. In an interview: Two pointers from both ends moving inward, O(n) time and O(1) space. I would also name reverse-and-compare and the recursive version, and ask whether case and punctuation matter.

Question 16

Maximum Product Subarray: find the largest product of a contiguous run of numbers in an array.

Accepted Answer

Answer: Scan once, tracking both the largest product ending here and the smallest product ending here. You need the smallest because a negative number times a very negative number becomes a large positive. At each element, the new max is the biggest of: the element itself, element times previous max, element times previous min. The new min is the smallest of those same three. Keep a running answer of the best max seen. O(n) time, O(1) space. The trick is remembering that a negative value flips max and min, so you carry both. Analogy: a big negative running product is not a dead end, it is a loaded spring. The next negative number could snap it into a huge positive, so you keep track of the most negative value too. In an interview: One pass tracking the max and the min product ending at each index, because a negative number swaps them. New max and min each come from {x, x*max, x*min}. O(n) time, O(1) space.

Question 17

What is the two-pointer technique and when do you use it?

Accepted Answer

Answer: You keep two indices into an array or string and move them based on a rule, instead of using nested loops. It turns many O(n squared) problems into O(n). Two common shapes: Opposite ends: one pointer at the start, one at the end, moving toward each other. Used for palindromes, reversing, and 'find a pair that sums to X' in a sorted array. Same direction (fast and slow): both start at the front, one moves faster or only advances on a condition. Used for removing duplicates in place, cycle detection, and sliding windows. Analogy: instead of one person checking every pair, put a person at each end of the row and let them walk toward each other, deciding who steps next. In an interview: Two indices moved by a rule instead of nested loops. Opposite-ends for sorted-array pair problems and palindromes, fast-and-slow for in-place edits and cycle detection. It often drops O(n squared) to O(n).

Question 18

What is the sliding window technique?

Accepted Answer

Answer: You keep a 'window' (a contiguous range) over an array or string, defined by a left and right index. You expand the right side to include more, and shrink the left side when the window breaks a condition. Each element enters and leaves the window at most once, so it is O(n). Use it for 'longest / shortest / max-sum contiguous subarray or substring that satisfies some condition', for example the longest substring with no repeated characters, or the smallest subarray with a sum at least K. Analogy: a window on a train sliding along the track. You only ever see a contiguous stretch, and you slide it forward rather than jumping around. In an interview: A left and right index bounding a contiguous window. Grow the right, shrink the left when a rule breaks. Each element is touched a constant number of times, so it is O(n). Good for longest/shortest contiguous-run problems.

Question 19

You are given a sorted list of numbers from a known range with exactly one missing. Find it in O(n) (or better).

Accepted Answer

Answer: If the numbers are 1 to n with one missing, the sum of 1 to n is n(n+1)/2. Add up the array and subtract it from that expected sum. The difference is the missing number. O(n) time, O(1) space. Another O(n) way with no overflow risk: XOR all the numbers from 1 to n together, then XOR that with every number in the array. Pairs cancel out and you are left with the missing one. If the list is sorted, you can also binary search for the first index where the value does not equal its expected value, which is O(log n). For 'missing prime in a range', you cannot use the sum formula, so you walk the range generating primes and compare against the array as you go, which is O(n) over the range. Analogy: you know what the full set should add up to. Whatever is missing shows up as the gap between the expected total and the actual total. In an interview: For 1..n, expected sum minus actual sum gives the missing number in O(n), O(1). XOR is the overflow-safe version. If sorted, binary search the first mismatched index for O(log n).

Question 20

How is an array stored in memory, and how does that make access O(1)?

Accepted Answer

Answer: An array is a single continuous block of memory. All the elements sit next to each other, and every element of a given type takes the same number of bytes. Because of that, the computer finds element i by arithmetic, not by searching: address of a[i] = base address + i * size of one element That is a single calculation, so access by index is O(1), the same cost whether i is 0 or 1,000,000. This is called random access. The trade-off: inserting or deleting in the middle is O(n) because every later element must shift to keep the block continuous, and the size is fixed at creation (a dynamic array like ArrayList works around this by allocating a bigger block and copying when it fills). A 2D array is still one continuous 1D block underneath, laid out row by row (row-major order, as in C and Java) or column by column (column-major, as in Fortran and MATLAB). Analogy: a row of identical numbered lockers built into a wall. You do not search for locker 40, you walk straight to it, because you know each locker's width and where the row starts. In an interview: An array is one continuous memory block with fixed-size elements, so the address of element i is base + i * element size, a single calculation, which makes indexed access O(1). The cost is O(n) mid-array insertion because elements must shift, and a fixed size. 2D arrays are stored as one block, row by row.

Question 21

Name the common sorting algorithms and their time complexities.

Accepted Answer

Answer: Bubble, insertion, selection sort: O(n squared) average and worst. Simple, in place. Insertion sort is fast on nearly-sorted data (close to O(n)). Merge sort: O(n log n) always. Stable. Needs O(n) extra space. Quicksort: O(n log n) average, O(n squared) worst (rare, from bad pivots). In place. Usually the fastest in practice. Heap sort: O(n log n) always. In place. Not stable. Counting / radix sort: O(n + k) or O(nk), not comparison-based, only for integers or fixed-size keys in a limited range. No comparison sort can beat O(n log n) in the worst case. Analogy: the O(n squared) ones are the toys you learn on. The O(n log n) ones are what real libraries use, and quicksort usually wins on speed despite its bad worst case. In an interview: The simple ones (bubble, insertion, selection) are O(n squared). Merge and heap sort are O(n log n) guaranteed. Quicksort is O(n log n) average and the fastest in practice, with a rare O(n squared) worst case. Comparison sorts cannot beat O(n log n).

Question 22

Explain merge sort and write the pseudocode.

Accepted Answer

Answer: Merge sort is divide and conquer. Split the array in half, sort each half by calling merge sort on it, then merge the two sorted halves into one sorted array. The merge step walks both halves with two pointers, always taking the smaller front element, so it is O(n) per level. There are log n levels of splitting, so the total is O(n log n), always, regardless of the input. It is stable (equal elements keep their order) and it needs O(n) extra space for the merged output. It is the standard choice when you need a guaranteed O(n log n) or a stable sort, or when sorting linked lists. Analogy: sorting a huge stack of exam papers: split it among helpers, each helper sorts their smaller pile, then you zip the sorted piles together by repeatedly taking the lower name off the top. In an interview: Split in half, recursively sort each half, merge the two sorted halves with a two-pointer walk. log n levels times O(n) merge work equals O(n log n) guaranteed. Stable, O(n) extra space.

Question 23

Explain quicksort. How does it pick a pivot, and what is the worst case?

Accepted Answer

Answer: Quicksort is also divide and conquer, but it divides by value instead of position. Pick a pivot element. Partition the array so everything smaller than the pivot is on the left and everything larger is on the right. The pivot is now in its final place. Recurse on the left part and the right part. Pivot choice matters. A fixed pivot (always the first or last element) gives O(n squared) on already-sorted input, because every partition is lopsided. Real implementations pick the median of three elements, or a random element, which makes the bad case extremely unlikely. Average case is O(n log n) and it is usually faster than merge sort because it sorts in place with good cache behaviour. Worst case is O(n squared). It is not stable. Analogy: line everyone up by height. Pick one person, send shorter people left and taller people right. That person is now in the right spot. Repeat on each side. In an interview: Pick a pivot, partition smaller-left larger-right, recurse on each side. A random or median-of-three pivot avoids the O(n squared) worst case that a fixed pivot hits on sorted input. Average O(n log n), in place, not stable.

Question 24

When is a simple O(n squared) sort actually the right choice, and what does "stable" mean?

Accepted Answer

Answer: Insertion sort is genuinely the best choice for very small arrays (say under about 10 to 20 elements) and for data that is already almost sorted, where it runs close to O(n). This is why real library sorts (like Timsort and introsort) switch to insertion sort for small chunks. A sort is stable if two elements that compare equal keep their original relative order. This matters when you sort by one key after already sorting by another: a stable sort by 'last name' will keep people with the same last name in first-name order from the earlier sort. Merge sort and insertion sort are stable; quicksort and heap sort are not. Analogy: for a handful of items, the fancy algorithm's setup cost is not worth it, like using a food processor to chop one clove of garlic. And 'stable' means the sort does not shuffle ties. In an interview: Insertion sort beats the O(n log n) sorts on tiny or nearly-sorted arrays, which is why library sorts fall back to it. Stable means equal elements keep their original order, which matters when you sort by multiple keys in turn.

Question 25

Explain binary search and write it. What is its time complexity?

Accepted Answer

Answer: Binary search finds a value in a sorted array by repeatedly halving the search range. Look at the middle element. If it is the target, done. If the target is smaller, search the left half. If larger, search the right half. Repeat until found or the range is empty. Each step throws away half the remaining elements, so it takes about log base 2 of n steps. Time is O(log n), space is O(1) for the loop version (O(log n) for the recursive version, from the call stack). The array must be sorted for this to work. Analogy: finding a word in a dictionary. You open to the middle, see if your word is before or after, and keep halving. You never read every page. In an interview: Halve the sorted range each step by comparing to the middle element. O(log n) time, O(1) space. The precondition is that the array is sorted.

Question 26

What are the common bugs when implementing binary search?

Accepted Answer

Answer: The classic ones: 1. Integer overflow in the midpoint. Writing (lo + hi) / 2 can overflow for large indices. Use lo + (hi - lo) / 2 instead. 2. Wrong loop condition. Using lo < hi instead of lo <= hi (or the reverse) can skip the last element or loop forever, depending on how you update the bounds. 3. Not moving the bounds past mid. Setting lo = mid instead of lo = mid + 1 can loop forever when lo and hi are adjacent. 4. Off-by-one in variants. 'Find the first element >= target' or 'find the insertion point' need careful handling of which side keeps mid. The safe habit: pick one template, know exactly what it returns, and test on arrays of size 0, 1, and 2. Analogy: binary search is short but easy to get wrong. Almost every bug is in the middle calculation, the loop condition, or how far you move the bounds. In an interview: Overflow in (lo+hi)/2, the wrong loop condition, and failing to move the bound past mid so it loops forever. I pick one template, know its exact contract, and test the tiny cases.

Question 27

How does a hash map (hash table) work internally?

Accepted Answer

Answer: A hash map stores key-value pairs in an array of 'buckets'. To store a key, it runs the key through a hash function to get a number, then takes that number modulo the array size to pick a bucket, and puts the entry there. To look a key up, it does the same calculation and goes straight to that bucket. Because the bucket is found by direct calculation, not by searching, get and put are O(1) on average. Two keys can land in the same bucket (a collision). The map handles that by keeping a small list (or, in modern Java HashMap, a balanced tree once a bucket gets large) in each bucket, and comparing keys with equals() to find the right one. When the map gets too full (past a 'load factor', often 0.75), it grows the array and re-places every entry. This resize is O(n) but rare. Analogy: a cloakroom with numbered pegs. The hash function turns your coat into a peg number, so you walk straight to peg 12 instead of checking every peg. In an interview: Keys are hashed to a bucket index in an array, so access is direct and O(1) on average. Collisions go into a per-bucket list or tree compared by equals(). Passing the load factor triggers an O(n) resize and rehash.

Question 28

What is a hash collision, and how is it handled?

Accepted Answer

Answer: A collision is when two different keys hash to the same bucket. It is unavoidable, because there are more possible keys than buckets. Two common strategies: Separate chaining: each bucket holds a list of entries. On collision, you append to that list and search it on lookup. Java's HashMap uses this, and converts a bucket to a balanced tree if it grows past 8 entries, so a bad bucket degrades to O(log n) instead of O(n). Open addressing: if a bucket is taken, probe for the next free slot by a rule (linear or quadratic probing). No lists, better cache behaviour, but it needs careful handling of deletions and stays efficient only at lower load factors. Analogy: two people assigned the same cloakroom peg. Chaining hangs both coats on one peg with name tags. Open addressing moves the second coat to the next empty peg. In an interview: Two keys hitting the same bucket. Separate chaining keeps a list (or tree) per bucket; open addressing probes for the next free slot. Java HashMap chains and treeifies long buckets.

Question 29

When does a hash map degrade from O(1) to O(n)?

Accepted Answer

Answer: When too many keys land in the same bucket. If every key hashes to the same value, every entry is in one bucket and a lookup scans the whole list, which is O(n). Causes: a bad hash function that does not spread keys out, or keys deliberately chosen by an attacker to all collide (a 'hash flooding' denial-of-service attack). A poorly overridden hashCode() in Java, for example one that returns a constant, does this. Defences: a good hash function, randomised hashing seeds, and, in Java's HashMap, converting an overloaded bucket into a balanced tree so the worst case is O(log n) rather than O(n). Also, your key's hashCode() and equals() must be consistent: equal objects must have equal hash codes. Analogy: the cloakroom works only if coats spread across all the pegs. If the hash function puts every coat on peg 1, you are back to checking every coat. In an interview: When keys cluster into one bucket, from a weak hashCode or a crafted attack, lookups scan a long list at O(n). A good hash function, hash randomisation, and treeifying long buckets keep it near O(1).

Question 30

Array versus linked list: when do you use which?

Accepted Answer

Answer: Array: elements sit next to each other in memory. Access by index is O(1). Inserting or deleting in the middle is O(n) because everything after has to shift. Great cache behaviour. Use it when you mostly read by position and the size is fairly stable. Linked list: each node holds a value and a pointer to the next node, scattered in memory. Access by index is O(n) because you walk from the head. Inserting or deleting is O(1) once you have the node. Poor cache behaviour, extra memory for the pointers. Use it when you do a lot of inserts and deletes at the ends or at a known node. In practice, arrays (and dynamic arrays like ArrayList) win most of the time because of cache performance. Analogy: an array is a row of numbered lockers, you jump straight to locker 40. A linked list is a treasure hunt where each clue points to the next spot. In an interview: Array for index access and cache performance, linked list for cheap inserts and deletes at a known position. Arrays usually win in practice because contiguous memory is fast.

Question 31

How do you detect a cycle in a linked list?

Accepted Answer

Answer: Use two pointers, a slow one that moves one node at a time and a fast one that moves two nodes at a time (Floyd's cycle detection, also called the tortoise and hare). If the list ends, the fast pointer reaches null and there is no cycle. If there is a cycle, the fast pointer will eventually lap the slow one and they will land on the same node. O(n) time, O(1) space. A hash set of visited nodes also works but costs O(n) space. Analogy: two runners on a track, one twice as fast. On a straight track the fast one finishes and leaves. On a circular track the fast one eventually catches up and taps the slow one on the shoulder. In an interview: Floyd's tortoise and hare: a slow pointer moving one step, a fast pointer moving two. They meet inside a cycle; the fast pointer hits null if there is none. O(n) time, O(1) space.

Question 32

Balanced parentheses: check whether a string of brackets is correctly balanced, for example "{[()]}".

Accepted Answer

Answer: Use a stack. Scan the string. When you see an opening bracket, push it. When you see a closing bracket, pop the stack and check it matches the right kind of opener. If the stack is empty when you need to pop, or the types do not match, it is unbalanced. At the end, the string is balanced only if the stack is empty. O(n) time, O(n) space in the worst case (all opening brackets). This is the same idea a compiler uses to check that code blocks and expressions are nested correctly. Analogy: a stack of plates. Every time you open a bracket you add a plate. Every time you close one you must take off the matching top plate. If the plates ever mismatch, or any are left over, it is broken. In an interview: Push openers onto a stack, and on each closer pop and check the type matches. Unbalanced if you pop an empty stack, hit a type mismatch, or finish with a non-empty stack. O(n) time and space.

Question 33

When do you reach for a stack versus a queue?

Accepted Answer

Answer: Stack is last in, first out (LIFO). The most recently added item comes out first. Use it for: undo/redo, matching brackets, the function call stack, depth-first search, and 'evaluate this expression'. Queue is first in, first out (FIFO). Items come out in the order they went in. Use it for: task scheduling, breadth-first search, buffering a stream of work, and anything 'process in arrival order'. Both offer O(1) add and remove. The choice is purely about the order you need things back. Analogy: a stack is a pile of plates, you take the top one. A queue is a line at a shop, the person who has waited longest is served next. In an interview: Stack is LIFO for undo, bracket matching, and DFS. Queue is FIFO for scheduling, buffering, and BFS. Both are O(1) at the ends; pick by the order you need items back.

Question 34

How do you insert a node at the head, the tail, and a given position of a singly linked list?

Accepted Answer

Answer: At the head: point the new node's next at the current head, then make the new node the head. O(1). At the tail: walk from the head until you reach the last node (the one whose next is null), then set its next to the new node. O(n), unless you keep a tail pointer, then O(1). At position k: walk to the node at index k-1, then splice the new node in: newNode.next = prev.next; prev.next = newNode. O(k). The rule for every linked-list edit: set the new node's link first, then update the old link, so you never lose the rest of the list. Analogy: adding a carriage to a train. Hook the new carriage to the one behind it first, then unhook and rehook the one in front. Never let go of the back half. In an interview: Head insert is O(1): new.next = head, head = new. Tail is O(n) walking to the last node, or O(1) with a tail pointer. Position k is O(k) to the node before, then splice. Always link the new node before rewiring the old link.

Question 35

How do you delete a node from a singly linked list, including a node in the middle?

Accepted Answer

Answer: To delete a node you need the node before it. Walk to the previous node, then set prev.next = nodeToDelete.next, which skips over it. O(n) to find it. Deleting the head is a special case: head = head.next. A famous trick: if you are given only a pointer to the node to delete (not the head, and it is not the last node), copy the next node's value into this node, then delete the next node instead. You cannot do this for the last node. Analogy: removing a carriage: the carriage in front reaches past the one you are removing and hooks directly to the one behind it. In an interview: Find the previous node and set prev.next = node.next to unlink it, O(n). Head deletion is head = head.next. If you only have the node itself and it is not the last, copy the next node's value in and skip the next node.

Question 36

How do you find the middle node of a linked list in one pass?

Accepted Answer

Answer: Use two pointers. A slow pointer moves one node at a time; a fast pointer moves two. When the fast pointer reaches the end, the slow pointer is at the middle. One pass, O(n) time, O(1) space. For an even-length list, this lands slow on the second of the two middle nodes; start fast at head.next if you want the first middle instead. The naive way is to count the length in one pass, then walk half of it in a second pass. The two-pointer version does it in a single pass. Analogy: two walkers on the same path, one going twice as fast. When the fast one reaches the end, the slow one is exactly halfway. In an interview: Slow and fast pointers: slow moves one, fast moves two. When fast hits the end, slow is at the middle. Single pass, O(n) time, O(1) space, no length count needed.

Question 37

What are the types of linked list, and what does a doubly linked list buy you?

Accepted Answer

Answer: Three kinds: Singly linked list (SLL): each node has a value and a pointer to the next node only. You can walk forward, not backward. To delete a node you need a pointer to the node BEFORE it, so finding it is O(n). Doubly linked list (DLL): each node also has a pointer to the previous node. You can walk both ways, and if you already hold a pointer to a node you can delete it in O(1) (you have its prev and next). The cost is an extra pointer per node and more bookkeeping on every insert and delete. Circular linked list (CLL): the last node points back to the first instead of to null, so you can loop around forever. Useful for round-robin scheduling (CPU time slices, turn-based games) and buffers that wrap. A DLL with a tail pointer also makes 'insert at the end' and 'delete the last node' O(1). Analogy: SLL is a one-way street, DLL is a two-way street, CLL is a roundabout. In an interview: Singly linked lists point forward only. Doubly linked lists add a prev pointer, so you can traverse backward and delete a known node in O(1), at the cost of an extra pointer per node. Circular linked lists have the last node point to the first, for round-robin scheduling and wrap-around buffers.

Question 38

What is the difference between a binary tree and a binary search tree?

Accepted Answer

Answer: A binary tree is any tree where each node has at most two children (left and right). There is no rule about the values. A binary search tree (BST) adds an ordering rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This rule is what makes search fast: at each node you know which way to go, so you can find, insert, or delete in O(h) where h is the height of the tree. If the BST is balanced, h is about log n, so those operations are O(log n). If it is unbalanced (for example you inserted sorted data), it can degrade to a straight line and O(n). Analogy: a binary tree is just a shape. A binary search tree is that shape with a filing rule: smaller things always go left, bigger things always go right, so you can zero in on any value. In an interview: A binary tree just limits each node to two children. A BST adds the rule left subtree < node < right subtree, which lets you search, insert, and delete in O(height), which is O(log n) when balanced and O(n) when it degenerates to a list.

Question 39

Write pseudocode to insert into and search a binary search tree.

Accepted Answer

Answer: Both operations follow the same path down the tree, going left when the target is smaller than the current node and right when it is larger. Search: start at the root. If the node is null, not found. If the value matches, found. If the target is smaller, recurse left; otherwise recurse right. Insert: follow the same path until you reach a null spot, then put the new node there. Duplicates are usually either ignored or sent consistently to one side. Both are O(h): O(log n) on a balanced tree, O(n) on a badly unbalanced one. Analogy: you are playing a number guessing game where each node tells you 'go lower' or 'go higher'. Insert just means walking until the trail runs out and dropping your node there. In an interview: Both walk down the tree comparing to each node: go left if smaller, right if larger. Search stops at a match or null. Insert stops at the first null slot and puts the node there. O(height).

Question 40

What are the tree traversals, and when do you use each?

Accepted Answer

Answer: There are four common ways to visit every node. Inorder (left, node, right): on a BST, this visits values in sorted order. Use it to print a BST sorted or to check it is valid. Preorder (node, left, right): visits a parent before its children. Use it to copy a tree or to serialise it. Postorder (left, right, node): visits children before the parent. Use it to delete a tree or to compute a value that depends on the subtrees (like folder sizes). Level-order (breadth-first): visits the tree row by row, using a queue. Use it for shortest-path-by-edges and 'process level by level'. The first three are depth-first and use recursion or a stack. Level-order uses a queue. Analogy: inorder, preorder, postorder differ only in when you 'deal with' the current node: before, between, or after its children. Level-order is reading the tree like lines on a page. In an interview: Inorder gives sorted order on a BST, preorder is for copying or serialising, postorder is for deleting or bottom-up aggregation, and level-order (a queue) walks row by row for edge-count shortest paths.

Question 41

What happens if a BST becomes unbalanced, and what is a self-balancing tree?

Accepted Answer

Answer: If you insert already-sorted data into a plain BST, each new value goes to the same side every time, so the tree becomes a straight line. Its height is n, and search, insert, and delete all become O(n), no better than a linked list. Self-balancing trees fix this by doing small local rearrangements (rotations) after each insert or delete to keep the height around log n. AVL trees keep it very strictly balanced (faster lookups, more rotations). Red-black trees keep it roughly balanced (fewer rotations, slightly taller); Java's TreeMap and C++'s std::map use red-black trees. Databases use B-trees and B+ trees, which are balanced trees with many children per node, tuned for reading whole disk pages at once. Analogy: a plain BST fed sorted data collapses into a walking stick. A self-balancing tree keeps nudging itself back into a bushy shape so no branch gets too long. In an interview: An unbalanced BST degrades to a linked list at O(n). Self-balancing trees (AVL, red-black) rotate after each change to keep height about log n. Databases use B-trees for the same idea tuned to disk pages.

Question 42

How should you approach a coding problem in an interview?

Accepted Answer

Answer: A clear order helps: 1. Clarify. Restate the problem. Ask about input size, types, duplicates, empty input, negative numbers, and whether the input is sorted. 2. Examples. Work one small example by hand, and one edge case. 3. Brute force first. Say the obvious O(n squared) or O(n!) solution out loud and give its complexity. This shows you can always produce something. 4. Optimise. Look for repeated work you can cache (hash map), structure you can exploit (sorted input, two pointers), or a known pattern. 5. State the plan, then code it. Keep talking while you type. 6. Test. Run through your example and the edge cases line by line. Fix bugs calmly. 7. Give the final time and space complexity. Analogy: the interviewer is grading your process. Talking through a clear brute-force-then-optimise path beats jumping silently to a clever answer that has a bug. In an interview: Clarify, do an example, give brute force with its complexity, then optimise by removing repeated work or using structure, code while narrating, trace test cases, and finish with the final Big-O.

Question 43

What patterns cover most coding interview questions?

Accepted Answer

Answer: A handful of patterns solve the large majority: Hashing: use a map or set to remember what you have seen, turning O(n squared) lookups into O(n) (Two Sum, duplicates, anagrams). Two pointers: opposite ends on a sorted array, or fast/slow on a list (pair sums, palindromes, cycle detection). Sliding window: a growing/shrinking contiguous range for 'longest/shortest subarray or substring with a property'. Binary search: on a sorted array, or on the answer itself ('smallest capacity that works'). BFS / DFS: for anything that is a graph or a tree, including grids. Sorting first: many problems become easy once the input is sorted. Stack: nesting, 'next greater element', expression evaluation. Dynamic programming: overlapping subproblems, 'count the ways' or 'best value' where a choice at each step depends on earlier choices. Analogy: most problems are a known pattern wearing a costume. Recognising 'this is a sliding window' is 80 percent of the work. In an interview: Hashing, two pointers, sliding window, binary search, BFS/DFS, sort-first, stack, and dynamic programming. I try to match the problem to one of these before inventing anything.

Question 44

Reverse an array in place, without using a second array.

Accepted Answer

Answer: Swap the first and last elements, then the second and second-to-last, and so on, walking two pointers toward the middle. Stop when they meet. O(n) time, O(1) extra space. The 'in place' part is the point: you are not allowed a temporary copy of the whole array, only a single temp variable for the swap (or a swap trick). Analogy: two people at opposite ends of a row of chairs, swapping seats and stepping toward the middle until they meet. In an interview: Two pointers from both ends, swap and move inward until they cross. O(n) time, O(1) space, no second array.

Question 45

Convert a string like "1234" into the integer 1234, without using built-in parsing.

Accepted Answer

Answer: Walk the string left to right. Start with result = 0. For each character, turn it into its digit (character code minus the code of '0'), then do result = result * 10 + digit. This shifts the running number one place left and adds the new digit. Handle a leading '-' or '+', and reject or skip anything that is not a digit. Watch for overflow on very long inputs. Analogy: building the number the way you read it aloud: 1, then 'one-two' is 12, then 'one-two-three' is 123. Each new digit means multiply what you have by 10 and add. In an interview: Loop the characters, result = result * 10 + (c - '0'), after handling an optional sign and rejecting non-digits. It builds the number digit by digit the way you read it.

Question 46

Find the largest and the second largest number in an array, in one pass.

Accepted Answer

Answer: Keep two variables, largest and second, both starting very small. For each number: if it is bigger than largest, then second becomes the old largest and largest becomes this number; else if it is bigger than second (and not equal to largest), second becomes this number. O(n) time, O(1) space. The mistake to avoid: sorting the array (O(n log n)) when one pass is enough. Also decide what to do if all elements are equal or the array has one element. Analogy: watching a race and only remembering the fastest two runners so far. When someone overtakes the leader, the old leader drops to second. In an interview: One pass tracking largest and second. When a new value beats largest, largest becomes second. O(n), no sorting. I would clarify the tie and single-element behaviour.

Question 47

Count how many times each character appears in a string.

Accepted Answer

Answer: Use a hash map from character to count. Walk the string once; for each character, add 1 to its entry (creating it at 0 first if missing). O(n) time, O(k) space where k is the number of distinct characters. If the input is limited to lowercase letters, you can use an int array of size 26 instead of a map, which is faster and O(1) space. Analogy: going down a shelf of books and adding a tally mark next to each author's name as you pass their books. In an interview: A hash map of character to count, one pass with a +1 per character. For a fixed alphabet like a-z, a size-26 int array is faster and O(1) space.

Question 48

Check whether a string contains any duplicate characters, using a single loop.

Accepted Answer

Answer: Keep a set of characters seen so far. Walk the string once. For each character, if it is already in the set, return true (there is a duplicate). Otherwise add it. If you finish the loop, return false. O(n) time, O(k) space. The naive version uses two nested loops comparing every pair, which is O(n squared). The set turns the inner search into an O(1) lookup, so it becomes one loop at O(n). Analogy: checking a guest list as people arrive: the moment you tick a name that is already ticked, you have a duplicate. In an interview: A HashSet of seen characters, one loop: if add() returns false the character was already there. O(n), replacing the O(n squared) nested-loop comparison.

Question 49

Split a sentence into words, where words are separated by spaces, commas, or full stops.

Accepted Answer

Answer: Split on a set of delimiters. In Java, use a regular expression that matches one or more of those characters: s.split("[ ,.]+"). Filter out any empty strings that a leading delimiter can produce. By hand, without a regex: walk the string building up the current word; whenever you hit a delimiter, if the current word is non-empty, add it to the result and reset. Add the last word after the loop. Analogy: cutting a string of beads wherever you see a knot, a clip, or a bead of a certain colour, and keeping each segment. In an interview: Split on the delimiter set with a regex like [ ,.]+ and drop empties, or walk the string building each word and flushing it on any delimiter.

Question 50

Print a star pattern (a right triangle of n rows).

Accepted Answer

Answer: An outer loop for each row (1 to n) and an inner loop that prints that many stars, then a newline. That is the whole idea behind pattern questions: the row number controls how many characters the inner loop prints. Time is O(n squared) for the printing, which is unavoidable since there are that many characters. Variations (pyramid, inverted, number triangle) just change how many spaces and characters the inner loop prints per row. Analogy: a staircase: row 1 has one step, row 2 has two, and so on. The row number is the step count. In an interview: Outer loop per row, inner loop prints (row) characters then a newline. Pattern questions are all this: the row index drives the inner loop count, with spaces added for pyramids.

Question 51

Write factorial both iteratively and recursively.

Accepted Answer

Answer: Iterative: start with result = 1, multiply by every number from 2 to n. O(n) time, O(1) space. Recursive: factorial(n) = n * factorial(n - 1), with factorial(0) = 1 as the base case. O(n) time, O(n) space for the call stack. Both overflow quickly (factorial of 21 exceeds a 64-bit long), so mention using BigInteger for large n. Analogy: iterative is walking up the stairs counting as you go. Recursive is asking the person one step above you for their total and multiplying by your step number. In an interview: Iterative: multiply 1 by 2..n, O(1) space. Recursive: n * factorial(n-1) with base case 1, O(n) stack. Both overflow fast, so BigInteger for large n.

Question 52

Compute the nth Fibonacci number: recursive, iterative, and memoised.

Accepted Answer

Answer: Naive recursion: fib(n) = fib(n-1) + fib(n-2). Correct but O(2^n) because it recomputes the same values over and over. Iterative: keep the last two values and loop up to n. O(n) time, O(1) space. This is the one to write. Memoised recursion: cache each fib(n) in a map or array the first time you compute it, so each value is computed once. O(n) time, O(n) space. This is the introduction to dynamic programming: overlapping subproblems solved once. Analogy: naive recursion is like re-deriving the same sub-answer every time you need it. Memoisation is writing each answer on a sticky note so you never redo it. In an interview: Naive recursion is O(2^n) from recomputation. The iterative version keeps the last two values at O(n) time and O(1) space. Memoised recursion caches each result, O(n) and O(n), and is the classic intro to dynamic programming.

Question 53

Find all prime numbers up to n (Sieve of Eratosthenes).

Accepted Answer

Answer: Make a boolean array of size n+1, all true, then mark 0 and 1 as not prime. Starting from 2, for each number still marked prime, cross out all its multiples (2p, 3p, 4p, ...). Whatever is still marked prime at the end is prime. O(n log log n) time, O(n) space, much faster than checking each number for factors. For checking a single number, trial division up to the square root of n is O(sqrt n). Analogy: line up all the numbers, then repeatedly circle the next uncircled one and cross out everything it divides. The circled ones are the primes. In an interview: The Sieve of Eratosthenes: mark all true, then for each prime cross out its multiples. O(n log log n). For one number, trial division to the square root is O(sqrt n).

Question 54

Implement a queue using two stacks.

Accepted Answer

Answer: A stack is last-in-first-out; a queue is first-in-first-out. Use two stacks, an 'in' stack and an 'out' stack. Enqueue: push onto the 'in' stack. O(1). Dequeue: if the 'out' stack is empty, pop everything from 'in' and push it onto 'out' (this reverses the order, so the oldest item is now on top). Then pop from 'out'. Each item is moved between stacks at most once, so dequeue is O(1) amortised even though a single dequeue can be O(n). Analogy: pour a stack of plates from one pile to another and the order flips. Do it once, and the plate that went in first is now on top, ready to serve. In an interview: Keep an 'in' stack and an 'out' stack. Enqueue pushes onto 'in'. Dequeue pops from 'out'; when 'out' is empty, move everything from 'in' to 'out', which reverses it so the oldest is on top. Amortised O(1) because each item transfers once.

Question 55

Rotate an array to the right by k positions, in place.

Accepted Answer

Answer: The clean O(n) time, O(1) space trick is three reversals: 1. Reverse the whole array. 2. Reverse the first k elements. 3. Reverse the remaining n minus k elements. First take k modulo n, so a k larger than the array still works. The naive way is to shift every element one place to the right, k times, which is O(n times k). The reversal trick avoids that. Analogy: to move the last few cards of a deck to the front, flip the whole deck over, then flip each of the two sections back the right way up. Everything ends up rotated. In an interview: Reverse the whole array, then reverse the first k, then reverse the rest, after taking k modulo n. O(n) time, O(1) space, versus O(n times k) for shifting one at a time.

Question 56

Plus One: given a number as an array of digits, add one to it. For example [1, 2, 9] becomes [1, 3, 0].

Accepted Answer

Answer: Walk from the last digit toward the first. If a digit is less than 9, add one to it and return, done. If a digit is 9, set it to 0 and carry on to the next digit left. If you fall off the front of the array (the number was all 9s, like [9, 9]), you need one more digit: put a 1 at the start. O(n) time. It is just primary-school column addition with a carry. Analogy: adding 1 to 199 on paper: 9 becomes 0 and carries, next 9 becomes 0 and carries, the leading 1 becomes 2. If it were 99, you write a new 1 in front to get 100. In an interview: Iterate from the last digit: if it is under 9, increment and return; if it is 9, set it to 0 and carry. If every digit was 9, prepend a 1. It is column addition with a carry, O(n).

Question 57

Given a list of [from, to] pairs like [["SL","IND"], ["PAK","USA"], ["IND","JPN"], ["JPN","PAK"]], reconstruct the full route in order.

Accepted Answer

Answer: The correct order is SL, IND, JPN, PAK, USA. Two steps: 1. Build a map from each 'from' to its 'to', and a set of all the 'to' values. 2. Find the start: the one 'from' that never appears as a 'to' (nobody travels to it). Here that is SL. 3. Follow the chain: from the start, keep looking up the next stop in the map until there is no next entry. O(n) time and space. This assumes the pairs form one simple chain with no branches or cycles. Analogy: you have a pile of 'ticket A to B' stubs. Find the city you have a ticket FROM but no ticket TO, that is where the trip began, then follow the tickets one by one. In an interview: Build a from-to map and a set of all destinations. The start is the 'from' that is never a destination. Then follow the map from the start until the chain ends. O(n), assuming a single unbranched chain.

Data structures & algorithms interview preparation

Foundations

Algorithm design strategies

Time and space complexity

Common whiteboard exercises

Arrays and strings

Sorting

Searching

Hash maps

Linked lists and stacks

Trees

How to approach coding problems