Sorting and Searching Algorithms Questions

Comparison and non-comparison sorting (quicksort with its pivot and partition choices and hybrid cutoffs, mergesort, heapsort as a sort, insertion/selection/bubble, counting/radix/bucket), their stability, in-place behavior, stack depth and lower bounds, and choosing a sort from input constraints, including near-sorted data, library sorts (Timsort, introsort, language defaults), comparator design and expensive comparisons or copies. Also selection (quickselect, median-of-medians, nth_element), external merge sorting of data larger than memory (run generation and merge passes), and binary search with its variants: first/last occurrence, lower/upper bound, rotated arrays with or without duplicates, peak and mountain arrays, sorted matrices, unbounded search, loop-invariant correctness and off-by-one pitfalls, and binary search on an answer space (discrete or continuous, including k-th smallest by value). Includes divide-and-conquer reasoning for sorts (merge step, merging sorted arrays, median of two sorted arrays, inversion counting). Excludes heap data-structure mechanics and heap-based top-k and k-way merging, trees and tries, general graph search, distributed data-processing systems, approximate nearest-neighbor and streaming-sketch algorithms, and abstract Big-O comparison.

EasyTechnical
48 practiced

When is linear search a better choice than binary search? Cover array size, data layout, access cost, unsorted or streaming data, and give two concrete cases for each approach.

EasyTechnical
47 practiced

Implement selection sort in C++ to sort an array of integers in place. Do not use library sort functions. Provide complexity analysis and explain one scenario where selection sort might be preferable despite O(n^2) time.

EasyTechnical
92 practiced

When should you use your language's built-in sort instead of writing a custom one? Cover performance, stability, comparator correctness and maintainability, and describe how you would evaluate replacing an existing hand-written sort in a production codebase.

MediumTechnical
88 practiced

You are choosing a sort for a library that orders variable-length records by timestamp. It must be stable, have low tail latency, and be memory-efficient on 64-bit Linux. Compare Timsort, merge sort, in-place quicksort and radix sort and recommend one.

MediumTechnical
45 practiced

Given an m x n matrix where each row is sorted left-to-right and each column is sorted top-to-bottom, implement in Python def search_matrix(matrix: List[List[int]], target: int) -> bool that returns True when target exists. Aim for O(m+n) time using the staircase search (start at top-right or bottom-left). Explain why this method is preferred over naive binary search on every row for certain shapes of m and n and include sample inputs and constraints.

Unlock Full Question Bank

Get access to all Sorting and Searching Algorithms interview questions and detailed answers.

Sign in to Continue

Join thousands of developers preparing for their dream job.