Hard Difficulty Algorithmic Problems Questions

Advanced algorithmic problem solving topics commonly encountered in coding interviews, focusing on data structures (arrays, strings, linked lists, trees, graphs, heaps, hashes), algorithmic techniques (dynamic programming, greedy, backtracking, divide and conquer, graph algorithms), and time/space complexity optimization to produce efficient solutions.

HardTechnical

69 practiced

Route optimization in a microservice mapping requires solving small TSP instances. Given symmetric distance matrix for N <= 16 nodes, implement bitmask dynamic programming (Held-Karp) to compute minimal Hamiltonian cycle cost and return the route. Ensure your implementation uses O(N * 2^N) memory/time and discuss pruning or meet-in-the-middle optimizations for larger N.

Sample Answer

**Approach (brief)** Use Held–Karp: DP[mask][v] = min cost to reach node v visiting nodes in mask (mask includes v). Backpointers to reconstruct cycle. Complexity O(N * 2^N) time and memory for N ≤ 16.

**Code (Python)**

python

from math import inf

def held_karp(dist):
    # dist: NxN symmetric matrix, N<=16
    N = len(dist)
    if N == 0: return 0, []
    ALL = 1 << N
    dp = [[inf]*N for _ in range(ALL)]
    parent = [[-1]*N for _ in range(ALL)]
    # start from node 0 (arbitrary)
    dp[1<<0][0] = 0
    for mask in range(ALL):
        for u in range(N):
            if not (mask & (1<<u)): continue
            cur = dp[mask][u]
            if cur == inf: continue
            nxt_mask = mask
            for v in range(N):
                if mask & (1<<v): continue
                nm = mask | (1<<v)
                cost = cur + dist[u][v]
                if cost < dp[nm][v]:
                    dp[nm][v] = cost
                    parent[nm][v] = u
    # close cycle returning to 0
    full = ALL - 1
    best = inf; last = -1
    for u in range(N):
        if u==0: continue
        c = dp[full][u] + dist[u][0]
        if c < best:
            best = c; last = u
    if best == inf:
        return None, []
    # reconstruct path
    path = []
    mask = full; u = last
    while u != -1:
        path.append(u)
        prev = parent[mask][u]
        mask ^= (1<<u)
        u = prev
    path.append(0)
    path.reverse()
    return best, path

**Explanation & Complexity** DP iterates all masks and edges: O(N * 2^N) time and O(N * 2^N) memory. Backpointers reconstruct route.

**Optimizations for larger N** - Pruning: branch-and-bound with heuristic lower bounds (MST on remaining nodes) to cut branches. - Meet-in-the-middle: split nodes, compute partial tours and combine (reduces exponent constant; used in Held–Karp improvements). - Bit-parallel and memory compression: store dp only for masks of same popcount when appropriate, or use iterative deepening + memoization. - For practical backend use, consider heuristic solvers (2-opt, LK) or integer programming for near-optimal routes when N>16.

MediumTechnical

84 practiced

A backend analytics job needs the top-k most frequent events. Given an array of items, return the k most frequent elements. Implement two approaches: (1) use a min-heap of size k for O(n log k) time, and (2) bucket sort for O(n) time when frequencies are bounded by n. Discuss memory tradeoffs and behavior when k ~ n.

Sample Answer

**Approach (brief)**1. Count frequencies with a hashmap. 2. Approach A: maintain a min-heap of size k keyed by frequency -> O(n log k). 3. Approach B: bucket sort by frequency (array of lists indexed 0..n) -> O(n) when max frequency ≤ n.

**Implementation — Python (heap)**

python

import heapq
from collections import Counter

def top_k_heap(items, k):
    freq = Counter(items)  # O(n)
    heap = []  # min-heap of (frequency, item)
    for item, f in freq.items():
        if len(heap) < k:
            heapq.heappush(heap, (f, item))
        else:
            if f > heap[0][0]:
                heapq.heapreplace(heap, (f, item))
    return [item for (_, item) in heapq.nlargest(k, heap)]

**Implementation — Python (bucket)**

python

def top_k_bucket(items, k):
    freq = Counter(items)
    n = len(items)
    buckets = [[] for _ in range(n+1)]  # index = frequency
    for item, f in freq.items():
        buckets[f].append(item)
    res = []
    for f in range(n, 0, -1):
        for item in buckets[f]:
            res.append(item)
            if len(res) == k:
                return res
    return res

**Complexity**- Heap: Time O(n + m log k) ≈ O(n log k) (m = distinct items), Space O(m + k).- Bucket: Time O(n + m) ≈ O(n) when m ≤ n, Space O(n + m).

**Memory tradeoffs & k ~ n**- Heap keeps only k entries (good when k << m). Bucket allocates O(n) buckets — memory heavy if n large but fast. - When k ~ n (return most elements), heap degenerates: O(n log n) and needs storing nearly all items; bucket is preferable if you can afford O(n) memory since it runs in linear time. If distinct items m << n, both are fine; choose based on memory constraints and typical k.

**Edge cases**- k = 0, k > number of distinct items, ties in frequency (any order unless specified).

EasyTechnical

86 practiced

In many backend linked structures (e.g., middleware chains or singly-linked log entries) you may need to reverse the order. Given the head of a singly linked list, implement an in-place algorithm to reverse it and return the new head. Provide both iterative and recursive implementations in your language of choice, and discuss stack depth implications for recursion in production systems with long lists.

Sample Answer

**Approach (brief)** Reverse pointers in-place by walking the list and flipping next pointers. Iterative is O(n) time, O(1) space. Recursive also O(n) time but O(n) call-stack.

**Iterative implementation (Python)**

python

# Definition for singly-linked list node
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_iterative(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        nxt = curr.next        # save next
        curr.next = prev       # reverse pointer
        prev = curr            # advance prev
        curr = nxt             # advance curr
    return prev               # new head

**Recursive implementation (Python)**

python

def reverse_recursive(head: ListNode) -> ListNode:
    # base: empty or single node
    if not head or not head.next:
        return head
    new_head = reverse_recursive(head.next)  # reverse rest
    head.next.next = head    # make next node point to current
    head.next = None         # sever old link
    return new_head

**Key concepts & complexity**- Time: O(n) both- Space: iterative O(1) extra; recursive O(n) stack frames- In-place: no new nodes allocated

**Stack-depth implications (production)**- Recursion depth equals list length. For long lists (e.g., millions of log entries) recursion risks stack overflow and high memory usage. Prefer iterative in backend services. If recursion is desired, convert to tail-recursive form only if the runtime optimizes it (Python/Java do not). For very large lists consider iterative or chunked processing (reverse blocks, process, then stitch) to limit memory.

HardTechnical

144 practiced

Dynamic connectivity under edge deletions is a challenging backend for collaborative applications. Design and implement a data structure that supports operations addEdge(u,v), removeEdge(u,v), and connected(u,v) queries on an undirected graph with up to 1e5 operations. Discuss trade-offs and implement either an offline divide-and-conquer with DSU rollback approach or describe use of link-cut trees for an online solution. Explain complexities and when each approach is appropriate.

Sample Answer

**Approach (brief)**

Use an offline divide-and-conquer over time + DSU with rollback. Map each add/remove to time intervals where the edge is active, build a segment tree over time; add edges to segment nodes covering their active interval. DFS the tree, joining edges at a node, answering connected(u,v) at leaves, and rollback DSU when returning.

**C++ implementation (core parts)**

cpp

// DSU with rollback
struct DSU {
  vector<int> p, sz; vector<pair<int,int>> st;
  DSU(int n):p(n+1),sz(n+1,1){iota(p.begin(),p.end(),0);}
  int find(int x){ while(x!=p[x]) x=p[x]; return x; }
  void unite(int a,int b){
    a=find(a); b=find(b); if(a==b){ st.emplace_back(-1,-1); return; }
    if(sz[a]<sz[b]) swap(a,b);
    st.emplace_back(b,sz[a]);
    p[b]=a; sz[a]+=sz[b];
  }
  void rollback(){ auto [b,sa]=st.back(); st.pop_back(); if(b==-1) return; int a=p[b]; sz[a]=sa; p[b]=b; }
};

// segment tree of edges (1..Q)
vector<vector<pair<int,int>>> seg;
void addSeg(int idx,int l,int r,int ql,int qr,pair<int,int> e){
  if(ql>r||qr<l) return;
  if(ql<=l&&r<=qr){ seg[idx].push_back(e); return; }
  int m=(l+r)>>1; addSeg(idx<<1,l,m,ql,qr,e); addSeg(idx<<1|1,m+1,r,ql,qr,e);
}
void dfs(int idx,int l,int r, DSU &d, vector<pair<int,int>>& queries, vector<bool>& ans){
  for(auto &e: seg[idx]) d.unite(e.first,e.second);
  if(l==r){
    if(queries[l].first!=-1) ans[l] = d.find(queries[l].first)==d.find(queries[l].second);
  } else {
    int m=(l+r)>>1; dfs(idx<<1,l,m,d,queries,ans); dfs(idx<<1|1,m+1,r,d,queries,ans);
  }
  for(size_t i=0;i<seg[idx].size();++i) d.rollback();
}

**Key concepts & reasoning**- Offline: convert deletions into intervals so each edge is added only O(log Q) places.- DSU rollback lets us undo unions in LIFO order while traversing tree.

**Complexity**- Time: O((Q + E) log Q * α(N)) ≈ O(Q log Q) for Q ops up to 1e5.- Space: O((Q + E) log Q).

**Edge cases**- Multiple identical add/remove pairs — track multiset counts or stack per edge.- Queries at times with no prior add — return false.

**Alternatives / Trade-offs**- Link-Cut Trees (LCT): provide fully online dynamic connectivity for forests (link, cut, connected) in O(log N) per op; good when operations must be online and edges form a forest. LCT is more complex and slower in practice; doesn't handle general graphs with cycles without extra structure (e.g., maintain spanning forest + replacement edges).- Use offline when you can buffer events (collaborative backends often can batch or tolerate small delays). Use LCT when strict online responses needed and graph is forest-like.

When to use which:- Offline DSU rollback: simpler, faster for 1e5 ops, supports general graphs for connectivity queries offline.- LCT: choose if you need true online with frequent immediate queries and edges are mostly tree-structured.

HardTechnical

70 practiced

File differencing for backup systems requires an efficient diff algorithm. Implement a memory-optimized longest common subsequence based diff for two sequences (e.g., file lines) and explain Hirschberg's algorithm to reduce space to O(min(n,m)). Provide approach to reconstruct an edit script (add/delete) while keeping memory small and discuss practical alternatives like Myers' diff.

Sample Answer

**Approach (brief)** Use Hirschberg's algorithm: compute LCS lengths with a space-optimized DP (only two rows) to find a mid-point split, recurse on halves to reconstruct the LCS, then derive edit script (add/delete) from LCS—all while keeping extra memory O(min(n,m)).

**Code (Python)**

python

# Hirschberg LCS + edit script (add/delete) — memory optimized
def lcs_score(a, b):
    # return last-row LCS lengths for a vs b using O(min(len(a),len(b))) space
    n, m = len(a), len(b)
    if m < n:
        # ensure b is the shorter for O(min(n,m)) space
        a, b, n, m = b, a, m, n
    prev = [0] * (m + 1)
    for i in range(1, n + 1):
        cur = [0] * (m + 1)
        ai = a[i-1]
        for j in range(1, m + 1):
            if ai == b[j-1]:
                cur[j] = prev[j-1] + 1
            else:
                cur[j] = cur[j-1] if cur[j-1] >= prev[j] else prev[j]
        prev = cur
    return prev

def hirschberg(a, b):
    # returns LCS sequence
    n, m = len(a), len(b)
    if n == 0: return []
    if n == 1:
        return [a[0]] if a[0] in b else []
    i = n // 2
    left_score = lcs_score(a[:i], b)
    right_score = lcs_score(a[i:][::-1], b[::-1])
    # find split k maximizing left_score[k] + right_score[m-k]
    k = max(range(len(b)+1), key=lambda j: left_score[j] + right_score[len(b)-j])
    return hirschberg(a[:i], b[:k]) + hirschberg(a[i:], b[k:])

def diff_script(a, b):
    lcs = hirschberg(a, b)
    script = []
    i = j = 0
    for x in lcs:
        while i < len(a) and a[i] != x:
            script.append(('delete', i, a[i])); i += 1
        while j < len(b) and b[j] != x:
            script.append(('add', i, b[j])); j += 1
        # match
        i += 1; j += 1
    # tail
    while i < len(a):
        script.append(('delete', i, a[i])); i += 1
    while j < len(b):
        script.append(('add', i, b[j])); j += 1
    return script

**Key concepts & reasoning**- lcs_score uses classic DP but stores only one row (O(m) space).- Hirschberg splits A in half, finds split k in B by combining forward/backward scores; recursion builds LCS using O(min(n,m)) auxiliary memory plus call stack O(min(n,m)) depth.- After LCS, build edit script by walking both sequences; operations are only add/delete (no replace—can be represented as delete+add).

**Complexity**- Time: O(n*m) worst-case (same as standard LCS).- Space: O(min(n,m)) extra for scores + recursion stack O(min(n,m)).

**Edge cases**- Very large files: recursion depth could be high—convert recursion to iterative divide-and-conquer or increase stack.- Lines with large content: compare hashes first to speed equality checks.

**Practical alternatives**- Myers' O((N+M)D) diff is preferred in practice: typically faster, outputs shortest edit script, and has efficient linear-space implementations used in git. For backup systems where performance matters, use Myers for speed and Hirschberg only when you specifically need classic LCS semantics with strict memory bounds.

Unlock Full Question Bank

Get access to hundreds of Hard Difficulty Algorithmic Problems interview questions and detailed answers.

Join thousands of developers preparing for their dream job.