Algorithmic Problem Solving Fundamentals Questions

Core foundation for solving entry level algorithmic problems. Focuses on arrays, strings, basic mathematics and number theory problems, simple bit manipulation, basic linked list and tree operations, stacks and queues, basic sorting and searching algorithms, simple recursion, and use of hash based data structures for counting and lookup. Emphasizes understanding asymptotic time and space complexity, selecting appropriate data structures for a task, and clear step by step problem solving including writing a brute force solution and analyzing correctness.

MediumTechnical

43 practiced

Implement quickselect in Python to find the k-th largest element in an unsorted array in average O(n) time. Provide code for randomized pivot selection, explain expected vs worst-case complexity, and show how to modify to find k-th smallest. Include considerations for duplicate elements.

Sample Answer

To solve this, use Quickselect: partition like Quicksort but recurse only into the side containing the k-th element. Use a randomized pivot to ensure expected O(n) time.

python

import random

def quickselect(nums, k):
    """
    Return the k-th largest element (1-based k).
    """
    if not 1 <= k <= len(nums):
        raise ValueError("k out of range")
    target = len(nums) - k  # convert to k-th smallest index (0-based)

    def partition(l, r):
        # randomized pivot
        pivot_idx = random.randint(l, r)
        nums[pivot_idx], nums[r] = nums[r], nums[pivot_idx]
        pivot = nums[r]
        i = l
        for j in range(l, r):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[r] = nums[r], nums[i]
        return i

    def select(l, r):
        if l == r:
            return nums[l]
        p = partition(l, r)
        if p == target:
            return nums[p]
        elif p < target:
            return select(p + 1, r)
        else:
            return select(l, p - 1)

    return select(0, len(nums) - 1)

Key points:- Expected time: O(n) due to random pivots giving good partitioning on average.- Worst-case: O(n^2) if partitions are highly unbalanced (rare with random pivot).- Space: O(1) extra (in-place) plus O(recursion depth) expected O(log n), worst O(n).- To get k-th smallest: remove the conversion (use target = k-1) or call quickselect(nums, len(nums)-k+1).- Duplicates: Partition uses "< pivot" which groups equals to the right; duplicates are handled naturally — for arrays with many duplicates, using 3-way partition (Dutch National Flag) can improve performance and avoid degenerate partitions.

HardTechnical

41 practiced

Given an array of integers, implement min_window_substring_like(nums, target_counts) in Python that finds the minimum-length contiguous subarray whose element counts cover target_counts (a dict of required counts for some integers). This is the numeric analog to "minimum window substring". Provide O(n) sliding-window solution and discuss correctness proof.

Sample Answer

We can solve this with a standard sliding-window + hash counts approach: expand right until the window covers all required counts, then contract left to minimize. Maintain a satisfied counter for how many distinct keys currently meet required counts to achieve O(n) time.

python

def min_window_substring_like(nums, target_counts):
    """
    nums: list[int]
    target_counts: dict[int, int] required counts per value
    Returns tuple (start, end) inclusive indices of min window, or (-1, -1) if none.
    """
    if not target_counts:
        return (0, -1)  # empty requirement -> empty window

    need = dict(target_counts)  # required counts
    have = {}
    required_keys = len(need)
    satisfied = 0

    left = 0
    best = (0, float('inf'))  # (start, length)
    for right, val in enumerate(nums):
        have[val] = have.get(val, 0) + 1
        # increment satisfied when a key reaches its required count exactly
        if val in need and have[val] == need[val]:
            satisfied += 1

        # when all required keys satisfied, try to shrink from left
        while satisfied == required_keys and left <= right:
            window_len = right - left + 1
            if window_len < best[1]:
                best = (left, window_len)

            # remove leftmost
            left_val = nums[left]
            have[left_val] -= 1
            if left_val in need and have[left_val] < need[left_val]:
                satisfied -= 1
            left += 1

    if best[1] == float('inf'):
        return (-1, -1)
    return (best[0], best[0] + best[1] - 1)

Why this is O(n): Each index is visited at most twice — once by right and once by left — so linear time. Space is O(k) where k is distinct values in nums (or in need).

Correctness sketch: The loop invariant is that before contracting, the window [left, right] either does not satisfy requirements or does; when it satisfies, we exhaustively shrink left while it remains satisfied, so we examine every minimal satisfying window ending at that right. Since we check all right positions and always tighten left to the smallest satisfying left for that right, we will find the globally minimum satisfying window. Edge cases: target_counts includes values not in nums (returns (-1,-1)), empty target_counts handled. Duplicate keys and zeros handled by counts.

HardTechnical

45 practiced

Given a large unsorted dataset of integers stored on disk, describe an algorithm to find the k-th smallest element using external memory (limited RAM). Discuss how to use selection by sampling, partitioning with disk-based scans, and multi-pass external quickselect or using external sorts. Explain I/O cost trade-offs.

Sample Answer

Situation: You have N integers on disk, RAM limited to M items (or M/B blocks), and need the k-th smallest.

Approach (high level)1. Use selection-by-sampling to choose good pivots.2. Partition the disk file(s) with sequential scans into < pivot, = pivot, > pivot files.3. Recurse on the partition containing k. Repeat until partition fits in RAM and finish in-memory, or fallback to external sort if needed.You can also use multiway partitioning (multiple pivots) to reduce passes, or just run an external sort (external merge-sort) and read the k-th element.

Algorithm (practical steps)- Sample: Read the file once using reservoir sampling or by uniformly reading every N/s-th record to collect s samples that fit in RAM (s ≪ M). Sort the sample in memory and pick pivot(s): e.g., median-of-sample or several quantiles for multiway partition.- Partition pass: Stream the full file once. For each block, write records to temporary files: L (< pivot), E (=), G (>). Writes are sequential; use buffered I/O to amortize block cost.- Size check: After the pass, determine sizes |L|,|E|. If k ≤ |L| recurse on L; if k ≤ |L|+|E| return pivot; else set k ← k−|L|−|E| and recurse on G.- Repeat until the target partition fits in RAM, then load and select in-memory.- Multi-pivot variant: choose t−1 pivots to partition into t buckets in one pass, reducing expected number of passes ≈ log_t(N/M). Choose t so metadata fits in RAM.

I/O cost and parameters- One full scan = reading N items and writing them once spread across buckets ≈ O(N/B) I/Os (B = block size). Each pass costs ≈ 2N/B (read + write) if you materialize partitions; if you overwrite or stream to new file then you still pay similar cost.- If pivots partition well (balanced), expected number of passes ≈ O(log_t(N/M)). With single-pivot quickselect-style expected passes ≈ O(log(N/M)) but can be high if pivots are poor.- Sampling size s trades sample quality vs extra I/O: collecting s samples costs one pass; picking s = Θ(M) (use all RAM for sample) gives high-quality pivots, reducing expected passes. For robust guarantees choose s = c·M or s = Θ(log N) for probabilistic bounds.- External sort cost: O((N/B) log_{M/B}(N/B)) I/Os (optimal external mergesort). If you only need one order statistic, selection-by-sampling + partitioning typically beats full sort when k far from extremes and sampling yields good pivots.

Trade-offs and practical considerations- Worst-case vs expected: External quickselect has good expected I/O but worst-case many passes; use randomization and multi-pivots to mitigate.- Disk locality: Partitioning creates many temporary files—use large buffered writes and merge small files to avoid many small I/Os.- Parallelism: Partition scans are embarrassingly parallel across disks or shards.- Stability and duplicates: Handle equals bucket to avoid infinite loops when many duplicates equal pivot.- When to sort: If you must repeatedly query different order statistics or need sorted output, pay the upfront sort cost.

When to choose which- Single selection (one k): sampling + partitioning (multi-pass external quickselect) with good sample size.- Many queries or full sorted output: external sort once.- Very tight RAM or adversarial data: increase sample size or use multiway pivots; if guarantees matter, use external selection algorithms with provable I/O bounds (median-of-medians over blocks), though they are more complex.

Example parameters (rule of thumb)- Use sample s = 0.1·M to get good pivots without starving RAM.- Aim to keep number of passes ≤ 3–5; adjust s or t (multi-pivot count) if too many passes occur.

This approach minimizes sequential I/O, controls number of passes via sampling/multiway partitioning, and provides a practical balance between expected I/O and implementation complexity for ML pipelines that need scalable single-order-statistic extraction.

EasyTechnical

73 practiced

Write a Python function gcd(a, b) that computes the greatest common divisor using the Euclidean algorithm. Provide both iterative and recursive versions, explain time complexity (in terms of number of digits), and describe behavior for negative inputs and zero. Also explain how to compute lcm(a, b) using gcd.

Sample Answer

Approach: use the Euclidean algorithm (repeated remainder) — both iterative and recursive. For lcm use lcm(a,b)=|a*b|/gcd(a,b). Handle negatives by taking absolute values; gcd(0,0) is typically defined as 0.

python

def gcd_iterative(a, b):
    """Iterative Euclidean algorithm. Returns non-negative gcd."""
    a, b = abs(a), abs(b)
    if a == 0 and b == 0:
        return 0
    while b:
        a, b = b, a % b
    return a

def gcd_recursive(a, b):
    """Recursive Euclidean algorithm. Returns non-negative gcd."""
    a, b = abs(a), abs(b)
    if a == 0 and b == 0:
        return 0
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

def lcm(a, b):
    """Least common multiple using gcd. lcm(0, x) == 0."""
    if a == 0 or b == 0:
        return 0
    return abs(a // gcd_iterative(a, b) * b)

Key points:- Both implementations use abs() so negatives are handled; gcd returns non-negative.- gcd(0, x) = |x|, gcd(0,0) we return 0 by convention.- lcm uses integer division to avoid intermediate float; compute a//g * b to reduce overflow.

Time complexity (digits):- Let N be the number of bits (or d decimal digits ~ N/log2(10)). The Euclidean algorithm takes O(N) iterations in the worst case, and each division/remainder by schoolbook arithmetic is O(N^2) bit-operations; overall bit-complexity is O(N^2) (classical analysis). In terms of decimal digits d, that's roughly O(d^2).- Practical note: for typical ML pipelines with 64-bit integers this is effectively O(1) and extremely fast.

Edge cases:- Negative inputs: abs handles them.- Zero: handled explicitly; lcm with zero returns 0.- Large big integers: Python handles big ints; if extreme performance needed, use optimized big-int algorithms or math.gcd from stdlib (which is highly optimized).

EasyTechnical

50 practiced

Write a Python function reverse_inplace(chars: List[str]) that reverses a list of characters in place (O(1) extra space). Example: input ['h','e','l','l','o'] -> ['o','l','l','e','h']. Provide working code, explain time and space complexity, and discuss edge cases (empty list, single character). Do not allocate another list or use built-in reverse().

Sample Answer

A simple two-pointer in-place swap reverses the list with O(1) extra space.

python

from typing import List

def reverse_inplace(chars: List[str]) -> None:
    """
    Reverse the list of characters in place.
    Modifies the input list and returns None.
    """
    left, right = 0, len(chars) - 1
    while left < right:
        # swap chars at left and right
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1

Key points:- Approach: Use two pointers (left starts at 0, right at n-1), swap and move inward until they meet.- Time Complexity: O(n) — each element swapped at most once; loop runs ~n/2 iterations.- Space Complexity: O(1) extra space — swaps done in-place using a constant number of variables.- Edge cases: - Empty list ([]) -> loop doesn't run; remains []. - Single character (['a']) -> left == right so no swaps; remains ['a']. - Even/odd lengths handled naturally.- Notes for ML engineering context: This pattern is efficient for in-place preprocessing of character arrays (e.g., token transformations) where allocating extra memory is costly.

Unlock Full Question Bank

Get access to hundreds of Algorithmic Problem Solving Fundamentals interview questions and detailed answers.

Join thousands of developers preparing for their dream job.