Articles 🧠 Quiz ↗

Qualcomm Practice — Part 1 Solutions — Recursion/DP/Graphs, C++ & OOP, Concurrency, Design

Clean, compilable, scannable solutions for Part 1 categories L, M, N, O of the practice_questions.md drill list — recursion/DP/graphs, C++ & OOP, concurrency, and code-heavy system design. Each entry: the idea, a commented solution, complexity, and the gotcha/variant interviewers tack on. C is used for pointer/memory/embedded items; C++ for OOP/STL/templates/concurrency. Solutions stand alone — no need to open the concept files.

Table of Contents

L. Recursion, DP & graphs - L1. Recursion + the call stack (factorial / fib) - L2. Maximise toys with amount K (coin-change DP) - L3. Generate valid sentences from words (word break) - L4. BFS vs DFS — graph traversal - L5. Number of Islands - L6. Topological sort - L7. Propagate failures through a dependency graph

M. C++ & OOP (write the code) - M1. Function overloading vs overriding - M2. Polymorphism — virtual functions & types - M3. Types of inheritance + diamond ambiguity - M4. Operator overloading (+ and <<) - M5. new/delete vs malloc/free; smart pointers - M6. Thread-safe Singleton - M7. Immutable class

N. Concurrency / multithreading (write the code) - N1. Print odd & even with two threads - N2. pthreads — create/join, pass args - N3. Two threads sharing a map — protect it - N4. Implement a binary semaphore - N5. Create a deadlock, then fix it - N6. Identify the race condition

O. Design / implement-a-system - O1. LRU cache (+ twisted LRU) - O2. LFU cache - O3. Timer module (min-heap / timer wheel) - O4. Lottery machine - O5. Screen-tearing fix (producer/consumer) - O6. Text editor with undo/redo - O7. Lift / elevator management system - O8. Camera-driver architecture (HAL + ops tables)

L. Recursion, DP & graphs

L1. Recursion + the call stack — factorial / fib, and the memory it uses (lead-in to DP) [E]

  • Idea: Each recursive call pushes a stack frame (return address, params, locals). Naive fib recomputes the same subproblems → exponential. Memoization caches results → linear. This is the classic recursion → DP bridge.
  • Code: 
    #include <stdio.h>

// Factorial: depth n -> O(n) call frames on the stack.
long fact(int n) {
    if (n <= 1) return 1;        // base case stops the recursion
    return n * fact(n - 1);      // each call adds a frame
}

// Naive Fibonacci: O(2^n) calls, O(n) stack depth -> recomputes subproblems.
long fib_naive(int n) {
    if (n < 2) return n;
    return fib_naive(n - 1) + fib_naive(n - 2);
}

// Memoized: each fib(k) computed once -> O(n) time. This is "top-down DP".
long fib_memo(int n, long *memo) {   // memo[] pre-filled with -1, size n+1
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];          // reuse cached result
    return memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
}

// Iterative: O(n) time, O(1) space -- no recursion, no stack growth at all.
long fib_iter(int n) {
    long a = 0, b = 1;
    for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
    return a;
}
  • Complexity: factorial O(n) time / O(n) stack. fib: naive O(2^n) / O(n) stack; memo O(n)/O(n); iterative O(n)/O(1).
  • Gotcha / variants: Deep recursion → stack overflow (no tail-call elimination guaranteed in C/C++). Factorial is naturally tail-recursive (fact_tail(n, acc)); fib is not. The point interviewers want: overlapping subproblems + optimal substructure ⇒ DP; memoization turns the recursion tree into a DAG.

L2. Maximise the number of toys purchasable with amount K (coin-change-style DP) [M]

  • Idea: Two readings: (a) max count of items within budget → if a toy can be bought once, sort prices and greedily buy cheapest first; (b) unbounded coin-change "fewest coins to make K" → DP. The interview "maximise toys" is usually the greedy one; I show both.
  • Code: 
    #include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// (a) Max DISTINCT toys you can buy with budget K (each toy bought at most once).
// Greedy: cheapest first is optimal when maximizing COUNT.
int maxToys(vector<int> price, int K) {
    sort(price.begin(), price.end());
    int count = 0;
    for (int p : price) {
        if (p > K) break;          // can't afford the next cheapest -> stop
        K -= p; count++;
    }
    return count;
}

// (b) Coin-change variant: FEWEST coins to make exactly K (unlimited supply).
// DP: dp[a] = min coins to make amount a. Classic when "maximise/optimise" needs DP.
int minCoins(vector<int>& coins, int K) {
    vector<int> dp(K + 1, INT_MAX);
    dp[0] = 0;
    for (int a = 1; a <= K; a++)
        for (int c : coins)
            if (c <= a && dp[a - c] != INT_MAX)
                dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[K] == INT_MAX ? -1 : dp[K];   // -1 if K is unreachable
}
  • Complexity: greedy O(n log n); DP O(K · #coins) time, O(K) space.
  • Gotcha / variants: Greedy is correct for maximising count with distinct items, but wrong for "fewest coins to make a value" with arbitrary denominations (e.g. coins {1,3,4}, target 6 → greedy 4+1+1=3, DP 3+3=2). If toys can be bought repeatedly and you cap total value, it becomes a 0/1 or unbounded knapsack — say which framing you're solving.

L3. Generate valid sentences from words — word break / segmentation [H]

  • Idea: Word Break II. Backtrack over prefixes that are in the dictionary; recurse on the suffix. Memoize suffix → list of sentences to avoid re-exploring. (Word Break I = just feasibility, a 1-D DP bool.)
  • Code: 
    #include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_set<string> dict;
    unordered_map<string, vector<string>> memo;   // suffix -> all sentences

    vector<string> solve(const string& s) {
        if (memo.count(s)) return memo[s];
        vector<string> res;
        if (s.empty()) { res.push_back(""); return res; }   // one empty completion
        for (int i = 1; i <= (int)s.size(); i++) {
            string word = s.substr(0, i);
            if (!dict.count(word)) continue;
            for (string& tail : solve(s.substr(i))) {        // recurse on suffix
                res.push_back(word + (tail.empty() ? "" : " " + tail));
            }
        }
        return memo[s] = res;
    }
public:
    vector<string> wordBreak(string s, vector<string>& words) {
        dict = {words.begin(), words.end()};
        return solve(s);
    }
};
// Feasibility-only (Word Break I): O(n^2) DP, no sentence reconstruction.
// dp[i] = true if s[0..i) is segmentable; dp[0]=true; check every cut j<i.
  • Complexity: worst case exponential in the number of segmentations (output-bound); memoized work per distinct suffix. Word Break I is O(n²·L).
  • Gotcha / variants: Pathological input like "aaaa...a" with dict {a, aa, aaa} explodes the number of sentences — guard with the feasibility DP first (if not segmentable, return empty fast). Don't forget the trailing-space handling when joining words.

L4. BFS vs DFS — implement graph traversal [M]

  • Idea: BFS = queue, explores level by level (shortest path in unweighted graphs). DFS = stack/recursion, goes deep first. Both need a visited set to avoid cycles.
  • Code: 
    #include <vector>
#include <queue>
using namespace std;

// adj = adjacency list. Both start from node `s`.
void bfs(int s, vector<vector<int>>& adj, vector<int>& visited) {
    queue<int> q;
    visited[s] = 1; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        // process(u);
        for (int v : adj[u])
            if (!visited[v]) { visited[v] = 1; q.push(v); }   // mark on enqueue
    }
}

void dfs(int u, vector<vector<int>>& adj, vector<int>& visited) {
    visited[u] = 1;
    // process(u);
    for (int v : adj[u])
        if (!visited[v]) dfs(v, adj, visited);                // recurse deeper
}

// Iterative DFS (avoids stack overflow on deep graphs):
void dfs_iter(int s, vector<vector<int>>& adj, vector<int>& visited) {
    vector<int> st = {s};
    while (!st.empty()) {
        int u = st.back(); st.pop_back();
        if (visited[u]) continue;
        visited[u] = 1;                                       // mark on pop
        for (int v : adj[u]) if (!visited[v]) st.push_back(v);
    }
}
  • Complexity: both O(V + E) time, O(V) space (visited + frontier/recursion).
  • Gotcha / variants: Mark visited on enqueue in BFS (not on dequeue) or nodes get queued multiple times. Use BFS for shortest path in unweighted graphs / minimum hops; DFS for cycle detection, topological sort, connected components. Recursive DFS risks stack overflow on long chains — prefer the iterative version for huge graphs.

L5. Number of Islands [M]

  • Idea: Scan the grid; each unvisited '1' starts a new island. Flood-fill (DFS/BFS) all connected land, sinking it to '0' so it isn't recounted.
  • Code: 
    #include <vector>
using namespace std;

class Solution {
    int rows, cols;
    void sink(vector<vector<char>>& g, int r, int c) {
        if (r < 0 || r >= rows || c < 0 || c >= cols || g[r][c] != '1') return;
        g[r][c] = '0';                       // mark visited in-place
        sink(g, r+1, c); sink(g, r-1, c);    // 4-directional flood fill
        sink(g, r, c+1); sink(g, r, c-1);
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        rows = grid.size(); cols = grid[0].size();
        int count = 0;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == '1') { count++; sink(grid, r, c); }
        return count;
    }
};
  • Complexity: O(R·C) time, O(R·C) worst-case recursion stack (all land).
  • Gotcha / variants: Mutating the grid avoids a separate visited array but destroys input — use a visited matrix if the grid must survive. Recursion can overflow on a giant all-land grid → switch to BFS with a queue. Follow-ups: 8-directional connectivity, max island area, count distinct island shapes.

L6. Topological sort [M]

  • Idea: Linear ordering of a DAG so every edge u→v has u before v. Kahn's algorithm: repeatedly emit nodes with in-degree 0. If you emit fewer than V nodes, there's a cycle (no valid order).
  • Code: 
    #include <vector>
#include <queue>
using namespace std;

// n nodes 0..n-1, edges as prerequisite pairs {a,b} meaning b -> a (b before a).
vector<int> topoSort(int n, vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    vector<int> indeg(n, 0);
    for (auto& e : edges) { adj[e[1]].push_back(e[0]); indeg[e[0]]++; }

    queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);   // sources first

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);   // edge "removed" -> maybe new source
    }
    if ((int)order.size() != n) return {};    // cycle => no topological order
    return order;
}
  • Complexity: O(V + E) time, O(V) space.
  • Gotcha / variants: Only DAGs have a topo order — the size check is the cycle test (this is exactly LC207/210 Course Schedule). DFS variant: post-order push onto a stack, then reverse. A min-priority-queue instead of a plain queue gives the lexicographically smallest order.

L7. Propagate failures through a dependency graph [H]

  • Idea: If a node fails, every node that depends on it (transitively) also fails. Build the dependency edge so it points from dependency → dependent, then BFS/DFS from each failed node, marking everything reachable as failed.
  • Code: 
    #include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

// deps[x] = list of nodes that x depends on.
// We invert to "dependents", then flood from each initially-failed node.
vector<bool> propagateFailures(int n,
                               vector<vector<int>>& deps,
                               vector<int>& initiallyFailed) {
    vector<vector<int>> dependents(n);            // edge: dep -> node that needs it
    for (int x = 0; x < n; x++)
        for (int d : deps[x]) dependents[d].push_back(x);

    vector<bool> failed(n, false);
    queue<int> q;
    for (int f : initiallyFailed)
        if (!failed[f]) { failed[f] = true; q.push(f); }

    while (!q.empty()) {                          // BFS the failure wavefront
        int u = q.front(); q.pop();
        for (int v : dependents[u])               // everyone who depended on u...
            if (!failed[v]) { failed[v] = true; q.push(v); }  // ...also fails
    }
    return failed;
}
  • Complexity: O(V + E) time and space.
  • Gotcha / variants: Get the edge direction right — failures flow toward dependents, not dependencies. failed[] doubles as the visited set, so cycles are handled safely. Variants: weighted/partial failure (a node fails only if all its deps fail → that's an in-degree-counting / AND-gate propagation, not simple reachability), or "which single node's failure breaks the most others" (run the flood from each node).

M. C++ & OOP (write the code)

M1. Function overloading vs overriding — show both [E]

  • Idea: Overloading = same name, different parameter lists, resolved at compile time (static), same scope. Overriding = derived class redefines a virtual base method with the same signature, resolved at runtime via the vtable.
  • Code: 
    #include <iostream>
using namespace std;

struct Calc {
    int add(int a, int b) { return a + b; }              // overload 1
    double add(double a, double b) { return a + b; }     // overload 2 (compile-time pick)
};

struct Base {
    virtual void speak() { cout << "Base\n"; }            // virtual => overridable
    virtual ~Base() = default;                            // virtual dtor (needed!)
};
struct Derived : Base {
    void speak() override { cout << "Derived\n"; }        // override: same signature
};

void demo() {
    Calc c;
    c.add(1, 2);        // calls int version    (overloading: by arg types)
    c.add(1.5, 2.5);    // calls double version

    Base* p = new Derived();
    p->speak();         // prints "Derived"     (overriding: dynamic dispatch)
    delete p;           // virtual dtor => Derived's dtor runs too
}
  • Complexity: N/A (language mechanics). Overload pick is free at compile time; override costs one vtable indirection at runtime.
  • Gotcha / variants: Overloads cannot differ by return type alone. Without virtual, p->speak() would call Base (static binding) — that's the classic trap. override is a compiler-checked safety net (catches signature typos). Hiding (a non-virtual same-name method in derived) is neither — it shadows the base name.

M2. Polymorphism — virtual function example & types [M]

  • Idea: Compile-time polymorphism = overloading + templates (resolved statically). Runtime polymorphism = virtual functions + base pointers/refs, dispatched through the vptr→vtable. A pure virtual makes the class abstract.
  • Code: 
    #include <iostream>
#include <vector>
#include <memory>
using namespace std;

struct Shape {
    virtual double area() const = 0;     // pure virtual => Shape is abstract
    virtual ~Shape() = default;          // virtual dtor for safe polymorphic delete
};
struct Circle : Shape {
    double r;
    Circle(double r) : r(r) {}
    double area() const override { return 3.14159 * r * r; }
};
struct Square : Shape {
    double s;
    Square(double s) : s(s) {}
    double area() const override { return s * s; }
};

void totalArea() {
    vector<unique_ptr<Shape>> shapes;
    shapes.push_back(make_unique<Circle>(2.0));
    shapes.push_back(make_unique<Square>(3.0));
    double sum = 0;
    for (auto& sh : shapes) sum += sh->area();   // runtime dispatch per object
    cout << sum << "\n";                          // 12.566 + 9 = 21.566
}

// Compile-time polymorphism via template (resolved at compile time, no vtable):
template <typename T> T maxOf(T a, T b) { return a > b ? a : b; }
  • Complexity: virtual call = one extra pointer indirection; templates have zero runtime cost (code generated per type).
  • Gotcha / variants: You cannot instantiate an abstract class. Always give a polymorphic base a virtual destructor or delete base_ptr leaks/UB the derived part. Mention the vtable/vptr: each polymorphic object carries a hidden pointer to its class's table of function addresses.

M3. Types of inheritance + resolving multiple-inheritance ambiguity (diamond) [M]

  • Idea: Single, multiple, multilevel, hierarchical, hybrid. The diamond problem (D inherits B and C, both from A) gives D two copies of A → ambiguity. Fix with virtual inheritance so there's one shared A.
  • Code: 
    #include <iostream>
using namespace std;

struct Animal {
    int legs = 4;
    void describe() { cout << "legs=" << legs << "\n"; }
};

// WITHOUT virtual: Mammal and Bird each carry their own Animal -> Bat has TWO.
// WITH "virtual" inheritance: one shared Animal base -> no ambiguity.
struct Mammal : virtual Animal {};
struct WingedThing : virtual Animal {};
struct Bat : Mammal, WingedThing {};   // diamond: A <- Mammal, A <- WingedThing <- Bat

void demo() {
    Bat b;
    b.legs = 2;        // unambiguous: exactly ONE Animal subobject (virtual base)
    b.describe();      // prints legs=2

    // Multiple inheritance with a real name clash is resolved by qualification:
    // struct X { void f(); };  struct Y { void f(); };  struct Z : X, Y {};
    // Z z; z.X::f();  // disambiguate explicitly
}
  • Complexity: N/A. Virtual bases add a small indirection to reach the shared subobject.
  • Gotcha / variants: Without virtual, b.legs is ambiguous and won't compile (need b.Mammal::legs). Virtual inheritance must be declared on the intermediate classes, not on Bat. Many style guides ban multiple implementation inheritance — prefer composition or interface (pure-virtual) inheritance.

M4. Operator overloading — + and << for a small class [M]

  • Idea: Overload operator+ as a member (returns a new object, doesn't mutate). Overload operator<< as a non-member friend because the left operand is std::ostream, not your class.
  • Code: 
    #include <iostream>
using namespace std;

class Complex {
    double re, im;
public:
    Complex(double r = 0, double i = 0) : re(r), im(i) {}

    // Member operator+: a + b. const because it doesn't modify *this.
    Complex operator+(const Complex& o) const {
        return Complex(re + o.re, im + o.im);
    }

    // Non-member (friend) so the ostream is the left operand: cout << c.
    friend ostream& operator<<(ostream& os, const Complex& c) {
        os << c.re << (c.im >= 0 ? "+" : "") << c.im << "i";
        return os;                      // return os to allow chaining: cout << a << b
    }
};

void demo() {
    Complex a(1, 2), b(3, -4);
    cout << (a + b) << "\n";            // 4-2i
}
  • Complexity: O(1) for these.
  • Gotcha / variants: operator<< must be non-member (you can't add methods to ostream) and return os& for chaining. Return Complex by value from operator+ (don't return a reference to a local — dangling). For symmetric mixed-type ops (2.0 + c), prefer a non-member operator+. Pair += (mutating member) with + (returns new) for consistency.

M5. new/delete vs malloc/free; smart-pointer basics [M]

  • Idea: new allocates + calls the constructor and is type-safe; malloc just returns raw bytes. delete calls the destructor; free doesn't. Smart pointers (unique_ptr/shared_ptr) own the resource and free it automatically (RAII) — no manual delete.
  • Code: 
    #include <memory>
#include <cstdlib>
using namespace std;

struct Widget { Widget(); ~Widget(); };

void rawVsNew() {
    // C style: no ctor/dtor, returns void*, size in bytes, returns NULL on failure.
    Widget* a = (Widget*)malloc(sizeof(Widget));   // ctor NOT called -- danger
    free(a);                                        // dtor NOT called

    // C++: ctor runs, type-safe, throws std::bad_alloc on failure.
    Widget* b = new Widget();
    delete b;                                       // dtor runs

    int* arr = new int[10];
    delete[] arr;                                   // MUST match new[] with delete[]
}

void smartPointers() {
    // unique_ptr: sole owner, freed when it goes out of scope. Move-only.
    auto u = make_unique<Widget>();
    auto u2 = std::move(u);            // ownership transferred; u is now null

    // shared_ptr: reference-counted; freed when the last owner dies.
    auto s = make_shared<Widget>();
    auto s2 = s;                       // use_count == 2
}                                     // everything auto-destroyed here, no leaks
  • Complexity: allocation is roughly O(1) amortized; shared_ptr adds an atomic refcount (control block).
  • Gotcha / variants: Never mix (free a new, or delete a malloc) — UB. Match new[]↔delete[]. Prefer make_unique/make_shared (exception-safe, one allocation for shared). shared_ptr cycles leak → break with weak_ptr. new throws bad_alloc; malloc returns NULL.

M6. Thread-safe Singleton [H]

  • Idea: Lead with the Meyers Singleton: a function-local static, which since C++11 is initialized exactly once, thread-safely ("magic statics") — lazy, leak-free, no locking. Show double-checked locking only as the pre-C++11 / heap variant.
  • Code: 
    #include <mutex>
#include <atomic>

// --- Preferred: Meyers Singleton (thread-safe since C++11, no manual locks) ---
class Config {
public:
    static Config& instance() {
        static Config inst;        // initialized once, race-free (magic static)
        return inst;
    }
    Config(const Config&) = delete;            // no copy -> can't clone the "single"
    Config& operator=(const Config&) = delete; // no assign
private:
    Config() = default;            // private ctor: nobody else can construct one
};

// --- Pre-C++11 / heap variant: Double-Checked Locking (needs atomic!) ---
class Logger {
    static std::atomic<Logger*> inst;
    static std::mutex m;
    Logger() = default;
public:
    static Logger* instance() {
        Logger* p = inst.load(std::memory_order_acquire);
        if (!p) {                                  // 1st check: usually skips the lock
            std::lock_guard<std::mutex> lk(m);
            p = inst.load(std::memory_order_relaxed);
            if (!p) {                              // 2nd check: under the lock
                p = new Logger();
                inst.store(p, std::memory_order_release);  // publish fully-built obj
            }
        }
        return p;
    }
};
std::atomic<Logger*> Logger::inst{nullptr};
std::mutex Logger::m;
  • Complexity: O(1) access; DCLP avoids locking on the common (already-initialized) path.
  • Gotcha / variants: The DCLP atomic with acquire/release is essential — a plain pointer is the textbook broken DCLP bug (a partially-constructed object becomes visible to another thread). Delete copy & move or you can duplicate the instance. Singletons hurt testability (global state) — mention dependency injection as the alternative. In an interview, just write the Meyers version unless they demand a heap instance.

M7. Implement your own immutable class [H]

  • Idea: State is set once in the constructor and never changes: private members (often const), only const getters, no setters. If it holds mutable data, deep-copy in and never expose non-const references to internals. "Modifications" return a new object.
  • Code: 
    #include <vector>
#include <utility>
using namespace std;

class ImmutablePoint {
    const int x_, y_;                 // const => provably never reassigned
public:
    ImmutablePoint(int x, int y) : x_(x), y_(y) {}   // set once
    int x() const { return x_; }      // const accessor, no setter
    int y() const { return y_; }
    // "Change" => return a brand-new object, original untouched.
    ImmutablePoint withX(int nx) const { return ImmutablePoint(nx, y_); }
};

class ImmutableConfig {
    vector<int> data_;                // not const (so the class stays movable),
public:                               // but never mutated after construction.
    explicit ImmutableConfig(vector<int> d) : data_(std::move(d)) {}  // copy in
    // Return a COPY (not a non-const ref) so the caller can't mutate internals.
    vector<int> data() const { return data_; }
    int at(size_t i) const { return data_[i]; }
};
  • Complexity: N/A; defensive copies cost O(n) but buy lock-free sharing.
  • Gotcha / variants: Immutable objects are inherently thread-safe — no writes, no data races, shareable across threads with zero locking (great for camera StreamConfig/FrameMetadata snapshots). const members make the class non-assignable/non-movable — fine, but note it. Holding a const* to a mutable external object does not make you immutable (the pointee can change) — that's why you copy in.

N. Concurrency / multithreading (write the code)

N1. Print odd & even sequentially using two threads + a mutex/condition variable [M]

  • Idea: Two threads alternate (1,2,3,...). Share a counter and a "whose turn" predicate; each thread waits on a condition variable until it's its turn, prints, flips the turn, and notifys the other.
  • Code: 
    #include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
using namespace std;

mutex m;
condition_variable cv;
int counter = 1;
const int N = 10;

void printer(bool wantOdd) {
    while (true) {
        unique_lock<mutex> lk(m);
        // wait until it's our parity's turn (predicate guards spurious wakeups)
        cv.wait(lk, [&] { return counter > N || (counter % 2 == 1) == wantOdd; });
        if (counter > N) break;                 // termination
        cout << counter++ << " ";
        cv.notify_all();                        // wake the other thread
    }
    cv.notify_all();                            // unblock peer so it can see counter>N
}

void run() {
    thread t1(printer, true);   // odd
    thread t2(printer, false);  // even
    t1.join(); t2.join();       // prints: 1 2 3 4 5 6 7 8 9 10
}
  • Complexity: O(N) prints; each handoff is one lock + one CV wake.
  • Gotcha / variants: Use the predicate form of wait (while, not if) to survive spurious wakeups. Both threads must re-check counter > N and notify on exit, or the peer hangs forever. Variant: do it with two semaphores ping-ponging (sem_odd.post/sem_even.wait) — often cleaner. Generalises to N threads printing 1..k in turn.

N2. Program using pthreads — create/join, pass args [M]

  • Idea: pthread_create launches a thread running a void* fn(void*); pass per-thread data through the void* arg (point at a struct, not a shared loop variable). pthread_join waits and collects the return value.
  • Code: 
    #include <pthread.h>
#include <stdio.h>

typedef struct { int id; int n; } Args;

void* worker(void* arg) {
    Args* a = (Args*)arg;                 // cast the void* back to our type
    long sum = 0;
    for (int i = 1; i <= a->n; i++) sum += i;
    printf("thread %d sum=%ld\n", a->id, sum);
    return (void*)sum;                    // returned to whoever joins
}

int main(void) {
    pthread_t t[3];
    Args args[3];                         // SEPARATE struct per thread (no aliasing)
    for (int i = 0; i < 3; i++) {
        args[i] = (Args){ .id = i, .n = (i + 1) * 100 };
        pthread_create(&t[i], NULL, worker, &args[i]);   // pass &args[i]
    }
    for (int i = 0; i < 3; i++) {
        void* ret;
        pthread_join(t[i], &ret);         // wait + collect return value
        printf("joined %d -> %ld\n", i, (long)ret);
    }
    return 0;
}
// Compile: gcc file.c -lpthread
  • Complexity: O(#threads) management; each thread does its own O(n) work.
  • Gotcha / variants: Don't pass &i (the loop variable) to every thread — they'd race and all see the final value; give each its own struct. Always join (or pthread_detach) to avoid resource leaks. Returning a pointer to a local is a dangling bug — return a value cast to void* or a heap pointer the joiner frees.

N3. Two threads accessing the same map — protect with mutex/locking [M]

  • Idea: std::map/unordered_map is not thread-safe for concurrent writes. Guard every access with a mutex. If reads dominate, use a shared_mutex (reader/writer lock): many concurrent readers, exclusive writers.
  • Code: 
    #include <unordered_map>
#include <string>
#include <mutex>
#include <shared_mutex>
using namespace std;

class SafeMap {
    unordered_map<string, int> m;
    mutable shared_mutex mtx;          // mutable so const reads can lock it
public:
    void put(const string& k, int v) {
        unique_lock lk(mtx);           // exclusive (writer) lock
        m[k] = v;
    }
    bool get(const string& k, int& out) const {
        shared_lock lk(mtx);           // shared (reader) lock: many can read at once
        auto it = m.find(k);
        if (it == m.end()) return false;
        out = it->second; return true;
    }
};
// Simpler version if reads don't dominate: just use std::mutex + lock_guard
// on every method. RAII guards unlock automatically (even on exception).
  • Complexity: map ops O(1) avg (unordered) under the lock; lock add small overhead.
  • Gotcha / variants: Every access — including reads, and including the implicit insert from m[k] — must be guarded; iterator invalidation under concurrent modification is UB. Keep critical sections short. shared_mutex shines when reads ≫ writes (camera config read by many stages, written rarely). Use RAII guards (lock_guard/unique_lock) so locks release on exceptions.

N4. Implement a binary semaphore [H]

  • Idea: A counter with wait (P: block while 0, then decrement) and post (V: increment, wake one). Back it with a mutex + condition variable so waiters sleep instead of busy-waiting. Binary = value capped at 1.
  • Code: 
    #include <mutex>
#include <condition_variable>

class BinarySemaphore {
    int value;
    std::mutex m;
    std::condition_variable cv;
public:
    explicit BinarySemaphore(int init = 1) : value(init ? 1 : 0) {}

    void wait() {                                  // P
        std::unique_lock<std::mutex> lk(m);
        cv.wait(lk, [&] { return value > 0; });    // sleep while 0 (while, not if)
        value = 0;                                 // take it (binary)
    }

    void post() {                                  // V
        std::unique_lock<std::mutex> lk(m);
        value = 1;                                 // cap at 1 for strictly-binary
        cv.notify_one();                           // wake one waiter
    }
};
  • Complexity: O(1) per wait/post (plus scheduler wakeup cost).
  • Gotcha / variants: Use while/predicate around cv.wait to handle spurious wakeups. A counting semaphore is the same with value--/value++ and no cap. Key difference from a mutex: a semaphore has no owner, so any thread (even an ISR) can post one that another thread waits — that ownerless handoff (e.g. "DMA done" signal) is exactly why you'd pick it over a mutex. Follow-up: a binary semaphore can act as a lock but loses priority inheritance.

N5. Write pseudocode that creates a deadlock, then fix it [M]

  • Idea: Two threads lock two mutexes in opposite order → circular wait → deadlock (all four Coffman conditions met). Fix: impose a global lock ordering so everyone acquires A before B (breaks circular wait). std::scoped_lock does this safely.
  • Code: 
    #include <mutex>
#include <thread>
std::mutex A, B;

// ---- DEADLOCK: opposite acquisition order ----
void t1_bad() { A.lock(); /* ...work... */ B.lock(); B.unlock(); A.unlock(); }
void t2_bad() { B.lock(); /* ...work... */ A.lock(); A.unlock(); B.unlock(); }
// t1 holds A waits B; t2 holds B waits A  =>  circular wait  =>  hang forever.

// ---- FIX 1: consistent global order (always A then B) ----
void t1_ok() { A.lock(); B.lock(); /* work */ B.unlock(); A.unlock(); }
void t2_ok() { A.lock(); B.lock(); /* work */ B.unlock(); A.unlock(); }

// ---- FIX 2 (idiomatic C++): lock both atomically, deadlock-free ----
void worker() {
    std::scoped_lock lk(A, B);   // acquires both with a deadlock-avoidance algorithm
    /* critical section */
}                                // both released automatically (RAII)
  • Complexity: N/A.
  • Gotcha / variants: The bug is lock order, not the locks themselves. Other fixes that break a different Coffman condition: try_lock + back-off (breaks no-preemption/hold-and-wait), a single coarse lock (removes the second resource), or std::lock(A,B) / scoped_lock (locks all-or-nothing). This is also why producer/consumer must take the counting semaphore before the mutex.

N6. Identify the race condition in given pseudocode [M]

  • Idea: A race exists when the result depends on thread interleaving. The classic: counter++ is really read–modify–write (3 steps); two threads can read the same value and one increment is lost. Fix with a mutex or an atomic.
  • Code: 
    // ---- BUGGY: data race on `counter` ----
int counter = 0;                       // shared, unprotected
void increment() {                     // run by many threads, each looping
    for (int i = 0; i < 100000; i++)
        counter++;                     // load, add, store -> NOT atomic
}
// Two threads can both load 5, both store 6 -> one increment lost.
// Final count is < expected and non-deterministic. THAT is the race.

// ---- FIX A: mutex around the critical section ----
#include <mutex>
std::mutex m; int c1 = 0;
void inc_locked() {
    for (int i = 0; i < 100000; i++) { std::lock_guard<std::mutex> lk(m); c1++; }
}

// ---- FIX B: atomic (lock-free for a simple counter, faster) ----
#include <atomic>
std::atomic<int> c2{0};
void inc_atomic() {
    for (int i = 0; i < 100000; i++) c2.fetch_add(1, std::memory_order_relaxed);
}
  • Complexity: atomic increment is O(1) lock-free; mutex adds lock overhead.
  • Gotcha / variants: To spot a race, look for shared mutable state touched without synchronization. Reads can race too (a torn read of a non-atomic). volatile does not fix races (it's not about atomicity/ordering) — use std::atomic or a mutex. For a plain counter prefer atomic (faster than locking); for compound invariants you still need a mutex.

O. Design / implement-a-system

O1. LRU cache (hashmap + doubly linked list) — and the "twisted LRU" variant [H]

  • Idea: O(1) get/put by combining a hash map (key → list node, for O(1) lookup) with a doubly linked list ordered by recency (front = most recent, back = least). On access, splice the node to the front; on overflow, evict the back.
  • Code: 
    #include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
    int cap;
    list<pair<int,int>> dll;                              // front=MRU, back=LRU: {key,val}
    unordered_map<int, list<pair<int,int>>::iterator> mp; // key -> node iterator
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) return -1;
        dll.splice(dll.begin(), dll, it->second);         // move to front, O(1)
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = mp.find(key);
        if (it != mp.end()) {                             // update existing
            it->second->second = value;
            dll.splice(dll.begin(), dll, it->second);     // refresh recency
            return;
        }
        if ((int)dll.size() == cap) {                     // evict LRU (back)
            mp.erase(dll.back().first);
            dll.pop_back();
        }
        dll.push_front({key, value});                     // insert as MRU
        mp[key] = dll.begin();
    }
};
  • Complexity: O(1) get and put; O(capacity) space.
  • Gotcha / variants: std::list::splice is O(1) and keeps iterators valid — that's why we store list iterators in the map. Twisted LRU usually adds: per-entry TTL (also evict expired on access), capacity by bytes (track total size, evict until it fits), or thread-safety (wrap in a mutex, or shard by key hash to cut contention). Don't use a plain array — eviction would be O(n).

O2. LFU cache [H]

  • Idea: Evict the least-frequently-used key; break ties by least-recently-used. Keep a map key→(value, freq, list-iterator), and a map freq → list of keys (each freq's list is LRU-ordered). Track minFreq for O(1) eviction.
  • Code: 
    #include <list>
#include <unordered_map>
using namespace std;

class LFUCache {
    int cap, minFreq = 0;
    unordered_map<int, list<int>> freqList;       // freq -> keys (front=MRU at that freq)
    unordered_map<int, int> val, freq;            // key -> value, key -> frequency
    unordered_map<int, list<int>::iterator> iter; // key -> its node in freqList[freq]

    void touch(int key) {                         // bump key's frequency by 1
        int f = freq[key];
        freqList[f].erase(iter[key]);             // remove from old freq bucket
        if (freqList[f].empty()) {
            freqList.erase(f);
            if (minFreq == f) minFreq++;          // advance minFreq if we emptied it
        }
        freq[key] = f + 1;
        freqList[f + 1].push_front(key);          // add to new bucket (as MRU)
        iter[key] = freqList[f + 1].begin();
    }
public:
    LFUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        if (!val.count(key)) return -1;
        touch(key);
        return val[key];
    }

    void put(int key, int value) {
        if (cap == 0) return;
        if (val.count(key)) { val[key] = value; touch(key); return; }
        if ((int)val.size() == cap) {             // evict LFU, ties -> LRU (back)
            int evict = freqList[minFreq].back();
            freqList[minFreq].pop_back();
            val.erase(evict); freq.erase(evict); iter.erase(evict);
        }
        val[key] = value; freq[key] = 1;          // new keys start at freq 1
        freqList[1].push_front(key);
        iter[key] = freqList[1].begin();
        minFreq = 1;                              // a fresh key resets minFreq
    }
};
  • Complexity: O(1) get and put; O(capacity) space.
  • Gotcha / variants: The subtlety is tie-breaking by recency within a frequency (front=MRU, evict back=LRU) and maintaining minFreq correctly — reset to 1 on every insert, advance only when its bucket empties. LFU favours hot items over merely-recent ones; LRU favours recency. Mention you'd pick LFU when access frequency, not recency, is the right eviction signal.

O3. Timer module — timeouts & callbacks for many clients (min-heap / timer wheel) [H]

  • Idea: Expose add(delay, cb, ctx), cancel(handle), and an internal tick(). For a moderate number of arbitrary-delay timers, a min-heap keyed by absolute expiry gives O(log n) insert and O(1) peek-soonest. For many clients, switch to a hashed timing wheel (O(1) insert/expire). Callbacks are function pointer + void* ctx.
  • Code: 
    #include <queue>
#include <vector>
#include <cstdint>
#include <functional>
using namespace std;

class TimerHeap {
    struct Timer {
        uint64_t expiry;                       // absolute fire time
        function<void()> cb;
        uint64_t id;
        bool operator>(const Timer& o) const { return expiry > o.expiry; }
    };
    // min-heap: soonest expiry on top
    priority_queue<Timer, vector<Timer>, greater<Timer>> pq;
    uint64_t now = 0, nextId = 1;
public:
    uint64_t add(uint64_t delay, function<void()> cb) {
        uint64_t id = nextId++;
        pq.push({now + delay, move(cb), id});  // O(log n)
        return id;                             // handle for cancel
    }

    // Advance time; fire everything due. Call this from your tick source / event loop.
    void tick(uint64_t elapsed) {
        now += elapsed;
        while (!pq.empty() && pq.top().expiry <= now) {  // O(1) peek soonest
            auto t = pq.top(); pq.pop();
            t.cb();                            // fire the callback
        }
    }
};
// Timing wheel (sketch) for MANY timers: bucket[(cursor + ticks) % N] with a
// per-timer `rounds` counter; each tick fires the current bucket -> O(1) amortized.
  • Complexity: min-heap: O(log n) insert/expire, O(1) peek. Timing wheel: O(1) amortized insert/cancel/expire.
  • Gotcha / variants: Cancel in a heap is the weak spot — mark a timer "cancelled" and skip it on pop (lazy deletion), since you can't cheaply remove from the middle. The timing wheel wins at high timer counts and bounded ranges (Linux uses hierarchical wheels); the min-heap wins for few timers with arbitrary delays. In C the callback is a function pointer plus a void* ctx cookie.

O4. Lottery machine — non-repeating draws, circular elimination, logging, clean design [H]

  • Idea: Draw non-repeating holders (Fisher–Yates style), eliminate around a circle continuing from the last position (Josephus), log everything, until one winner remains. Separate responsibilities: RNG, pool, elimination, logging — injected for testability.
  • Code: 
    #include <vector>
#include <string>
#include <iostream>
#include <cstdlib>
using namespace std;

struct IRandom { virtual int next(int n) = 0; virtual ~IRandom() = default; }; // [0,n)
struct ILogger { virtual void log(const string& s) = 0; virtual ~ILogger() = default; };

class LotteryMachine {
    vector<int> pool;          // surviving ticket holders, 1..N
    IRandom& rng;
    ILogger& log;
public:
    LotteryMachine(int N, IRandom& r, ILogger& l) : rng(r), log(l) {
        for (int i = 1; i <= N; i++) pool.push_back(i);
    }
    int run() {
        int pos = 0;                          // circular cursor (continue from here)
        while (pool.size() > 1) {
            int step = rng.next(pool.size()); // pick an offset
            pos = (pos + step) % pool.size(); // circular advance
            log.log("eliminate holder " + to_string(pool[pos]));
            pool.erase(pool.begin() + pos);   // remove; next draw continues from pos
            if (pos == (int)pool.size()) pos = 0;  // wrap if we erased the last slot
        }
        log.log("winner is " + to_string(pool[0]));
        return pool[0];
    }
};
  • Complexity: O(N) draws × O(N) erase from a vector = O(N²); use a circular linked list for O(1) removal if N is large.
  • Gotcha / variants: Use Fisher–Yates (swap chosen index to the end, shrink) for an unbiased non-repeating draw if you want O(1) per pick. The "continue from the last eliminated position" requirement is the Josephus twist — keep the cursor across draws and wrap with % size. Inject IRandom/ILogger (the logger is an Observer) so the machine is deterministic and unit-testable. One class per responsibility (Single Responsibility).

O5. Screen-tearing fix — CRT panel + SoC share one frame buffer (producer/consumer, reader-writer sync) [H]

  • Idea: Tearing happens when the display reads a frame while the SoC is mid-write. Decouple with double buffering + producer/consumer sync: the writer fills a back buffer, then atomically swaps it to front; the reader only ever reads a complete front buffer. A condition variable signals "new frame ready."
  • Code: 
    #include <mutex>
#include <condition_variable>
#include <vector>
using namespace std;

class FrameSwap {
    vector<int> front, back;          // two buffers (double buffering)
    bool ready = false;               // a fresh frame is waiting in `front`
    mutex m;
    condition_variable cv;
public:
    FrameSwap(size_t sz) : front(sz), back(sz) {}

    // SoC (producer): render into `back`, then publish by swapping under the lock.
    void produce(const vector<int>& frame) {
        back = frame;                 // write the complete frame off-screen
        {
            lock_guard<mutex> lk(m);
            swap(front, back);        // atomic publish -> reader never sees a partial
            ready = true;
        }
        cv.notify_one();              // wake the display
    }

    // Display (consumer): wait for a full frame, then scan it out.
    vector<int> consume() {
        unique_lock<mutex> lk(m);
        cv.wait(lk, [&]{ return ready; });   // block until a complete frame exists
        ready = false;
        return front;                 // front is always a fully-written frame
    }
};
  • Complexity: O(frame size) per swap-copy; sync ops O(1).
  • Gotcha / variants: The real-hardware fix is VSync: swap buffers only during the panel's vertical blanking interval so the swap never lands mid-scanout. Triple buffering lets the SoC start the next frame without waiting for the display to finish. This is the reader-writer / producer-consumer problem — readers (display) must never see a half-written buffer; keep the swap critical section tiny.

O6. Text editor with undo/redo [H]

  • Idea: Command pattern + two stacks. Each edit is a command that knows how to apply and undo itself. Push applied commands onto the undo stack; undo pops one, reverses it, and pushes it to redo. A new edit clears redo.
  • Code: 
    #include <string>
#include <stack>
#include <memory>
using namespace std;

struct Command {
    virtual void apply(string& doc) = 0;
    virtual void undo(string& doc) = 0;
    virtual ~Command() = default;
};

struct InsertCmd : Command {            // insert `text` at `pos`
    size_t pos; string text;
    InsertCmd(size_t p, string t) : pos(p), text(move(t)) {}
    void apply(string& doc) override { doc.insert(pos, text); }
    void undo(string& doc)  override { doc.erase(pos, text.size()); }  // inverse
};

class Editor {
    string doc;
    stack<unique_ptr<Command>> undoStk, redoStk;
public:
    void execute(unique_ptr<Command> c) {
        c->apply(doc);
        undoStk.push(move(c));
        while (!redoStk.empty()) redoStk.pop();   // new edit invalidates redo
    }
    void undo() {
        if (undoStk.empty()) return;
        auto c = move(undoStk.top()); undoStk.pop();
        c->undo(doc);                              // reverse it
        redoStk.push(move(c));
    }
    void redo() {
        if (redoStk.empty()) return;
        auto c = move(redoStk.top()); redoStk.pop();
        c->apply(doc);                             // re-apply
        undoStk.push(move(c));
    }
    const string& text() const { return doc; }
};
  • Complexity: O(cost of one edit) per op; O(#edits × edit size) memory for history.
  • Gotcha / variants: Each command must store enough to invert itself (a delete must remember the deleted text). A new edit clears the redo stack — easy to forget. Cap history depth or use a snapshot/memento approach for huge documents. Coalescing consecutive single-char inserts into one command makes undo feel natural.

O7. Lift / elevator management system (FSM + scheduling) [H]

  • Idea: Model the car as a state machine (IDLE / MOVING_UP / MOVING_DOWN / DOOR_OPEN). Use the SCAN ("elevator") algorithm: keep going in the current direction servicing requests, then reverse. Hold pending stops in two sorted sets (up-going, down-going).
  • Code: 
    #include <set>
using namespace std;

enum class State { IDLE, UP, DOWN };

class Elevator {
    int floor = 0;
    State state = State::IDLE;
    set<int> upStops;                 // requested floors above (ascending)
    set<int> downStops;               // requested floors below (descending via rbegin)
public:
    void request(int target) {
        if (target > floor) upStops.insert(target);
        else if (target < floor) downStops.insert(target);
    }
    // One simulation step: move toward the nearest stop in the current direction.
    void step() {
        if (state == State::IDLE) {                       // pick a direction
            if (!upStops.empty()) state = State::UP;
            else if (!downStops.empty()) state = State::DOWN;
            else return;                                  // nothing to do
        }
        if (state == State::UP) {
            floor++;
            if (upStops.count(floor)) { /* doors open */ upStops.erase(floor); }
            if (upStops.empty())                          // exhausted this direction
                state = downStops.empty() ? State::IDLE : State::DOWN;  // reverse
        } else if (state == State::DOWN) {
            floor--;
            if (downStops.count(floor)) { /* doors open */ downStops.erase(floor); }
            if (downStops.empty())
                state = upStops.empty() ? State::IDLE : State::UP;
        }
    }
    int currentFloor() const { return floor; }
};
  • Complexity: O(log k) per request insert; O(1)–O(log k) per step (k = pending stops).
  • Gotcha / variants: SCAN beats FCFS — serving requests in directional order minimizes total travel and avoids starvation (don't reverse on every new request). Distinguish external (hall, has a direction) from internal (cabin) calls. Multi-car systems add a dispatcher that assigns the request to the best car (nearest in the right direction). The FSM keeps door timing and direction logic clean.

O8. Camera-driver architecture for multiple sensors (HAL + ops tables + registration) [H]

  • Idea: Decouple the generic camera framework from per-sensor specifics with a HAL: a struct of function pointers (an "ops table"), one implementation per sensor. Sensors register themselves; the framework calls through the table without knowing the concrete driver (polymorphism in C).
  • Code: 
    #include <stdint.h>
#include <stddef.h>

/* The HAL contract: every sensor driver fills in this ops table. */
struct sensor_ops {
    int  (*power_on)(void *ctx);
    int  (*set_mode)(void *ctx, int mode);       /* resolution/fps */
    int  (*start_stream)(void *ctx);
    int  (*stop_stream)(void *ctx);
    int  (*read_frame)(void *ctx, uint8_t *buf, size_t len);
    void (*power_off)(void *ctx);
};

struct sensor {
    const char *name;
    const struct sensor_ops *ops;   /* vtable-like dispatch */
    void *ctx;                       /* per-instance private data */
};

/* --- Registration: drivers add themselves to a table at init --- */
#define MAX_SENSORS 8
static struct sensor *registry[MAX_SENSORS];
static int n_sensors;
int sensor_register(struct sensor *s) {
    if (n_sensors >= MAX_SENSORS) return -1;
    registry[n_sensors++] = s;
    return 0;
}

/* --- Generic framework code: works for ANY registered sensor --- */
int camera_capture(struct sensor *s, uint8_t *buf, size_t len) {
    if (s->ops->power_on(s->ctx)) return -1;
    s->ops->set_mode(s->ctx, /*mode=*/0);
    s->ops->start_stream(s->ctx);
    int rc = s->ops->read_frame(s->ctx, buf, len);   /* dispatch to real driver */
    s->ops->stop_stream(s->ctx);
    s->ops->power_off(s->ctx);
    return rc;
}
/* A specific sensor (e.g. IMX_586) defines its own ops table + struct sensor,
   then calls sensor_register() from its init -- exactly how Linux V4L2/HAL3 work. */
  • Complexity: O(1) dispatch (one indirect call); registry lookup O(#sensors).
  • Gotcha / variants: This is runtime polymorphism in C — the ops table is a hand-rolled vtable, void* ctx is the this pointer. It mirrors V4L2 subdev ops and Android Camera HAL3. Validate function pointers before calling (a NULL op = unsupported feature). Extensions: a probe/match step (bind driver to detected hardware ID), reference-counted open/close, and per-request settings passed as an immutable config struct.

Covers Part 1 categories L (recursion/DP/graphs), M (C++ & OOP), N (concurrency), and O (design) of practice_questions.md. All code is written to compile cleanly (C with -lpthread where noted; C++ as C++17 for scoped_lock/shared_mutex/structured bindings). Drill the idea first, then reproduce the code from memory — that's what the whiteboard tests.