Fundamental Algorithms and Techniques Questions

Covers core algorithmic concepts and problem solving patterns commonly assessed in technical interviews. Topics include searching algorithms such as binary search; sorting algorithms such as merge sort and quick sort; graph traversal methods such as breadth first search and depth first search; recursion and divide and conquer techniques; greedy heuristics; and dynamic programming including memoization and tabulation. Also includes implementation patterns such as two pointers, sliding window, prefix sums, and divide and conquer composition, as well as practical considerations like in place versus out of place implementations, stability for sorting, recursion stack and memory usage, and amortized analysis. Candidates should be able to implement these algorithms correctly, explain correctness and trade offs, analyze time and space complexity using Big O notation for best case average case and worst case, select appropriate approaches given input constraints, combine patterns to solve composite problems, and optimize or refactor solutions while handling edge cases.

MediumTechnical

90 practiced

As an AI Engineer working on tokenization, implement the 'word break' problem in Python: given a string s and a set of dictionary words, return True if s can be segmented into a sequence of dictionary words. Provide a dynamic programming solution with O(n * L) time where L is the max dictionary word length, describe Trie-based optimizations, and discuss applicability to languages without explicit word boundaries.

Sample Answer

Approach: use dynamic programming where dp[i] = True if s[:i] can be segmented. For each position i, try dictionary words of length up to L (max word length) ending at i; this bounds checks to O(n * L). This is practical for tokenization and can be extended with a Trie to avoid checking all lengths.

python

def word_break(s: str, word_dict: set) -> bool:
    """
    DP solution: O(n * L) time where n = len(s), L = max len(word) in dict.
    Returns True if s can be segmented into words from word_dict.
    """
    if not s:
        return True
    n = len(s)
    max_l = max((len(w) for w in word_dict), default=0)
    dp = [False] * (n + 1)
    dp[0] = True  # empty prefix

    for i in range(1, n + 1):
        # only check substrings of allowed lengths
        start = max(0, i - max_l)
        for j in range(start, i):
            if dp[j] and s[j:i] in word_dict:
                dp[i] = True
                break
    return dp[n]

Key points:- Time: O(n * L) because each i checks up to L substring checks; substring hashing/lookup in a hash set is average O(1).- Space: O(n) for dp plus O(sum lengths) for dict storage.

Trie-based optimization:- Build a Trie of dictionary words and, for each start index j where dp[j] is True, walk the Trie forward from s[j:] character by character. This lets you stop early when no prefix matches and avoids forming substrings or checking many lengths; complexity becomes O(n * average_branching_depth) and is usually faster when many small/overlapping words exist.

Applicability to languages without explicit word boundaries (e.g., Chinese, Japanese):- Same algorithm applies if you have a lexicon, but segmentation is harder: ambiguities are frequent and language models (e.g., statistical CRF, HMM, or neural tokenizers like BERT's WordPiece/Unigram) are commonly used. Combine dictionary-based DP with heuristic scoring (maximize probability) or use a Trie + Viterbi to find the most likely segmentation rather than just existence. Edge cases: overlapping words, very large dictionaries, and OOV (out-of-vocab) tokens—handle with fallbacks (character-level tokens or subword models).

MediumTechnical

71 practiced

Write an efficient Python function to count the number of set bits in a 64-bit integer. Compare naive bit-by-bit scans, Kernighan's algorithm (x &= x-1), and precomputed lookup-table approaches. Analyze time complexity and discuss vectorization or SIMD/GPU techniques for bulk population counts used in Bloom filters or feature hashing.

Sample Answer

A good approach is to present three methods (naive, Kernighan, and lookup table), show working Python code, then compare complexities and discuss vectorized/SIMD/GPU techniques for bulk popcounts.

Approach: use bit ops; for bulk data prefer numpy vectorization or CPU intrinsics (popcnt) / GPU kernels.

python

def popcount_naive(x: int) -> int:
    # works for 64-bit non-negative ints
    cnt = 0
    for i in range(64):
        cnt += (x >> i) & 1
    return cnt

def popcount_kernighan(x: int) -> int:
    cnt = 0
    while x:
        x &= x - 1
        cnt += 1
    return cnt

# 8-bit lookup table -> process 8 bytes
LOOKUP8 = [bin(i).count("1") for i in range(256)]
def popcount_table(x: int) -> int:
    cnt = 0
    for shift in range(0, 64, 8):
        cnt += LOOKUP8[(x >> shift) & 0xFF]
    return cnt

Key points and complexity:- Naive: O(64)=O(1) per integer but does 64 shifts; worst practical cost high constant.- Kernighan: O(k) where k = number of set bits — best when sparse.- Lookup-table: O(8)=O(1) with small constant (8 table lookups); usually fastest in Python due to fewer loops and byte-level work.

Edge cases:- Negative ints: mask to 64-bit: x &= (1<<64)-1.- x larger than 64 bits: adapt loop ranges.

Bulk/vectorization:- For large arrays, use numpy with dtype=uint64 and vectorized tricks (split to bytes + lookup via np.take) or use Python bindings to hardware popcnt (via C extension) — GCC/clang provide __builtin_popcountll or x86 POPCNT instruction (through intrinsics). For GPUs, implement a parallel popcount kernel using bitwise ops per thread and reduction — excellent throughput for Bloom filters/feature hashing. Use existing libraries (Intel SVML, AVX2/AVX-512 popcount, CUDA __popcll) for best performance; Python-level loops will be much slower. Trade-offs: table method uses memory, Kernighan is branchy, hardware popcnt gives best throughput when available.

MediumTechnical

72 practiced

Implement in Python the 'minimum window substring' function: given strings s and t, find the minimum window in s that contains all characters of t (including duplicates) and return that substring or an empty string. Use sliding window with counters, analyze time/space complexity, and discuss optimizations for large alphabets or Unicode.

Sample Answer

To solve this, use a sliding window with two pointers and counters: expand right to include chars until window covers t, then shrink left to find the smallest covering window. Use collections.Counter to track required counts and a running count for the current window.

python

from collections import Counter, defaultdict

def min_window(s: str, t: str) -> str:
    if not t or not s:
        return ""
    need = Counter(t)               # required counts
    have = defaultdict(int)         # current window counts
    required = len(need)            # number of distinct chars we must satisfy
    formed = 0                      # how many distinct chars currently satisfy required count
    l = 0
    best = (float('inf'), None, None)  # length, left, right

    for r, ch in enumerate(s):
        have[ch] += 1
        if ch in need and have[ch] == need[ch]:
            formed += 1

        # try to contract while window still valid
        while l <= r and formed == required:
            if (r - l + 1) < best[0]:
                best = (r - l + 1, l, r)

            # remove leftmost and move left pointer
            left_char = s[l]
            have[left_char] -= 1
            if left_char in need and have[left_char] < need[left_char]:
                formed -= 1
            l += 1

    return "" if best[0] == float('inf') else s[best[1]:best[2]+1]

Key points:- We track distinct characters that meet their required counts (formed vs required) so we don't check whole Counter each time.- Time complexity: O(n + m) where n = len(s), m = len(t) — each char is visited at most twice (right and left moves). Hash ops are average O(1).- Space complexity: O(k) for maps where k is number of distinct characters in s or t.

Edge cases:- t longer than s -> return ""- duplicates in t handled by counts- empty strings

Optimizations for large alphabets / Unicode:- Use dictionary-based counters (as above) rather than fixed-size arrays to avoid huge memory for sparse Unicode.- Pre-filter s to only characters present in t (store their indices) to shrink traversal when t is small relative to possible alphabet — iterate over filtered indices instead of all characters.- If characters map to small range (ASCII), using list/array for counts can be faster and more memory-efficient.

MediumTechnical

82 practiced

Implement a solver for the N-Queens problem in Python that returns one valid arrangement or the count of all solutions for N. Use backtracking and demonstrate bitmask optimizations (columns, diagonals, anti-diagonals) to achieve high performance. Explain why bitmasks are faster and discuss time complexity and how to scale up to N=15 efficiently.

Sample Answer

To solve N-Queens efficiently we use backtracking with bitmasking to represent columns, diagonals and anti-diagonals as integers. Bitmasks allow O(1) checks and fast generation of available positions via bit operations instead of scanning arrays — fewer branches and lower constant factors.

python

def solve_nqueens(n, return_count=False):
    """
    If return_count=False -> returns one solution as list of column indices per row (0..n-1) or []
    If return_count=True  -> returns number of solutions
    """
    if n <= 0: return [] if not return_count else 0
    solutions = 0
    one_solution = []

    def backtrack(row, cols, diags, anti, state):
        nonlocal solutions, one_solution
        if row == n:
            solutions += 1
            if not return_count and not one_solution:
                one_solution = state.copy()
            return
        # bits with 1 = free positions
        free = (~(cols | diags | anti)) & ((1 << n) - 1)
        while free:
            # pick lowest set bit
            bit = free & -free
            free -= bit
            col = (bit.bit_length() - 1)
            state.append(col)
            backtrack(row + 1,
                      cols | bit,
                      (diags | bit) << 1,
                      (anti | bit) >> 1,
                      state)
            state.pop()
            if not return_count and one_solution:
                return  # early exit when one solution found

    backtrack(0, 0, 0, 0, [])
    return solutions if return_count else one_solution

# Example:
# print(solve_nqueens(8, return_count=True))
# print(solve_nqueens(8))

Why bitmasks are faster:- Constant-time occupancy checks and updates with bit ops.- Compact representation reduces memory/cache misses.- Using lowest-bit extraction (bit & -bit) avoids loops.

Time complexity:- Worst-case exponential ~O(k^n) but effective pruning reduces search; number of valid boards grows much slower than n!.- For counting all solutions it's roughly O(N!) in worst view but practical runtimes for N≤15 are feasible with bitmasking and symmetry.

Scaling to N=15 efficiently:- Use symmetry: only explore half columns in first row and mirror results (double except middle when n odd).- Use iterative optimizations (bit operations only), avoid recursion overhead if necessary.- For counts, use 64-bit integers; Python ints are arbitrary precision but keep performance in mind.

Edge cases:- n=1 returns [0]; n<1 handle gracefully; ensure shifts don't overflow by masking with ((1<<n)-1).

HardTechnical

72 practiced

Explain Bellman-Ford algorithm for single-source shortest paths, implement it in Python to compute distances and detect negative cycles reachable from the source, analyze its time complexity, and discuss practical uses and limitations. Explain why Dijkstra is not appropriate for graphs with negative edge weights and relate negative cycles to reward loops in reinforcement learning.

Sample Answer

To compute single-source shortest paths on graphs that may have negative edge weights, Bellman–Ford repeatedly relaxes all edges up to |V|-1 times; if any edge can still be relaxed on the |V|th pass, a negative cycle is reachable from the source.

Approach:- Initialize dist[source]=0, all others = +inf.- Repeat relaxing every edge (u,v,w): if dist[u]+w < dist[v] then update.- After |V|-1 iterations, run one more pass: any vertex updated is part of or reachable from a negative cycle; propagate that information.

python

from math import inf
from collections import defaultdict, deque

def bellman_ford(edges, n, src):
    """
    edges: list of tuples (u, v, w)
    n: number of vertices (0..n-1)
    src: source vertex
    Returns: (distances list, neg_cycle_reachable set)
    distances: list with shortest distances or -inf for nodes reachable from negative cycles
    neg_cycle_reachable: set of vertices reachable from a negative cycle
    """
    dist = [inf]*n
    dist[src] = 0

    # Relax edges |V|-1 times
    for _ in range(n-1):
        updated = False
        for u, v, w in edges:
            if dist[u] != inf and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break

    # Detect nodes affected by negative cycles
    neg = [False]*n
    for u, v, w in edges:
        if dist[u] != inf and dist[u] + w < dist[v]:
            neg[v] = True

    # Propagate negativity through reachable nodes (BFS on adjacency)
    adj = defaultdict(list)
    for u, v, w in edges:
        adj[u].append(v)
    q = deque([i for i, x in enumerate(neg) if x])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not neg[v]:
                neg[v] = True
                q.append(v)

    # Mark distances impacted by negative cycles as -inf
    for i in range(n):
        if neg[i]:
            dist[i] = -inf

    neg_set = {i for i, x in enumerate(neg) if x}
    return dist, neg_set

Key concepts:- Correct even with negative weights; detects negative cycles reachable from source.- Dijkstra relies on nonnegative edge weights because it greedily finalizes the closest node; a later negative edge could invalidate that choice, breaking correctness.

Complexity:- Time: O(V * E) worst-case (|V|-1 relaxation rounds).- Space: O(V + E) for distances and edge list.

Practical uses and limitations:- Use when negative weights exist (e.g., currency exchange graphs, some economic models).- Limitation: slower than Dijkstra for nonnegative graphs; cannot handle graphs with negative cycles for "shortest path" (paths undefined/unbounded below).- In large-scale systems prefer Johnson’s algorithm (reweight with Bellman–Ford once) or specialized linear programming approaches.

Relation to reinforcement learning:- A negative cycle in shortest-paths corresponds to a reward loop in RL where cumulative reward can be made arbitrarily large (positive or negative depending on sign)—this creates unbounded value estimates and makes optimal policy undefined unless cycles are penalized or discounted. Detecting such cycles helps identify pathological MDPs (e.g., positive reward loops under maximization).

Unlock Full Question Bank

Get access to hundreds of Fundamental Algorithms and Techniques interview questions and detailed answers.

Join thousands of developers preparing for their dream job.