Advanced Data Structures and Implementation Questions

Deep and practical expertise in advanced data structures, their implementation details, performance characteristics, and selection for both algorithmic problems and production systems. Topics include arrays and dynamic arrays, strings, linked lists, stacks and queues, hash tables, heaps and priority queues, various tree forms including binary search trees and balanced trees, tries or prefix trees, segment trees and binary indexed trees or fenwick trees, union find or disjoint set union, suffix arrays, and advanced graph representations. Candidates should be able to implement core structures from first principles, demonstrate interfaces and invariants, reason about insertion deletion search traversal and iteration costs including worst case average case and amortized analysis, and discuss memory management and ownership in low level languages such as C and C plus plus as well as safe memory and reference use in managed languages. Evaluation also covers trade offs between contiguous and pointer based layouts, cache friendliness, concurrency considerations, selection of structures based on access patterns update frequency and memory constraints, handling of edge cases, testing and performance tuning for realistic inputs, and applying structures to problems such as top K queries prefix search connectivity range queries caches and union operations.

HardTechnical

81 practiced

Implement a suffix automaton (SAM) for a given string S (C++ or Java) that can be used to compute the number of distinct substrings and the longest common substring between two strings. Explain SAM states, transitions, suffix links, and why suffix automata can be more memory-efficient than suffix trees in many cases.

Sample Answer

**Approach (brief)** Build a suffix automaton (SAM) for S in O(|S|) time. Each SAM state represents an equivalence class of end positions; transitions are by characters; suffix links point to the longest proper suffix-state. Distinct substrings = sum over states (len[v] - len[link[v]]). Longest common substring (LCS) between S and T: run T through SAM, tracking matched length and best match.

cpp

// C++ SAM implementation with distinct substrings & LCS
#include <bits/stdc++.h>
using namespace std;
struct SAM {
    struct State { int len, link; array<int,26> next; State():len(0),link(-1){next.fill(-1);} };
    vector<State> st; int last=0;
    SAM(int n=1){ st.reserve(2*n); st.push_back(State()); last=0; }
    void extend(char cc){
        int c=cc-'a', cur=st.size(); st.push_back(State()); st[cur].len=st[last].len+1;
        int p=last;
        while(p!=-1 && st[p].next[c]==-1){ st[p].next[c]=cur; p=st[p].link; }
        if(p==-1) st[cur].link=0;
        else{
            int q=st[p].next[c];
            if(st[p].len+1==st[q].len) st[cur].link=q;
            else{
                int clone=st.size(); st.push_back(st[q]); st[clone].len=st[p].len+1;
                // adjust links
                while(p!=-1 && st[p].next[c]==q){ st[p].next[c]=clone; p=st[p].link; }
                st[q].link = st[cur].link = clone;
            }
        }
        last=cur;
    }
    long long countDistinct(){
        long long res=0;
        for(int v=1; v<st.size(); ++v) res += (st[v].len - st[st[v].link].len);
        return res;
    }
    int longestCommonSubstring(const string &t){
        int v=0,l=0,best=0;
        for(char ch: t){
            int c=ch-'a';
            if(st[v].next[c]!=-1){ v=st[v].next[c]; ++l; }
            else{
                while(v!=-1 && st[v].next[c]==-1) v=st[v].link;
                if(v==-1){ v=0; l=0; continue; }
                l = st[v].len + 1; v = st[v].next[c];
            }
            best = max(best,l);
        }
        return best;
    }
};
int main(){
    string s="ababa", t="baba";
    SAM sam(s.size());
    for(char c: s) sam.extend(c);
    cout << "Distinct: " << sam.countDistinct() << "\n";
    cout << "LCS: " << sam.longestCommonSubstring(t) << "\n";
}

**Key concepts** - State.len = max length of substrings in class; transitions follow characters; suffix link = largest proper suffix class. - Memory: SAM has at most 2|S|-1 states and only needed transitions for actual characters, often much smaller than suffix tree node+edge structures, leading to better constant memory for many alphabets.

**Why SAM vs suffix tree** - SAM stores end-position equivalence classes (compact states), simpler array maps for transitions; suffix trees keep edges with substrings and can be heavier in pointer/edge overhead. SAM is generally more memory-efficient and faster to implement for substring queries.

HardTechnical

86 practiced

Implement a lock-free stack in C++ using atomic compare-and-swap for push and pop. Explain the ABA problem and demonstrate one mitigation strategy such as tagged (versioned) pointers or hazard pointers for safe memory reclamation. Provide a code sketch for push/pop and discuss practical testing and performance considerations.

Sample Answer

**Approach (brief)** Use a singly-linked stack whose head is an atomic tagged pointer (pointer + 64-bit version tag) to avoid ABA. Push/pop use compare_exchange_strong on the combined atom. For safe reclamation in pop, show two mitigations: tagged pointers reduce ABA but don’t free safely — use hazard pointers for memory reclamation.

**Code sketch (C++17, simplified)**

cpp

#include <atomic>
#include <cstdint>

struct Node { int value; Node* next; };

struct TaggedPtr {
  Node* ptr;
  uint64_t tag;
};

std::atomic<uint128_t> head; // conceptual: pack ptr + tag into 128 bits

// helper to pack/unpack omitted for brevity

void push(Node* n){
  TaggedPtr old = unpack(head.load());
  for(;;){
    n->next = old.ptr;
    TaggedPtr desired{n, old.tag + 1};
    if(head.compare_exchange_strong(pack(old), pack(desired))) return;
    old = unpack(head.load());
  }
}

Node* pop(){
  TaggedPtr old = unpack(head.load());
  for(;;){
    if(old.ptr == nullptr) return nullptr;
    TaggedPtr desired{old.ptr->next, old.tag + 1};
    if(head.compare_exchange_strong(pack(old), pack(desired))){
      // safe reclamation: use hazard pointers to ensure no other thread holds old.ptr
      return old.ptr;
    }
    old = unpack(head.load());
  }
}

**ABA problem (concise)** ABA occurs when A -> B -> A happens between load and CAS; CAS succeeds though the state changed. Versioned (tagged) pointers add a tag increment so A with different tag is detected.

**Hazard pointers (summary)** Before accessing head->ptr, publish it in a per-thread hazard slot; only reclaim nodes not present in any hazard list. This prevents use-after-free.

**Testing & performance** - Test under high concurrency with thread sanitizer and stress tests (push/pop workloads, varying ratios). - Measure latency and throughput; compare with mutex-based stack. - Trade-offs: tagged pointers are cheap but need wide atomics (128-bit) on some platforms; hazard pointers add overhead but safe reclamation scales better than epoch GC in low-contention cases.

HardTechnical

92 practiced

Implement a Fenwick Tree variant that supports range-add(l, r, delta) and point-query(i), and explain how to convert that to support range-add and range-sum queries using two BITs. Provide code (Python or C++) and the mathematical reasoning behind using two BITs to reconstruct a prefix sum after range additions.

Sample Answer

**Approach (brief)** Use a single BIT that stores deltas to support range-add(l,r,delta) by doing point updates at l and r+1, then point-query(i) is prefix-sum(i) of that BIT. To support range-sum after range-adds, maintain two BITs (B1, B2). After applying range-add(l,r,delta) we update:- B1.add(l, delta), B1.add(r+1, -delta)- B2.add(l, delta*(l-1)), B2.add(r+1, -delta*r)

Prefix sum at x is:

text

sum(x) = x * query(B1, x) - query(B2, x)

This reconstructs the accumulated array prefix after many range adds.

**Why it works (math intuition)** We store piecewise linear contributions: B1 holds coefficient per index; multiplying by x accumulates total contribution. B2 corrects the offset introduced by starting index.

**Python implementation**

python

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    def add(self, i, v):
        while i<=self.n:
            self.bit[i]+=v
            i+=i&-i
    def sum(self, i):
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s

class RangeBIT:
    def __init__(self, n):
        self.n=n
        self.B1=BIT(n)
        self.B2=BIT(n)
    def range_add(self,l,r,delta):
        self.B1.add(l, delta); self.B1.add(r+1, -delta)
        self.B2.add(l, delta*(l-1)); self.B2.add(r+1, -delta*r)
    def prefix_sum(self,x):
        return x*self.B1.sum(x) - self.B2.sum(x)
    def range_sum(self,l,r):
        return self.prefix_sum(r) - self.prefix_sum(l-1)
    def point_query(self,i):
        return self.range_sum(i,i)

**Complexity & Notes**- All ops O(log n). - Edge cases: 1-based indices; watch overflow for large values (use 64-bit). This pattern is practical on backend services (e.g., analytics counters) and on frontend for offline range updates in client state.

EasyTechnical

97 practiced

In C++, implement a function that reverses a singly linked list in-place: Node* reverse(Node* head). The implementation must be iterative and use O(1) extra space. Explain pointer invariants, edge-case handling (empty list, single node), and list cycle considerations. Suggest unit tests to validate correctness.

Sample Answer

**Approach (brief)** Use three pointers iteratively: prev, curr, next. At each step reverse curr->next to point to prev, then advance pointers. This is O(n) time, O(1) space.

**Code**

cpp

// C++ iterative in-place reversal of singly linked list
struct Node {
    int val;
    Node* next;
    Node(int v): val(v), next(nullptr) {}
};

Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;
    while (curr) {
        Node* nxt = curr->next; // save next
        curr->next = prev;      // reverse link
        prev = curr;            // move prev forward
        curr = nxt;             // move curr forward
    }
    return prev; // new head
}

**Pointer invariants** - At loop start: prev points to the head of the already-reversed prefix (or nullptr), curr points to first node of unreversed suffix. - After body: curr advanced, and the prefix length increases by one; no node is lost because nxt saved curr->next first.

**Edge cases** - Empty list: head == nullptr → loop skipped, returns nullptr. - Single node: one iteration sets node->next = nullptr (was already), returns same node as new head.

**List cycles** This function assumes an acyclic list. If input has a cycle, loop becomes infinite. Detect cycles (Floyd's algorithm) before reversing if cycle is possible; break or reject cyclic inputs.

**Unit tests to validate** - Empty list -> nullptr. - Single-node -> same node, next == nullptr. - Two nodes -> order reversed. - Multiple nodes (odd/even length). - Preserve values and node counts. - (Optional) Feed cyclic list and assert function either detects cycle or test harness prevents calling reverse.

HardSystem Design

80 practiced

Design a concurrent hash map optimized for high read concurrency and occasional writes suitable for a web server cache. Discuss locking strategies (per-bucket locks, lock striping, read-copy-update, or lock-free), memory layout (contiguous bucket arrays vs node pointers), resizing approaches with minimal blocking, and memory reclamation considerations in C++ (hazard pointers, epoch-based GC).

Sample Answer

**Clarify goal & constraints**- Mostly reads (web‑cache), occasional writes; low latency reads under high concurrency; C++ implementation; safe memory reclamation; minimal blocking during resize.

**High‑level design**- Use a read‑optimized table where readers are lock‑free or use shared reads; writers do copy‑on‑write for buckets or small regions to avoid blocking readers.

**Locking strategies**- Preferred: lock‑striping with per‑stripe std::shared_mutex (or pthread rwlocks) so readers use shared_lock (concurrent) and writers take exclusive on that stripe. Stripe size = multiple buckets to reduce mutex count.- For even higher read scalability: hybrid RCU / epoch-based RCU: readers are almost entirely lock‑free (enter/exit epoch), writers do copy‑on‑write of affected buckets and publish with atomic pointer swap.

**Memory layout**- Contiguous bucket array (vector of buckets) for cache locality. Each bucket holds an atomic pointer to a node or an inline small-value slot (open addressing variant) for fastest reads.- Chaining with node pointers when values large; keep bucket array contiguous and nodes allocated from an arena to improve locality.

**Resizing with minimal blocking**- Use double‑table technique: allocate new larger table, publish it (atomic pointer), then perform incremental migration: lookups check new table first then old; writers help migrate buckets they touch. Finalize when migration complete. Readers never block; writers may briefly coordinate per‑stripe.- Alternatively, use epoch + swap: allocate new table, writers insert into new table while readers still read old; then switch root pointer once migrated.

**Memory reclamation**- Use epoch‑based reclamation (quiescent‑state batching) for simplicity and throughput in read‑heavy workloads: retired nodes are reclaimed only after all preexisting readers leave the epoch.- Hazard pointers are safer per‑pointer but have higher overhead and complexity; choose them if per‑pointer immediate safety required.- In C++: implement epochs with thread local counters, std::atomic for global epoch, and guard RAII for readers. Beware ABA; use tagged pointers or std::atomic<std::uintptr_t> with version bits.

**Trade‑offs**- Shared_mutex striping: simpler, slightly more reader overhead.- RCU/epoch + copy‑on‑write: best read latency, complex implementation and careful reclamation.- Open addressing vs chaining: open addressing gives best cache behavior but complicates incremental resizing; chaining simpler to migrate.

**Recommendation**- For a full‑stack developer building a web cache: start with stripe+shared_mutex + contiguous bucket array + chaining; implement incremental resize and epoch‑based reclamation. Later optimize hot paths with RCU-style reads if monitoring shows read latency needing improvement.

Unlock Full Question Bank

Get access to hundreds of Advanced Data Structures and Implementation interview questions and detailed answers.

Join thousands of developers preparing for their dream job.