Sorting and Searching Algorithms Questions

Core computer science algorithms for ordering and locating data, including understanding, implementing, and applying common sorting algorithms and search techniques and analyzing their performance. Candidates should know comparison sorts such as merge sort, quick sort, heap sort, insertion sort, selection sort, and bubble sort and understand stability, in place versus out of place behavior, and best average and worst case time and space complexities. They should master binary search and linear search and variations and know when searching requires a different approach. Knowledge should include algorithmic patterns such as divide and conquer and two pointers, selection algorithms such as quickselect and nth element, and non comparison sorts such as counting sort, radix sort and bucket sort when appropriate. Candidates must be able to implement clean iterative or recursive versions, reason about recursion depth and stack usage, explain trade offs between using built in language sort utilities and custom implementations, and choose the right algorithm for a problem based on input size, memory constraints, and stability requirements. Interviewers often assess coding correctness, complexity analysis using big O notation, edge cases, comparator usage for custom ordering, and ability to justify algorithm choices.

MediumSystem Design

60 practiced

Design and implement (pseudocode acceptable) a k-way merge algorithm to merge k sorted files into a single sorted output when each file may be large (up to 10GB) but you have limited RAM (8GB). Explain buffering strategy, I/O patterns, min-heap usage and overall complexity statements. Describe how you'd implement this on a single machine and how you'd scale it across multiple machines.

Sample Answer

Requirements:- Merge k sorted files (each up to 10GB) into one sorted output.- RAM limited to 8GB; assume disk sequential I/O is fastest.- Stable merge, support numeric or comparable records.

High-level approach:- Use external k-way merge with buffered I/O and a min-heap of size k.- Read each file in a fixed-size read buffer (e.g., 32–128 MB) to keep memory <8GB including heap and output buffer.- Maintain an output buffer to batch writes (e.g., 64–128 MB) for sequential writes.

Pseudocode (Python-like):

python

# buffer_size per file ~ 64MB; adjust so k*buffer + output_buffer + heap < 8GB
class FileBuffer:
    def __init__(self, path, buf_bytes):
        self.f = open(path, 'rb')
        self.buf = read_chunk(self.f, buf_bytes)  # in-memory list/iterator of records
        self.idx = 0
    def peek(self): return self.buf[self.idx] if self.idx < len(self.buf) else None
    def pop(self):
        val = self.buf[self.idx]; self.idx += 1
        if self.idx >= len(self.buf):
            self.buf = read_chunk(self.f, buf_bytes)
            self.idx = 0
        return val

# initialize
buffers = [FileBuffer(path, buf_bytes) for path in input_paths]
heap = []
for i, buf in enumerate(buffers):
    v = buf.peek()
    if v is not None: heappush(heap, (v, i))

out_buf = []
while heap:
    val, i = heappop(heap)
    out_buf.append(val)
    if len(out_buf) >= OUT_BATCH:
        write_batch(output_file, out_buf); out_buf.clear()
    buffers[i].pop()  # advance
    nxt = buffers[i].peek()
    if nxt is not None: heappush(heap, (nxt, i))

if out_buf: write_batch(output_file, out_buf)

Key concepts and reasoning:- Min-heap of size k gives O(log k) per record to pick next smallest.- Buffering reduces syscalls and turns random small reads into large sequential reads.- Choose buffer sizes so total in-memory = k*buf + output_buf + heap_overhead <= 8GB. Example: k=100, buf=64MB -> 6.4GB.

I/O patterns:- Sequential reads in large chunks from each file; refill only when buffer consumed.- Writes are batched sequential writes.

Complexity:- Time: O(N log k) where N = total records; dominated by disk I/O when data large.- Space: O(k * buffer_size + output_buffer + heap) in RAM.

Single-machine tuning:- Tune buf sizes to disk bandwidth; use asynchronous prefetching threads per file to hide latency.- Use memory-mapped files if records are fixed-size for zero-copy reads.

Scaling across machines:- Partition inputs by key range (range-sharding) or hash to produce disjoint sub-keys; assign each shard to a worker that performs local k-way merge.- Alternatively use two-phase external merge: Map phase merges subsets into sorted runs -> Shuffle to reducers that merge runs into final ranges.- Use distributed storage (HDFS/S3) and workers reading runs; final step concatenates range-ordered outputs.

Trade-offs:- More buffers -> fewer I/O refills but higher memory. Range-sharding requires choosing boundaries; sampling helps.- For very large k, multi-level merge: merge groups into intermediate runs, then final merge to reduce heap size.

EasyTechnical

65 practiced

Explain non-comparison sorts: counting sort, radix sort, and bucket sort. For each, describe constraints on keys (range, integer vs. float), stability, time and space complexity, and practical applications in AI/data processing (e.g., histogramming integer features, batching by bucketed keys). When would these outperform comparison sorts for large datasets of integers?

Sample Answer

Non-comparison sorts exploit key structure instead of pairwise comparisons. Briefly:

Counting sort- Keys: non-negative integers (or mapped to small integer range) with range U.- Stable: yes (if implemented by scanning cumulative counts).- Time: O(n + U). Space: O(n + U).- Use cases: histogramming integer features, converting categorical labels to counts, fast preprocessing for one-hot / embedding frequencies.- When better: when U = O(n) (or small constant factor) so O(n) beats O(n log n).

Radix sort- Keys: integers or fixed-length digit strings; can handle floats by bitwise reinterpretation or separate sign/exponent/mantissa processing.- Stability: stable if each digit pass uses a stable subroutine (usually counting sort).- Time: O(d (n + b)) where d = digits, b = base per digit. For w-bit integers, O((w / log b) * (n + b)). Space: O(n + b).- Use cases: sorting 32/64-bit integer IDs, large index arrays, batching by hashed keys, lexicographic sorting of fixed-length tokens.- When better: when key width is bounded and d is small → linear-time practical advantage for large n.

Bucket sort- Keys: typically real numbers in a known range (e.g., [0,1)); works for floats if distribution is roughly uniform or buckets sized appropriately.- Stability: can be stable depending on bucket implementation and internal sort.- Time: average O(n + k) where k = number of buckets (with O(n²) worst-case if buckets uneven and internal sort is quadratic). Space: O(n + k).- Use cases: approximate quantile computation, stratified batching, distributing items for parallel processing, smoothing continuous features.- When better: when keys are uniformly distributed so buckets remain small — gives near-linear performance.

Practical notes for AI/data pipelines- Use counting/radix for massive integer keys (IDs, binned features, discrete vocab indices) to build frequency tables, sharding maps, or sorted indices quickly.- Bucket sort is useful for bucketing continuous features for stratified sampling, minibatch construction, or approximate quantiles.- They outperform comparison sorts when keys are low-entropy, bounded, or fixed-size (leading to O(n) behavior) and when memory for auxiliary arrays is acceptable.

HardTechnical

64 practiced

Design a GPU-accelerated sorting pipeline (conceptual) to sort 100M 32-bit keys using CUDA/Thrust or similar primitives. Discuss algorithm choices (radix sort vs sample sort vs merge sort), memory layout for coalesced access, shared-memory optimization, number of kernel launches, and how to integrate the result into a PyTorch data pipeline with minimal PCIe transfers.

Sample Answer

Approach summary- For 100M 32-bit keys (~400 MB), prefer a GPU-first radix-sort pipeline (fast, memory-friendly) with fallback to a multi-stage sample/merge for extreme skew or if stable global ordering with payloads is required. Use CUDA primitives (CUB/Thrust) for building blocks: block/radix histograms, block-wide scan, and device-wide scatter.

Algorithm choice and why- Radix sort (LSD) is typically best for raw 32-bit keys: deterministic O( (N / W) * B ) work, few passes, avoids expensive comparisons. Use 8-bit digits → 4 passes; or 11/11/10 for fewer passes with bigger shared histograms tradeoff.- Sample sort / GPU merge-sort is attractive if keys are large records or need strictly stable global partitioning: sample to choose P pivots, partition into buckets (each fits in one GPU block-range), then local sort. Use when distribution is highly skewed or when merging sorted runs from other sources.- Merge-sort (parallel merge) higher branch/divergence and more memory movement; use only if comparisons are cheap and radix impossible (non-integer keys) or stable complex keys.

Memory layout & coalescing- Keys (and optional values/indices) stored in SoA: separate arrays for keys and values to ensure coalesced 128B loads/stores. Align arrays to 128B and use uint32_t for keys.- Process in 128-thread warps accessing contiguous addresses: thread t reads element base + t for coalesced memory.- Use double-buffering: ping-pong between input and output buffers across radix passes to avoid atomic contention.

Shared-memory optimizations- Per-block histograms in shared memory (e.g., 256 bins for 8-bit digits) using warp-cooperative aggregation: each warp computes local histogram in registers then reduces to shared histogram with atomic adds or warp-aggregates to reduce atomic pressure.- Use warp-aggregated prefix-sum for fast local offsets, then a device-wide prefix-sum of block histograms (using CUB DeviceScan) to compute global bucket offsets.- For local sorts (within bucket), leverage shared-memory sorting (e.g., bitonic or merge networks) for buckets that fit in shared memory to avoid global memory writes.

Kernel launches & pipeline- Per radix digit: (1) histogram kernel (per-block local histograms), (2) global prefix-sum on histogram (CUB DeviceScan), (3) scatter kernel that writes keys to final position using computed offsets. So ~3 kernels per pass → ~12 kernels for 4-pass 8-bit radix.- Reduce kernel count by fusing histogram + scatter where feasible (block computes local hist, then does a block-level exclusive scan and writes) but needs careful synchronization—fusing reduces global memory roundtrips.- Use multiple CUDA streams to overlap GPU compute with PCIe/H2D transfers or other GPU work. Use persistent kernels or cooperative groups when latency-critical.

Handling values/indices and stability- Move (key, payload) pairs as two arrays (keys[], values[]) and scatter both concurrently to maintain alignment. If stability required, include original index as secondary key or perform stable radix by processing LSB→MSB.

Dealing with skew & large buckets- Use sample sort hybrid: sample ~sqrt(N) keys, pick pivots, partition to P buckets balanced to ~N / P, then radix-sort each bucket in parallel (helps avoid hot-buckets causing load imbalance).

Integration with PyTorch / minimizing PCIe transfers- Keep all data on the GPU. Expose the sorted device buffer to PyTorch without copying: - Use DLPack: create a CUDA device buffer (raw pointer) in your CUDA extension and wrap it as a torch tensor via from_dlpack / to_dlpack (or use torch.utils._dlpack if C++). This avoids host roundtrip. - Alternatively, write a custom C++/CUDA extension (ATen/TorchScript) that returns an at::Tensor pointing to the GPU allocation used by your sort (make sure memory is managed correctly).- If upstream data originates on CPU, use pinned host memory + async cudaMemcpyHtoD with streams to overlap transfer while previous GPU sort runs.- For a training pipeline: prefetch and sort on the same GPU used for training if possible; otherwise use NVLink / GPUDirect RDMA or peer-to-peer transfers to avoid PCIe when moving between GPUs.- Only transfer minimal required slices to host for further CPU-only processing. For DataLoader interaction, return torch tensors already on cuda:0 so no PCIe copy occurs when the training loop consumes them.

Practical performance tips- Use CUB/Thrust where possible for well-optimized primitives (DeviceRadixSort::SortKeys, etc.) and measure. CUB’s radix is highly optimized and can often beat custom kernels.- Tune block size and histogram bin granularities for target GPU (shared mem limit, L2).- Benchmark memory bandwidth: with 400 MB of keys, 4 passes → ~1.6 GB read + write, so ensure memory bandwidth is saturated.- Profile with nvprof/nsight to find bank conflicts, uncoalesced accesses, and atomics hot spots.

Edge cases- Duplicate-heavy data: ensure histograms can handle large counts without overflow; choose stable approach if duplicates require deterministic secondary order.- Out-of-GPU-memory: process in chunks and use external merge (GPU-based merges) to assemble final sorted sequence.

This design balances raw throughput (radix on GPU), load-balanced scaling (sample partitions), reduced kernel overhead (fused ops where safe), and zero-copy integration into PyTorch via DLPack/C++ extensions to avoid PCIe penalties.

HardTechnical

52 practiced

Implement the deterministic linear-time selection algorithm (median of medians) in Python to find the k-th smallest element. Provide correct code that partitions into groups of 5, finds median-of-medians pivot, and achieves worst-case O(n). Discuss constant factors and when you might prefer randomized Quickselect instead.

Sample Answer

To guarantee worst-case linear time, we use the median-of-medians pivot: partition the array into groups of 5, find each group's median (by sorting 5 elements), recursively find the median of those medians, use it as pivot to partition, then recurse on the appropriate side.

python

def select_kth(a, k):
    """
    Return k-th smallest element (0-based k) in list a.
    Worst-case O(n) using median-of-medians with groups of 5.
    """
    if not 0 <= k < len(a):
        raise IndexError("k out of range")

    def pivot_single(arr):
        # For small arrays, sort and return median directly
        n = len(arr)
        if n <= 5:
            return sorted(arr)[n // 2]
        # Partition into groups of 5 and collect medians
        medians = []
        for i in range(0, n, 5):
            group = sorted(arr[i:i+5])
            medians.append(group[len(group)//2])
        # Recursively select median of medians
        return pivot_single(medians)

    def partition(arr, pivot):
        lows, highs, pivots = [], [], []
        for x in arr:
            if x < pivot:
                lows.append(x)
            elif x > pivot:
                highs.append(x)
            else:
                pivots.append(x)
        return lows, pivots, highs

    def select(arr, k):
        if len(arr) <= 5:
            return sorted(arr)[k]
        pivot = pivot_single(arr)
        lows, pivots, highs = partition(arr, pivot)
        if k < len(lows):
            return select(lows, k)
        elif k < len(lows) + len(pivots):
            return pivot  # k falls within pivot-equals
        else:
            return select(highs, k - len(lows) - len(pivots))

    return select(list(a), k)

Key points:- Time: O(n) worst-case; space: O(n) due to partitioning (can be made in-place but more complex).- Constant factors: groups-of-5 and sorting each group add overhead — each level does ~n/5 sorts of 5 (constant work) plus recursion. The recursion depth is O(log n) but with larger constant work than randomized Quickselect.- Use randomized Quickselect when simplicity and average-case speed matter (lower constants, in-place, excellent average performance). Use median-of-medians when you need strict worst-case guarantees (e.g., real-time systems or adversarial inputs). Edge cases: duplicates handled, k bounds checked, empty array disallowed.

MediumTechnical

60 practiced

Implement an algorithm in Python to find the median of two sorted arrays (possibly of different lengths) in O(log(min(n, m))) time. Provide code, handle odd/even total length cases, and explain edge cases such as empty arrays and duplicates.

Sample Answer

To compute the median of two sorted arrays in O(log(min(n,m))) time, do a binary search on the smaller array to find a partition where left halves of both arrays contain exactly half of total elements and every element on the left ≤ every element on the right. Then median depends on total parity.

python

def find_median_sorted_arrays(a, b):
    # Ensure a is the smaller array
    if len(a) > len(b):
        return find_median_sorted_arrays(b, a)
    n, m = len(a), len(b)
    if n == 0:
        # Median of single sorted array b
        mid = m // 2
        return (b[mid] if m % 2 else (b[mid-1] + b[mid]) / 2.0)
    half = (n + m + 1) // 2  # left partition size

    lo, hi = 0, n
    while lo <= hi:
        i = (lo + hi) // 2      # elements taken from a
        j = half - i            # elements taken from b

        a_left = a[i-1] if i > 0 else float('-inf')
        a_right = a[i] if i < n else float('inf')
        b_left = b[j-1] if j > 0 else float('-inf')
        b_right = b[j] if j < m else float('inf')

        if a_left <= b_right and b_left <= a_right:
            # correct partition
            if (n + m) % 2:  # odd
                return max(a_left, b_left)
            else:
                return (max(a_left, b_left) + min(a_right, b_right)) / 2.0
        elif a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1

    raise ValueError("Input arrays not sorted or invalid")

Key points:- Binary search on smaller array yields O(log min(n,m)).- Handles odd/even totals using left/right max/min.- Edge cases: - Empty arrays: handled by early return when smaller is empty; if both empty, raise error. - Duplicates: comparisons (<=) allow duplicates and still produce correct partition. - Arrays of very different sizes: still fine because we search smaller one.Time complexity: O(log min(n,m)). Space: O(1).

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.