All 169 Algorithms & Data Structures quiz questions below come with a short explanation, visible right on the page — no sign-in needed. They're grouped by beginner and intermediate levels and 16 subtopics, so you can revise one part at a time. Choose Try Algorithms & Data Structures quiz above to take a scored run and review the questions you got wrong.
What the Algorithms & Data Structures quiz covers
Trees & BST16
Sorting15
Stack & Queue15
Recursion & Backtracking14
Complexity14
Linked Lists13
Graphs11
Arrays & Strings11
Hash map & set10
Overview & ADTs10
Heap & Priority Queue8
Dynamic Programming8
Postfix Notation & Expression Trees7
Search7
Binary Search6
Two Pointers & Sliding Window4
Beginner level — 39 Algorithms & Data Structures questions
Question 1·Complexity
What does Big-O notation describe about an algorithm?
A.How many lines of code the implementation takes
B.How the cost grows as the input gets larger
C.How many milliseconds the algorithm takes on a specific machine
D.The maximum RAM the process may allocate
Answer: B
Big-O describes how cost grows relative to input size n, not absolute runtime. Saying a function is O(n) means that when n doubles, the cost roughly doubles. This is how algorithms are compared independent of machine, language, or compiler quality.
Two nested loops, each running over an array of n elements, have what time complexity?
javascript
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
check(a[i], a[j])
}
}
A.O(n)
B.O(n²)
C.O(2n)
D.O(n log n)
Answer: B
O(n²). The outer loop runs n times, and each time the inner loop runs another n times, so check is called n × n times. Recognizable pattern: nested loops where both depend on n. If the inner loop runs a fixed number of times, it stays O(n).
Question 3·Arrays & Strings
Why does inserting at the front of an array cost O(n) while appending costs O(1)?
A.Inserting at the front forces every later element to shift by one
B.Because inserting at the front must recompute the array's hash
C.Because appending is buffered and written later
D.Because the start of the array is in read-only memory
Answer: A
Arrays store elements contiguously and access them with address = base + index × size. Inserting at the front increases the index of every existing element by 1, so all n elements must be shifted. Appending only writes into a free slot, giving amortised O(1).
Concatenating with s += x inside an n-iteration loop, in a language with immutable strings, leads to what?
A.O(n) cost, since the compiler always fuses the concatenations
B.A memory leak because the intermediate strings are never freed
C.A runtime error when the string exceeds its initial capacity
D.O(n²) cost, since each concatenation creates a new string and copies it
Answer: D
O(n²). Immutable strings mean s += x creates a new string and copies all previous content, so the i-th iteration costs about i steps. The total 1 + 2 + … + n is O(n²). The right approach is to collect pieces in an array and join once, or use the language's string builder.
A.The keys are kept sorted so binary search is very fast
B.Because each slot holds exactly one key so no comparison is ever needed
C.A hash function turns the key into a slot index for direct access
D.The whole table is preloaded into the CPU cache
Answer: C
The hash function turns the key into a number, and taking it modulo the number of buckets gives the slot to look in, so no elements need to be scanned. The cost is computing the hash plus a few comparisons in the bucket, independent of n. This is the average case, not a guarantee for every case.
On an array sorted ascending, two pointers at both ends look for a pair summing to a target. When the current sum is below the target, what do you do?
A.Move the left pointer one step to the right
B.Restart from the beginning with a new right pointer
C.Move both pointers inward at once
D.Move the right pointer one step to the left
Answer: A
Move the left pointer right. Since the array is ascending, only increasing the left end makes the sum larger. Conversely, if the sum is greater than the target, move the right pointer left. Each step safely eliminates one possibility, so the whole thing runs in O(n) time with O(1) space.
Why is a stack the right structure for checking whether brackets are balanced?
A.A closing bracket must match the nearest unclosed opening one
B.A stack can count the open brackets without storing them
C.A stack allows O(1) access to any element
D.A stack keeps the brackets in sorted order
Answer: A
Because the bracket rule is last in, first out: a closing bracket must match the most recent unclosed opening bracket, exactly the semantics of a stack. On an opening bracket, push; on a closing bracket, pop the top and compare. The string is valid when nothing mismatches along the way and the stack is empty at the end.
What is the mandatory precondition for applying binary search?
A.The array must be contiguous in physical memory
B.The data must sit in an array whose size is a power of two
C.The search space must have a clear monotonicity
D.The elements must all be distinct
Answer: C
The search space must be monotonic: after each comparison you must be able to conclude definitively which half contains the answer. A sorted array is the most familiar case, but the real condition is monotonicity of the predicate, not that the data itself is sorted.
Quicksort averages O(n log n) but degrades to O(n²). When does the worst case happen?
A.When the element count is not a power of two
B.When the array is too large to fit in the CPU cache
C.When the pivot is always the smallest or the largest element
D.When the array has many elements with the same value
Answer: C
When every partition is maximally unbalanced: the pivot is the smallest or largest element, so one side is empty and the other has n − 1 elements. Recursion depth becomes n, total cost O(n²). Picking a fixed pivot at the start of the array hits this case when data is already sorted.
Sort employees by department ascending, then by salary descending within a department. What is the cleanest way?
A.Concatenate department and salary into a string and sort by that
B.Group by department and sort each group with its own algorithm
C.Sort by department, then re-sort the whole thing by salary
D.One comparison function: compare departments first, then salaries when equal
Answer: D
Write a multi-key comparator: compare departments first, and only when they are equal compare salary in reverse. One sort pass is enough and the priority order sits right in the code. If the language guarantees a stable sort, sorting twice from secondary key to primary key is also correct.
A binary search tree gives O(log n) lookups but can degrade to O(n). When?
A.When the node count exceeds the CPU cache
B.When the tree has more leaves than internal nodes
C.When the tree holds both negative and positive values
D.When the tree degenerates into a straight chain
Answer: D
When the tree degenerates into a straight chain. Inserting 1, 2, 3, … in ascending order makes every node have only a right child, the height equals n, and lookup becomes linear traversal. BST cost is O(height), equal to O(log n) only when the tree is kept balanced.
To find the path with fewest edges between two vertices in an unweighted graph, what do you use?
A.Depth-first traversal, recording the shortest path found
B.Breadth-first traversal from the source vertex
C.A topological sort, then the difference of the two positions
D.Dijkstra's algorithm with a priority queue
Answer: B
BFS. Because the queue visits vertices in increasing distance order, the first time you reach the target is the fewest-edge path. Cost O(V + E). To reconstruct the path, store each vertex's parent and walk back from the target.
Which component must every recursive function have?
A.A parameter counting how many calls have been made
B.An auxiliary structure holding the intermediate results
C.A return type different from the parameter's type
D.A base case that stops without calling further
Answer: D
Base case: a branch that returns immediately without recursing again. Also, each call must move closer to the base case. With both, the function terminates; missing either one, the program runs until stack overflow.
In a binary min-heap, what does reading the minimum cost, and what does removing it cost?
A.Reading is O(log n) and removing is O(n)
B.Reading is O(log n) and removing is O(log n)
C.Reading is O(1) and removing is O(log n)
D.Reading is O(1) and removing is O(1)
Answer: C
Reading is O(1) because the smallest element is always at the root. Removal is O(log n): move the last element to the root, then sift down along the tree height. Insertion is also O(log n). In return, a heap does not let you find an arbitrary element quickly; that remains O(n).
What is the core difference between an array and a linked list when fetching the k-th element?
A.A linked list is faster since it needs no address computation
B.An array fetches it immediately while a linked list must walk k nodes
C.It depends on the language, with no general rule
D.Both fetch it immediately, differing only in how the memory is allocated
Answer: B
An array stores elements contiguously, so the address of the k-th element is computed as base + k * size — one multiplication, O(1). A linked list is scattered in memory, each node only knows the next one, so reaching the k-th element means walking through k nodes — O(k). This is the root reason behind every other trade-off between the two structures.
What stopping condition does traversing a singly linked list need?
javascript
let cur = head
while (/* ??? */) {
visit(cur.value)
cur = cur.next
}
A.cur !== head
B.cur.value !== null
C.cur.next !== null
D.cur !== null
Answer: D
The correct condition is cur !== null. In a singly linked list, the last node has next = null, so once cur becomes null you've gone past the end. Using cur.next !== null is the classic off-by-one bug: the loop stops at the last node and skips it.
Question 17·Linked Lists
In a circular linked list, what signals that a full pass is complete?
A.The starting node's value repeats
B.The pointer comes back to the starting node
C.The pointer becomes null
D.You meet a node whose next points at itself
Answer: B
When the pointer returns to the starting node. A circular list has no null anywhere, so cur !== null would loop forever. The standard pattern is a do-while loop: visit the node, advance the pointer, and repeat while cur !== start.
How does an array differ from a linked list in terms of storage?
A.The elements are always kept in sorted order
B.Each element carries an extra pointer to the next one
C.The elements are allocated separately and linked together by index
D.The elements sit contiguously in one single block of memory
Answer: D
An array stores elements contiguously in one memory block. The position of the i-th element is computed from its index, so access is O(1). In return, inserting or deleting in the middle requires shifting subsequent elements to maintain contiguity.
For computing n factorial recursively, what is the degenerate case?
A.n = 0, returning 1 without recursing further
B.When n has fallen to half its original value
C.A negative n, since the computation is meaningless
D.n = 1, since multiplying by 1 changes nothing
Answer: A
The degenerate case is n = 0, returning 1. This is the known value that requires no further recursive call, giving the call chain a stopping point. Choosing n = 1 also works for all positive n but makes the function wrong for input n = 0, which is a valid value.
What happens to a program whose recursive function has no stopping condition?
A.The compiler detects it and refuses to compile the program
B.It runs forever without stopping
C.The call stack overflows
D.The function returns the type's default value after a number of rounds
Answer: C
The program halts with a stack overflow — StackOverflowError in Java, RangeError: Maximum call stack size exceeded in JavaScript, RecursionError in Python. Every call that hasn't returned occupies a frame on the call stack; the stack has a finite size, so an infinite call chain hits the ceiling.
For the same algorithm, why is the recursive version usually slower than the loop?
A.Because the compiler cannot optimize a recursive function's body
B.Because recursion always recomputes
C.Because recursion must allocate memory dynamically for each call
D.Each call costs setting up and tearing down a stack frame
Answer: D
Because of call overhead. Each call must push arguments, save the return address, build a new frame, then pop the frame and restore state when it returns. A loop has only a jump and a compare. This difference is a constant factor and does not change the complexity class, but it is clearly measurable when call counts are large.
Question 22·Stack & Queue
How do a stack and a queue differ in their removal rule?
A.A stack removes the most recently added item while a queue removes the first
B.A stack has a size limit while a queue does not
C.A stack allows removal at both ends while a queue allows only one
D.A stack removes the smallest item while a queue removes the largest
Answer: A
A stack is LIFO — last in, first out; the element taken is the top. A queue is FIFO — first in, first out; the element taken is the front. Both restrict operations to a predetermined end; that constraint is exactly what keeps every operation O(1) and makes the structures easy to reason about.
C.When the element count falls below half the maximum capacity
D.When the element at the top holds a null value
Answer: A
Occurs when calling pop or top on an empty stack. The symmetric pair is overflow (push when full) vs underflow (pop when empty). A correct implementation must therefore check for empty and full states before operating.
Which data structure best fits multi-step undo in an editor?
A.A stack
B.A hash table
C.A search tree
D.A queue
Answer: A
Stack. Undo always targets the most recent operation, which matches LIFO. Each operation is pushed when performed and undo just pops the top and reverses it. Supporting redo requires two stacks.
Question 25·Stack & Queue
Beyond structures a programmer creates, every program already runs one stack. Which?
A.The CPU cache
B.The function call stack
C.The queue of processes waiting for the scheduler to give them CPU time
D.The heap, where objects are allocated at runtime
Answer: B
The call stack. Each function call pushes a frame holding parameters, local variables and the return address; when the function returns, the frame is popped. This is why the error trace printed when a program crashes is called a "stack trace" — it is a snapshot of the call stack at the moment of the error.
Bubble sort with a swap flag, run on an already-sorted array, costs what?
A.O(n log n), since the flag skips the redundant passes
B.O(n²), exactly as for any other input
C.O(n), because the first pass makes no swaps so it stops immediately
D.O(1), since the algorithm notices at once that there is nothing to do
Answer: C
O(n). Bubble sort with a swap flag scans one pass, sees that no swaps occurred and exits immediately. This is the best case of the algorithm. The version without the flag still runs the full n−1 passes, so it is always O(n²) regardless of the data.
Why is insertion sort considered a good choice for nearly sorted arrays?
A.Because it splits the array into segments and sorts each separately
B.Because it uses binary search to locate the insertion point
C.Because it skips entirely the elements already in the right place
D.Each element shifts by exactly how many misplaced elements precede it
Answer: D
Because its cost is proportional to the number of inversions — the number of pairs of elements in the wrong relative order. A nearly sorted array has very few such pairs, so each element only has to shift a few positions. The best case is a fully sorted array, with cost O(n).
Linear search over n elements takes how many comparisons on average?
A.About n/4 because the algorithm can stop early in many situations
B.About n/2 when the element is present in the array
C.About log n
D.Always exactly n in every case
Answer: B
About n/2 when the element is in the array. If its position is uniformly distributed the expected number of comparisons is (n+1)/2. When the element is not in the array it always scans all n. Both are O(n).
What happens if you run binary search on an unsorted array?
A.The result is always right but the running time becomes linear
B.The program errors as soon as the search starts
C.The loop runs forever
D.The loop still terminates but the result can be wrong with no error reported
Answer: D
The algorithm still terminates normally but the result may be wrong, with nothing signalling an error. Binary search relies on the sortedness assumption to decide which half to discard; if that assumption is false, it discards the half containing the answer and reports not found even though the element is still in the array.
In what order does preorder (NLR) traversal visit the nodes of a binary tree?
A.Both subtrees first, left then right, and only then the root
B.Level by level, each level from left to right
C.The whole left subtree first, then the root, then the right subtree
D.The root first, then the whole left subtree, then the right one
Answer: D
Root node → left subtree → right subtree. The three letters N-L-R are exactly the order: Node, Left, Right. Swapping the position of N gives the other two types — LNR is inorder, LRN is postorder. All three traverse depth-first, differing only in when the parent node is visited.
In postfix notation, where does the operator sit relative to its two operands?
A.The position varies with that operator's precedence
B.After both operands
C.Before both operands
D.Between the two operands, exactly as in ordinary maths
Answer: B
After both operands. Three ways to write the same addition: infixa + b, prefix+ a b, postfixa b +. Postfix is also called reverse Polish notation, named after the logician Jan Łukasiewicz.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Two common mix-ups: log n is smaller than n, not larger, and n log n is smaller than n² because log n grows far more slowly than n. Also, an exponential always overtakes any polynomial once n is large enough.
B.The operation is faster than every operation of another class
C.The operation reads exactly one element of the data
D.The operation finishes in exactly one machine cycle
Answer: A
Cost does not depend on n — 10 elements or 10 million costs about the same. Common misconception: O(1) does not mean fast. A 5ms O(1) operation is still O(1) and can be slower than a few-microsecond O(log n) operation.
A simple undirected graph with n vertices has at most how many edges?
A.n(n−1)/2
B.n(n−1)
C.n² + n
D.2(n−1)
Answer: A
n(n−1)/2 edges. Each pair of distinct vertices can be joined by exactly one edge, and the number of pairs is n choose 2. A graph reaching this edge count is called a complete graph. For a directed graph the number is n(n−1) because each pair has two directions.
A.The programming language and standard library used to realize it
B.The set of operations and their meaning, saying nothing about storage
C.How many bytes each element of the type occupies when allocated
D.How the data is laid out in memory
Answer: B
By its set of operations and their meaning, with no mention of how it is stored. A stack is an ADT: it promises push, pop, top with a last-in-first-out rule. Implementing it with an array or a linked list is fine; users need not know and should not depend on that.
What is Niklaus Wirth's well-known equation about data structures and algorithms?
A.Data Structures + Programming Language = Algorithms
B.Data Structures + Algorithms = Programs
C.Data Structures = Programs − Algorithms
D.Algorithms + Programs = Data Structures
Answer: B
Data Structures + Algorithms = Programs, the title of Wirth's book published in 1976. Its point: a program needs both sides, and they constrain each other — the data structure you choose determines which algorithms are feasible, and vice versa.
What is the first step when choosing a data structure for a problem?
A.Pick the structure with the best complexity from a lookup table
B.List the operations needed and how often each one is used
C.Estimate how much memory the program will be allowed to use at most
D.Check which structures the language's standard library already provides
Answer: B
List the operations you need along with their frequencies. Do you need key lookup, ordered traversal, and where and how often do insertions and deletions occur. Once answered, the choice usually narrows to one or two options, and only then does the complexity table become usable.
Question 38·Dynamic Programming
Climbing n stairs taking 1 or 2 steps at a time, the number of ways satisfies which recurrence?
A.f(n) = f(n−1) + 1
B.f(n) = f(n−1) × f(n−2)
C.f(n) = 2·f(n−1)
D.f(n) = f(n−1) + f(n−2)
Answer: D
f(n) = f(n−1) + f(n−2) — the Fibonacci sequence. Reasoning: the last step onto stair n is either a 1-step from stair n−1 or a 2-step from stair n−2. These two groups are disjoint and cover all cases, so you add them.
A.Every level holds values smaller than every value on the level just below
B.The left node is smaller than the root and the right one larger
C.Every parent node's value is less than or equal to both its children
D.Every node in the tree is in ascending order under an in-order traversal
Answer: C
Every parent node is less than or equal to both of its children. The invariant only constrains the vertical direction, so the minimum value is guaranteed to be at the root. Two sibling nodes have no ordering relationship at all, and neither do two nodes in different branches.
Intermediate level — 130 Algorithms & Data Structures questions
Question 1·Complexity
Why is 3n² + 500n + 20 written simply as O(n²)?
A.Because summing the terms always gives the degree of the first one
B.Because Big-O only accepts one term in an expression
C.Because 500n and 20 only affect memory rather than time
D.For large n, the highest-order term dominates the rest
Answer: D
Because Big-O looks at behavior as n approaches infinity. At n = 1,000,000, 3n² is 3×10¹² while 500n is only 5×10⁸, roughly 6000 times smaller. Constants and lower-order terms are dropped because they cannot change the shape of the growth curve.
A recursive function walks a linked list of n nodes and allocates no extra array. How much auxiliary memory does it use?
A.O(1), because no data structure is created
B.O(n), because n stack frames sit on the call stack
C.O(log n), because recursion always halves the problem
D.Nothing, since the compiler always eliminates the recursion
Answer: B
O(n). Each recursive call pushes a frame onto the stack and those frames are only popped once the deepest call returns, so depth n means n frames coexist. For a long enough list, this is exactly the cause of stack overflow.
Appending to a dynamic array is said to be "amortised O(1)". What does that mean?
A.It is O(1) while the array has room and O(n) when it is full
B.The garbage collector repays the allocation cost later
C.Every append costs exactly the same fixed number of steps
D.Some appends cost O(n) but the average is still O(1)
Answer: D
When full, the array allocates a new region twice as large and copies, costing O(n). But the next doubling only happens after another n cheap appends, so the total cost of n appends is O(n), averaging O(1) each. This guarantee applies to a sequence of operations, not to any single one.
You must answer many "sum of elements from index i to j" queries on an unchanging array. Which technique fits?
A.Build a prefix sum array so each query is one subtraction
B.Hash each (i, j) pair and cache the computed result
C.Rewalk from i to j for each query, which is already optimal
D.Sort the array first and binary search for the two endpoints
Answer: A
Prefix sums. Build prefix[k] = a[0] + … + a[k−1] once at O(n) cost, then the range sum over [i, j] is prefix[j+1] − prefix[i], each query O(1). Trade O(n) extra memory for constant-time answers.
Compared with an array, where does a singly linked list have its clearest advantage?
A.Accessing the i-th element by index
B.Iterating sequentially over every element
C.Finding the largest value in the structure
D.Insertion or removal when you already hold the pointer
Answer: D
Insertion and deletion at a position where you already hold the pointer: just relink, O(1), while an array must shift elements, so O(n). In exchange, a linked list loses O(1) index access and is cache-unfriendly.
The worst case for a hash map lookup is O(n). What causes it?
A.The table has too many empty slots so it must scan for a filled one
B.The keys are so long that the hash function loops many times
C.Many keys landing in one slot, forming a long list
D.The table is reallocated too often as elements are added
Answer: C
Collisions piling up. If the hash function distributes poorly, or the data is chosen adversarially, every key lands in the same bucket and that bucket becomes a list of n elements, so lookup has to scan them all. Modern implementations defend against this with randomized-seed hashing and converting a crowded bucket into a balanced tree.
Given an array of numbers and a target, find two elements summing to it. Which approach runs in a single O(n) pass?
A.Walk once, looking up each number's complement in a hash map
B.Walk every index pair and check each pair's sum
C.Sort the array and use two pointers from the ends
D.Halve the array and solve each half recursively
Answer: A
One pass using a hash map as memory: at each element x, check whether target − x is already in the map; if so return the pair, otherwise store x with its index. Each element is looked up and written exactly once, so the total is O(n) time, O(n) space.
Question 8·Hash map & set
You use a mutable object as a hash map key, then modify it after insertion. What happens?
A.The program errors as soon as the key is modified
B.The entry is removed from the table to keep it consistent
C.The entry becomes almost unfindable because its hash has changed
D.The table automatically moves the entry to the right slot when the key changes
Answer: C
The entry becomes unreachable garbage. The table placed it in a bucket computed from the old hash; after the key changes, the next lookup computes a new bucket and finds nothing there, even though the entry still occupies memory. So keys must be immutable for as long as they stay in the table.
Finding the longest substring without repeating characters, how does a sliding window react to a character already inside the window?
A.Keep the window and skip the current character
B.Move the right boundary back one step and try the next character
C.Reset the window to empty and start from the current character
D.Move the left boundary to just after the previous occurrence
Answer: D
Move the left boundary to just after the previous occurrence of the character just seen, taken from a map of character to index. The window always maintains the invariant "no repeated characters", and the right boundary only moves forward, so each character enters and leaves at most once: O(n).
A sliding window has two nested loops yet still counts as O(n). Why?
A.Each element enters and leaves the window exactly once
B.Because the left boundary is computed by a formula rather than looped
C.The inner loop always runs exactly once for any input
D.Because the window has a fixed size so the inner loop is constant
Answer: A
Because you count the total number of steps, not multiply the loop counts. The right boundary moves at most n steps, and the left boundary also moves at most n steps and never goes backward, so the total work is bounded by 2n. Nested loops do not automatically mean O(n²).
The fast and slow pointer technique detects a cycle in a linked list based on what?
A.The two pointers always meet exactly at the cycle's start
B.If a cycle exists, the fast pointer catches the slow one
C.The fast pointer returns to the head after exactly one lap
D.The slow pointer records the visited nodes for comparison
Answer: B
The slow pointer moves one step, the fast pointer two. If there is a cycle, both get stuck in the loop and the distance between them decreases by exactly one each step, so it is guaranteed to reach 0. Without a cycle, the fast pointer hits null and stops. Cost is O(n) time, O(1) space.
For each array element, find the first greater element to its right. Which approach gives O(n)?
A.For each element, scan the remaining tail until a larger number appears
B.Build a prefix sum array and compare consecutive differences
C.Sort the array descending and map back by the original indices
D.One pass with a stack holding indices in decreasing order
Answer: D
Monotonic stack. Scan left to right, keep a stack of indices with decreasing values; when the current element is larger than the top, pop the top and record the current element as its answer, repeating until the top is larger. Each index is pushed/popped once so O(n).
In graph traversal, replacing the queue with a stack changes what?
A.It changes breadth-first traversal into depth-first
B.It reduces the time complexity from O(V + E) to O(V)
C.It makes the algorithm find the shortest path more accurately
D.It lets you drop the visited set on a graph with cycles
Answer: A
It changes traversal order: queue gives BFS, visiting all vertices level by level; stack gives DFS, going deep down one branch before backtracking. Same O(V + E) complexity, but only BFS guarantees the shortest path (fewest edges) on unweighted graphs.
Simulating a queue with two stacks, what is the cost of a dequeue?
A.O(log n) because the two stacks must be rebalanced
B.Worst-case O(1) since the top is always ready
C.O(n) for every dequeue without exception
D.Amortised O(1), even though one dequeue can cost O(n)
Answer: D
O(1) amortized. Enqueue always pushes onto stack in. Dequeue pops from stack out; if out is empty, dump all of in into out, which reverses the order exactly once. Each element moves only once in its lifetime so n operations total O(n).
Why do many references recommend mid = lo + (hi - lo) / 2 over mid = (lo + hi) / 2?
A.It avoids integer overflow when lo and hi are both large
B.Because the other form does not work with an odd element count
C.Because the other form always biases the midpoint to the right
D.Because subtraction is faster than addition on most CPUs
Answer: A
To avoid integer overflow. With fixed-width integers, lo + hi can exceed the maximum value when both are large, yielding a negative index and causing incorrect behavior or failure. lo + (hi - lo) / 2 always stays in range because the difference never exceeds hi.
A sorted array has duplicate values and you need the first position of a value. What changes?
A.Re-sort the array by value and index before searching
B.On finding the value, keep narrowing to the left rather than stopping
C.Stop as soon as the value is found and walk back linearly to the start
D.Change the loop condition from less-than-or-equal to less-than
Answer: B
Don't stop on a match. Record mid as a candidate then set hi = mid - 1 to continue searching left. The loop ends with the last candidate as the first position. Still O(log n), while stepping back linearly after a hit can degrade to O(n).
What does a "stable" sorting algorithm mean, and when does that property matter?
A.It allocates no extra memory while sorting
B.It always runs in O(n log n) regardless of the input
C.It gives the same result on every run with the same input
D.It preserves the relative order of equal keys
Answer: D
Stable means two elements with equal keys keep their relative order as before sorting. This lets you sort by multiple criteria by sorting sequentially from secondary to primary key. Merge sort and Timsort are stable; quicksort and heapsort are not.
Why is merge sort usually preferred for linked lists while quicksort is not?
A.A linked list is always nearly sorted already
B.Quicksort does not work when the element count is unknown
C.Merge sort needs no comparisons so it runs linearly
D.Merging two lists only requires relinking pointers
Answer: D
Merge sort only needs sequential traversal and pointer relinking, exactly what linked lists do well, and on lists it needs no O(n) extra memory. Quicksort relies on random access for pivot selection and in-place partitioning, which linked lists don't provide in O(1).
Sorting 10 million integers in the range 0 to 100. What beats O(n log n)?
A.Use quicksort with a randomly chosen pivot for each segment
B.Count the occurrences and write them back in ascending order
C.Split the array across several threads and merge the results
D.Sort on disk in blocks and merge externally
Answer: B
Counting sort: count occurrences of each value into a 101-slot array, then write them out in ascending order. Cost is O(n + k) with k the value-range size. This beats the n log n lower bound because it never compares elements and instead uses values as indices.
What does an in-order traversal of a binary search tree produce?
A.A sequence starting from the root then going into the branches
B.The leaves from left to right
C.The values level by level from the top down
D.A sequence of values in ascending order
Answer: D
An ascending sequence. In-order goes left, then root, then right; combined with the BST invariant that left children are smaller and right children larger, the values come out in order. This is also a way to check whether a tree is truly a BST.
Red-black and AVL trees both self-balance. What is the practical difference?
A.AVL is for on-disk data while red-black is for in-memory
B.Red-black keeps the keys ordered while AVL does not
C.AVL gives O(log n) while red-black is only O(n) in the worst case
D.AVL balances more strictly so reads are faster while red-black writes are cheaper
Answer: D
Both guarantee O(log n); the difference is the trade-off. AVL keeps the height difference of the two subtrees at most 1, so the tree is shorter and lookups are faster, at the cost of more rotations on writes. Red-black trees allow more imbalance, making inserts and deletes cheaper, which suits write-heavy workloads.
Printing a binary tree level by level, one line per level. What does it need beyond a plain BFS?
A.Record how many nodes are in the queue before each level
B.Traverse the tree twice, once to count levels and once to print
C.Swap the queue for a stack to distinguish the levels
D.Store the depth in every node before traversing
Answer: A
Capture the queue size at the start of each loop. That number equals the node count of the current level, so dequeue exactly that many nodes, print one line, then push their children for the next level. Still O(n) time and O(width) memory.
A recursive DFS on a cyclic graph without a visited set leads to what?
A.Each vertex is visited exactly once thanks to the call stack
B.The right result but slower than the version with a visited set
C.Infinite recursion until the stack overflows
D.Some vertices are missed but it still terminates normally
Answer: C
Recursion loops forever around the cycle until stack overflow. The visited set ensures each vertex is expanded only once, and also brings complexity down to O(V + E). On a tree it isn't needed because trees have no cycles.
Why does Dijkstra produce wrong results when the graph has negative edge weights?
A.Because the path total can overflow when many negatives are added
B.It fixes a vertex as optimal the moment it leaves the queue
C.Because the algorithm requires every vertex to be connected
D.Because a priority queue cannot store negative numbers
Answer: B
Dijkstra is greedy: when it takes the smallest-distance vertex out of the queue, it finalizes that vertex as optimal. This argument relies on the assumption that a path never gets shorter by adding an edge. Negative edges break that assumption, so a finalized vertex can still be improved later. Use Bellman-Ford when negative edges exist.
You must order tasks under constraints of the form "A must finish before B". Which algorithm fits?
A.Dijkstra with each task's duration as the weight
B.Breadth-first traversal from the first task in the list
C.A topological sort on the directed dependency graph
D.Sort the tasks by their dependency count and run them in turn
Answer: C
Topological sort. Build a directed graph with edge A→B meaning A must finish before B, then repeat: take out vertices with in-degree 0, decrement the in-degree of adjacent vertices. If any vertices remain untaken, there is a cyclic dependency. Cost O(V + E).
A graph with 100,000 vertices but only 300,000 edges. Adjacency list or adjacency matrix?
A.An adjacency matrix, since checking whether two vertices are adjacent is O(1)
B.Either, since both are O(V + E)
C.An adjacency matrix, since iterating a vertex's neighbours is faster
D.An adjacency list, since the memory scales with the real edge count
Answer: D
Adjacency list. A matrix needs V² = 10¹⁰ cells, infeasible, while a list costs only O(V + E), about 400,000 entries. For a sparse graph always choose an adjacency list; a matrix is only worth it when the graph is dense or you need O(1) adjacency checks very many times.
In backtracking, why must changes be undone after the recursive call returns?
A.So the garbage collector can free the allocated memory
B.To ensure the solutions are generated in ascending order
C.To lower the complexity from exponential to polynomial
D.So the next branch starts from the original state
Answer: D
Because state is shared between branches. After trying a choice and recursing, if you don't undo it the next branch starts with corrupted state and produces wrong answers. The pattern is: choose, recurse, unchoose.
Naive recursive Fibonacci runs in O(2ⁿ). What does memoisation bring it down to?
A.O(n log n), because of the cache lookup cost
B.O(n), because each value is computed exactly once
C.Still O(2ⁿ) but with a much smaller constant
D.O(n²), because it still rewalks the smaller values
Answer: B
O(n) time and O(n) memory. The pure recursion's call tree repeats the same subproblems endlessly; memoisation makes each value from 0 to n computed once, later calls return immediately. A bottom-up iterative version can cut memory to O(1) if you keep only the two previous values.
Question 29·Dynamic Programming· select all that apply
Which two properties indicate a problem is solvable by dynamic programming?
A.The input is small enough to enumerate exhaustively
B.The input data is already sorted
C.The subproblems overlap and repeat
D.The optimal solution is built from the subproblems' optimal solutions
Answer: C, D
Both are needed: overlapping subproblems (the same subproblem appears many times, so caching pays off) and optimal substructure (an optimal overall solution is built from optimal solutions of the parts). Without the first, memoisation is useless; without the second, the recurrence is wrong.
How does top-down dynamic programming (memoisation) differ from bottom-up (tabulation)?
A.Top-down needs no recurrence relation
B.Bottom-up always gives a better time complexity
C.Top-down only computes the states actually needed
D.Bottom-up only applies when the state is one-dimensional
Answer: C
Top-down is recursion plus a cache, computing only the states actually reached and keeping the problem's original shape. Bottom-up fills a table in order, avoiding call overhead and opening the way to memory optimisation, but must compute even unneeded states and requires you to determine the evaluation order yourself.
Find the 10 largest values in a 100-million-number stream that does not fit in memory. Which approach fits?
A.Keep a 10-element min-heap and replace the root when a larger value appears
B.Split the stream into blocks, take each block's maximum and compare them
C.Keep a max-heap of every element and pop ten times
D.Sort the entire stream and take the last ten elements
Answer: A
A min-heap of size k = 10. One pass: if the heap has fewer than 10, insert; once full, compare with the root, and if larger replace the root and sift down. The root is always the smallest among the current leaders. Cost O(n log k) time and O(k) memory.
What does building a heap from an existing n-element array cost, versus inserting elements one by one?
A.Building directly is O(n log n) while inserting one by one is O(n)
B.Both are O(n log n) since both sift n times
C.Building directly is O(n) while inserting one by one is O(n log n)
D.Both are O(n) since each element is touched once
Answer: C
Building directly by sifting down from the bottom up is O(n), while inserting one by one is O(n log n). The reason is that half the nodes sit at the bottom and need no sifting at all; only a few nodes near the root cost log n. Summed up, it converges to linear.
Given a pointer to node p, how long does inserting a new node right after p take?
A.It depends on where p sits in the list
B.O(1)
C.O(log n)
D.O(n)
Answer: B
O(1). All it takes is node.next = p.next then p.next = node — two assignments, independent of n. The easy mistake: the O(n) cost textbooks mention is the cost of finding the insertion position. When the problem already gives you a pointer to p, that search is gone.
Holding only a pointer to a middle node p of a singly linked list, how can you delete p?
A.Just assign p = p.next
B.Assign p = null to cut the node out of the list
C.There is no way; you must walk again from the head
D.Copy p.next's data into p and delete the node p.next
Answer: D
Copy the value of p.next over p, then link p.next = p.next.next to drop the next node. Result: the value at position p disappears from the list in O(1), even though the freed cell is actually the next node's. This trick only works when p is not the last node — the last node has nothing to copy over.
A doubly linked list pays extra memory in exchange for what?
A.Markedly fewer cache misses when walking the list sequentially
B.Accessing the k-th element in O(1)
C.Searching for a value in O(log n)
D.Deleting a node you already hold in O(1), and traversing backwards
Answer: D
Each node keeps an extra prev pointer, buying two things: O(1) deletion once you hold a pointer to the node, and backward traversal from tail to head. A singly linked list deleting node p must find the node before p, i.e. O(n). The price is more memory per node and every operation updating two directions instead of one.
Remove the n-th node from the end of a singly linked list in a single pass. How?
A.Put every node into an auxiliary array and index into it to delete
B.Reverse the list, delete the n-th from the front, and reverse it back
C.Send one pointer n steps ahead and then advance both to the end
D.Walk once to count the length, then walk again to the position and unlink
Answer: C
Use two pointers exactly n steps apart. Move the fast pointer n steps ahead, then advance both one step at a time until the fast one hits the end. At that point the slow pointer sits right before the node to delete. One pass, O(1) memory.
Reversing a singly linked list in place needs at least how many pointers?
A.One, since you only reverse the next field
B.Four, with an extra pointer keeping the original head
C.Three: the previous node, the current one and the next one
D.Two: the current node and the next one
Answer: C
Three pointers: prev, cur, next. Each loop iteration does exactly four things in order — save next = cur.next, break cur.next = prev, move prev = cur, move cur = next. The next pointer is mandatory because the moment you overwrite cur.next you lose the path to the rest of the list.
constbuild = (arr) => arr.reduceRight((next, value) => ({ value, next }), null)
functionreverse(head) {
let prev = nulllet cur = head
while (cur) {
const next = cur.next
cur.next = prev
prev = cur
cur = next
}
return prev
}
const out = []
for (let n = reverse(build([1, 2, 3, 4])); n; n = n.next) out.push(n.value)
console.log(out.join(','))
A.1,2,3,4
B.3,4,1,2
C.2,1,4,3
D.4,3,2,1
Answer: D
It prints 4,3,2,1. build creates the list 1→2→3→4, reverse flips each link and returns prev — the old last node, i.e. node 4. Traversing from there gives the reverse order.
What is a dummy head node placed before the list for?
A.Speeding up access to the k-th element
B.Removing the special case for inserting or deleting at the head
C.Storing how many elements the list currently holds
D.Marking the end so the loop knows exactly when to stop
Answer: B
The dummy head turns "insert/delete at head" into a normal case. Without it, every list-modifying function needs a separate if (node === head) branch to update the head variable. With it, every real node has a predecessor, so there is only one code path — shorter code and far fewer edge-case bugs.
How do you find the middle node of a linked list in a single pass?
A.Walk once to count n, then walk n/2 steps
B.Put every node into an auxiliary array and take the middle element
C.Reverse the list and take the first node
D.One pointer steps by 1 and another by 2 until the fast one reaches the end
Answer: D
Still fast and slow pointers, but read the result from the slow pointer. When the fast pointer reaches the end, the slow pointer is exactly at the middle because it has traveled half the distance. One pass, O(1) space.
Both are O(n), so why is walking an array usually faster than walking a linked list?
A.Because a linked list must allocate more memory while traversing
B.Because an array does fewer comparisons in the loop
C.Array elements sit next to each other so one cache load serves several
D.Because a linked list's O(n) is really O(n log n)
Answer: C
Due to cache locality. The CPU doesn't fetch byte-by-byte but loads a ~64-byte cache line at a time. With an array, one load brings in many consecutive elements. With a linked list, nodes are scattered so each step can be a cache miss, and one main-memory stall costs tens of times more than a compute instruction.
What does merging two sorted linked lists into one sorted list cost?
A.O(n + m) time and O(1) extra memory if you relink the pointers
B.O(n + m) time but necessarily O(n + m) extra memory
C.O(n · m) since each node must be compared with every node of the other list
D.O((n + m) log(n + m)) since the result must be sorted afterwards
Answer: A
O(n + m) time and O(1) extra space. Always compare the two current heads, append the smaller node to the result and advance that list's pointer. Each node is visited exactly once. Since it only rewires next pointers without creating new nodes, no extra memory is used.
A contiguous list holds 10 elements at positions 1..10. Inserting at position 4 shifts how many elements?
A.10
B.4
C.7
D.6
Answer: C
Seven elements. To free slot 4, every element from position 4 to 10 must shift right by one — exactly 10 − 4 + 1 = 7 elements. The first three stay put. The shift loop must run backwards from the end to the insertion point; running forward would overwrite data.
Same 10-element contiguous list at positions 1..10. Deleting the element at position 4 shifts how many?
A.6
B.4
C.5
D.7
Answer: A
Six elements. Elements at positions 5 to 10 move forward one slot to fill the gap, i.e., 10 − 4 = 6. Note the off-by-one vs. insertion: on insert the element at i also shifts, on delete the element at i disappears so only the tail shifts. This loop runs forward from i to n − 1.
Question 45·Arrays & Strings
What makes accessing a[i] in an array O(1)?
A.The compiler keeps a lookup table of every element's address
B.The address is computed from the base, the index and the element size
C.The CPU holds the whole array in registers
D.The array is always sorted so it is found by halving
Answer: B
Thanks to the formula address = base + i × size. Since every element has the same size and they sit contiguously, the position of element i is one multiply-add — constant cost no matter how long the array is. Lose either condition and you lose the O(1).
When a dynamic array runs out of room it doubles instead of adding a fixed amount. Why?
A.Doubling gives amortised O(1) while adding a constant gives O(n)
B.Because memory can only be allocated in powers of two
C.Because copying one large region is faster than copying many small ones
D.So the array always fits exactly into a cache line
Answer: A
Because of the total copy cost. Doubling makes reallocations increasingly rare in geometric fashion: copying 1 + 2 + 4 + … + n < 2n, which amortized over n elements gives amortized O(1). If you only add k elements each time, the number of reallocations is n/k and total copying is O(n²), i.e. O(n) per append.
A 2D array is stored row-major. Why is row-wise traversal faster than column-wise?
A.Because computing the address row-wise takes fewer multiplications
B.Because the compiler automatically turns a column loop into a row loop
C.Row-wise reads adjacent cells while column-wise jumps a whole row each step
D.Because row-wise traversal has fewer loop iterations
Answer: C
Because the access order does or doesn't match the storage order. Row-major means an entire row sits contiguously in memory. Row-wise traversal goes sequentially, so each cache line loaded serves many cells. Column-wise traversal jumps a full row length each step, usually landing in a different cache line — potentially one cache miss per cell.
What is the cheapest way to remove the element at index i from an array whose order does not matter?
A.Copy the last element over position i and shorten the length by one
B.Create a new array and copy everything except element i
C.Assign null at position i and keep the length
D.Shift every element after i up by one and shorten the length
Answer: A
Copy the last element over position i and shrink the length — usually called swap-remove, O(1) cost. The trade-off is that element order gets shuffled. This only works when the array acts as an unordered set; if order matters you have to accept the O(n) shifting.
Question 49·Recursion & Backtracking
Which data structure does the machine use to remember where to return between recursive calls?
A.A queue
B.A hash table
C.A list
D.A stack
Answer: D
The call stack. Each call pushes a frame containing parameters, local variables, and the return address; when the function returns the frame is popped and the thread resumes at the correct location. Its LIFO order exactly matches the completion order of nested calls.
The Towers of Hanoi with n disks needs at least how many moves?
A.n·log n
B.n² − n
C.2ⁿ − 1
D.n × 2ⁿ
Answer: C
Exactly 2ⁿ − 1 moves. Recursive solution: move the top n−1 disks to the auxiliary peg, move the largest disk to the target peg, then move the n−1 disks from auxiliary to target. The recurrence T(n) = 2·T(n−1) + 1 with T(1) = 1 solves to 2ⁿ − 1, which is also the minimum.
What does this code counting naive Fibonacci calls print?
javascript
let calls = 0functionfib(n) {
calls++
if (n < 2) return n
returnfib(n - 1) + fib(n - 2)
}
const value = fib(6)
console.log(value, calls)
A.8 25
B.8 15
C.13 25
D.8 13
Answer: A
Prints 8 25. The Fibonacci sequence starts 0, 1, 1, 2, 3, 5, 8, so fib(6) = 8. The call count satisfies C(n) = C(n−1) + C(n−2) + 1 with C(0) = C(1) = 1, giving C(6) = 25. The closed form is C(n) = 2·fib(n+1) − 1.
Question 52·Recursion & Backtracking
What shape of recursion is tail recursion?
A.The recursive call sits on the last line of the body when reading the source
B.The function calls itself exactly once in the whole body
C.The function handles the structure's last element first and works back to the front
D.The recursive call is the last thing done, with the result returned straight out
Answer: D
The recursive call is the last thing the function does, and its result is returned straight out. return f(n - 1, acc * n) is tail recursion; return n * f(n - 1) is not, because after f returns there is still a multiply to do. With no work after the call, the current stack frame can be reused.
What do you need to add in order to rewrite a recursive function as a loop?
A.An explicit stack you manage yourself
B.A memoisation table
C.A counter holding how many times the function has called itself
D.A queue holding the states still to be processed
Answer: A
An explicit stack. Recursion runs on the machine call stack; removing recursion just means turning that implicit stack into one you push and pop yourself. Each element stores exactly what a call frame stored: the parameters and the point where processing left off.
Question 54·Recursion & Backtracking
How does backtracking differ from plain brute force?
A.Backtracking explores the candidates in the reverse order from brute force
B.Backtracking abandons a whole branch as soon as it cannot lead to a solution
C.Backtracking uses loops while brute force must be written recursively
D.Backtracking is always polynomial while brute force is always exponential
Answer: B
Backtracking prunes: as soon as a partial solution violates a constraint, the entire subtree below is dropped without being built. Plain brute force generates every candidate and only then checks. Both have exponential worst-case complexity, but backtracking is often many times faster on real data.
A recursive function sums an n-element array, one element per call. What is its auxiliary space?
A.O(n²)
B.O(log n)
C.O(n)
D.O(1)
Answer: C
O(n). Even though the function allocates no array, each call still takes a frame on the stack and up to n frames exist simultaneously before the deepest call starts returning. The call stack is real memory and must be counted in the space complexity.
How do linear and binary recursion differ in the number of calls?
A.Linear makes n² calls since each level rescans all the data
B.Linear makes n calls while binary can make on the order of 2ⁿ
C.Both make exactly n calls, differing only in execution order
D.Binary makes log n calls since each step halves the problem
Answer: B
Linear recursion calls itself once per level, totaling n calls and depth n. Binary recursion calls itself twice per level, so the call tree doubles per level and the total can reach on the order of 2ⁿ, even though the depth is still only n. This is why the memory and time of the two forms differ so widely.
Question 57·Stack & Queue
What problem with a queue on a straight array does a circular queue solve?
A.The space freed at the front of the array goes to waste after several removals
B.You cannot tell where the front of the queue is
C.Appending to the back becomes O(n) rather than O(1)
D.The elements lose their order after the queue fills and empties again
Answer: A
Wasted space at the front of the array — each dequeue advances the head index and never reuses the freed slots in front. Eventually the tail hits the end and the queue reports full while half the array is empty. A circular queue reuses space by wrapping both indices with modulo.
How does a stack backed by a dynamic array differ from one backed by a linked list?
A.The array makes push and pop O(n) while the linked list makes them O(1)
B.Only the array-backed version really keeps last-in-first-out order
C.The linked list uses less memory
D.The array is faster thanks to the cache but occasionally pays for a reallocation
Answer: D
Asymptotically equivalent, differing in constants and stability. A dynamic array gives amortized O(1) push — occasional reallocation and copy — but contiguous storage is cache-friendly. A linked list gives worst-case O(1) with no spikes, at the cost of an extra pointer per node and cache misses.
const s = []
for (const ch of'ABCD') s.push(ch)
s.pop()
s.push('E')
s.pop()
s.pop()
console.log(s.join('') + '|' + s.length)
A.ABE|3
B.AB|2
C.AC|2
D.ABC|3
Answer: B
Prints AB|2. Sequence: push A, B, C, D; pop removes D leaving ABC; push('E') makes ABCE; pop removes E leaving ABC; pop removes C leaving AB. Final length is 2.
Question 60·Stack & Queue
How does a priority queue differ from an ordinary queue?
A.It removes the highest-priority item rather than the earliest added
B.It only allows inserting at the already-sorted position
C.It can only hold numbers while an ordinary queue holds any type
D.It has a fixed capacity while an ordinary queue grows freely
Answer: A
Dequeue order is determined by priority, not arrival time. An ordinary queue is pure FIFO; a priority queue always returns the element with the smallest or largest key. Implemented with a binary heap, enqueue and dequeue are O(log n) and peek is O(1).
What does a deque allow that neither a stack nor a queue can do?
A.Adding and removing at both ends, each in O(1)
B.Accessing a middle element by index
C.Automatically keeping the elements inside sorted
D.Letting several threads operate on it without synchronization
Answer: A
Insert and remove at both ends, both O(1). A deque is a double-ended queue, so it can act as a stack if used at one end or as a queue if enqueued at one end and dequeued at the other. Hence many standard libraries provide only deque and let users choose how to use it.
Why does breadth-first graph traversal require a queue?
A.So every vertex k steps from the source is processed before layer k plus one
B.Because only a queue offers constant-time insertion and removal
C.Because a queue uses less memory than a stack on a large graph
D.To avoid revisiting a vertex processed in an earlier step
Answer: A
Because FIFO preserves level order — a queue ensures all vertices k steps from the source are dequeued before any vertex k+1 steps away. That makes the first time a vertex is reached the shortest path by edge count. Replacing it with a stack becomes depth-first search and loses this guarantee.
What makes the sliding-window maximum problem achievable in O(n)?
A.Sort the whole array first and take each segment's largest
B.A deque holds indices in decreasing value order, each element entering and leaving once
C.Rescan each window but skip the elements already known to be smaller
D.Use a priority queue holding exactly the k elements inside the window
Answer: B
Thanks to a monotonic deque that stores indices with decreasing values. Before inserting, remove from the back all smaller elements — they can never become the maximum — and remove from the front any index outside the window. The front is always the answer and each element enters and leaves once, so total is O(n).
Among the three familiar O(n²) sorts, which performs the fewest swaps?
A.All three are equal since they are all O(n²)
B.Selection sort, exactly n−1 swaps regardless of the input
C.Bubble sort, since each pass pushes exactly one element to the end
D.Insertion sort, since it only shifts rather than truly swapping
Answer: B
Selection sort, exactly n−1 swaps regardless of the data. Each pass it scans for the smallest element in the remaining part and then swaps exactly once. Bubble sort and insertion sort have a data-dependent number of writes that can reach O(n²).
How much auxiliary memory does merge sort on an array need, and why is it unavoidable?
A.O(n), because the merge must write the result elsewhere before copying back
B.O(1), because the merge happens in place on the original array
C.O(log n), exactly the recursion tree's depth
D.O(n log n), because each level of the recursion tree needs its own buffer
Answer: A
O(n). The merge step reads two sorted runs and writes out the resulting sequence; writing directly over the original array would destroy elements that have not been read yet. The standard approach is to allocate a buffer the size of the original array and reuse it across every level of recursion, since the levels do not run at the same time.
Heapsort is worst-case O(n log n) and in-place. Why is it still rarely the default?
A.Because it needs an extra buffer the size of the input array
B.Because its worst case is really O(n²)
C.It accesses memory in jumps so it uses the cache poorly, and it is unstable
D.Because it only works with integer data
Answer: C
Because of cache and stability. Heapsort jumps between index i and 2i+1, with ever-growing distance, so each sift-down step usually lands in a different cache line. Quicksort scans sequentially, so in practice it is significantly faster despite a worse worst case. Heapsort is also not stable.
const a = [10, 9, 100, 1, 25]
console.log(a.sort().join(','))
A.1,10,100,25,9
B.9,10,25,100,1
C.10,9,100,1,25
D.1,9,10,25,100
Answer: A
It prints 1,10,100,25,9. Array.prototype.sort() with no argument converts every element to a string and compares by UTF-16 code unit, i.e. lexicographic order. The string "10" comes before "9" because the character "1" is smaller than "9". For correct numeric order you must write a.sort((x, y) => x - y).
A.It finishes sorting in a single pass over the array
B.It creates no temporary variables at all while running
C.It never swaps elements, only reading and writing them back in place
D.It uses only a constant amount of extra memory beyond the input array
Answer: D
The algorithm uses only O(1) extra memory beyond the input array. A few temporary variables for swapping or holding indices are fine; the requirement is that this amount does not grow with n. Insertion sort, selection sort, bubble sort and heapsort are all in place. Merge sort on an array is not, because it needs an O(n) buffer.
A.It skips duplicate elements to reduce the comparison count
B.It uses several threads to process segments of the array in parallel
C.It buckets by each digit rather than comparing the elements
D.It sorts a small sample first and infers the order for the rest
Answer: C
Because it does not compare elements with each other. The Ω(n log n) lower bound only applies to comparison-based algorithms. Radix sort buckets by individual digits, running d passes where each pass is O(n + k) — with d the number of digits and k the number of possible digit values — for a total of O(d·(n + k)).
The number of swaps bubble sort performs on an array equals exactly what quantity?
A.The number of inversions, that is pairs in the wrong relative order
B.Exactly n(n−1)/2 for every input array
C.The number of passes made before the array is sorted
D.The number of elements not in their final position
Answer: A
It equals the number of inversions in the array. Bubble sort only swaps two adjacent elements, and each such swap removes exactly one inversion. A sorted array has 0 inversions so no swaps happen; a reverse-sorted array has n(n−1)/2 inversions, which is the worst case.
Question 71·Sorting
An array contains only the values 0, 1 and 2. How do you sort it in one pass with O(1) space?
A.Walk the array swapping each out-of-order adjacent pair until done
B.Three pointers dividing the array into a zeros region, a ones region and a twos region
C.Count each value's occurrences and rewrite the array according to the counts
D.Call quicksort with a randomly chosen pivot each time
Answer: B
Use Dijkstra's three-way partition, known as the Dutch National Flag problem. Maintain three pointers: low is the right boundary of the 0s region, high is the left boundary of the 2s region, and mid scans. On 0 swap with low and advance both; on 2 swap with high and decrement high; on 1 just advance mid.
Which check does the sentinel technique remove from linear search?
A.The comparison between the current element and the sought value
B.The check on whether the input array is empty before scanning
C.The check on whether the index has passed the end of the array
D.Incrementing the index after each iteration
Answer: C
It removes the bounds checki < n. Method: place the target value itself in the slot right after the last element. The loop is then guaranteed to stop because at least one match will be found. After the loop just check whether the stopping index is the sentinel position to know if it was a real find.
Binary search over n elements needs at most how many iterations?
A.About √n
B.It depends where the sought element actually sits in the array
C.About n/2 since each step drops half the elements
D.About log₂n, rounded up
Answer: D
About log₂n iterations, exactly ⌈log₂(n+1)⌉. Each iteration discards half the remaining interval, so n elements must be halved log₂n times to get down to one. One million elements needs about 20 iterations; one billion needs about 30.
const a = [2, 5, 8, 12, 16, 23, 38, 56]
let lo = 0let hi = a.length - 1let steps = 0while (lo <= hi) {
steps++
const mid = (lo + hi) >> 1if (a[mid] === 23) { console.log(mid, steps); break }
if (a[mid] < 23) lo = mid + 1else hi = mid - 1
}
A.5 2
B.5 3
C.6 2
D.23 2
Answer: A
Prints 5 2. Round 1: lo=0, hi=7, mid=3, a[3]=12 is less than 23 so lo=4. Round 2: lo=4, hi=7, mid=5, a[5]=23 matches and exits. So the index is 5 and the iteration count is 2.
A sorted array is rotated at an unknown pivot. Can binary search still work?
A.Yes, because at each split at least one half is still in order
B.Yes, but the complexity rises to O(n)
C.Yes, but the array must be re-sorted before searching
D.No, because the array is no longer sorted
Answer: A
Yes, still O(log n). Key insight: when splitting at mid, at least one of the two halves is correctly sorted contiguously. Comparing a[lo] with a[mid] tells which half; if the target lies within the range of that sorted half search there, otherwise search the other half.
You need the k-th smallest element of an unsorted array. Which approach is O(n) on average?
A.Sort the array and take the element at position k
B.Quickselect, partitioning like quicksort but recursing into only one side
C.Build a binary search tree and traverse in order to the k-th node
D.Walk the array k times, each time finding and removing the smallest remaining element
Answer: B
Quickselect. Partition the array around a pivot like quicksort, but then recurse only into the side containing position k instead of both. With a random pivot, the expected total cost of the partitioning passes is O(n). The worst case remains O(n²) when the pivot is consistently skewed.
Under what condition can interpolation search beat binary search?
A.When the array is small, under a few dozen elements
B.When the array is not sorted in any order
C.When the array contains many duplicate values
D.When the values are reasonably evenly distributed
Answer: D
When the values are fairly uniformly distributed. Instead of always taking the midpoint, interpolation estimates the position by value ratio — like how people open a dictionary: to find a word starting with "v" you open near the end, not the middle. For uniform data, the average cost is O(log log n).
When is a hash table a better choice than a sorted array with binary search?
A.When the dataset is small and barely changes
B.When you only need exact key lookups and no ordered traversal
C.When you need the keys falling within a value range
D.When you need the smallest or the largest key in the whole dataset
Answer: B
When you only need exact key lookup and don't care about order. A hash table gives O(1) average versus O(log n) for binary search, and insertion or deletion is also O(1) instead of O(n). The trade-off is that it completely loses key ordering, so it cannot support range queries, finding extremes, or in-order traversal.
Question 79·Search
A small unsorted array of about 20 elements, queried exactly once. Which approach fits?
A.Sort it and binary search
B.Linear scan; sorting first costs more than lookup
C.Build a binary search tree and look it up in the tree
D.Build a hash table from the array and look the key up in it
Answer: B
Linear scan. Sorting costs O(n log n) and building a hash table costs O(n) — both are more expensive than or equal to the single O(n) scan they would replace. Preparation cost is only worth paying when it is amortized over many later lookups.
Question 80·Trees & BST
A binary tree has at most how many nodes at level k, counting the root as level 0?
A.k²
B.2^k
C.2^k − 1
D.2k
Answer: B
At most 2^k nodes. Level 0 has 1 node, the root; level 1 has at most 2; level 2 has at most 4 — each level doubles because each node has at most two children. From this it follows that a tree of height h has at most 2^(h+1) − 1 nodes in total.
A complete binary tree stored in an array with the root at index 0. Where are node i's children?
A.i/2 and i/2+1
B.2i+1 and 2i+2
C.2i and 2i+1
D.i+1 and i+2
Answer: B
Left child at 2i+1, right child at 2i+2, and the parent of node j at ⌊(j−1)/2⌋. Thanks to these three formulas, a complete tree can be stored in a flat array with no pointers at all. If the root is placed at index 1, the formulas are cleaner: children are 2i and 2i+1, parent is ⌊j/2⌋.
When inserting a new key into a binary search tree, where does the new node always appear?
A.At a leaf position
B.At the root position
C.At the shallowest free position, to keep the tree balanced
D.In the middle of the tree, wherever the key falls in the ordering
Answer: A
Always at the position of a leaf node. The algorithm starts at the root, compares the new key with each node to go left or right, until it hits an empty link — the new node is hung exactly there. Therefore the shape of the tree depends entirely on the insertion order.
Deleting a node with two children from a BST replaces it with which node?
A.The smallest node of the right subtree, or the largest of the left
B.Its left child, with the right subtree hung on the end of the left branch
C.The whole tree's root, with the tree then rebuilt from scratch
D.The deepest leaf in the tree, to keep the height from growing
Answer: A
Replace with the in-order successor — the smallest node in the right subtree — or symmetrically the predecessor, the largest node in the left subtree. These two nodes are immediate neighbors of the deleted node in the in-order sequence, so promoting either preserves all ordering relations.
Prints 1 2 3 4 5 6. The out.push is between the two recursive calls, i.e., in-order traversal. Since this tree is a valid BST, in-order yields the keys in sorted ascending order.
A.When a key is deleted, while insertions never need a rotation
B.When a node's two subtrees differ in height by more than one
C.When the node count exceeds a preset threshold
D.When the left and right subtrees differ too much in their node counts
Answer: B
When a node's balance factor — left subtree height minus right subtree height — falls outside [−1, 1]. After each insert or delete, the algorithm walks back from the modified node to the root, updating heights and rotating at the first violating node.
Finding the lowest common ancestor of two nodes in a BST lets you exploit what?
A.The first node whose value lies between the two keys is the answer
B.You must traverse the whole tree and record the path from the root to both nodes
C.Traverse in order and take the node midway between the two keys' positions
D.The lowest common ancestor of any two nodes in a BST is always the root
Answer: A
Exploits the ordering property. Starting from the root: if both keys are smaller than the current node go left, if both larger go right. The first node where the two keys diverge to different sides — or the node that equals one of the keys — is the lowest common ancestor. Cost is O(height) with no extra memory.
A heap and a BST are both binary trees. How do their ordering constraints differ?
A.A heap only constrains parent to child while a BST puts left below right
B.A heap requires every node's value to differ while a BST allows duplicates
C.Both constraints are the same, differing only in the underlying storage
D.A heap constrains by height while a BST constrains each branch's node count
Answer: A
A heap only guarantees the parent-child relation — parent is always smaller than both children in a min-heap. Sibling nodes have no ordering. A BST constrains horizontally: every node in the left subtree is smaller than the root, every node in the right subtree is larger. Thus a BST has global ordering while a heap only has ordering along each root-to-leaf path.
A.Work needing a binary search tree's keys in ascending order
B.Work needing the tree serialized so it can be stored and rebuilt in shape
C.Work needing the children's results before the parent can be processed
D.Work needing the fewest-edge path between any two nodes
Answer: C
Tasks where the parent depends on the children's results. Computing directory size must sum child directories first; freeing memory must delete children before the parent; evaluating an expression tree must have both operand values before applying the operator. Postorder guarantees that order.
A full binary tree, where every node has 0 or 2 children, with L leaves has how many internal nodes?
A.2L − 1
B.L
C.L + 1
D.L − 1
Answer: D
Exactly L − 1 internal nodes, and 2L − 1 total nodes. Proof by induction: a single-node tree has L = 1 and 0 internal nodes. Each time a leaf is turned into an internal node by adding two children, internal nodes increase by 1 and leaves increase by 1, so the difference stays constant.
Level-order traversal needs which structure, and how do you separate the levels?
A.A queue, recording how many elements it holds before processing each level
B.A queue, inserting a marker element between two consecutive levels
C.A stack, counting the nodes popped to know when the next level starts
D.A priority queue, ordering the nodes by their depth in the tree
Answer: A
You need a queue. Level-separation trick: at the start of each outer loop iteration, record size = queue.length — that is exactly the number of nodes in the current level. Pop exactly size nodes, process them, and push their children; when the inner loop ends, one level is done.
The infix expression a + b * c converts to which postfix form?
A.a b + c *
B.a b c * +
C.b c * a +
D.a + b c *
Answer: B
a b c * +. Since multiplication has higher precedence than addition, b * c is grouped first, giving b c *; then adding a gives a b c * +. Verify by evaluating: on * pop b and c and multiply them, on + pop a and the result just computed.
Question 92·Postfix Notation & Expression Trees
Evaluating an expression already in postfix form requires which data structure?
A.A queue
B.A stack
C.A binary tree
D.A hash table
Answer: B
A stack. Scan the expression left to right: on an operand, push it; on an operator, pop two values, compute, and push the result back. When the expression ends, the single remaining value on the stack is the answer.
functionevalPostfix(expr) {
const st = []
for (const t of expr.split(' ')) {
if (!'+-*/'.includes(t)) { st.push(Number(t)); continue }
const b = st.pop()
const a = st.pop()
st.push(t === '+' ? a + b : t === '-' ? a - b : t === '*' ? a * b : a / b)
}
return st.pop()
}
console.log(evalPostfix('5 1 2 + 4 * + 3 -'))
A.14
B.-2
C.11
D.20
Answer: A
It prints 14. Trace the stack: push 5, 1, 2 → on + pop 1 and 2 giving 3, stack is [5, 3] → push 4 → on * 3×4 = 12, leaving [5, 12] → on + 17 → push 3 → on - 17 − 3 = 14.
When does the shunting-yard algorithm pop an operator off the stack?
A.Only when the whole expression has been scanned and the stack is drained
B.When the stack already holds more than two operators
C.When a new operand is encountered while scanning the infix expression
D.When the operator on top has precedence greater than or equal to the current one
Answer: D
When the operator at the top of the stack has precedence greater than or equal to the operator just scanned. Pop it straight to the output, repeat until the condition no longer holds, then push the new operator. An opening parenthesis is the exception: it blocks popping until a closing parenthesis is reached.
Preorder traversal of an expression tree produces which notation?
A.Postfix
B.Infix
C.No notation at all
D.Prefix
Answer: D
Prefix notation. In an expression tree, internal nodes are operators and leaves are operands. Preorder visits the operator before its two operands, exactly the + a b form. Correspondingly, postorder gives postfix and inorder gives infix.
Question 96·Postfix Notation & Expression Trees
Why is postfix notation unambiguous without parentheses?
A.Because the operands are reordered into the sequence they must be computed in
B.The operator's position already fixes which two operands belong to it
C.Because a postfix expression may contain at most one operator
D.Because postfix gives every operator the same precedence level
Answer: B
Because the operator's position already determines its two operands: they are always the two most recently completed results. There is no way to read it two different ways, so neither precedence nor parentheses are needed. With infix, a + b * c can be read two ways without precedence rules.
Two code blocks run in sequence, one O(n) and one O(n²). What is the total?
A.O(n)
B.O(n³)
C.O(n²)
D.O(n² + n)
Answer: C
O(n²). This is the sum rule: for sequential blocks, take the higher degree, since once n is large enough the smaller term no longer matters. Distinguish it from the product rule: only nested loops multiply degrees, giving O(n) × O(n²) = O(n³).
Question 98·Complexity
The inner loop runs 0 to i while the outer runs i from 0 to n. What order is the total?
javascript
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
work()
}
}
A.O(n log n)
B.O(n)
C.O(n²)
D.O(n³)
Answer: C
O(n²). The total iteration count is 0 + 1 + 2 + … + (n−1) = n(n−1)/2, which is about n²/2. Big-O drops the 1/2 constant, so it is still O(n²). The easy mistake: seeing the inner loop "only run up to i" and assuming it is cheaper, when in fact it is only cheaper by a factor of one half.
Question 99·Complexity
How many times does the loop for (i = 1; i < n; i *= 2) run?
A.About n/2 times
B.About √n times
C.Exactly n times
D.About log₂n times
Answer: D
About log₂n times. i takes the values 1, 2, 4, 8, …, 2^k and the loop stops once 2^k ≥ n, so k ≈ log₂n. For n = 1000 that is only about 10 iterations; for n = one million it is about 20.
Question 100·Complexity
How does Θ (theta) notation differ from Big-O?
A.Θ drops constants while O keeps the multiplicative constant
B.Θ counts memory while O only counts running time
C.Θ is for the average case and O for the worst case
D.Θ bounds both above and below while O only bounds above
Answer: D
Θ is a two-sided bound; O is only an upper bound. Saying binary search is O(n²) is not wrong — it really is no slower than n² — but it is useless. Saying Θ(log n) is the precise description. Ω is a lower bound, and Θ exists when O and Ω have the same degree.
How do "average-case" and "amortised" cost differ?
A.The two are really the same, differing only in what the literature calls them
B.Amortisation always gives a better result than the average
C.The average takes an expectation over the data while amortisation spreads across a sequence of operations
D.The average is for time while amortisation is for memory
Answer: C
Average-case is expectation over the input distribution — quicksort is O(n log n) on average, but bad input still gives O(n²). Amortised is cost spread evenly over a sequence of operations and is a firm guarantee: appending to a dynamic array is O(1) amortised, meaning n appends always take O(n), regardless of luck.
Does an algorithm's space complexity include the size of the input itself?
A.Yes, the total memory must always include the input data
B.It is only counted when the algorithm modifies the input data
C.It depends on the programming language used to implement it
D.Usually not; people report the auxiliary memory, that is the extra allocated
Answer: D
Usually no. The convention is to report auxiliary space — the extra memory allocated beyond the input. If the input were counted, every algorithm on an n-element array would be at least O(n) and the number would distinguish nothing. This convention is what makes "in-place sort" meaningful as O(1).
Algorithm A is O(n) with a huge constant, B is O(n²) with a tiny one. Which do you pick?
A.Always B, since a small constant is always faster in practice
B.Either works since Big-O drops the constants
C.Always A, since linear beats quadratic
D.It depends on n; you must estimate the break-even point before deciding
Answer: D
It depends on the actual n. Big-O only describes the trend as n tends toward infinity; for small n the constant factors dominate. The right approach is to estimate the break-even point — solve c₁·n = c₂·n² — and compare it with the range of n the real system actually encounters.
Question 104·Hash map & set
The two common collision strategies are chaining and open addressing. What is the basic difference?
A.Chaining is O(1) while open addressing is always O(n)
B.Chaining needs a good hash function while open addressing does not
C.Chaining is for string keys while open addressing is for numeric ones
D.Chaining puts the colliding elements outside the table while open addressing finds another free slot inside it
Answer: D
Chaining has each table slot point to a linked list holding all keys hashing to that slot. Open addressing keeps all elements directly in the table array: when a slot is occupied, probe by a rule — linear, quadratic, or double hashing — until an empty slot is found.
What is a hash table's load factor, and what happens when it exceeds the threshold?
A.The number of collisions so far; exceeding the threshold swaps the hash function
B.The lookups per second; exceeding the threshold queues the requests
C.The element-to-slot ratio; exceeding the threshold makes the table grow and rehash
D.The average bytes each element occupies; exceeding the threshold compacts the table
Answer: C
Load factor is number of elements divided by number of slots. Higher means more collisions and more probes. Exceeding the threshold — typically 0.75 for chaining and 0.5 to 0.7 for open addressing — triggers allocating a larger array, usually double, and rehashing all keys into the new table.
What property matters most in a good hash function for a hash table?
A.Resisting recovery of the original key from the hash value
B.Never producing the same hash value for two different keys
C.Producing hash values that increase with the key's order
D.Spreading the keys evenly across the slots even when the inputs have a pattern
Answer: D
Uniform distribution. The hash function must spread keys across all slots even when inputs are patterned — sequential numbers, names with common prefixes, evenly spaced memory addresses. Poor distribution lengthens collision chains and degrades lookup from O(1) to O(n).
Linear probing suffers from which phenomenon that degrades performance?
A.The occupied slots pile into adjacent clusters that keep growing
B.The hash value overflows once the table passes a certain size
C.The keys spread so evenly that the cache locality is lost
D.The table must rehash after each insertion to keep the probe chains short
Answer: A
Primary clustering. Linear probing moves to the next slot on collision, so occupied slots coalesce into contiguous clusters. The longer a cluster, the higher the chance a new key hashes into it and makes it even longer. This positive feedback loop sharply increases probe count as load factor rises.
Why is a hash table size often chosen to be a prime number?
A.It reduces clustering when the hash values share a factor with the table size
B.A prime number guarantees no two keys land in the same slot
C.A prime number makes the modulo operation faster on the processor
D.A prime number lets the table grow without rehashing the keys
Answer: A
To reduce clustering when hashes are patterned. If table size is 16, hash % 16 uses only the low four bits of the hash; keys differing only in high bits will all collide. A prime size makes the modulo depend on all bits, so distribution is more even.
Question 109·Hash map & set
A class overrides equals() but forgets to override hashCode(). What happens when it is used as a hash map key?
A.Two equal objects land in different buckets, so the lookup misses
B.The compiler errors out because equals() and hashCode() must be overridden together
C.Every object of that class is treated as equal
D.The hash map falls back to equals() in place of hashCode()
Answer: A
Two objects that are equals() have different hashes, so they land in different buckets. A hash map locates the bucket via hashCode() first, then calls equals() inside that bucket — different buckets means equals() is never invoked. Result: after map.put(key, v), map.get(equivalentKey) returns null.
How do DFS and BFS differ in memory usage on the same graph?
A.BFS costs less since the queue holds only one vertex at a time
B.Both always cost O(V) since both must store the visited set
C.DFS costs more since it must store every edge it has crossed
D.DFS costs by depth while BFS costs by the widest layer
Answer: D
DFS costs O(depth) for the stack, BFS costs O(widest layer) for the queue. On a wide, shallow branching graph DFS uses much less memory; on a deep, narrow graph the opposite. Both need an additional O(V) for the visited set.
How does cycle detection in a directed graph differ from an undirected one?
A.You must distinguish a vertex on the recursion stack from one already finished
B.You must skip the edge leading straight back to the parent you came from
C.You must run BFS instead of DFS since DFS cannot find directed cycles
D.Cycles in a directed graph cannot be found by traversal at all
Answer: A
You must use three states instead of two: unvisited, currently on the recursion stack, and fully processed. A cycle exists when you encounter a vertex currently on the stack. Meeting a fully processed vertex only means two paths lead to it, which is perfectly valid in a directed graph.
Kruskal and Prim both find a minimum spanning tree. How do their approaches differ?
A.Kruskal is for directed graphs and Prim for undirected ones
B.Kruskal considers the edges in increasing weight while Prim grows from one vertex
C.Kruskal gives the minimum spanning tree while Prim gives just any spanning tree
D.Kruskal needs positive weights while Prim accepts negative ones
Answer: B
Kruskal sorts all edges by increasing weight then takes each edge that does not create a cycle, using union-find to check. Prim starts from a vertex and at each step adds the lightest edge connecting the current tree to a vertex not yet in the tree, using a priority queue.
What kind of question does a union-find (disjoint set union) structure answer?
A.Listing every element currently belonging to a given group
B.Whether two elements are in the same group, and merging two groups
C.Sorting the elements by increasing key
D.The shortest path between any two vertices of a graph
Answer: B
Two questions: whether two elements are in the same group (find) and merging two groups (union). With two optimizations — path compression and union by rank — each operation is nearly O(1), precisely O(α(n)) where α is the inverse Ackermann function, below 5 for every practical n.
How do you count the connected components of an undirected graph?
A.Traverse from each unvisited vertex, counting how many times you must restart
B.Run Dijkstra from one vertex and count the unreachable vertices
C.Count the vertices and subtract the edge count
D.Count the vertices with degree zero
Answer: A
Iterate over every vertex; when you meet an unvisited vertex, increment the counter and run DFS or BFS from it to mark the entire connected region containing it. The number of times you must start a fresh traversal is the number of connected components. Cost is O(V + E), one full pass over the graph.
A sequence of steps qualifies as an algorithm only if it satisfies which property?
A.It finishes in polynomial time in the input size
B.It gives the same result for every possible input
C.It can be written in at least one high-level programming language
D.It halts after finitely many steps, each unambiguously defined
Answer: D
Two core properties: termination — it ends after finitely many steps — and definiteness — each step must be clear, with the same input always yielding the same sequence of operations. Textbooks often add: it has input, has output, and each step must be feasible to carry out.
What criteria determine whether a data structure is a good fit?
A.It reflects the problem correctly, the needed operations are fast enough, and it is memory-efficient
B.Whether it appears in the textbooks and the common references
C.How many lines of code it takes to implement
D.Whether the standard library of the language in use already provides it
Answer: A
Three criteria textbooks usually list: faithfully reflecting the problem's reality, frequent operations must be fast enough, and memory efficiency. Of the three, the second usually decides — you must identify which operation runs most often, then choose the structure optimal for that operation.
Question 117·Overview & ADTs
How does a primitive data type differ from a structured one?
A.A primitive cannot be used as a key in lookup data structures
B.A primitive is built into the language while a structured type is created by the programmer
C.A primitive uses less memory than a structured type
D.A primitive is a single indivisible value while a structured type groups several components
Answer: D
A primitive type holds a single indivisible value with no accessible internal components: integers, reals, characters, booleans. A structured type combines multiple components and allows accessing each part separately: arrays, records, strings, sets.
How does a static data structure differ from a dynamic one?
A.A static one lives on the stack while a dynamic one always lives on the heap
B.A static one's element values cannot be changed while a dynamic one's can
C.A static one has a fixed size from declaration while a dynamic one allocates more at runtime
D.A static one can only hold primitive types while a dynamic one can hold structured ones
Answer: C
A static structure fixes the number of elements at declaration time — a fixed-size array is the canonical example. A dynamic structure allocates and frees memory at runtime, so it flexes with actual demand — linked lists, trees, and dynamic arrays all belong to this group.
Why is declaring a variable by interface rather than concrete class beneficial?
A.You can change the implementation later without editing the code that uses it
B.The program runs faster because an interface is lighter than a concrete class
C.The compiler can catch more errors when it knows the exact interface
D.It saves memory since an interface carries no data of its own
Answer: A
Because calling code depends only on the contract, not on the implementation. Declaring List<T> ds = new ArrayList<>() means switching to LinkedList later requires changing exactly one line. If you declare ArrayList<T> directly, every place using that variable can become tied to the concrete class.
What role do pointers or references play in dynamic data structures?
A.Linking scattered memory regions into one related structure
B.Making indexed access faster than with an array
C.Freeing the memory automatically once an element is no longer used
D.Ensuring the structure's elements are always allocated next to each other
Answer: A
Pointers carry the relationships between elements. An array derives relationships from contiguous positions, so it needs no pointers. A dynamic structure allocates each node scattered across memory, so the only thing indicating which node connects to which is the pointer stored in each node.
For the same priority queue ADT, how does a sorted-list implementation differ from a heap?
A.A heap only works with numeric keys while a sorted list accepts any key type
B.Only a heap can correctly implement a priority queue's contract
C.A sorted list is more accurate than a heap when several items share a priority
D.A sorted list inserts in O(n) and removes in O(1) while a heap is O(log n) for both
Answer: D
Sorted list: insertion is O(n) because you must find the position and shift elements, while taking the highest-priority element is O(1) since it sits at the front. Heap: both insertion and removal are O(log n). Same ADT contract, two very different cost profiles.
For coin change with arbitrary denominations, why does greedily taking the largest coin fail?
A.Because greedy is much slower than dynamic programming
B.Because greedy cannot handle an amount that is too large
C.Because greedy requires the denominations to be pre-sorted in ascending order
D.The locally best choice can block the globally optimal solution
Answer: D
Because the best choice locally does not guarantee a globally optimal solution. The cleanest counterexample: denominations {1, 3, 4}, making change for 6. Greedy takes 4 and is then forced to take 1 and 1, three coins total. The optimal solution is 3 + 3, just two coins.
What is the core difference between dynamic programming and divide and conquer?
A.Dynamic programming is always written with loops and divide and conquer with recursion
B.Dynamic programming only solves optimization problems while divide and conquer solves any
C.Dynamic programming's subproblems overlap so storing the results pays off
D.Divide and conquer always gives a better complexity on the same problem
Answer: C
Dynamic programming subproblems overlap, while divide and conquer subproblems are disjoint. Merge sort splits an array into two non-overlapping halves, so storing results is useless. Fibonacci or the knapsack problem ask the same subproblem repeatedly, so caching it saves a great deal.
Edit distance between strings of length m and n uses a table of what size?
A.A one-dimensional table as long as both strings combined
B.An (m+n) × (m+n) table to hold every possible position pair
C.An m × n table, with no extra row and column for the empty string
D.An (m+1) × (n+1) table, each cell being the distance between two prefixes
Answer: D
A table of (m+1) × (n+1). Cell dp[i][j] is the edit distance between the first i characters of the first string and the first j characters of the second. Row 0 and column 0 correspond to the empty string, prefilled with 0, 1, 2, … because you must insert or delete everything. Cost is O(m·n) in both time and space.
What does Bellman's principle of optimality state?
A.A greedy algorithm always gives the optimum when the subproblems overlap
B.An optimization problem's optimal solution is always unique
C.Every sub-segment of an optimal solution must itself be optimal for that segment
D.Every optimization problem can be solved by dynamic programming
Answer: C
That every subpath of an optimal solution must itself be optimal for that subpath. This is the optimal substructure property. The argument: if a subpath were not optimal, replacing it with a better one would yield a better overall solution, contradicting the assumption that the original was optimal.
Memoisation provides no benefit for which of these algorithms?
A.The 0/1 knapsack solved recursively
B.Counting the paths from the top-left to the bottom-right of a grid
C.Merge sort, since its two halves never overlap
D.Naive recursive Fibonacci
Answer: C
Merge sort. It splits the array into two disjoint halves, so no subproblem is ever asked twice. A memo table would only waste memory and never hit. Memoisation only helps when subproblems overlap.
A.Append it at the end and rerun the heap-building procedure over the whole array
B.Put it at the root and push the old root down the appropriate branch
C.Put it in the last free position and bubble it up while it is smaller than its parent
D.Find the right position by value walking down from the root and insert there
Answer: C
Place the new element in the last empty slot to keep the tree complete, then sift up: compare with the parent, swap if smaller, and repeat until it is larger than the parent or reaches the root. Cost is O(log n) because the path from leaf to root is the height of the tree.
Why does building a heap from an array only need to sift from index n/2 backwards?
A.The indices from n/2 onwards are all leaves so they already satisfy the invariant
B.Because sifting the second half takes too long so it is skipped
C.Because the algorithm only guarantees the invariant for the array's first half
D.Because the array's second half always holds larger values than the first
Answer: A
Because every index from ⌊n/2⌋ onward is a leaf node. In the array representation of a heap, node i has children at 2i+1 and 2i+2; for i ≥ n/2 both indices are out of bounds. A leaf has no children, so it already satisfies the invariant and needs no sifting.
A.Sorting the graph's edges by increasing weight before traversing
B.Detecting a cycle of negative total weight during the traversal
C.Always removing the unfixed vertex with the smallest tentative distance
D.Storing every path found so far for later comparison
Answer: C
To always extract the unsettled vertex with the smallest tentative distance. This is the core greedy step: the vertex closest to the source among the unsettled ones has a distance that is already optimal, since any other path to it would have to pass through a farther vertex.
How much does it cost to check whether a specific value exists in a heap?
A.O(log n) on average, rising to O(n) in the worst case
B.O(n), since there is no direction to branch towards
C.O(1), since a heap is stored in an array so access is direct
D.O(log n), walking down from the root by value comparison as in a search tree
Answer: B
O(n) — you have to scan everything. The heap invariant only says a parent is smaller than its children; it says nothing about whether the target value is in the left or right branch. There is no direction to prune, so you cannot exploit the tree structure, unlike a binary search tree with O(log n).
31 more Advanced questions for Algorithms & Data Structures
Advanced goes deep on real-world scenarios and the technical pitfalls candidates actually run into. Included with Pro.
