Algorithms interview questions

22 questions on algorithms: Big-O, searching, the common sorts, hashing, graphs and trees, Dijkstra, two pointers, sliding window, recursion, and dynamic programming, with C# code.

01AlgorithmsFoundation

Big O (how we talk about speed)

Answer

  • Big O describes how runtime or memory grows as the input size n grows. Drop constant factors and lower-order terms so the dominant growth shows.
  • O(1) stays about the same cost as n grows. Array index lookup and hash map average get are common examples.
  • O(log n) grows slowly. Binary search on a sorted list halves the remaining range each step.
  • O(n) grows in a straight line with n. Scanning every item once is the usual case.
  • O(n log n) is common for efficient comparison sorts such as merge sort and typical quicksort average behavior.
  • O(n²) grows with nested loops over the same list. Classic bubble sort and naive pairwise checks fall here.
  • Unless someone asks for average or best case, people usually mean worst case.
  • Space complexity uses the same notation for extra memory beyond the input. Recursive call stacks count as space.
  • Compare algorithms by growth class first, then by constants and real data when classes match.
Flow diagram: How cost scales as n gets larger
C#
// Same work described at different growth rates
int Linear(int[] a, int target)
{
    for (var i = 0; i < a.Length; i++) // O(n)
        if (a[i] == target) return i;
    return -1;
}

int Binary(int[] sorted, int target)
{
    int lo = 0, hi = sorted.Length - 1;
    while (lo <= hi) // O(log n)
    {
        int mid = lo + (hi - lo) / 2;
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}


02AlgorithmsFoundation
Linear search
Answer
  • Walk the list from the start and compare each item to the target until you find a match or reach the end.
  • Works on unsorted data. You need no preprocessing beyond having the list in memory.
  • Time is O(n). Extra memory is O(1) when you scan in place.
  • Stop early when you find a match. If nothing matches, you checked every item.
  • Use linear search for small lists, one-off lookups, or data that is not sorted and not hashed.
  • If you search the same unsorted list many times, building a hash set or sorting once for binary search can pay off.
  • Pitfall: forgetting early exit still costs O(n) but wastes work on large hits near the front.
  • In interviews, state that average case is also O(n) when the target is equally likely in any position.
Flow diagram: Check each index until you hit 7
C#
int LinearSearch(int[] a, int target)
{
    for (int i = 0; i < a.Length; i++)
    {
        if (a[i] == target)
            return i;
    }
    return -1;
}


03AlgorithmsFoundation
Binary search
Answer
  • The list must already be sorted under the same comparison you use to search.
  • Look at the middle item. If it is too small, discard the left half. If it is too large, discard the right half.
  • Each step cuts the remaining range roughly in half, so the loop runs about log₂(n) times.
  • Time is O(log n). Iterative versions use O(1) extra memory. Recursive versions use O(log n) stack frames.
  • Use mid = lo + Math.floor((hi - lo) / 2) so the midpoint stays in range for large indexes.
  • Invariant: if the target exists, it always lies inside the current [lo, hi] (or half-open) bounds.
  • Decide whether any match, the leftmost match, or the rightmost match is required when duplicates exist.
  • Pitfall: mixing inclusive and exclusive bounds causes off-by-one infinite loops or skipped indexes.
  • Use binary search when data is sorted once and you need many lookups, or when finding a boundary in a monotone predicate.
Flow diagram: Sorted array: throw away half each time
C#
int BinarySearch(int[] a, int target)
{
    int lo = 0;
    int hi = a.Length - 1;

    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target)
            return mid;
        if (a[mid] < target)
            lo = mid + 1;
        else
            hi = mid - 1;
    }

    return -1;
}


04AlgorithmsFoundation
Bubble sort
Answer
  • Compare each pair of neighbors. Swap when they are out of order. Repeat passes until one pass does no swaps.
  • Each pass moves the largest remaining value toward the end of the array. After k passes, the last k items are in final order.
  • Average and worst case are O(n²). Best case is O(n) if you stop after a clean pass on already sorted input.
  • Extra memory is O(1). The sort is stable when you only swap on strict greater-than.
  • Fine for teaching adjacent swaps and early-exit ideas. Rarely the right pick for large data.
  • Compared with selection sort, bubble sort can finish early on nearly sorted data if you track swaps.
  • Pitfall: omitting the early-exit flag forces full O(n²) work even when the array is already sorted.
  • Interview tip: explain why libraries use O(n log n) sorts or insertion sort on small slices instead.
Flow diagram: One pass: largest value moves to the end
C#
void BubbleSort(int[] a)
{
    for (int i = 0; i < a.Length - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < a.Length - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                (a[j], a[j + 1]) = (a[j + 1], a[j]);
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
}


05AlgorithmsFoundation
Selection sort
Answer
  • For each index i, find the smallest value from i to the end and swap it into position i.
  • After k passes, the first k positions hold the k smallest values in sorted order. That is the loop invariant.
  • Comparisons are always Θ(n²). You always scan the unsorted suffix, even when the array is already sorted.
  • Extra memory is O(1). The number of swaps is at most n (one per outer step).
  • It does fewer swaps than bubble sort, but the asymptotic time class is still quadratic.
  • Not stable in the usual swap form, because a swap can jump equal keys past each other.
  • Use only for tiny arrays or when write cost dominates and you must minimize swaps.
  • Prefer insertion sort for nearly sorted data and merge or heap based sorts for large n.
Flow diagram: Each pass: swap the next minimum into place
C#
void SelectionSort(int[] a)
{
    for (int i = 0; i < a.Length - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < a.Length; j++)
        {
            if (a[j] < a[min])
                min = j;
        }
        (a[i], a[min]) = (a[min], a[i]);
    }
}


06AlgorithmsFoundation
Insertion sort
Answer
  • Keep a growing sorted prefix on the left. Take the next value and slide it left until it belongs.
  • Same motion as sorting cards in your hand: shift larger cards right, then drop the new card into the gap.
  • Best case is O(n) on already sorted input (one comparison per item). Average and worst case are O(n²).
  • Extra memory is O(1). The usual adjacent-shift form is stable.
  • Often fast on small or nearly sorted arrays. Many library sorts switch to insertion sort as a base case.
  • Invariant: after processing index i, the subarray from 0 through i is sorted.
  • Pitfall: shifting with the wrong bound can overwrite or skip the insertion spot.
  • Good interview contrast: adaptive like bubble with early stop, but usually fewer moves on nearly sorted data.
Flow diagram: Take the next value and slide it into the sorted left side
C#
void InsertionSort(int[] a)
{
    for (int i = 1; i < a.Length; i++)
    {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}


07AlgorithmsFoundation
Merge sort
Answer
  • Split the array in half, sort each half recursively, then merge the two sorted halves into one sorted array.
  • Merge walks both halves with two pointers and always takes the smaller next value into the output buffer.
  • Time is O(n log n) in the best, average, and worst cases. The recursion tree has log n levels, each doing O(n) merge work.
  • Needs O(n) extra memory for the merge buffers in a typical array implementation.
  • Stable: equal items keep their relative order when the merge prefers the left half on ties.
  • Use when you need guaranteed O(n log n), stability, or external sorting of large runs.
  • Pitfall: allocating a new buffer on every recursive call increases constants; reuse one buffer when possible.
  • Linked-list merge sort can merge with O(1) extra nodes beyond recursion, but the array form is the usual interview version.
Flow diagram: Split down, then merge sorted pairs back up
C#
int[] MergeSort(int[] a)
{
    if (a.Length <= 1)
        return a;

    int mid = a.Length / 2;
    int[] left = MergeSort(a[..mid]);
    int[] right = MergeSort(a[mid..]);
    return Merge(left, right);
}

int[] Merge(int[] left, int[] right)
{
    var result = new int[left.Length + right.Length];
    int i = 0, j = 0, k = 0;
    while (i < left.Length && j < right.Length)
        result[k++] = left[i] <= right[j] ? left[i++] : right[j++];
    while (i < left.Length) result[k++] = left[i++];
    while (j < right.Length) result[k++] = right[j++];
    return result;
}


08AlgorithmsFoundation
Quick sort
Answer
  • Pick a pivot. Partition so items less than the pivot go left and items greater go right. Recurse on both sides.
  • Average time is O(n log n). Worst case is O(n²) when partitions are badly unbalanced, for example sorted data with a fixed end pivot.
  • In-place Lomuto or Hoare partition uses O(log n) average stack space for recursion. Worst stack can reach O(n).
  • Not stable in the usual in-place form. Equal keys can change relative order across the pivot.
  • Random pivots or median-of-three reduce the chance of the worst case without changing average asymptotics.
  • Partition invariant: after partition, the pivot sits in its final sorted index.
  • Use when average speed and low extra memory matter more than worst-case guarantees or stability.
  • Pitfall: forgetting to exclude the pivot from both recursive ranges can cause infinite recursion.
  • Prefer merge sort or heapsort when you must bound the worst case tightly.
Flow diagram: Partition once around a pivot, then sort each side
C#
void QuickSort(int[] a, int lo, int hi)
{
    if (lo >= hi) return;

    int p = Partition(a, lo, hi);
    QuickSort(a, lo, p - 1);
    QuickSort(a, p + 1, hi);
}

int Partition(int[] a, int lo, int hi)
{
    int pivot = a[hi];
    int i = lo;
    for (int j = lo; j < hi; j++)
    {
        if (a[j] <= pivot)
        {
            (a[i], a[j]) = (a[j], a[i]);
            i++;
        }
    }
    (a[i], a[hi]) = (a[hi], a[i]);
    return i;
}


09AlgorithmsFoundation
Hashing and hash maps
Answer
  • A hash function maps a key to a bucket index in a table. Good hashes spread keys evenly across buckets.
  • Average lookup, insert, and delete are O(1) when the load factor stays reasonable and collisions stay short.
  • Collisions happen when two keys land in the same bucket. Chaining stores a list per bucket. Open addressing probes other slots.
  • Worst case can degrade toward O(n) if many keys collide or the hash is poor. Adversarial keys can trigger that path.
  • Common uses: counting frequencies, detecting duplicates, grouping, and constant-time membership checks.
  • Resize (rehash) when the load factor grows past a threshold so average chain or probe length stays short.
  • Pitfall: mutable keys that change after insert break lookup. Hash only immutable key material.
  • In interviews, contrast hash maps with trees: average O(1) vs ordered O(log n) with sorted iteration.
Flow diagram: Hash the key, then land in a bucket
C#
var counts = new Dictionary<string, int>();
foreach (var word in words)
{
    counts.TryGetValue(word, out int n);
    counts[word] = n + 1;
}

bool hasDup = counts.Values.Any(n => n > 1);


10AlgorithmsFoundation
Stack and queue
Answer
  • Stack: last in, first out (LIFO). Push and pop at the same end. Peek reads the top without removing it.
  • Queue: first in, first out (FIFO). Enqueue at the back, dequeue at the front.
  • Stacks undo work, parse nested structure (brackets, call frames), and drive iterative DFS.
  • Queues schedule work in arrival order and drive BFS level by level.
  • Array or linked-list backs are fine. Amortized O(1) push and pop are the usual expectation.
  • Deque variants allow insert and remove at both ends when the problem needs that flexibility.
  • In .NET, Stack<T> and Queue<T> are the common choices. Avoid the non-generic Stack and Queue types.
  • Pitfall: using a list and always shifting index 0 for a queue is O(n) per dequeue. Use a proper queue structure.
  • Interview check: name one algorithm that needs a stack and one that needs a queue, and say why order matters.
Flow diagram: Stack pops the newest; queue pops the oldest
C#
var stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
var top = stack.Pop(); // 2

var queue = new Queue<int>();
queue.Enqueue(1);
queue.Enqueue(2);
var first = queue.Dequeue(); // 1


11AlgorithmsFoundation
Breadth-first search (BFS)
Answer
  • Visit nodes level by level, starting from a source. All nodes at distance d are processed before distance d + 1.
  • Use a queue: dequeue a node, then enqueue its unseen neighbors. Mark visited when you enqueue (or dequeue) to avoid duplicates.
  • On an unweighted graph, the first time you reach a node is a shortest path in edge count.
  • Time is O(V + E) when each vertex and edge is processed a constant number of times. Extra memory can hold a whole frontier level.
  • Track a parent pointer or distance array if you must reconstruct the path or report lengths.
  • Works on trees and graphs. On graphs, the visited set is mandatory to stop cycles.
  • Use BFS for shortest unweighted paths, level-order tree walks, and connectivity from a start node.
  • Pitfall: marking visited too late can enqueue the same node many times and explode memory.
  • Prefer Dijkstra when edge weights are positive and not all equal.
Flow diagram: Queue order: finish a layer before the next
C#
IEnumerable<string> Bfs(Dictionary<string, List<string>> g, string start)
{
    var seen = new HashSet<string> { start };
    var q = new Queue<string>();
    q.Enqueue(start);

    while (q.Count > 0)
    {
        var node = q.Dequeue();
        yield return node;

        foreach (var next in g[node])
        {
            if (seen.Add(next))
                q.Enqueue(next);
        }
    }
}


12AlgorithmsFoundation
Depth-first search (DFS)
Answer
  • Go as deep as you can along one path, then backtrack. Explore one branch fully before siblings.
  • Use recursion or an explicit stack. Both express the same control flow.
  • Useful for cycle detection, topological ideas on DAGs, connected components, and path finding when any path is enough.
  • Time is O(V + E). Recursion depth can reach O(V) on a long chain and risk stack overflow.
  • Colors or visit states (unvisited, active, done) help detect back edges in directed graphs.
  • Preorder, inorder, and postorder on trees are DFS with different visit timing relative to children.
  • Use DFS when you need to explore structure deeply, build recursion-shaped answers, or walk component forests.
  • Pitfall: forgetting to mark visited on undirected graphs revisits edges and loops forever.
  • Convert to an explicit stack when input depth is not bounded by the language call stack.
Flow diagram: Stack/recursion order: finish a branch before siblings
C#
void Dfs(
    Dictionary<string, List<string>> g,
    string node,
    HashSet<string> seen,
    List<string> order)
{
    if (!seen.Add(node))
        return;

    order.Add(node);
    foreach (var next in g[node])
        Dfs(g, next, seen, order);
}


13AlgorithmsFoundation
Binary tree traversals
Answer
  • Preorder: visit the node, then left, then right. Useful to copy a tree or serialize structure root-first.
  • Inorder: left, then node, then right. On a binary search tree this visits keys in sorted order.
  • Postorder: left, then right, then node. Useful when children must finish before the parent (delete, evaluate expressions).
  • Level order is BFS on the tree: process nodes with a queue by depth.
  • Each of the three DFS orders visits every node once, so time is O(n) for n nodes. Extra space is O(h) for height h.
  • Recursive forms are clear. Iterative forms use an explicit stack (DFS) or queue (level order).
  • Pitfall: confusing inorder with preorder on a BST leads to wrong sorted claims.
  • Interview tip: say which order preserves BST sortedness and which orders suit serialize or free-node tasks.
  • Null children are base cases. Always define what empty left or right means in your walk.
Flow diagram: One tree, three visit sequences
C#
void Inorder(TreeNode? n, List<int> outList)
{
    if (n is null) return;
    Inorder(n.Left, outList);
    outList.Add(n.Val);
    Inorder(n.Right, outList);
}


14AlgorithmsFoundation
Two pointers
Answer
  • Two indexes move through a structure and shrink, grow, or cross a region of interest under a clear rule.
  • Classic case: sorted array, one pointer at each end. Move the end that fixes the sum toward the target.
  • Also used to remove duplicates in place, reverse an array, or partition around a pivot value.
  • Often turns a nested O(n²) scan into O(n) when sorted order or monotonic movement helps.
  • Invariant examples: everything left of i is processed, or the pair (lo, hi) still brackets any feasible answer.
  • Same-direction pointers (slow and fast) detect cycles in linked lists or find the middle node.
  • Pitfall: moving both pointers incorrectly can skip the only valid pair. Move one pointer per step based on the comparison.
  • Confirm the array is sorted when the algorithm depends on order. Unsorted input needs a different plan.
  • State time O(n) and extra space O(1) for the usual in-place forms.
Flow diagram: Sorted array: move the end that fixes the sum
C#
(int, int)? TwoSumSorted(int[] a, int target)
{
    int l = 0, r = a.Length - 1;
    while (l < r)
    {
        int sum = a[l] + a[r];
        if (sum == target) return (l, r);
        if (sum < target) l++;
        else r--;
    }
    return null;
}


15AlgorithmsFoundation
Sliding window
Answer
  • Maintain a contiguous window [left, right] while right advances through the array or string.
  • Grow the window by moving right. Shrink from the left when a constraint breaks (too many distinct chars, sum too large, and so on).
  • Common for longest substring without repeats, minimum window covering required counts, or max sum of a fixed-length window.
  • Often O(n) time because each index enters and leaves the window at most once when left only moves forward.
  • Use a counter map, frequency array, or running sum to test the window constraint in O(1) amortized time.
  • Fixed-size windows slide by adding the new right and removing the old left in one step.
  • Variable-size windows adjust left until the invariant holds again, then record a candidate answer.
  • Pitfall: shrinking past the needed left bound, or forgetting to update the answer after each valid growth.
  • Prefer two pointers language when the window is not contiguous or when ends move independently without a range invariant.
Flow diagram: Grow right; shrink left when the rule breaks
C#
int LongestUnique(string s)
{
    var last = new Dictionary<char, int>();
    int left = 0, best = 0;
    for (int right = 0; right < s.Length; right++)
    {
        char c = s[right];
        if (last.TryGetValue(c, out int prev) && prev >= left)
            left = prev + 1;
        last[c] = right;
        best = Math.Max(best, right - left + 1);
    }
    return best;
}


16AlgorithmsFoundation
Recursion
Answer
  • A function solves a smaller copy of the same problem, then combines the results into the answer for the current input.
  • Every recursive solution needs a base case that returns without another recursive call, or the chain never stops.
  • The call stack stores pending frames. Deep recursion can overflow even when the algorithm is correct.
  • Many recursive ideas have an iterative form with an explicit stack that holds the same pending work.
  • Factorial, tree walks, backtracking, and divide-and-conquer sorts are common examples.
  • Trust the induction view: assume smaller calls are correct, then prove the combine step is correct.
  • Pitfall: missing or unreachable base cases, overlapping subproblems without memoization, and huge branching factors.
  • Tail recursion can be rewritten as a loop. C# and many JS engines do not optimize tail calls into loops for you.
  • State both time (often related to the recursion tree size) and stack space when you analyze a recursive solution.
Flow diagram: Calls go down; returns multiply back up
C#
int Factorial(int n)
{
    if (n <= 1)
        return 1;
    return n * Factorial(n - 1);
}


17AlgorithmsFoundation
Reverse a linked list
Answer
  • Walk the list once. For each node, point its next to the previous node instead of the original successor.
  • Keep three references: previous (starts null), current (starts at head), and the next node to visit before you overwrite links.
  • Time is O(n). Extra memory is O(1) for the iterative version.
  • The old head becomes the tail with next = null. The last visited node becomes the new head.
  • Recursive reverse: reverse the rest, then attach the old head after the new tail of the rest. Uses O(n) stack space.
  • Invariant: at each step, previous points to the head of the already reversed prefix.
  • Pitfall: losing the next pointer before reading it, which orphans the remainder of the list.
  • Works the same for singly linked lists. Doubly linked lists also need to update previous links if you keep them.
  • Test empty list, single node, and two nodes. Those cases catch null and link bugs quickly.
Flow diagram: Flip each next pointer as you walk
C#
ListNode? Reverse(ListNode? head)
{
    ListNode? prev = null;
    var curr = head;
    while (curr is not null)
    {
        var next = curr.Next;
        curr.Next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}


18AlgorithmsFoundation
Binary heap / priority queue
Answer
  • A binary heap is a complete binary tree stored in an array. Parent and child indexes use simple arithmetic (for 0-based: children at 2i+1 and 2i+2).
  • Min-heap: parent is never larger than its children. Max-heap is the mirror rule. The root holds the extreme value.
  • Peek is O(1). Insert and remove-root are O(log n) after sift up or sift down restores the heap property.
  • Build-heap from an unordered array can run in O(n) with bottom-up sift down (Floyd).
  • In .NET, PriorityQueue<TElement, TPriority> is the built-in heap for priority scheduling.
  • Heaps power Dijkstra, top-k problems, median maintenance with two heaps, and heap sort.
  • Heap sort extracts the root repeatedly. Time is O(n log n). It is not stable.
  • Pitfall: treating a heap as fully sorted. Only the root is guaranteed extreme. The rest is partially ordered.
  • Prefer a balanced BST or sorted structure when you need ordered iteration of all keys, not only repeated extract-min.
Flow diagram: Min-heap tree and the matching array
C#
var pq = new PriorityQueue<string, int>();
pq.Enqueue("task-a", 2);
pq.Enqueue("task-b", 1);
var first = pq.Dequeue(); // task-b (priority 1)


19AlgorithmsIntermediate
Dijkstra's shortest path
Answer
  • Finds the cheapest path from a start node to others when every edge weight is non-negative.
  • Keep a best-known distance for each node, initialized to infinity except the start at zero.
  • Always expand the unsettled node with the smallest known distance next. A binary heap priority queue supports that choice.
  • Relax neighbors: if going through the current node is cheaper, update that neighbor's distance and push it to the queue.
  • With a binary heap, a common bound is O((V + E) log V). Fibonacci heaps improve the theory but are rare in practice.
  • Negative edge weights invalidate the greedy settle step. Use Bellman-Ford (or other methods) when negatives exist.
  • Invariant: once a node is settled with the classic decrease-key form, its distance is final for non-negative weights.
  • Pitfall: allowing negative weights silently produces wrong answers. State the non-negative precondition.
  • Use Dijkstra for maps, routing, and weighted graphs without negatives. Prefer BFS when all weights are equal.
Flow diagram: Always settle the closest remaining node
C#
static Dictionary<string, int> Shortest(Dictionary<string, List<(string To, int W)>> g, string start)
{
    var dist = g.Keys.ToDictionary(k => k, _ => int.MaxValue);
    dist[start] = 0;
    var pq = new PriorityQueue<string, int>();
    pq.Enqueue(start, 0);

    while (pq.TryDequeue(out var u, out var priority))
    {
        if (priority > dist[u]) continue; // stale queue entry
        foreach (var (v, w) in g[u])
        {
            var next = dist[u] + w;
            if (next >= dist[v]) continue;
            dist[v] = next;
            pq.Enqueue(v, next);
        }
    }
    return dist;
}


20AlgorithmsIntermediate
Dynamic programming (intro)
Answer
  • DP stores answers to overlapping subproblems so you never recompute them. Optimal substructure lets you build larger answers from smaller ones.
  • Start from a recurrence plus base cases. Fill a table bottom-up, or memoize top-down from the original call.
  • Classic starters: Fibonacci with an array, or the number of ways to climb stairs taking 1 or 2 steps.
  • Time often drops from exponential naive recursion to time proportional to the number of distinct states times work per state.
  • Ask: can the problem be built from smaller solved pieces with a clear state and a recurrence?
  • Define the state carefully (index, remaining capacity, last choice). Wrong state design either misses answers or explodes the table.
  • Space can sometimes shrink from a full table to a few rolling rows when the recurrence only needs recent layers.
  • Pitfall: confusing DP with greedy. Greedy picks locally without storing a table of overlapping subanswers.
  • Interview flow: state the recurrence, base cases, order of filling, and final answer cell.
Flow diagram: Build fib(n) from two smaller answers
C#
int ClimbStairs(int n)
{
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++)
    {
        int next = a + b;
        a = b;
        b = next;
    }
    return b;
}


21AlgorithmsAdvanced
Advanced: binary search bugs
Answer
  • Off-by-one bugs come from mixing inclusive and exclusive bounds. Pick one scheme (closed [lo, hi] or half-open [lo, hi)) and stick to it.
  • mid = (lo + hi) / 2 can overflow fixed-width signed integers when lo and hi are large. mid = lo + (hi - lo) / 2 stays safe.
  • With duplicates, decide whether you need any match, the leftmost, or the rightmost. The loop updates for lo and hi change for each goal.
  • The array must be sorted under the same comparison the search uses. A mismatched comparer returns wrong answers without throwing.
  • Infinite loops happen when mid equals lo or hi and you do not shrink the range. Ensure every branch moves lo or hi.
  • For lower_bound style search, keep the first index where the predicate becomes true, and narrow until lo == hi.
  • Test empty arrays, one element, target below minimum, target above maximum, and runs of duplicates.
  • Pitfall: using < vs <= inconsistently between the while condition and the mid branch.
  • Write the invariant in a comment during interviews so reviewers see that the answer always stays inside the live range.
Flow diagram: After comparing mid, move lo or hi past mid
C#
// Leftmost index of target, or -1
int LowerBound(int[] a, int target)
{
    int lo = 0, hi = a.Length; // exclusive hi
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo < a.Length && a[lo] == target ? lo : -1;
}


22AlgorithmsAdvanced
Advanced: recursion depth limits
Answer
  • Each recursive call uses stack space for the frame. Deep trees or long linked lists can overflow before the work finishes.
  • C# does not turn tail calls into loops the way some functional runtimes do. Use an explicit Stack<T> or a loop for unbounded depth.
  • Convert recursive DFS to a stack loop when input size is not capped by a known small height.
  • Memoization still walks a deep cold path on the first call. Skewed inputs can blow the stack before the cache helps.
  • JavaScript engines also have finite call stacks. Prefer iterative forms for adversarial or very deep inputs.
  • Estimate worst depth: a linked list of n nodes or a skewed binary tree needs Θ(n) frames in naive recursion.
  • Pitfall: assuming balanced trees. Interview inputs often include the skewed case on purpose.
  • When you must keep recursion for clarity, document the depth bound or raise the stack only in controlled environments.
  • Pair this topic with binary heap and graph DFS: algorithms that look fine asymptotically can still fail on stack limits.
Flow diagram: Call stack depth vs an explicit heap stack
C#
// Recursive
void Dfs(Node n)
{
    Visit(n);
    foreach (var c in n.Children) Dfs(c);
}

// Iterative
void DfsIter(Node root)
{
    var stack = new Stack<Node>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var n = stack.Pop();
        Visit(n);
        for (var i = n.Children.Count - 1; i >= 0; i--)
            stack.Push(n.Children[i]);
    }
}


Sources and further reading