Coding Fundamentals and Problem Solving Questions

Focuses on algorithmic thinking, data structures, and the process of solving coding problems under time constraints. Topics include core data structures such as arrays, linked lists, hash tables, trees, and graphs, common algorithms for searching and sorting, basics of dynamic programming and graph traversal, complexity analysis for time and space, and standard coding patterns. Emphasis on a disciplined problem solving approach: understanding the problem, identifying edge cases, proposing solutions with trade offs, implementing clean and readable code, and testing or reasoning about correctness and performance. Includes debugging strategies, writing maintainable code, and practicing medium difficulty interview style problems.

EasyTechnical

65 practiced

You have a list of floating-point batch losses observed during training. Implement a Python function max_average_window(arr, k) that returns the maximum average of any contiguous subarray of length k. Assume k > 0 and k <= len(arr). Aim for O(n) time and O(1) extra space. Example: arr=[0.4,0.5,0.1,0.2,0.9], k=3 -> 0.4.

Sample Answer

To solve this, use a sliding-window of fixed length k: compute the sum of the first k elements, then slide the window across the array updating the sum by subtracting the element leaving and adding the entering element. Track the maximum average = max_sum / k. This is O(n) time and O(1) extra space.

python

def max_average_window(arr, k):
    """
    Returns the maximum average of any contiguous subarray of length k.
    Assumes 0 < k <= len(arr).
    """
    n = len(arr)
    if n == 0 or k <= 0 or k > n:
        raise ValueError("Invalid array length or k")

    # initial window sum
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # slide the window
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum

    return max_sum / k

# Example:
# arr = [0.4, 0.5, 0.1, 0.2, 0.9], k = 3 -> windows sums: [1.0,0.8,1.2] => max avg = 1.2/3 = 0.4

Key points:- Time complexity: O(n) — one pass after initial sum.- Space complexity: O(1) extra — only a few scalar variables.Edge cases:- k == len(arr): returns average of whole array.- Floating-point precision: sums may accumulate small rounding errors; use double precision (Python floats) which is usually sufficient. Alternative: keep averages in numerator form if comparing fractions without division.

HardTechnical

35 practiced

Implement Dijkstra's shortest paths in Python using an adjacency list and heapq to compute distances from a source to all nodes for non-negative weights. Discuss how to handle outdated entries in the heap, parent pointers for path reconstruction, and how to scale to very large sparse graphs.

Sample Answer

Approach- Use a min-heap (heapq) storing (distance, node). Maintain a distances dict/array and parents dict/array. When popping, ignore outdated entries by comparing the popped distance with the current recorded distance. This keeps heap operations lazy and correct without decrease-key.

Code implementation (Python)

python

import heapq
from typing import Dict, List, Tuple, Optional

def dijkstra(adj: Dict[int, List[Tuple[int, float]]], source: int
            ) -> Tuple[Dict[int, float], Dict[int, Optional[int]]]:
    """
    adj: adjacency list {u: [(v, weight), ...], ...}
    source: start node
    Returns: distances and parent pointers for path reconstruction
    """
    INF = float("inf")
    dist: Dict[int, float] = {u: INF for u in adj}
    parent: Dict[int, Optional[int]] = {u: None for u in adj}

    dist[source] = 0.0
    heap: List[Tuple[float, int]] = [(0.0, source)]

    while heap:
        d_u, u = heapq.heappop(heap)
        # Skip outdated heap entries
        if d_u != dist[u]:
            continue

        for v, w in adj[u]:
            nd = d_u + w
            if nd < dist.get(v, INF):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))

    return dist, parent

def reconstruct_path(parent: Dict[int, Optional[int]], target: int) -> List[int]:
    path = []
    cur = target
    while cur is not None:
        path.append(cur)
        cur = parent.get(cur)
    return path[::-1]

Key concepts and why they matter- Outdated heap entries: heapq has no decrease-key; pushing updated distances and ignoring stale pops (check dist equality) yields correctness and simpler code. This keeps amortized push/pop complexity bounded.- Parent pointers: store parent when a shorter distance is found. Reconstruct path by following parents from target to source.

Complexity- Time: O((V + E) log V) using binary heap.- Space: O(V + E) for adjacency; O(V) for dist/parent/heap entries (heap may contain multiple entries per node).

Edge cases- Disconnected nodes: distances remain INF, parents None.- Zero-weight edges: algorithm handles them fine.- Non-negative weights precondition must hold; negative edges break correctness.- Source not in adj: handle explicitly (add node or raise).

Scaling to very large sparse graphs- Use integer node IDs and dense arrays (list/np.array) instead of dicts for memory/speed when nodes are 0..n-1.- Store adjacency in compressed sparse row (CSR) format (scipy.sparse) for memory efficiency; combine with a custom efficient visitor loop.- Reduce heap pressure: if memory/time critical, consider pairing heap / Fibonacci heap (theoretical), but in practice binary heap with lazy updates is fast.- Algorithmic improvements: use A* with admissible heuristic for single-source-to-target; bidirectional Dijkstra for point-to-point; contraction hierarchies or ALT for repeated queries on road networks.- Implementation choices: write hot loops in C/Cython, use PyPy, or call a C++ implementation via pybind11 for production-scale graphs.- Parallelism: multi-source multi-threaded relaxations are tricky; prefer graph partitioning or specialized libraries (e.g., GraphChi, SNAP) for massive graphs.

This implementation is production-ready for many ML pipelines (feature graph distances, KNN graph traversal) and can be optimized to scale further by switching data structures or leveraging native libraries.

EasyTechnical

34 practiced

In Python implement merge_sorted_inplace(A, m, B, n) that merges sorted list B into sorted list A which has length m + n with the first m elements valid and the remaining n positions reserved (e.g., zeros). This mirrors merging timestamped feature arrays. Do it in O(m + n) time and O(1) extra space. Example: A=[1,2,3,0,0,0], m=3; B=[2,5,6], n=3 -> A becomes [1,2,2,3,5,6].

Sample Answer

Approach: Use three pointers from the end so we place the largest elements into A's reserved tail in-place. This avoids extra space and runs in O(m + n).

python

def merge_sorted_inplace(A, m, B, n):
    """
    Merge sorted list B into sorted list A in-place.
    A has length m + n, with first m valid elements and last n reserved.
    Modifies A to contain the merged sorted array.
    """
    i = m - 1         # last valid element in A
    j = n - 1         # last element in B
    k = m + n - 1     # write position in A

    while j >= 0:
        if i >= 0 and A[i] > B[j]:
            A[k] = A[i]
            i -= 1
        else:
            A[k] = B[j]
            j -= 1
        k -= 1

Key points:- We iterate at most m + n steps, copying the larger of A[i] and B[j] to A[k].- O(m + n) time, O(1) extra space.- Handles duplicates correctly and works when A's valid part is empty (m=0) or B is empty (n=0).

Edge cases to consider:- m or n equals 0- Negative or non-integer values (comparison still valid)- A already contains elements equal to placeholders (ensure placeholders are outside first m)

In ML pipelines this pattern is useful when merging time-ordered feature arrays or streaming batches into preallocated buffers without reallocating memory.

MediumTechnical

62 practiced

Implement Rabin-Karp substring search in Python: find all start indices where pattern occurs in text using a rolling hash. Discuss choice of base and modulus, collision handling, and average/worst-case complexity. Provide code-level details for the rolling computation.

Sample Answer

To solve this, use Rabin–Karp: compute an integer rolling hash for the pattern and for every length-m window of text; compare hashes and on match verify the substring to avoid false positives from collisions.

python

def rabin_karp_all(text: str, pattern: str):
    if not pattern:
        return list(range(len(text)+1))
    n, m = len(text), len(pattern)
    if m > n:
        return []

    # Choose base and modulus: base ~ alphabet size, modulus large prime to reduce collisions
    base = 256
    mod = 2**61 - 1  # large Mersenne-like prime; faster with overflow tricks; safe choice here

    # precompute base^(m-1) % mod
    high = pow(base, m-1, mod)

    # initial hashes
    def hash_of(s):
        h = 0
        for ch in s:
            h = (h * base + ord(ch)) % mod
        return h

    pat_hash = hash_of(pattern)
    win_hash = hash_of(text[:m])

    results = []
    for i in range(n - m + 1):
        if win_hash == pat_hash:
            # verify to avoid collision false positive
            if text[i:i+m] == pattern:
                results.append(i)
        if i < n - m:
            left = ord(text[i])
            right = ord(text[i+m])
            # remove left, multiply, add right, keep modulo
            win_hash = (win_hash - left * high) % mod
            win_hash = (win_hash * base + right) % mod

    return results

Key points:- Base = 256 handles byte/char alphabets; smaller bases (e.g., 31) often used for letters.- Modulus: a large prime (like 2**61-1) reduces collisions; using Python's big ints is safe.- Collision handling: always verify substring when hashes match.- Rolling computation: subtract left_char * base^(m-1), multiply by base, add new char, all modulo mod.Complexity:- Average time O(n + k*m) where k is number of hash matches (usually O(n)); average O(n). Worst-case O(n*m) if many collisions or adversarial input. Space O(1) besides output. Edge cases: empty pattern, pattern longer than text.

EasyTechnical

42 practiced

Describe how you'd write unit tests for a data preprocessing function normalize_and_fill(dataframe) that normalizes numerical columns and fills missing values. List edge cases and provide 3 pytest-style test examples (constant column, all-NaN column, extremely large values).

Sample Answer

Approach: Test normalize_and_fill by creating small controlled DataFrames, calling the function, and asserting properties: mean/std (or min/max) for normalization, missing values filled appropriately, dtype preserved, and no infinities/NaNs remain. Use pytest and pandas; prefer deterministic numeric tolerances (np.isclose) and parametrize where useful.

Edge cases to cover:- Constant column (std=0) — normalization should avoid divide-by-zero (e.g., return zeros or original).- All-NaN column — filled with strategy (mean/global, median, zero); ensure consistent behavior and dtype.- Extremely large values — avoid overflow; check numerical stability.- Mixed dtypes, categorical columns untouched.- Single-row DataFrame.- Columns with infinities.- Empty DataFrame.

Pytest examples:

python

import pandas as pd
import numpy as np
from your_module import normalize_and_fill

def test_constant_column():
    df = pd.DataFrame({"a": [5,5,5,5], "b":[1,2,3,4]})
    out = normalize_and_fill(df.copy())
    # constant column should become zeros (or unchanged but finite); choose expected behavior
    assert np.allclose(out["a"].values, 0)
    assert out["b"].mean() == pytest.approx(0, rel=1e-6) or True  # depends on normalization convention

python

def test_all_nan_column():
    df = pd.DataFrame({"a":[np.nan,np.nan,np.nan], "b":[1,2,np.nan]})
    out = normalize_and_fill(df.copy())
    assert not out["a"].isna().any()  # filled
    assert not out["b"].isna().any()
    # check dtype preserved
    assert out["a"].dtype == df["a"].dtype or np.issubdtype(out["a"].dtype, np.floating)

python

def test_extremely_large_values():
    big = 1e308
    df = pd.DataFrame({"a":[big, big/2, np.nan], "b":[-big, 0, big]})
    out = normalize_and_fill(df.copy())
    assert np.isfinite(out.values).all()
    # normalized columns roughly centered/scaled
    assert abs(out["a"].mean()) < 1e3 or True  # check no overflow; adjust per implementation

Notes: Make expected assertions match the implementation contract (e.g., z-score vs min-max, fill strategy). Use fixtures/parametrize to reduce repetition. Mock random seeds if imputation uses randomness.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.