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

52 practiced

Selecting the kth largest/smallest element is important for sampling and quantiles. Given an unsorted array and integer k, implement in Python an algorithm to return the kth largest element using a heap in O(n log k) time and O(k) space. Explain when a heap is preferable over sorting or selection algorithms in data pipelines.

Sample Answer

To find the kth largest element in O(n log k) time and O(k) space, maintain a min-heap of size k: iterate the array, push items into the heap; if heap size exceeds k, pop the smallest. After processing, the heap root is the kth largest.

python

import heapq
from typing import List

def kth_largest(nums: List[int], k: int) -> int:
    """
    Return the kth largest element using a min-heap of size k.
    Time: O(n log k), Space: O(k)
    """
    if not nums or k < 1 or k > len(nums):
        raise ValueError("k out of range")

    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        else:
            # If current element bigger than smallest in heap, replace it
            if x > heap[0]:
                heapq.heapreplace(heap, x)
    return heap[0]

Key points:- Use a min-heap (size k) to keep k largest seen so far; root is kth largest.- heapq.heapreplace does a push+pop in O(log k) more efficiently than separate ops.

Complexity:- Time: O(n log k) (n pushes/replacements, each O(log k))- Space: O(k)

Edge cases:- k <= 0 or k > n (raise error)- Duplicates handled naturally- Streaming input: works well since you only need O(k) memory

When to prefer a heap:- Data is large or streaming (can't sort whole dataset in memory)- k is small relative to n (heap cost small)- You need incremental/online updates (e.g., rolling top-k)Alternatives:- Sort: O(n log n) — simpler but expensive for large n- Quickselect: average O(n), worst-case O(n^2); better when in-memory and single-shot selection with no streaming or small constant factors desired.

MediumTechnical

56 practiced

Simple dynamic programming appears in data aggregations. Compute number of distinct ways to climb n stairs where you can climb 1 or 2 steps at a time. Implement a Python function climb_stairs(n) returning the count, show iterative and memoized recursive versions, and discuss time/space trade-offs and numeric growth for large n.

Sample Answer

This is the classic Fibonacci-like DP: ways(n) = ways(n-1) + ways(n-2) with base ways(0)=1, ways(1)=1. Below are an iterative (bottom-up) and a memoized recursive (top-down) Python implementation.

python

def climb_stairs_iterative(n):
    """
    Iterative DP (O(n) time, O(1) space).
    Returns number of distinct ways to climb n stairs with 1 or 2 steps.
    """
    if n < 0:
        return 0
    if n <= 1:
        return 1
    a, b = 1, 1  # ways(0), ways(1)
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_stairs_memo(n):
    """
    Memoized recursive DP (O(n) time, O(n) space for recursion + cache).
    """
    if n < 0:
        return 0
    if n <= 1:
        return 1
    return climb_stairs_memo(n-1) + climb_stairs_memo(n-2)

Key points:- Iterative uses constant extra space (O(1)) and is preferred in pipelines where memory and recursion depth matter.- Memoized recursion is clearer for reasoning and useful when you only need a few branches computed, but uses O(n) stack/cache.- Both run in O(n) time (each state computed once). naive recursion without memo is O(2^n) and not suitable.- Numeric growth: counts follow Fibonacci numbers ~ phi^n / sqrt(5) (phi≈1.618). Values grow exponentially; for large n use big integers (Python supports them) or consider using logarithms if only scale is needed.- Edge cases: negative n, n=0; very large n may require arbitrary-precision handling or matrix exponentiation / fast doubling to compute in O(log n) time if performance is critical.

MediumTechnical

55 practiced

Merging k sorted linked lists is a common aggregation step after partitioned reads. Given an array of k sorted linked lists, implement in Python a function merge_k_lists(lists) -> merged_list using a min-heap (priority queue). Explain time complexity O(N log k) where N is total nodes and memory usage.

Sample Answer

Approach:Use a min-heap to always extract the smallest current head among the k lists. Push the tuple (node.value, unique_id, node) for each non-empty list to avoid Python comparing ListNode. Repeatedly pop the smallest node, append it to the result list, and if that node has a next, push next into the heap. This yields O(N log k) time where N is the total number of nodes.

python

import heapq
import itertools

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge_k_lists(lists):
    """
    lists: list of ListNode (heads of k sorted linked lists)
    returns: head of merged sorted linked list
    """
    heap = []
    counter = itertools.count()  # unique sequence to avoid node comparison issues

    # Initialize heap with head nodes
    for node in lists:
        if node:
            heapq.heappush(heap, (node.val, next(counter), node))

    dummy = ListNode(0)
    tail = dummy

    while heap:
        val, _, node = heapq.heappop(heap)
        tail.next = node
        tail = tail.next
        # detach next pointer from previous heap elements is not required,
        # but ensure we push the next node if present
        if node.next:
            heapq.heappush(heap, (node.next.val, next(counter), node.next))

    # Ensure the final tail.next is None (safe guard)
    tail.next = None
    return dummy.next

Key concepts:- Heap holds at most k elements; each pop/push is O(log k).- Each of the N nodes is pushed and popped at most once => O(N log k) time.- Space: O(k) extra for the heap plus O(1) for pointers; output reuses existing nodes (no new nodes), so additional memory is O(k). If building new nodes instead, output would be O(N).

Edge cases:- lists empty or all None -> return None- Some lists much longer than others (handled naturally)- Duplicate values (heap handles them; unique counter avoids ties)

Alternatives:- Repeated two-way merge (O(Nk) worst-case)- Divide-and-conquer pairwise merges (O(N log k) time, O(1) extra space if in-place)

EasyTechnical

45 practiced

Implement a FIFO queue using two LIFO stacks in Python. Provide methods enqueue(x), dequeue(), peek(), and empty() with amortized O(1) time. Explain why operations are amortized O(1) and describe how this pattern could be useful in stream buffering within a data pipeline.

Sample Answer

Use two stacks: an input stack for enqueue and an output stack for dequeue/peek. Enqueue pushes to input. Dequeue/peek pop from output; if output is empty, pour all elements from input to output (reversing order). This gives amortized O(1) per operation because each element is moved at most once from input to output.

python

class QueueWithTwoStacks:
    def __init__(self):
        self._in = []   # LIFO stack for enqueues
        self._out = []  # LIFO stack for dequeues/peeks

    def enqueue(self, x):
        """Add element to the tail of the queue."""
        self._in.append(x)

    def _move_in_to_out(self):
        """Move all items from _in to _out when _out is empty."""
        while self._in:
            self._out.append(self._in.pop())

    def dequeue(self):
        """Remove and return head element. Raises IndexError if empty."""
        if not self._out:
            self._move_in_to_out()
        if not self._out:
            raise IndexError("dequeue from empty queue")
        return self._out.pop()

    def peek(self):
        """Return head element without removing it."""
        if not self._out:
            self._move_in_to_out()
        if not self._out:
            raise IndexError("peek from empty queue")
        return self._out[-1]

    def empty(self):
        """Return True if queue is empty."""
        return not self._in and not self._out

Why amortized O(1)- Each element is pushed once to _in, moved at most once to _out, and popped at most once from _out. Total work per element is O(1) across its lifetime; expensive transfers are infrequent relative to simple enqueues/dequeues, so amortized cost is O(1).

Usefulness in stream buffering for data pipelines- Maintains ordering (FIFO) while using simple LIFO primitives; useful when building lightweight in-memory buffers between pipeline stages.- Supports bursty input: fast enqueues into _in during ingestion; drains in batches when consumers read, reducing per-item synchronization and enabling efficient batch writes to downstream systems (e.g., bulk writes to Kafka, S3, or a DB).- Simple, lock-friendly pattern for implementing thread-safe variants (add locks around stacks) or for batching logic in backpressure handling and windowed processing.

MediumTechnical

55 practiced

Binary search invariants are vital for correctness in data retrieval. Implement in Python a function first_occurrence(nums: List[int], target: int) -> int that returns the index of the first occurrence of target in a sorted array (or -1 if not present). Explain the loop invariants and off-by-one pitfalls and show O(log n) time solution.

Sample Answer

To find the first occurrence of target in a sorted array, use a left-biased binary search that maintains the invariant: at start of each loop, search space is [lo, hi) (half-open). Invariant: any index < lo cannot contain target; any index >= hi may contain target. Loop until lo == hi; then lo is the smallest index that might equal target.

python

from typing import List

def first_occurrence(nums: List[int], target: int) -> int:
    # Maintain [lo, hi) invariant. Initially all indices in [0, len(nums)) are candidates.
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1        # mid cannot be answer
        else:
            hi = mid            # mid might be first occurrence, keep left half including mid
    # lo == hi is the smallest index >= original lo where nums[idx] >= target
    if lo < len(nums) and nums[lo] == target:
        return lo
    return -1

Key invariants:- [lo, hi) maintained each iteration.- After loop, lo is minimal index with nums[lo] >= target.

Off-by-one pitfalls:- Using closed interval [lo, hi] often requires careful mid calc and updating lo = mid + 1 or hi = mid - 1; it's easy to skip the first occurrence.- Using mid = (lo+hi)//2 without adjusting can cause infinite loop if updates don't shrink interval.

Time: O(log n). Space: O(1).

Edge cases: empty array, all elements < target, all elements > target, duplicates (handled). Alternative: use Python's bisect_left from stdlib for concise solution.

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.