Comprehensive Guide to 69 High‑Frequency Algorithm Interview Questions with Solutions

The author, Xiao Hao, shares a massive compilation of 69 high‑frequency algorithm interview questions drawn from the classic "剑指 Offer" book, providing brief English descriptions, key insights, and visual illustrations for each problem.

Interview Question 1 : Assignment‑operator overloading – tests copy constructors, destructors, and operator overloading in C++.

Interview Question 2 : Implementing the Singleton pattern – discusses lazy (thread‑unsafe) vs. eager (thread‑safe) implementations and the double‑checked locking technique with the volatile keyword.

Interview Question 3 : Searching in a row‑ and column‑sorted 2‑D array – start from the top‑left corner and move down or left based on comparison with the target.

Interview Question 4 : Replacing spaces in a string – use a two‑pointer technique from the end after calculating the final length to avoid repeated shifting.

Interview Question 5 : Printing a linked list from head to tail using a stack to reverse the order.

Interview Question 6 : Reconstructing a binary tree from preorder and inorder traversals – locate the root in inorder, split left/right subtrees, and recurse.

Interview Question 7 : Implementing a queue with two stacks – push to Stack1, pop by transferring elements to Stack2 when needed.

Interview Question 8 : Finding the minimum element in a rotated sorted array – a modified binary search that handles equal elements by linear scan when necessary.

Interview Question 9 : Fibonacci sequence without recursion – store the two previous numbers in an array; also mentions variations like frog‑jump problems.

Interview Question 10 : Counting the number of 1s in a binary integer – repeatedly apply n = n & (n-1) and count iterations; also notes related tricks for power‑of‑two detection and bit‑difference calculation.

Interview Question 11 : Computing a number’s integer power – discusses handling negative exponents, zero base, floating‑point tolerance, and a recursive approach using exponentiation by squaring.

Interview Question 12 : Printing all numbers with up to n digits – use string‑based addition to avoid overflow and handle leading zeros correctly.

Interview Question 13 : Deleting a node from a singly linked list in O(1) time – copy the next node’s data when the node is not the tail; handle head‑only and tail cases separately.

Interview Question 14 : Reordering an array so that odd numbers appear before even numbers – use a two‑pointer approach similar to quicksort partitioning.

Interview Question 15 : Finding the k‑th node from the end in a linked list – advance a first pointer k‑1 steps, then move both pointers together until the first reaches the tail.

Interview Question 16 : Reversing a linked list recursively and iteratively – handle empty or single‑node lists, maintain previous/current/next pointers, and discuss a recursive variant.

Interview Question 17 : Merging two sorted linked lists – take care of empty‑list inputs to avoid crashes.

Interview Question 18 : Determining whether a tree is a subtree of another – check for null pointers to prevent dereferencing errors.

Interview Question 19 : Mirroring a binary tree – handle null root and leaf nodes appropriately.

Interview Question 20 : Clockwise matrix printing – consider edge cases where only a subset of the four directions is possible in the final layer.

Interview Question 21 : Stack that supports retrieving the minimum element – maintain a secondary minStack alongside the main data stack.

Interview Question 22 : Validating a push/pop sequence using an auxiliary stack – compare the top of the auxiliary stack with the next element of the pop sequence.

Interview Question 23 : Level‑order traversal (printing a binary tree from top to bottom) – use a queue; the same idea applies to BFS on directed graphs.

Interview Question 24 : Verifying a post‑order sequence of a binary search tree – recursively split the sequence into left/right sub‑trees based on the root value.

Interview Question 25 : Finding all root‑to‑leaf paths whose sum equals a target – solved via recursion.

Interview Question 26 : Copying a complex linked list with random pointers – create new nodes, copy .val , .next , and .random fields, handling null pointers carefully.

Interview Question 27 : Converting a binary search tree into a doubly linked list – recursively connect left subtree’s rightmost node to the root and right subtree’s leftmost node to the root.

Interview Question 28 : Generating all permutations of a string – recursively insert each character into all positions of previously generated substrings.

Interview Question 29 : Finding the element that appears more than half the time – use a quick‑select‑like partition or Boyer‑Moore voting algorithm with a final verification step.

Interview Question 30 : Finding the smallest k numbers – either quick‑select partition (O(n)) or maintain a max‑heap of size k while scanning (O(n log k)).

Interview Question 31 : Maximum subarray sum – Kadane’s algorithm or dynamic programming, maintaining current sum and global maximum.

Interview Question 32 : Counting the number of digit ‘1’ appearing from 1 to n – use positional analysis to compute contributions of each digit place.

Interview Question 33 : Forming the smallest number by concatenating an array of integers – compare string concatenations mn vs nm to decide order, then sort accordingly.

Interview Question 34 : Generating ugly numbers – use three pointers for multiples of 2, 3, and 5, selecting the minimum each step.

Interview Question 35 : Finding the first non‑repeating character in a string – hash table for counts, then a second pass to locate the character with count 1.

Interview Question 36 : Counting inverse pairs in an array – use a merge‑sort based approach that counts how many elements from the right sub‑array are placed before elements from the left.

Interview Question 37 : Finding the first common node of two linked lists – align lengths by advancing the longer list, then move both pointers together.

Interview Question 38 : Counting occurrences of a target number in a sorted array – two binary‑search passes to find the first and last positions.

Interview Question 39 : Computing the depth of a binary tree – recursive definition where depth = max(leftDepth, rightDepth) + 1.

Interview Question 39 (Balance Check) : Determining whether a binary tree is height‑balanced – compare left/right subtree heights and ensure the difference ≤ 1 for every node.

Interview Question 40 : Finding the two numbers that appear only once in an array where every other number appears twice – use XOR to isolate the differing bit, then partition and XOR each group.

Interview Question 41 : Two‑sum problem – two‑pointer technique on a sorted array to find a pair that sums to a target.

Interview Question 42 : Finding all continuous positive integer sequences that sum to s – sliding‑window with two pointers small and big .

Interview Question 43 : Reversing the order of words in a sentence – reverse the whole string, then reverse each word individually.

Interview Question 44 : Left‑rotating a string by n characters – reverse the whole string, then reverse the two parts split at len‑n .

Interview Question 45 : Computing the probability distribution of the sum of n dice – dynamic programming with two arrays, updating counts for each additional die.

Interview Question 46 : Determining whether a hand of cards can form a straight – map face cards to numbers, sort, count gaps, and compare with the number of jokers (zeros).

Interview Question 47 : Josephus problem – recurrence f[i] = (f[i‑1] + m) % i gives the survivor’s position.

Interview Question 48 : Summation 1 + 2 + … + n – recursive implementation using two functions, one for the recursive step and one for termination.

Interview Question 49 : Adding two integers without using +, – use bitwise XOR for sum without carry and (a & b) << 1 for the carry, repeat until carry is zero.

Interview Question 50 : Converting a string to an integer – handle null, empty, sign characters, and invalid non‑digit characters robustly.

Interview Question 51 : Lowest common ancestor in a binary tree – for BST use value comparisons; for a general binary tree, find paths from root to each node and compare.

Interview Question 52 : Finding a duplicate number in an array where numbers range from 0 to n‑1 – either sort, use a hash set, or perform in‑place swapping to place each number at its index.

Interview Question 53 : Constructing a product array where each element is the product of all other elements – initialize result vector with 1s and compute prefix and suffix products.

Interview Question 54 : Regular expression matching – implement a recursive or DP matcher that respects '.' and '*'.

Interview Question 55 : Validating numeric strings – ensure proper placement of signs, decimal points, and exponent 'E' with integer exponent.

Interview Question 56 : First non‑repeating character in a stream – maintain a hash map for counts and a queue for order.

Interview Question 57 : Detecting the entry node of a cycle in a linked list – use fast/slow pointers to find meeting point, then locate cycle length and entry.

Interview Question 58 : Deleting duplicate nodes from a sorted linked list – use previous pointer to skip over duplicates.

Interview Question 59 : Finding the next node in an in‑order traversal of a binary tree – consider right subtree, parent left‑child relationship, or climb up to the first ancestor where current node is a left child.

Interview Question 60 : Checking whether a binary tree is symmetric – compare left‑right subtrees recursively or iteratively using a queue.

Interview Question 61 : Printing a binary tree level by level – use two queues to alternate between current and next level.

Interview Question 62 : Zigzag level order traversal – use two stacks to reverse the order of nodes on alternating levels.

Interview Question 63 : Serializing and deserializing a binary tree – preorder traversal with a sentinel (e.g., "#") for null nodes.

Interview Question 64 : Finding the k‑th smallest element in a BST – inorder traversal yields sorted order.

Interview Question 65 : Maintaining the median of a data stream – two heaps (max‑heap for lower half, min‑heap for upper half) with rebalancing.

Interview Question 66 : Sliding‑window maximum – deque stores indices of useful elements in decreasing order.

Interview Question 67 : Finding a path in a matrix – backtracking from each cell, matching characters sequentially.

Interview Question 68 : Robot movement range – backtracking with digit‑sum constraint on coordinates.

Interview Question 69 : Solving the eight‑queen puzzle – backtracking with conflict checks on rows, columns, and diagonals.