Qualcomm Interview Prep — 10. Low-Level Design & System Design¶
Scope. Object-oriented / low-level design (LLD) and pragmatic system design as Qualcomm actually asks it — a repeatable method for attacking a design problem, plus the specific designs that show up in the reports: a timer module for many clients, Google Maps road-block handling, a lift/elevator system, a lottery machine, a camera-driver architecture for multiple sensors, a low-latency preview pipeline, the screen-tearing / producer–consumer display problem, a text editor with undo/redo, an immutable class, a hardware-vs-software model comparison, and the warm-ups (parking lot, rate limiter, bounded producer-consumer, LRU). It also owns SOLID and the design patterns these use (Singleton, Factory, Observer, Strategy, State, Adapter) at the design level. Pure C language lives in
01_c_programming.md; C++ syntax/OOP mechanics (vtable, virtual, friend, RAII, smart pointers) in02_cpp_oop.md; the algorithms themselves (Dijkstra, heaps, LRU mechanics, graph traversal) in03_dsa.md; threads/mutex/semaphore/scheduling theory in04_os.md; the camera/ISP pipeline domain in05_camera_isp_multimedia.md; kernel/driver/HAL/ioctlplumbing in07_embedded_linux_kernel.md. Overlaps are cross-linked, not duplicated — here we design with those pieces, we don't re-teach them.How to read each entry. Every question is answered in layers so you can stop at the depth you need: - Q — the question, phrased as interviewers actually ask it. - Frequency — how often it showed up in the 75 collected reports (tier + approximate count). - Concept — the basis — book-style fundamentals with worked examples and, where it helps, an SVG diagram. - The "wh"s — Why it exists / matters (the problem the design solves), Where you see it (real Qualcomm/camera/embedded/SoC situations), and any important caveat. - Answer — a tight, say-it-out-loud interview answer. - Solution / good example — for "design / implement X" questions, a complete, copy-pasteable class design or code (not a sketch). - Follow-ups / gotchas — the traps interviewers spring next. - Seen in — the source reports.
Terms in bold-italics like SOLID, Strategy pattern, timing wheel, SCAN, producer–consumer, Singleton are defined in the § Encyclopedia at the bottom — search there for any keyword.
Frequency legend (sample = 75 collected interview reports; counts are approximate and partly from aggregator pages, so treat them as directional): 🔥🔥🔥 Very common (~8+ reports) · 🔥🔥 Common (~4–7) · 🔥 Occasional (~2–3) · ◽ Foundational (rarely asked verbatim, but assumed and underpinning everything else).
Why design rounds matter at Qualcomm. Almost every loop has at least one open-ended design round — candidates report a dedicated "Design Round (1–2 hrs)" with continuous cross-questioning and interviewer hints (Associate SWE off-campus), a 2-hour display LLD round (screen tearing), and embedded loops that ask you to "write code for the timer module" or "design Google Maps road-block handling" on the spot. Interviewers explicitly weight collaboration and thinking aloud over a perfect final answer. They want to see you clarify, decompose, name entities, pick data structures, reason about trade-offs and concurrency, and adapt to hints — the same skill you use when architecting an ISP node graph or a sensor HAL. Evidence base: qualcomm_camera_interview_experiences.md.
Table of contents¶
- A. The method & principles — A1 a repeatable LLD method · A2 SOLID principles · A3 what are design patterns & why · A4 UML association/aggregation/composition
- B. The actually-asked designs — B1 timer module · B2 Google Maps road-blocks · B3 lift/elevator · B4 lottery machine · B5 text editor undo/redo
- C. Camera / display / SoC designs — C1 camera-driver architecture · C2 low-latency preview pipeline · C3 screen-tearing / producer–consumer · C4 hardware vs software model
- D. LLD warm-ups — D1 immutable class · D2 parking lot · D3 rate limiter · D4 bounded producer-consumer · D5 LRU cache (design view)
- E. The patterns these use — E1 Singleton (thread-safe) · E2 Factory · E3 Observer · E4 Strategy · E5 State · E6 Adapter
- § Encyclopedia — searchable glossary
- § Last-5-minutes cheat sheet
A. The method & principles¶
A1 · Q: Walk me through how you approach an open-ended low-level design problem.¶
Frequency: 🔥🔥🔥 Very common (~8+ reports) — essentially every loop has a design round, and the method is what's being graded as much as the answer (Associate SWE off-campus "2 open-ended design problems with continuous cross-questioning"; LeetCode kernel SWE "Google Maps design"; Display LLD "screen tearing"; foundit/CleverPrep design prompts).
Concept — the basis. An LLD problem is under-specified on purpose. The interviewer wants to watch you impose structure. Use the same seven-step pipeline every time, narrating each step:
- Clarify requirements & scope. Ask: who are the actors? what are the must-have operations vs nice-to-haves? what's the scale (10 clients or 10 million)? single-process or distributed? real-time? Pin down 3–5 functional requirements and 1–2 non-functional ones (latency, memory, thread-safety). Never start coding before this.
- Identify entities → classes. The nouns in the problem become classes/attributes ("a car serves requests in a building" →
Elevator,Request,Building). Give each a single responsibility. - Relationships & APIs. The verbs become methods/APIs ("request a floor, dispatch a car"). Decide has-a (composition/aggregation) vs is-a (inheritance), and define the public interface first — the contract.
- Data structures + complexity. Pick the concrete structure behind each operation and state its Big-O (a min-heap for next-stop, a hash map + DLL for LRU, a ring buffer for frames). This is where Qualcomm loves to push.
- Edge cases & errors. Empty input, full capacity, duplicate request, concurrent shutdown, invalid floor, overflow. Enumerate them out loud.
- Concurrency. Who touches shared state? What's the locking strategy, the producer/consumer boundary, the ownership of buffers? Even single-threaded-looking problems (timer, preview) are concurrent at Qualcomm.
- Trade-offs. Compare two designs (heap vs timing wheel, lock vs lock-free), invoke SOLID and a pattern where it genuinely helps, and say what you'd change at 100× scale.
Worked micro-example — applying it in 20 seconds to "design a parking lot":
1. Clarify: multi-floor? vehicle types? payment? -> assume floors, {motorcycle,car,truck}, ticket on entry.
2. Entities: ParkingLot, Floor, Spot, Vehicle, Ticket, Gate.
3. APIs: park(Vehicle)->Ticket, unpark(Ticket)->fee; Spot.assign()/free().
4. Structures: per-type free-spot queues -> O(1) park/unpark; map ticket->spot.
5. Edge: lot full, lost ticket, vehicle too big for spot.
6. Concurrency: two cars racing for the last spot -> lock the spot pool / atomic claim.
7. Trade-off: queue-per-type (fast) vs single sorted structure (flexible).
Why it matters. A structured method is the single highest-leverage interview skill — it turns a scary blank-page prompt into a checklist, keeps you talking (collaboration is explicitly scored), and guarantees you cover concurrency and complexity, the two things juniors skip. Reports repeatedly credit "discuss approach first, then code" and "explain visually before coding."
Where you see it (Qualcomm). Designing an ISP node graph, a sensor HAL, a buffer-manager, a request queue for CamX — all real work that is LLD. The interviewer is simulating a design review.
Answer. "I clarify requirements and scale first, then pull the nouns out as classes and the verbs as APIs, decide the relationships, pick a data structure for each operation and state its complexity, walk the edge cases, address concurrency and ownership of shared state, and finish with trade-offs — comparing at least two approaches and naming where a SOLID principle or a pattern earns its place. I think aloud the whole time and adapt to the interviewer's hints."
Follow-ups / gotchas. Don't gold-plate (designing payments before the interviewer asked). Don't jump to a pattern name to sound smart — justify it. Always give complexity. State assumptions explicitly so a wrong assumption is the interviewer's to correct, not a silent failure.
Seen in: Associate SWE off-campus (#12, "2 open-ended design problems with continuous cross-questioning and interviewer hints"), Display Senior Engineer (#2, 2-hr design round), kernel SWE (#15, Google Maps), CleverPrep camera guide (#1), foundit (#9, "Implement malloc/free — describe the strategy").
A2 · Q: What are the SOLID principles? Give an example of each.¶
Frequency: 🔥🔥 Common (~4–7, aggregator-reported) — design rounds and OOP rounds lean on this; "design patterns and why" (#15) and OOP pillars (#51) are adjacent.
Concept — the basis. SOLID is five object-oriented design principles (Robert C. Martin) that keep a design maintainable, extensible, and testable:
| Letter | Principle | One-line rule |
|---|---|---|
| S | Single Responsibility | A class should have one reason to change — one job. |
| O | Open/Closed | Open for extension, closed for modification — add behavior without editing tested code. |
| L | Liskov Substitution | A subtype must be usable anywhere its base type is, without breaking correctness. |
| I | Interface Segregation | Many small, specific interfaces beat one fat one; clients don't depend on methods they don't use. |
| D | Dependency Inversion | Depend on abstractions, not concretions — high-level policy shouldn't depend on low-level detail. |
Example — applying each to a camera/sensor design:
// S: each class one job
class SensorReader { Frame read(); }; // only reads frames
class FrameEncoder { Blob encode(Frame); }; // only encodes — not mixed in
// O: add a new sensor by adding a class, NOT by editing the framework
struct ISensor { virtual Frame read() = 0; virtual ~ISensor() = default; };
class IMX586 : public ISensor { Frame read() override; }; // new sensor, zero core edits
// L: a substitute must honor the contract
class OV64B : public ISensor { Frame read() override; }; // returns a valid Frame too
// I: split a fat "Device" interface so a read-only sensor isn't forced to implement write()
struct IReadable { virtual Frame read() = 0; };
struct IWritable { virtual void write(Frame) = 0; };
// D: the pipeline depends on the ISensor abstraction, injected — not on IMX586 directly
class Pipeline { ISensor& s; public: Pipeline(ISensor& s):s(s){} void run(){ s.read(); } };
Why it exists. Without these, designs rot: one class grows to do everything (violates S), every new sensor means editing a giant switch (violates O), and the framework is welded to one concrete device (violates D), so nothing can be unit-tested in isolation. SOLID is the vocabulary an interviewer uses to ask "why is this design good?"
Where you see it (Qualcomm). A camera HAL that adds sensors via registration (O + D); an ISP node base class whose subclasses (denoise, demosaic) are substitutable (L); splitting a control interface from a streaming interface (I). The Linux driver "ops table" pattern is Dependency Inversion in C.
Answer. "SOLID is Single Responsibility — one reason to change per class; Open/Closed — extend without modifying; Liskov — subtypes substitutable for their base; Interface Segregation — small focused interfaces; Dependency Inversion — depend on abstractions, inject the concretion. In a camera design: each class does one thing, new sensors are new classes implementing an ISensor interface (no core edits), every sensor honors the same read() contract, control and streaming interfaces are separate, and the pipeline holds an ISensor& reference rather than a concrete type."
Follow-ups / gotchas. "Closed for modification" doesn't mean never edit — it means new features shouldn't force edits to stable code. The clean way to get O+D is an interface + a Factory/registration. Over-applying ISP/DIP creates interface explosion — judgment matters.
Seen in: design-pattern / OOP rounds (#15 "design patterns and why", #51 OOP pillars); standard LLD expectation.
A3 · Q: What are design patterns and why do you use them?¶
Frequency: 🔥🔥 Common (~4–7) — asked verbatim in the kernel SWE loop (#15 "What are design patterns and why use them?"), and the patterns recur in Singleton/Factory/Observer questions.
Concept — the basis. A design pattern is a named, reusable solution to a recurring design problem — a shared vocabulary so "use a Factory here" conveys an entire structure. The classic "Gang of Four" set splits into three families: - Creational — how objects are made: Singleton (one instance), Factory (decide the concrete type at runtime), Builder, Prototype. - Structural — how objects compose: Adapter (make incompatible interfaces work together), Decorator, Facade, Proxy, Composite. - Behavioral — how objects interact: Observer (publish/subscribe), Strategy (swap an algorithm), State (behavior changes with state), Command, Iterator.
Example — naming the patterns inside the designs in this file:
Singleton -> the global config / ID generator / logger (B4 lottery log, E1)
Factory -> create the right sensor driver from a sensor-id (C1, E2)
Observer -> floor buttons / lottery log subscribers / preview consumers (E3)
Strategy -> the elevator scheduling policy (SCAN vs nearest), rate-limit algo (E4)
State -> elevator FSM (IDLE/UP/DOWN/DOORS_OPEN), capture-session state (E5)
Adapter -> wrap a vendor sensor SDK behind your ISensor interface (E6)
Why they matter. Patterns let you reuse proven structure instead of reinventing it, they make designs communicable in code review, and several directly implement SOLID (Strategy/Factory give you Open/Closed; the ops table gives you Dependency Inversion). The risk is cargo-culting — applying a pattern where a plain function would do.
Where you see it (Qualcomm). Singleton for a hardware-resource manager or logger; Factory/registration for sensor and codec drivers; Observer for V4L2 event delivery and frame-ready callbacks; Strategy for swappable 3A or scheduling algorithms; State for capture-session and stream state machines.
Answer. "Design patterns are named, reusable solutions to recurring design problems — a vocabulary for design. Creational ones control object creation (Singleton, Factory), structural ones control composition (Adapter, Decorator, Facade), behavioral ones control interaction (Observer, Strategy, State). I use them because they reuse proven structure, communicate intent in review, and implement SOLID — Strategy and Factory give Open/Closed, the driver ops table is Dependency Inversion. But I apply them only when they earn their keep, not to decorate a simple problem."
Follow-ups / gotchas. Be ready to write Singleton (E1) and Factory (E2) — those are the two they make you code. Don't confuse Strategy (swap algorithm, chosen by client) with State (behavior driven by internal state, transitions itself). Singleton is the most-abused pattern — mention it can hide global state and hurt testability.
Seen in: kernel SWE (#15), Engineer C++ (#62 Singleton + thread safety), FTE on-campus (#19 Singleton class); standard LLD expectation.
A4 · Q: Explain UML association vs aggregation vs composition.¶
Frequency: 🔥 Occasional (~2–3) — asked directly in the Associate SWE off-campus loop (#12 "UML Association vs Aggregation vs Composition").
Concept — the basis. These are three flavors of "has-a" relationship, distinguished by ownership and lifetime:
- Association — a plain "uses/knows" link, no ownership; objects have independent lifetimes. (A Driver uses a Car.) UML: a plain line.
- Aggregation — a "has-a" with shared ownership; the part can outlive the whole and be shared. (A Team has Players; players exist without the team.) UML: a hollow diamond at the owner.
- Composition — a "has-a" with exclusive ownership and coincident lifetime; destroy the whole and the parts die. (A House has Rooms; rooms don't exist without the house.) UML: a filled diamond at the owner.
Example — in code the lifetime difference is concrete:
// Association: holds a reference/pointer it does NOT own
class Pipeline { ISensor* sensor; }; // sensor created/destroyed elsewhere
// Aggregation: a container of shared parts
class Team { std::vector<std::shared_ptr<Player>> players; }; // players shared, outlive team
// Composition: owns parts by value / unique_ptr -> they die with it
class Elevator { std::vector<Door> doors; // doors live & die with car
std::unique_ptr<Motor> motor; }; // exclusive ownership
Why it matters. The distinction is an ownership/memory-lifetime decision — exactly the thing that causes dangling pointers and leaks in C/C++ (cross-ref 01_c_programming.md). Picking composition vs aggregation tells you who calls delete/free, which is half of a correct embedded design.
Where you see it (Qualcomm). A capture session composes its buffers (they die with the session); a pipeline aggregates shared sensor handles; a logger is associated (used, not owned). Smart-pointer choice (unique_ptr = composition, shared_ptr = aggregation) encodes this directly → 02_cpp_oop.md.
Answer. "All three are 'has-a', differing by ownership and lifetime. Association is a plain use-link with no ownership and independent lifetimes. Aggregation is shared ownership where the part can outlive and be shared by multiple wholes — a hollow diamond. Composition is exclusive ownership with coincident lifetime — destroy the whole and the parts go with it — a filled diamond. In C++ I encode composition with unique_ptr/by-value and aggregation with shared_ptr."
Follow-ups / gotchas. Composition implies the owner is responsible for cleanup (RAII handles it). Aggregation needs care: who frees the shared part last? (refcount / shared_ptr). Don't confuse with inheritance ("is-a") — that's a different axis.
Seen in: Associate SWE off-campus (#12); standard OOD expectation.
B. The actually-asked designs¶
B1 · Q: Write/design a timer module that handles timeouts and runs each client's callback at expiry, for many clients.¶
Frequency: 🔥🔥 Common (~3–4, and a signature embedded-design ask) — asked twice in the GfG Set-2 embedded loop (#23 "write code for the timer module which actually handles timeout functionality for all clients and execute handlers of client at timeout"; #23 again with callback/function-pointer follow-ups).
Concept — the basis. Many clients each register "call me back in T ms." You need: register(delay, callback, ctx) → handle, cancel(handle), and an internal tick that fires every expired timer's callback. The design choice is the data structure that orders pending timers:
| Structure | insert | cancel | get-next / expire | notes |
|---|---|---|---|---|
| Sorted linked list | O(n) | O(1) w/ handle | O(1) front | simple, dies at scale |
| Min-heap (by expiry) | O(log n) | O(log n) / O(n) find | O(1) peek, O(log n) pop | exact ordering, great for few timers, arbitrary delays |
| Hashed timing wheel** ** | O(1) | O(1) | O(1) amortized | best for many timers with bounded/clustered delays — Linux uses hierarchical wheels |
A timing wheel is a circular array of N buckets; a cursor advances one bucket per tick. A timer due in ticks from now goes to bucket (cursor + ticks) % N with rounds = ticks / N. Each tick: advance the cursor, walk that bucket's list, fire timers with rounds == 0, decrement the rest. Insertion is a hash (mod) + list push → O(1); the heap's strength is exact ordering and arbitrary far-future delays.
Why it exists. Polling every client "are you done?" is O(clients) every tick and burns power. A timer facility centralizes waiting so the CPU sleeps until the next expiry. The wheel exists because at high timer counts (network stacks, thousands of connections) O(log n) per operation dominates — Varghese & Lauck's wheel makes it O(1).
Where you see it (Qualcomm). Watchdog/timeout timers in drivers; per-request capture timeouts in the camera framework (a request that never returns a frame must time out and clean up); retransmit timers in the modem stack; RTOS software timers. The "execute handler at timeout" is exactly a function-pointer callback (cross-ref 01_c_programming.md).
Answer. "I expose register(delay, cb, ctx), cancel(handle), and an internal tick(). For a handful of timers with arbitrary delays I keep a min-heap keyed by absolute expiry — O(log n) insert, O(1) to peek the soonest, and the tick fires everything whose deadline has passed. For many clients I switch to a hashed timing wheel: a circular bucket array, O(1) insert by (cursor+ticks) mod N with a rounds counter, O(1) cancel via the stored node, and each tick fires the current bucket's due timers. Callbacks are function pointers plus a void* ctx cookie."
Solution / good example — min-heap timer (clean, interview-sized):
#include <stdint.h>
typedef void (*timer_cb)(void *ctx);
typedef struct { uint64_t deadline; timer_cb cb; void *ctx; int id; int alive; } Timer;
typedef struct { Timer *a; int n, cap; uint64_t now; int next_id; } TimerHeap;
static void sift_up(TimerHeap *h, int i){
while (i && h->a[(i-1)/2].deadline > h->a[i].deadline){
Timer t = h->a[i]; h->a[i] = h->a[(i-1)/2]; h->a[(i-1)/2] = t; i = (i-1)/2;
}
}
static void sift_down(TimerHeap *h, int i){
for(;;){ int l=2*i+1, r=2*i+2, m=i;
if (l<h->n && h->a[l].deadline<h->a[m].deadline) m=l;
if (r<h->n && h->a[r].deadline<h->a[m].deadline) m=r;
if (m==i) break;
Timer t=h->a[i]; h->a[i]=h->a[m]; h->a[m]=t; i=m; }
}
/* register: O(log n). Returns an id for cancellation. */
int timer_add(TimerHeap *h, uint64_t delay_ticks, timer_cb cb, void *ctx){
Timer t = { h->now + delay_ticks, cb, ctx, ++h->next_id, 1 };
h->a[h->n] = t; sift_up(h, h->n); h->n++;
return t.id;
}
/* tick: advance time, fire all due callbacks. O(k log n) for k expirations. */
void timer_tick(TimerHeap *h){
h->now++;
while (h->n && h->a[0].deadline <= h->now){
Timer due = h->a[0];
h->a[0] = h->a[--h->n]; sift_down(h, 0);
if (due.alive && due.cb) due.cb(due.ctx); // run client handler
}
}
Follow-ups / gotchas. Cancel from a heap needs a position index (mark-and-lazy-delete is simpler — set alive=0 and skip on fire). Callbacks must be short and must not block the tick thread (offload heavy work). Re-entrancy: a callback that registers another timer must not corrupt the structure mid-iteration. Concurrency: protect the structure with a lock, or run timers on a dedicated thread and hand work to clients. Don't free a timer's ctx while it could still fire (ownership → dangling, 01_c_programming.md).
Seen in: GfG Set 2 second process (#23, "Timer module code … handles timeout functionality for all clients and execute handlers … callback functions, function pointers").
B2 · Q: If you were to design Google Maps, how would you handle road blocks that add extra travel time? (rerouting)¶
Frequency: 🔥🔥 Common (~2–3, signature open-ended ask) — asked in the kernel SWE loop (#15 "How does Google Maps work / manage road blocks? If you were to design Google Maps, how would you identify and handle road blocks causing extra time?").
Concept — the basis. Model the map as a weighted directed graph: intersections are nodes, road segments are edges, and each edge's weight is the current travel time (a function of distance, speed limit, and live traffic). Shortest path = Dijkstra (O((V+E) log V) with a binary heap) or, for a single source→destination with a geographic heuristic, A* (Dijkstra + an admissible heuristic — straight-line/Euclidean time — that never overestimates, so the result stays optimal but explores far fewer nodes).
A road block is a dynamic edge-weight update: set the blocked edge's weight to ∞ (closed) or a higher value (congested/extra time), then re-route by re-running the search from the current position. The key is the weights are not static — they change with incidents, time of day, and traffic.
Example — the model and the update:
Graph G = (V intersections, E road segments)
weight(u->v) = base_time(u,v) * congestion_factor(u,v, now)
road block on edge (x->y): weight(x->y) = INF // closed
or weight(x->y) += delay // slow
reroute: path = A*(current_node, dest, weight) // recompute with updated weights
Why it exists / why A* over plain Dijkstra. Dijkstra explores uniformly in all directions; on a continent-sized graph that's far too much work for one trip. A*'s heuristic biases the search toward the goal, cutting explored nodes massively while staying optimal (because the heuristic is a lower bound). For all-pairs or precomputed routing, production systems add contraction hierarchies / precomputed shortcuts; for live traffic they keep edge weights in a time-dependent table and recompute affected routes.
Where you see it (Qualcomm). Less literal — but the pattern (graph + dynamic weights + incremental recompute) maps to routing data through an SoC fabric, scheduling DMA paths, or pathfinding in an AR/XR scene. The interviewer is testing graph modeling + algorithm selection + handling change.
Answer. "I model the map as a weighted directed graph: intersections are nodes, road segments are edges, edge weight is live travel time. Shortest route is A* — Dijkstra plus an admissible straight-line-time heuristic so it stays optimal but explores far fewer nodes. A road block is just a dynamic edge-weight update: I set the blocked edge to infinity (closed) or add the extra delay (congested), then reroute by re-running A* from the user's current position. Weights are time-dependent and refreshed from live traffic, so I only recompute routes whose edges changed. At scale I'd precompute shortcuts (contraction hierarchies) and partition the graph."
Solution / good example — the rerouting core:
import heapq
def a_star(graph, start, goal, weight, h): # h = admissible heuristic
dist = {start: 0}
pq = [(h(start, goal), start)] # f = g + h
prev = {}
while pq:
_, u = heapq.heappop(pq)
if u == goal:
return reconstruct(prev, goal), dist[u]
for v in graph[u]:
g = dist[u] + weight(u, v) # weight() reads LIVE edge cost
if v not in dist or g < dist[v]:
dist[v] = g; prev[v] = u
heapq.heappush(pq, (g + h(v, goal), v))
return None, float('inf')
def report_roadblock(weight_table, x, y, extra=float('inf')):
weight_table[(x, y)] += extra # ∞ = closed, finite = congestion delay
# then: re-run a_star(current_position, dest) for affected active routes
Follow-ups / gotchas. Heuristic must be admissible (never overestimate) or A* can return a sub-optimal path — straight-line time at max speed is the standard. Negative weights break Dijkstra/A* (use Bellman–Ford); road blocks only increase weights, so you're safe. Don't recompute every route on every update — only those touching the changed edge. For live, two-way ETA you also run from destination backward (bidirectional search). Full Dijkstra/A* internals → 03_dsa.md.
Seen in: kernel SWE Hyderabad (#15).
B3 · Q: Design a lift / elevator management system.¶
Frequency: 🔥🔥 Common (~2–3, classic LLD) — asked open-endedly in the Associate SWE off-campus loop (#12 "Design a Lift Management System (open-ended, with candidate discretion on defining actors, displays/console, operations, and switches)").
Concept — the basis. Two pieces: a per-car finite state machine (FSM) and a scheduling policy that assigns requests to cars.
FSM (per car): states IDLE, MOVING_UP, MOVING_DOWN, DOORS_OPEN. Transitions are driven by events (request added, floor reached, doors timeout). Modeling it as an explicit State machine (not nested ifs) keeps it correct and extensible.
Scheduling — the SCAN ("elevator algorithm"): keep moving in the current direction, serving every request in that direction in order, until none remain ahead, then reverse. (Strictly, reversing as soon as nothing remains ahead is the LOOK variant; pure SCAN continues to the physical top/bottom floor before reversing — most elevators use LOOK.) It's the same family as SCAN/LOOK disk scheduling — no starvation, low variance in wait time. Each car keeps two heaps: a min-heap of up-stops and a max-heap of down-stops, so "next stop in current direction" is O(1) peek. Two request kinds: hall calls (a floor button, with a direction) and cabin calls (an in-car floor button).
Example — the dispatch decision:
hall call at floor F going UP:
pick the car that is (a) moving UP and below F (it'll pass F anyway), else
(b) IDLE and nearest, else (c) the one that will free up soonest.
-> Strategy pattern: swap "nearest car" vs "SCAN-compatible car" policies.
Why it exists. Naive "serve in FIFO arrival order" makes a car bounce top-to-bottom wastefully and can starve nobody-but-also-please-nobody. SCAN minimizes total travel and guarantees every request is eventually served (bounded wait), which is why both elevators and disk arms use it.
Where you see it (Qualcomm). Pure LLD/OOD signal — but the FSM + policy split is exactly how a capture-session state machine or a scheduler for hardware resources is built. SCAN/LOOK is in the kernel I/O scheduler (cross-ref 04_os.md / 07_embedded_linux_kernel.md).
Answer. "I split it into a per-car state machine — IDLE, MOVING_UP, MOVING_DOWN, DOORS_OPEN, driven by events — and a scheduler that assigns requests to cars using the SCAN / elevator algorithm: keep going one direction serving all requests that way, then reverse, which avoids starvation and minimizes travel. Each car holds a min-heap of up-stops and a max-heap of down-stops so the next stop is O(1). I distinguish hall calls (floor + direction) from cabin calls, and make the scheduling policy a Strategy so I can swap nearest-car for SCAN. Entities: ElevatorSystem, Elevator, Scheduler (interface), Request, Door."
Solution / good example — the core classes (C++):
enum class State { IDLE, UP, DOWN, DOORS_OPEN };
enum class Dir { UP, DOWN, NONE };
struct Request { int floor; Dir dir; }; // hall call has dir; cabin call dir=NONE
class Elevator {
int id, cur = 0;
State state = State::IDLE;
std::priority_queue<int, std::vector<int>, std::greater<int>> up; // min-heap
std::priority_queue<int> down; // max-heap
public:
void addStop(int f){ (f >= cur ? up.push(f) : down.push(f)); }
void step(){ // called each tick: the FSM
switch (state){
case State::IDLE:
if (!up.empty()) state = State::UP;
else if (!down.empty()) state = State::DOWN;
break;
case State::UP:
if (up.empty()) { state = down.empty() ? State::IDLE : State::DOWN; break; }
cur++; if (cur == up.top()){ up.pop(); state = State::DOORS_OPEN; }
break;
case State::DOWN:
if (down.empty()){ state = up.empty() ? State::IDLE : State::UP; break; }
cur--; if (cur == down.top()){ down.pop(); state = State::DOORS_OPEN; }
break;
case State::DOORS_OPEN:
/* open, wait, close */ state = up.size() ? State::UP
: down.size() ? State::DOWN : State::IDLE;
break;
}
}
int distanceTo(int f) const { return std::abs(cur - f); }
friend class Scheduler;
};
struct Scheduler { // Strategy: swap the policy
virtual Elevator* pick(std::vector<Elevator>& cars, const Request& r) = 0;
virtual ~Scheduler() = default;
};
struct NearestCar : Scheduler { // simplest policy
Elevator* pick(std::vector<Elevator>& cars, const Request& r) override {
Elevator* best = nullptr; int bd = INT_MAX;
for (auto& c : cars){ int d = c.distanceTo(r.floor); if (d < bd){ bd=d; best=&c; } }
return best;
}
};
Follow-ups / gotchas. Edge cases: request for the current floor (open doors immediately), multiple cars, overload/weight limit, emergency/fire-service override (preempts the FSM), doors blocked. Concurrency: button presses arrive from many threads → guard the request queues. Fairness vs throughput is the SCAN trade-off. State pattern beats a tangle of booleans (isMoving && goingUp && !doorsOpen). Don't forget cabin vs hall call direction.
Seen in: Associate SWE off-campus (#12).
B4 · Q: Design a lottery machine — draw non-repeating random ticket holders, eliminate them in a circle, continue from the last position, log everything, until one winner remains. Keep it modular and readable.¶
Frequency: 🔥🔥 Common (~2–3, asked in detail) — the Associate SWE off-campus loop spells it out (#12 "Design a Lottery Machine: generate non-repeating random numbers from 1 to N, eliminate the corresponding lottery ticket holders, continue generation from the last eliminated person's position (circular queue treatment), continue until one winner remains, log all operations, and ensure modular, readable code").
Concept — the basis. Two requirements drive the design: (1) non-repeating random selection (each ticket drawn at most once), and (2) circular elimination continuing from the last position until one survivor. This is a blend of Fisher–Yates (for unbiased non-repeating draws) and the Josephus-style circular queue (for elimination order).
- Non-repeating draw: keep an array of remaining holders; to draw, pick
r = rand(0, n-1), takepool[r], swap it withpool[n-1], and decrementn. This is one Fisher–Yates step — O(1) per draw, never repeats, uniform. - Circular continuation: model holders in a circular doubly linked list (or a list with a moving index); after eliminating someone, resume scanning from the next node, wrapping around — O(1) removal with a node handle.
- Logging: every operation (draw, eliminate, winner) is recorded via a Observer/logger so the run is auditable — this also keeps logging decoupled from the draw logic (Single Responsibility).
Why it matters. The interviewer is testing clean class decomposition more than the random math: can you separate the random source, the holder collection, the elimination policy, and the logger into single-responsibility classes? "Modular, readable" is in the prompt verbatim — they're grading SOLID, not cleverness.
Where you see it. Pure LLD signal (clean OOD, RNG correctness, circular structures). The circular-buffer mechanic recurs everywhere at Qualcomm (frame queues, ring buffers).
Answer. "I separate four responsibilities: a RandomSource (injectable, so it's testable and seedable), a TicketPool holding the remaining holders, an EliminationStrategy, and a Logger. The pool is a circular doubly linked list so elimination is O(1) and I can resume from the next node. Each draw is one Fisher–Yates step — pick a random index, swap to the end, shrink — which is O(1), uniform, and never repeats. I eliminate the drawn holder, log it through an Observer, advance to the next position, and repeat until one remains, who I log as the winner. The classes are small and single-responsibility so it reads cleanly."
Solution / good example — the modular design (C++):
struct IRandom { virtual int next(int lo, int hi) = 0; virtual ~IRandom() = default; };
struct ILogger { virtual void log(const std::string&) = 0; virtual ~ILogger() = default; };
class LotteryMachine {
std::vector<int> pool; // remaining ticket ids
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); // tickets 1..N
}
int run() { // returns the winner
int draw = 0;
while (pool.size() > 1) {
int n = pool.size();
int r = rng.next(0, n - 1); // non-repeating: Fisher-Yates step
int eliminated = pool[r];
std::swap(pool[r], pool[n - 1]); // move drawn to the end
pool.pop_back(); // O(1) removal
log.log("draw #" + std::to_string(++draw) +
" -> ticket " + std::to_string(eliminated) + " ELIMINATED");
}
log.log("WINNER -> ticket " + std::to_string(pool.front()));
return pool.front();
}
};
// Concurrency-free, deterministic with a seeded IRandom -> unit-testable.
vector for a std::list circular iterator and step a fixed/random count each round, erasing at the cursor.
Follow-ups / gotchas. Bias trap: never rand() % n naively if you care about uniformity at large n (modulo bias) — use a proper bounded RNG (std::uniform_int_distribution). Testability: inject IRandom so tests are deterministic (seedable) — a hidden rand() is unmockable. Edge cases: N == 1 (immediate winner), N == 0 (error). Don't reseed inside the loop. Logging is a separate responsibility — don't cout inline.
Seen in: Associate SWE off-campus (#12).
B5 · Q: Design a text editor with undo/redo.¶
Frequency: 🔥 Occasional (~2) — Display Senior Engineer loop (#6 "Design a Text Editor with Undo/Redo (System Design)").
Concept — the basis. Undo/redo is the textbook Command pattern + two stacks. Every mutating action (insert, delete, replace) becomes a Command object that knows how to execute() and undo() itself. Maintain an undo stack and a redo stack:
- do/execute(cmd): cmd.execute(), push to undo stack, clear redo stack (a new action invalidates the redo history).
- undo(): pop the undo stack, call cmd.undo(), push it to the redo stack.
- redo(): pop the redo stack, call cmd.execute() (or redo()), push back to undo stack.
For the text storage itself, a naive std::string is O(n) per edit; a gap buffer or a rope (balanced tree of substrings) gives efficient inserts/deletes at scale — mention as the scaling answer.
Example — the command interface and the two-stack engine:
struct Command { virtual void execute() = 0; virtual void undo() = 0; virtual ~Command()=default; };
class InsertCmd : public Command {
std::string& doc; size_t pos; std::string text;
public:
InsertCmd(std::string& d, size_t p, std::string t): doc(d), pos(p), text(std::move(t)){}
void execute() override { doc.insert(pos, text); }
void undo() override { doc.erase(pos, text.size()); } // inverse op
};
class Editor {
std::string doc;
std::stack<std::unique_ptr<Command>> undoS, redoS;
public:
void run(std::unique_ptr<Command> c){ c->execute(); undoS.push(std::move(c));
while(!redoS.empty()) redoS.pop(); } // new action wipes redo
void undo(){ if(undoS.empty()) return; auto c=std::move(undoS.top()); undoS.pop();
c->undo(); redoS.push(std::move(c)); }
void redo(){ if(redoS.empty()) return; auto c=std::move(redoS.top()); redoS.pop();
c->execute(); undoS.push(std::move(c)); }
const std::string& text() const { return doc; }
};
Why it matters. It's a compact test of the Command pattern, stack discipline, and the invariant that a fresh edit clears redo. Storing inverse operations (not whole-document snapshots) is the memory-smart choice.
Where you see it (Qualcomm). Editor/IDE-style tooling and config UIs; more broadly, the Command pattern is how you build a replayable/reversible action log — useful for transactional config changes in a driver or a tuning tool.
Answer. "Each edit is a Command object with execute() and undo() that stores just the inverse operation, not a full snapshot. I keep an undo stack and a redo stack: doing an action executes it, pushes to undo, and clears redo; undo pops from undo, calls undo(), pushes to redo; redo does the reverse. For the buffer I'd start with a string and move to a gap buffer or rope for large documents so edits aren't O(n)."
Follow-ups / gotchas. A new edit must clear the redo stack (common bug). Group keystrokes into one undo unit (coalescing) for good UX. Bound the stacks (memory). For collaborative editing you'd need operational transforms / CRDTs — out of LLD scope. Don't snapshot the whole document per edit (memory blowup).
Seen in: Display Senior Engineer (#6).
C. Camera / display / SoC designs¶
C1 · Q: Design a camera-driver architecture that supports multiple sensors.¶
Frequency: 🔥🔥 Common (~2–3, signature camera-design ask) — CleverPrep camera guide lists it (#1 "Design a camera driver architecture supporting multiple sensors"), and it's implied by every "sensor->ISP->driver->HAL->framework" prompt.
Concept — the basis. The goal: one generic framework that drives any sensor, with each concrete sensor isolated behind a uniform interface so adding a sensor needs no change to the core (Open/Closed + Dependency Inversion). The mechanism is an ops table — a struct of function pointers — that each sensor driver fills in and registers; the framework calls through the table without knowing the concrete device. This is exactly the Linux v4l2_subdev_ops / Android Camera HAL3 model, and it's the Strategy/Adapter pattern realized in C.
Example — the HAL contract and a registered driver:
struct sensor_dev; // opaque per-instance state (the "object")
struct sensor_ops { // the vtable / HAL contract
int (*probe)(struct sensor_dev *d); // detect chip (read ID register)
int (*power_on)(struct sensor_dev *d);
int (*set_mode)(struct sensor_dev *d, const struct mode *m); // res/fps/format
int (*start_stream)(struct sensor_dev *d);
int (*stop_stream)(struct sensor_dev *d);
int (*get_frame)(struct sensor_dev *d, struct buffer *b);
};
struct sensor_dev { const struct sensor_ops *ops; void *priv; int i2c_addr; };
/* a concrete sensor fills the table and registers itself */
static int imx586_probe(struct sensor_dev *d){ /* read chip-id regs 0x0016/0x0017 over I2C, expect 0x0586 */ return 0; }
static const struct sensor_ops imx586_ops = { imx586_probe, /* ... */ };
/* framework code — knows ONLY the abstract ops */
int camera_open(struct sensor_dev *d){ return d->ops->probe(d); } // late binding
Why it exists. Phones ship many sensor SKUs (wide, ultra-wide, tele, front). Hard-coding a switch (sensor_id) everywhere violates Open/Closed — every new sensor edits and re-tests the core. The ops-table indirection inverts the dependency: the core defines the interface, drivers implement it and plug in. Adding a sensor = adding one file that registers its ops. This is the single most important embedded design idea.
Where you see it (Qualcomm). Spectra ISP / CamX sensor drivers, the V4L2 subdev model, codec plugin registries, audio device drivers — all ops-table registration. The "void *priv cookie" carries per-instance state (cross-ref 01_c_programming.md void*, function pointers).
Answer. "I define an abstract sensor_ops interface — a struct of function pointers: probe, power_on, set_mode, start_stream, stop_stream, get_frame — plus an opaque per-instance sensor_dev carrying a void *priv. Each concrete sensor implements these and registers its ops table with the framework; the framework calls through dev->ops->... and never knows the concrete chip. Adding a sensor is a new driver file that registers — zero core changes. That's Dependency Inversion and Open/Closed, and it's exactly how Linux V4L2 subdevs and Android Camera HAL3 work. A factory picks the right driver by probing the chip ID over I2C."
Solution / good example — the registration + factory:
#define MAX_SENSORS 8
static const struct sensor_ops *registry[MAX_SENSORS];
static int n_reg;
void sensor_register(const struct sensor_ops *ops){ registry[n_reg++] = ops; } // each driver calls this
/* Factory: probe each registered driver, bind the one that recognizes the chip */
struct sensor_dev *sensor_create(int i2c_addr){
struct sensor_dev *d = calloc(1, sizeof *d);
d->i2c_addr = i2c_addr;
for (int i = 0; i < n_reg; i++){
d->ops = registry[i];
if (d->ops->probe(d) == 0) return d; // this driver claims the device
}
free(d); return NULL; // no driver matched
}
Follow-ups / gotchas. Per-instance state goes in priv, never in globals (two cameras at once). Error/teardown ordering matters (power_on must be undone on failure — goto cleanup, cross-ref 01_c_programming.md). set_mode validates resolution/fps against a capability table. Versioning the ops struct lets new fields be added compatibly. Don't make the framework #include sensor headers — that re-couples it.
Seen in: CleverPrep camera guide (#1); GfG Graphics SWE hardware/software model adjacency (#3).
C2 · Q: Design a low-latency camera preview pipeline for real-time display.¶
Frequency: 🔥🔥 Common (~2–3) — CleverPrep camera guide (#1 "Design a low-latency camera preview pipeline for real-time display"); overlaps the display producer–consumer reports (#2, #6).
Concept — the basis. Preview is a producer–consumer chain: the sensor/ISP produces frames into buffers, the display consumes them, decoupled by buffer pools and queues so neither stalls the other. The whole point is low latency with no copies and no tearing:
- Buffer pool: pre-allocate a fixed set of DMA-able frame buffers at init (no malloc in the hot path — determinism). Buffers cycle: free → filled by ISP → queued → displayed → returned to free.
- Queues: a lock-protected (or lock-free SPSC) filled queue and free queue. Producer pops a free buffer, fills it, pushes to filled; consumer pops filled, displays, pushes back to free.
- Pass by reference: move buffer handles/pointers, never copy pixels (a 12 MP frame is ~18 MB — copying kills latency and power).
- Frame dropping: if the consumer is slow, drop the oldest preview frame rather than queue up latency (preview prefers fresh over complete).
Example — the buffer lifecycle:
[free pool] --pop--> producer (ISP) fills --push--> [filled queue]
[filled queue] --pop--> consumer (display) shows --push--> [free pool]
slow consumer? drop oldest in filled queue -> bounded latency, no copies
Why it matters. Naive "ISP writes, display reads the same buffer" tears (C3) and races. Allocating per frame is non-deterministic and fragments. The pool+queue structure gives constant-latency, zero-copy, back-pressure-aware flow — the core of every camera preview and video path.
Where you see it (Qualcomm). Exactly the CamX/Spectra preview path: sensor → ISP → buffer manager → display/GPU. ION/DMA-BUF buffers, V4L2 VIDIOC_QBUF/DQBUF (queue/dequeue), surface flinger consumers. This is real Qualcomm camera plumbing (cross-ref 05_camera_isp_multimedia.md).
Answer. "I model it as producer–consumer with a fixed pre-allocated buffer pool and two queues. At init I allocate N DMA-able buffers (no allocation in the hot path). The ISP pops a free buffer, fills it, and pushes it to the filled queue; the display pops from filled, shows it, and returns it to the free pool. I move buffer handles, never copy pixels — zero-copy is critical for an 18 MB frame. If the consumer falls behind I drop the oldest preview frame to keep latency bounded — preview wants freshness over completeness. Synchronization is a lock per queue, or a lock-free single-producer/single-consumer ring for the lowest latency. Triple-buffering avoids tearing."
Solution / good example — SPSC ring of buffer indices (lock-free, the hot path):
/* single-producer (ISP) / single-consumer (display) ring of buffer indices */
typedef struct { int buf[N]; _Atomic unsigned head, tail; } Ring; // power-of-two N
int ring_push(Ring *r, int idx){ // producer side
unsigned h = atomic_load_explicit(&r->head, memory_order_relaxed);
if (h - atomic_load_explicit(&r->tail, memory_order_acquire) == N) return -1; // full
r->buf[h & (N-1)] = idx;
atomic_store_explicit(&r->head, h + 1, memory_order_release); // publish
return 0;
}
int ring_pop(Ring *r, int *idx){ // consumer side
unsigned t = atomic_load_explicit(&r->tail, memory_order_relaxed);
if (t == atomic_load_explicit(&r->head, memory_order_acquire)) return -1; // empty
*idx = r->buf[t & (N-1)];
atomic_store_explicit(&r->tail, t + 1, memory_order_release);
return 0;
}
Follow-ups / gotchas. Buffers shared with DMA must be volatile-treated and cache-coherent (flush/invalidate, or use coherent allocations) — a stale cache line shows a half-old frame. Never free a buffer the ISP is still DMA-ing into (dangling, 01_c_programming.md). Min buffers: 3 (one filling, one displaying, one ready) for smooth triple-buffering. Lock-free is only safe for single producer/consumer; multi needs CAS or a lock. Frame sync via fences/poll. Threads/mutex theory → 04_os.md.
Seen in: CleverPrep camera guide (#1); Display screen-tearing (#2, #6).
C3 · Q: A CRT panel and an SoC share one frame buffer (SoC produces, panel consumes) at 120 FPS, 1 ms turnaround; line-by-line display causes tearing. Design an algorithm to fix the tearing.¶
Frequency: 🔥🔥 Common (~3) — the Display loop asks it as a 1-hour LLD round (#2 "screen-tearing low-level design … design an algorithm to fix tearing, presented 3 solutions, discussion of synchronization like reader-writer problem"; #6 lists it; CodingKaro #6).
Concept — the basis. Tearing happens when the consumer (panel) reads a frame buffer while the producer (SoC) is still writing it — the panel shows the top of frame N+1 and the bottom of frame N in one refresh. It's a producer–consumer / reader–writer race on shared memory. Three standard fixes (the report says the candidate "presented 3 solutions"):
- Double buffering + page flip: two buffers, front (panel reads) and back (SoC writes). On completion, swap the pointers atomically. The panel always reads a complete frame; the SoC always writes the idle one.
- VSync synchronization: the SoC only swaps/writes during the vertical blanking interval (between the panel finishing one refresh and starting the next), so the swap never lands mid-scan. Double buffer + VSync is the classic combo.
- Triple buffering: three buffers so the SoC can start the next frame without waiting for the panel to release the front buffer — removes the producer stall double-buffering can cause, at the cost of one extra buffer and up to one extra frame of latency.
Example — double buffer + VSync swap:
front = bufA (panel scanning) back = bufB (SoC drawing)
SoC finishes bufB ----+
| wait for VSync (panel between refreshes)
v
swap(front, back) -> panel now scans bufB (complete), SoC draws into bufA
Why it matters. This is the canonical hardware producer–consumer sync problem, and Qualcomm's display team asks it precisely because it tests whether you can connect an OS concept (reader–writer / mutual exclusion) to real silicon timing (VSync, scan-out, TAT). The "1 ms TAT, 120 FPS" framing is asking whether your solution fits the timing budget.
Where you see it (Qualcomm). Display Processing Unit (DPU/MDP), surface composition, VSync-driven page flips, DRM/KMS atomic commits. The same producer–consumer/buffer-swap logic underlies the camera preview path (C2).
Answer. "Tearing is a producer–consumer race: the panel reads the buffer while the SoC is still writing it. Fix it by never letting the consumer read a buffer that's being written. Simplest: double buffering — SoC writes the back buffer, panel scans the front, and you atomically swap them only during VSync (the vertical blanking gap), so the swap never happens mid-scan. If the SoC shouldn't stall waiting for the panel to release a buffer, go to triple buffering — a third buffer lets it start the next frame immediately, costing one extra buffer and up to a frame of latency. Underneath it's the reader–writer problem: the swap is the critical section, protected so reader and writer never touch the same buffer."
Solution / good example — page-flip on VSync:
volatile fb_t *front, *back; // two frame buffers
sem_t vsync; // posted by the panel's VSync interrupt
void soc_render_loop(void){
for(;;){
draw_frame(back); // SoC produces into the idle (back) buffer
sem_wait(&vsync); // block until the panel is in vertical blanking
fb_t *tmp = front; front = back; back = tmp; // atomic pointer swap (critical section)
panel_set_scanout(front); // program DPU to scan the new front buffer
}
}
/* VSync ISR: void vsync_isr(void){ sem_post(&vsync); } // wakes the renderer in the safe window */
Follow-ups / gotchas. The pointer swap must be atomic w.r.t. the scan-out hardware (program it during blanking, or use hardware double-buffered registers that latch on VSync). Double buffering can stall the producer if the consumer holds the front buffer too long → triple buffering. Latency vs tearing is the trade-off (more buffers = smoother but laggier). Reader–writer/semaphore theory → 04_os.md. At 120 FPS the blanking window is tiny — the swap must be cheap (pointer, not copy).
Seen in: Display Senior Engineer (#2), CodingKaro Display (#6).
C4 · Q: How would you design a hardware simulation model, and how do you compare its output against the software model?¶
Frequency: 🔥 Occasional (~2) — Graphics SWE loop (#3 "How would you design a hardware simulation model? How do you compare the output between hardware and software models?").
Concept — the basis. In silicon/ISP development you build two models of the same block: a software reference model (a "golden" model — clean, readable, bit-accurate C/C++/Python that defines correct behavior) and a hardware model (RTL or a cycle/bit-accurate simulator of the actual silicon, with fixed-point arithmetic, pipeline latency, finite precision). You verify the hardware by feeding both the same inputs and comparing outputs.
Comparison methodology: - Bit-exact compare when the spec demands it (e.g. a CRC, a lossless block): outputs must match exactly. - Tolerance / error-metric compare for DSP/image blocks where fixed-point rounding differs from the float reference: compare with a bound — max absolute difference, PSNR, SSIM, or "within ±1 LSB." Define the pass threshold up front. - Coverage: drive directed tests (corner cases: saturation, min/max, overflow) and randomized/constrained-random stimulus, tracking functional coverage so you know you exercised every mode. - Mismatch triage: on a diff, dump both outputs, find the first differing pixel/sample, and bisect to the pipeline stage.
Example — the verification harness:
+-----------------+ same stimulus +-----------------+
inputs --->| SW reference |---- golden out ----+ | HW model (RTL/ |
\--->| (float, exact) | | | sim, fixed-pt) |---- dut out
+-----------------+ v +-----------------+
compare(golden, dut, metric, tol) -> PASS / FAIL+diff
Why it exists. Hardware uses fixed-point and pipelining; the float reference is the intent. You need a model that's obviously correct (the reference) to judge the model that's fast/cheap (the hardware) — and a defined notion of "close enough" so rounding noise isn't a false failure but a real bug is caught.
Where you see it (Qualcomm). This is literally ISP / DV / "Computer Vision Systems & Modeling" work: a C model of a denoise/demosaic node vs the RTL, compared per-pixel with a PSNR/LSB tolerance; design-verification rounds (cross-ref 09_computer_arch_digital_design.md, 05_camera_isp_multimedia.md).
Answer. "I build two models of the block: a software reference (the golden model — float, obviously correct, defines the spec) and a hardware model (RTL or a bit/cycle-accurate sim with fixed-point and pipeline effects). I verify by driving both with the same stimulus — directed corner cases plus constrained-random — and comparing outputs. For lossless paths I require bit-exactness; for DSP/image paths I compare with a tolerance (max abs diff, ±1 LSB, or PSNR/SSIM) defined up front, because fixed-point rounding legitimately differs from float. On a mismatch I dump both, find the first differing sample, and bisect to the offending stage. I track functional coverage to know every mode was exercised."
Follow-ups / gotchas. Choosing the tolerance is the crux — too tight flags rounding, too loose hides bugs; derive it from the spec's precision. Beware both models sharing the same wrong assumption (compare against an independent third source if possible). Randomized stimulus needs a self-checking comparator (you can't eyeball millions of frames). Reproducibility: seed the random generator. Fixed-point vs float subtleties → 09_computer_arch_digital_design.md.
Seen in: Graphics SWE (#3); CV Systems & Modeling adjacency (Part B B4).
D. LLD warm-ups¶
D1 · Q: Implement / design your own immutable class.¶
Frequency: 🔥🔥 Common (~2–3) — asked directly in the Associate SWE off-campus loop (#12 "Implement your own immutable class").
Concept — the basis. An immutable object's state cannot change after construction — every "modification" returns a new object. The rules (verified against the standard Java recipe, and the same idea in C++):
1. No setters — expose only getters / read accessors.
2. All fields final / const, set once in the constructor.
3. Prevent subclass override — make the class final (Java) / non-virtual (C++) so a subclass can't add mutability.
4. Defensive copies — if a field is a reference to a mutable object (array, list, another mutable class), deep-copy it in the constructor and return a copy from getters, so no external alias can mutate your internals.
Example — Java (the canonical form):
public final class Point { // 3: final class, no subclassing
private final int x, y; // 2: final fields
private final int[] tags; // a mutable reference field
public Point(int x, int y, int[] tags) {
this.x = x; this.y = y;
this.tags = tags.clone(); // 4: defensive copy IN
}
public int getX() { return x; } // 1: getters only, no setters
public int getY() { return y; }
public int[] getTags() { return tags.clone(); } // 4: defensive copy OUT
public Point withX(int nx) { return new Point(nx, y, tags); } // "mutate" => new object
}
const members / a const object):
class Point {
const int x_, y_;
const std::vector<int> tags_;
public:
Point(int x, int y, std::vector<int> tags) // by value = a copy in
: x_(x), y_(y), tags_(std::move(tags)) {}
int x() const { return x_; }
int y() const { return y_; }
const std::vector<int>& tags() const { return tags_; } // const ref out
Point withX(int nx) const { return Point(nx, y_, tags_); }
};
Why it matters. Immutable objects are inherently thread-safe (no writes → no data races → no locks needed), trivially cacheable and shareable, safe to use as map keys, and free of aliasing bugs. They're the simplest possible answer to "how do you share data across threads safely."
Where you see it (Qualcomm). Configuration/tuning snapshots passed between threads without locks; immutable frame metadata; a const capture-request descriptor shared by producer and consumer. Immutability is why you can hand a config to the ISP thread without a mutex.
Answer. "Immutable = state fixed at construction. The recipe: no setters (getters only); all fields final/const, assigned once in the constructor; the class itself final/non-subclassable so no one adds mutability; and defensive copies for any mutable reference field — deep-copy it in the constructor and return a copy from the getter, so no outside alias can change your internals. Any 'modification' returns a new object. The payoff is that immutable objects are inherently thread-safe and need no locking to share."
Follow-ups / gotchas. The classic bug: storing or returning the same array/list reference (caller mutates it → your object changes) — that's why defensive copies matter. In C++, const members make the object non-assignable/non-movable; often you make the object const and rely on the type's interface instead. A final field referencing a mutable object is only "shallowly" final — the object it points to can still change unless you copy. Strings are already immutable in Java; in C use const char * to a copy you own.
Seen in: Associate SWE off-campus (#12).
D2 · Q: Design a parking lot.¶
Frequency: 🔥 Occasional (commonly expected / aggregator-reported) — the canonical LLD warm-up; the report set asks open-ended OOD (#12, #19) that this models.
Concept — the basis. The textbook OOD warm-up — it exercises the whole method. Entities: ParkingLot → Floor → Spot (sized: motorcycle/compact/large); Vehicle (hierarchy); Ticket; Gate/EntryPoint. Key operations: park(vehicle) → ticket, unpark(ticket) → fee. Data structure: per-size free-spot queues/sets so park/unpark are O(1), plus a ticket → spot map.
Example — the core API and structures:
enum class Size { MOTORCYCLE, COMPACT, LARGE };
struct Spot { int id; Size size; bool free = true; };
struct Ticket { int id; int spotId; long entryTime; };
class ParkingLot {
std::unordered_map<Size, std::queue<Spot*>> freeBySize; // O(1) find a spot
std::unordered_map<int, Spot*> ticketToSpot; // O(1) unpark
int nextTicket = 1;
public:
Ticket park(Size needed){
auto& q = freeBySize[needed];
if (q.empty()) throw std::runtime_error("lot full for size");
Spot* s = q.front(); q.pop(); s->free = false;
Ticket t{ nextTicket++, s->id, now() };
ticketToSpot[t.id] = s; return t;
}
double unpark(const Ticket& t){
Spot* s = ticketToSpot[t.id]; s->free = true;
freeBySize[s->size].push(s); ticketToSpot.erase(t.id);
return fee(now() - t.entryTime);
}
};
Why it matters. It's the cleanest demonstration of nouns→classes, verbs→APIs, and a data-structure-per-operation. Interviewers extend it (pricing strategy, multiple gates, find-nearest-spot) to probe Strategy and concurrency.
Where you see it. Pure OOD signal; the "pool of typed free resources" pattern recurs (buffer pools, spot pools, thread pools).
Answer. "Entities: ParkingLot has Floors, each with Spots sized motorcycle/compact/large; Vehicle, Ticket, Gate. park(vehicle) pulls a free spot of the right size from a per-size queue — O(1) — issues a ticket, and records ticket→spot; unpark(ticket) frees the spot, returns it to the queue, and computes the fee from the dwell time. Pricing is a Strategy so I can swap flat/hourly/tiered. Concurrency: two cars racing for the last spot means the spot pool is the critical section — lock it or claim atomically."
Follow-ups / gotchas. Edge cases: lot full, lost ticket, vehicle larger than any free spot (allow a bigger spot?), payment failure. Concurrency on the free pool is the real test. "Find nearest spot" turns the queue into a per-floor sorted structure. Make pricing a Strategy, not an if-chain.
Seen in: standard LLD warm-up expectation; OOD rounds (#12, #19).
D3 · Q: Design a rate limiter.¶
Frequency: 🔥 Occasional (commonly expected / aggregator-reported) — classic system-design warm-up; adjacent to throughput/back-pressure designs (#8 bit-rate control, #2 producer-consumer).
Concept — the basis. A rate limiter caps how many actions are allowed per time window. The two canonical algorithms (verified):
- Token bucket: a bucket holds up to capacity tokens, refilled at rate tokens/sec; each request consumes one token; empty bucket → reject. Allows bursts up to capacity while bounding the long-run average. Most common (APIs, clients).
- Leaky bucket: requests enter a FIFO queue that drains at a constant rate; overflow → reject. Smooths traffic to a steady output, no bursts — good for protecting a downstream that needs stable throughput.
- (Also: fixed-window counter — simple but allows 2× burst at the boundary; sliding-window log/counter — smoother, more memory.)
Example — token bucket (lazy refill, O(1), no background thread):
typedef struct { double tokens, capacity, rate; double last; } TokenBucket; // rate = tokens/sec
int allow(TokenBucket *b, double now){
b->tokens += (now - b->last) * b->rate; // lazily refill since last call
if (b->tokens > b->capacity) b->tokens = b->capacity;
b->last = now;
if (b->tokens >= 1.0){ b->tokens -= 1.0; return 1; } // consume a token -> allow
return 0; // empty -> reject
}
Why it matters. It's the standard test of "control a rate with O(1) state and no per-request timer." The token-vs-leaky choice (burst-tolerant vs strictly-smooth) is the design trade-off they want to hear. Lazy refill (compute tokens from elapsed time on access) avoids a background thread — the elegant answer.
Where you see it (Qualcomm). Throttling a producer in a pipeline, capping interrupt/event rates, video bit-rate control (#8 is literally rate control), pacing modem transmissions, protecting a slow consumer (back-pressure, ties to C2/C3).
Answer. "Two main algorithms. Token bucket: tokens refill at a fixed rate up to a capacity, each request spends one, empty means reject — it allows short bursts up to the capacity while bounding the average. Leaky bucket: a queue drains at a constant rate, smoothing output with no bursts. I'd use token bucket for client/API limiting because bursts are normal, and leaky bucket when the downstream needs stable throughput. I implement token bucket with lazy refill — compute accrued tokens from elapsed time on each request — so there's no background timer; it's O(1) state and O(1) per request."
Follow-ups / gotchas. Lazy refill avoids a timer thread. Distributed rate limiting needs shared state (Redis) and atomic decrement. Fixed-window has a 2× boundary-burst flaw → sliding window fixes it at memory cost. Thread-safety: the bucket update is a tiny critical section (lock or atomic CAS). Don't busy-wait when rejecting — return/queue.
Seen in: standard system-design warm-up; bit-rate control (#8) adjacency.
D4 · Q: Design a bounded (thread-safe) producer–consumer queue.¶
Frequency: 🔥🔥 Common (~3) — the screen-tearing/display loop is producer–consumer (#2), camera preview is producer–consumer (C2), and "print odd/even with two threads" (#12, #16) is the same synchronization.
Concept — the basis. A fixed-capacity queue shared by producers (push) and consumers (pop) where: producers block when full, consumers block when empty, and access is mutually exclusive. The classic solution is a mutex + two condition variables (not_full, not_empty) — or counting semaphores (empty, full) plus a mutex.
Example — mutex + condition variables (C++):
template <class T> class BoundedQueue {
std::queue<T> q; size_t cap;
std::mutex m; std::condition_variable not_full, not_empty;
public:
explicit BoundedQueue(size_t c): cap(c) {}
void push(T v){
std::unique_lock<std::mutex> lk(m);
not_full.wait(lk, [&]{ return q.size() < cap; }); // block while full
q.push(std::move(v));
not_empty.notify_one(); // wake a consumer
}
T pop(){
std::unique_lock<std::mutex> lk(m);
not_empty.wait(lk, [&]{ return !q.empty(); }); // block while empty
T v = std::move(q.front()); q.pop();
not_full.notify_one(); // wake a producer
return v;
}
};
Why it matters. It's the concurrency primitive behind every pipeline at Qualcomm — preview, codec, audio, modem all decouple stages with bounded queues so a fast stage can't run a slow stage out of memory (back-pressure). The bounded-ness is the point: unbounded queues hide bugs and OOM.
Where you see it (Qualcomm). Frame queues between ISP and display (C2), the screen-tearing buffer hand-off (C3), work queues between threads, the timer-callback offload (B1). The "two threads print odd/even alternately" question is this pattern with capacity 1.
Answer. "A bounded queue protected by a mutex and two condition variables: push waits on not_full then enqueues and signals not_empty; pop waits on not_empty then dequeues and signals not_full. Producers block when it's full, consumers block when it's empty — that gives back-pressure so a fast producer can't exhaust memory. The wait predicates guard against spurious wake-ups. Equivalent with two counting semaphores (empty initialized to capacity, full to 0) plus a mutex for the queue itself. For one-producer/one-consumer at the lowest latency I'd use a lock-free SPSC ring instead."
Follow-ups / gotchas. Always use the predicate form of wait (loops on spurious wake-ups). notify_one vs notify_all (all for broadcast conditions). Semaphore version: lock the mutex inside the empty/full waits, never around them (deadlock). Lock-free rings only safe for single producer+consumer (C2). Mutex/semaphore/condition-variable theory and deadlock → 04_os.md.
Seen in: Display producer–consumer (#2), print odd/even threads (#12, #16), ML&Sys (#11 semaphore/mutex/threading).
D5 · Q: Design an LRU cache (the design view).¶
Frequency: 🔥🔥 Common (~3+) — LRU appears repeatedly (#31 "LRU Cache Implementation (Hard DSA)", #62 "twisted version of LRU Cache", #24 "What is LRU Cache?"). Full coding/DSA mechanics live in 03_dsa.md; here is the design framing.
Concept — the basis. An LRU (Least-Recently-Used) cache holds up to capacity items and evicts the least-recently-used on overflow, with O(1) get and put. The standard design = hash map + doubly linked list: the map gives O(1) lookup (key → node), the DLL maintains recency order (most-recent at the head). On access, move the node to the head; on insert past capacity, evict the tail.
Example — the two-structure design and the operations:
HashMap<key, Node*> : O(1) find
DoublyLinkedList head..tail: recency order (head = most recent, tail = LRU)
get(k): node = map[k]; move node to head; return node.val // O(1)
put(k,v): if exists -> update + move to head;
else -> new node at head, map[k]=node;
if size > cap -> evict tail (remove from map + list) // O(1)
Why it matters. It's the most-asked cache design because it forces the hash-map-plus-linked-list insight — using two structures so each operation is O(1). Qualcomm asks it both as DSA (code it) and as design ("what's a cache, what's the eviction policy, why these structures").
Where you see it (Qualcomm). Buffer/page caches, a recently-used sensor-mode cache, translation caches (TLB is hardware LRU-ish), tuning-parameter caches. Eviction policy choice (LRU vs LFU vs FIFO) is a real design decision.
Answer. "LRU caches up to a capacity and evicts the least-recently-used item, with O(1) get and put. I combine a hash map (key → list node, for O(1) lookup) with a doubly linked list ordered by recency (head = most recent, tail = least). On get, I find via the map and move the node to the head; on put, I insert/update at the head, and if I'm over capacity I evict the tail and erase it from the map. The DLL gives O(1) splice, the map gives O(1) find — together O(1) for both operations. If the policy were frequency-based I'd switch to LFU."
Follow-ups / gotchas. std::list + unordered_map<key, list::iterator> is the idiomatic C++ (splice is O(1)). The "twisted LRU" (#62) usually adds TTL, capacity-by-bytes, or thread-safety (wrap in a lock — or shard to reduce contention). Don't use a single array (O(n) eviction). LFU is harder (needs frequency buckets). Coding details → 03_dsa.md.
Seen in: Engineer C++ (#31, #62), Technical Profiles (#24); coding mechanics in 03_dsa.md.
E. The patterns these use¶
E1 · Q: Implement a Singleton class — and make it thread-safe.¶
Frequency: 🔥🔥 Common (~3) — asked with code in two loops (#19 "Create a Singleton Class (private destructor, static object creation)"; #62 "Implement a Singleton class and make it thread-safe — write the code").
Concept — the basis. Singleton guarantees a class has exactly one instance with a global access point. Mechanics: private constructor (no one else can construct), a private static instance, and a public getInstance(). The interview twist is always thread safety — two threads calling getInstance() simultaneously must not create two instances.
Example — the clean, thread-safe C++11 form (Meyers Singleton):
class Logger {
Logger() = default; // private ctor
public:
Logger(const Logger&) = delete; // no copy
Logger& operator=(const Logger&) = delete;
static Logger& instance() { // C++11: static local init is thread-safe
static Logger inst; // constructed once, lazily, race-free
return inst;
}
void log(const std::string& s){ /* ... */ }
};
// use: Logger::instance().log("hi");
static std::atomic<Logger*> ptr{nullptr};
static std::mutex mtx;
Logger* get(){
Logger* p = ptr.load(std::memory_order_acquire);
if (!p){ // 1st check (no lock, fast path)
std::lock_guard<std::mutex> lk(mtx);
p = ptr.load(std::memory_order_relaxed);
if (!p){ p = new Logger(); ptr.store(p, std::memory_order_release); } // 2nd check
}
return p;
}
Why it exists. Some resources are genuinely singular — one hardware register block, one logger, one config registry, one ID generator. A Singleton enforces "only one" in the type system instead of by convention. The thread-safe requirement exists because lazy init is a classic race.
Where you see it (Qualcomm). A hardware-resource/clock manager, a global logger, a sensor registry (C1), a one-time bring-up guard. In C it's a file-static singleton with pthread_once (cross-ref 01_c_programming.md B2's pthread_once example).
Answer. "Singleton ensures one instance with a global access point: private constructor, deleted copy, and a static instance(). In C++11 the cleanest thread-safe version is the Meyers Singleton — a function-local static, which the standard guarantees is initialized exactly once even under concurrency, so no manual locking. If I can't rely on that, I use double-checked locking with an atomic pointer and a mutex: check without the lock, lock, check again, then construct. In C the equivalent is pthread_once."
Follow-ups / gotchas. Pre-C++11 double-checked locking was broken without atomics/fences (the infamous DCLP bug) — needs acquire/release. Singletons are criticized: hidden global state, hard to unit-test, init-order fiasco across translation units (Meyers' local-static avoids the order fiasco). Prefer dependency injection where you can. Make destructor/copy controlled. vtable/vptr details → 02_cpp_oop.md.
Seen in: FTE on-campus (#19), Engineer C++ (#62).
E2 · Q: How would you use a Factory pattern? (e.g. create the right driver/object at runtime)¶
Frequency: 🔥 Occasional (commonly expected / aggregator-reported) — implied by the camera-driver factory (C1) and "design patterns and why" (#15).
Concept — the basis. A Factory decides which concrete class to instantiate at runtime and returns it behind a common interface, so the caller doesn't new concrete types or contain a creation switch. It centralizes object creation (Single Responsibility) and is the standard way to satisfy Open/Closed for creation.
Example — a sensor factory (the C1 design, OO form):
struct ISensor { virtual Frame read() = 0; virtual ~ISensor() = default; };
class IMX586 : public ISensor { Frame read() override; };
class OV64B : public ISensor { Frame read() override; };
std::unique_ptr<ISensor> makeSensor(SensorId id){ // the factory
switch (id){
case SensorId::IMX586: return std::make_unique<IMX586>();
case SensorId::OV64B: return std::make_unique<OV64B>();
default: throw std::invalid_argument("unknown sensor");
}
}
// caller: auto s = makeSensor(detected_id); s->read(); // no concrete type leaks out
id → creator function in a map at startup; the factory just looks up and calls it. That's the C1 ops-table registry in OO clothes.
Why it exists. It localizes the one place that knows concrete types, so adding a type touches only the factory (or nothing, with registration) — the rest of the code depends only on ISensor. Without it, new IMX586() litters the codebase and every new sensor is a shotgun edit.
Where you see it (Qualcomm). Sensor/codec/driver creation by probed ID (C1), creating the right ISP node from a config, building the right packet handler by message type.
Answer. "A Factory centralizes object creation: the caller asks for an interface (ISensor) by some key (a probed sensor ID), and the factory returns the right concrete instance — the caller never names or news a concrete type. The basic form is a switch in one function; the Open/Closed form is a registration map of id → creator, so each driver self-registers and adding a sensor touches no central code. That's exactly the camera-driver ops-table registry, in OO form."
Follow-ups / gotchas. Factory Method (subclass decides) vs Abstract Factory (families of related objects) vs simple factory function — know the distinction lightly. Registration beats a central switch for extensibility. Return by unique_ptr so ownership is clear (composition). Pair with C1's C ops table to show you know both the OO and the C-idiom.
Seen in: camera-driver design (C1, #1); design-patterns ask (#15).
E3 · Q: Where would you use the Observer pattern?¶
Frequency: 🔥 Occasional (commonly expected / aggregator-reported) — the lottery log (B4), frame-ready callbacks (C2), and button/event handling (B3) are all Observer; callbacks/function-pointers asked directly (#15, #23, #9).
Concept — the basis. Observer (publish/subscribe) lets a subject notify a set of observers when its state changes, without knowing their concrete types — they subscribe, the subject notifys. It decouples the event source from the (possibly many, possibly changing) listeners.
Example — frame-ready notification:
struct IFrameObserver { virtual void onFrame(const Frame&) = 0; virtual ~IFrameObserver()=default; };
class FrameSource { // the subject
std::vector<IFrameObserver*> obs;
public:
void subscribe(IFrameObserver* o){ obs.push_back(o); }
void publish(const Frame& f){ for (auto* o : obs) o->onFrame(f); } // notify all
};
// a display and an encoder both subscribe; the source doesn't know either concretely.
Why it exists. Many parts of a system care about one event (a new frame: display, encoder, statistics, autofocus). Hard-wiring the source to each consumer couples them and breaks Open/Closed. Observer inverts it: consumers register; the source just broadcasts. In C this is exactly a list of function-pointer callbacks with a void* ctx (cross-ref 01_c_programming.md).
Where you see it (Qualcomm). V4L2 event delivery, frame-ready/buffer-done callbacks, 3A-converged notifications, the lottery audit log (B4), elevator floor-button events (B3). Every "register a callback" API is Observer.
Answer. "Observer is publish/subscribe: a subject keeps a list of observers and notifies them on state change, without knowing their concrete types — they subscribe, it broadcasts. I use it for events with multiple, changing listeners: a frame source notifying a display, an encoder, and statistics; a button notifying the elevator; the lottery machine notifying its logger. In C it's a list of function-pointer callbacks each with a void* ctx cookie — the kernel and HALs do exactly this."
Follow-ups / gotchas. Lifetime/dangling: an observer must unsubscribe before it's destroyed, or the subject calls a dangling pointer (use weak refs / explicit unregister). Notification order is usually unspecified — don't rely on it. Re-entrancy: an observer that modifies the subject's list mid-notify corrupts iteration (iterate a copy). Don't do heavy work in the callback — offload (ties to B1, D4).
Seen in: callbacks/function-pointers (#15, #23, #9); lottery log (#12); standard pattern expectation.
E4 · Q: Where would you use the Strategy pattern?¶
Frequency: 🔥 Occasional (commonly expected / aggregator-reported) — the elevator scheduling policy (B3), rate-limit algorithm (D3), parking pricing (D2), and swappable 3A are all Strategy.
Concept — the basis. Strategy encapsulates a family of interchangeable algorithms behind a common interface, so the client picks the algorithm at runtime and the surrounding code stays unchanged. It's the behavioral twin of dependency injection — inject which algorithm.
Example — swappable elevator scheduling:
struct SchedulePolicy { virtual Elevator* pick(std::vector<Elevator>&, const Request&) = 0;
virtual ~SchedulePolicy() = default; };
struct NearestCar : SchedulePolicy { Elevator* pick(...) override; }; // policy A
struct ScanPolicy : SchedulePolicy { Elevator* pick(...) override; }; // policy B
class ElevatorSystem {
std::unique_ptr<SchedulePolicy> policy; // swap at runtime
public:
void setPolicy(std::unique_ptr<SchedulePolicy> p){ policy = std::move(p); }
void dispatch(const Request& r){ policy->pick(cars, r)->addStop(r.floor); }
};
Why it exists. When one decision has several valid algorithms (scheduling, pricing, rate-limiting, compression), baking one in with an if/switch violates Open/Closed and makes A/B testing or per-context choice impossible. Strategy makes the algorithm a pluggable object.
Where you see it (Qualcomm). Swappable 3A algorithms, scheduling policies (B3), rate-limit algorithm (token vs leaky, D3), pricing (D2), compression/codec selection, the sensor ops table (C1 is Strategy in C — the ops are the swappable behavior).
Answer. "Strategy makes a family of algorithms interchangeable behind one interface, chosen at runtime, so the surrounding code doesn't change when you swap algorithms. I use it for the elevator's scheduling policy (nearest-car vs SCAN), the rate limiter (token vs leaky bucket), parking pricing (flat vs hourly), and swappable 3A. It's Open/Closed for behavior — add a strategy without editing the client. The camera ops table is the same idea in C: the function pointers are the pluggable strategy."
Follow-ups / gotchas. Strategy (client chooses, stateless-ish algorithm) vs State (object changes its own behavior as internal state transitions) — same structure, different intent. Inject the strategy (constructor or setter), don't new it inside. Stateless strategies can be shared singletons.
Seen in: elevator (#12), rate/throughput designs; standard pattern expectation.
E5 · Q: Where would you use the State pattern?¶
Frequency: 🔥 Occasional (commonly expected / aggregator-reported) — the elevator FSM (B3) and any capture-session/stream state machine are State; FSMs recur across embedded design.
Concept — the basis. State lets an object change its behavior when its internal state changes, by delegating to a state object — replacing a sprawl of if (state == X && ...) with one class per state that knows its own transitions. It's a finite state machine expressed as objects (or, in C, a function-pointer jump table indexed by state — cross-ref 01_c_programming.md A4).
Example — capture session as a State machine (C, jump-table form):
typedef enum { S_IDLE, S_CONFIGURED, S_STREAMING, S_ERROR, S_COUNT } State;
typedef State (*handler)(int event);
static State on_idle(int e){ return e == EV_CONFIG ? S_CONFIGURED : S_IDLE; }
static State on_cfg (int e){ return e == EV_START ? S_STREAMING : S_CONFIGURED; }
static State on_strm(int e){ return e == EV_STOP ? S_CONFIGURED : S_STREAMING; }
static State on_err (int e){ (void)e; return S_ERROR; }
static handler table[S_COUNT] = { on_idle, on_cfg, on_strm, on_err }; // one entry per state
State step(State s, int e){ return table[s](e); } // O(1) dispatch, no switch
Why it exists. Stateful protocols (a capture session, a stream, an elevator car, a connection) have legal/illegal transitions. Encoding them as a State machine makes illegal transitions impossible-by-construction and the logic readable, versus a fragile mass of boolean flags.
Where you see it (Qualcomm). Capture-session/stream state machines in the camera framework, connection/link state in the modem, an elevator car (B3), device power states (off/standby/active). The C ops/jump-table form is ubiquitous in drivers.
Answer. "State expresses a finite state machine as objects (or, in C, a function-pointer jump table indexed by the current state): each state owns its transitions, so behavior changes as the object's state changes and illegal transitions are designed out. I use it for the elevator car (IDLE/MOVING/DOORS_OPEN), and for capture-session/stream and power-state machines. It replaces a brittle tangle of boolean flags with one handler per state and O(1) dispatch."
Follow-ups / gotchas. State (object transitions itself) vs Strategy (client sets it) — same shape, different driver. The jump-table form is the C idiom and is O(1). Guard against an event in a state with no transition (return same state or error). Entry/exit actions (open doors on entering DOORS_OPEN) belong in the transition. Function-pointer mechanics → 01_c_programming.md.
Seen in: elevator (#12); FSM-style embedded design; standard pattern expectation.
E6 · Q: Where would you use the Adapter pattern?¶
Frequency: 🔥 Occasional (commonly expected / aggregator-reported) — wrapping a vendor sensor SDK behind your ISensor (C1), and any "make a third-party interface fit ours."
Concept — the basis. Adapter wraps an object with an incompatible interface so it fits the interface your code expects — a translator between a class you have and a class you need. It lets you reuse existing/third-party code without changing it (you can't, or shouldn't).
Example — adapting a vendor SDK to your ISensor:
struct ISensor { virtual Frame read() = 0; virtual ~ISensor() = default; };
class VendorBlob { // third-party SDK you cannot change
public: int grab(uint8_t* out, int* len); // wrong shape for our pipeline
};
class VendorSensorAdapter : public ISensor { // the adapter
VendorBlob v;
public:
Frame read() override { // translate their API into ours
uint8_t buf[MAX]; int len = MAX;
v.grab(buf, &len);
return Frame(buf, len);
}
};
// our pipeline keeps using ISensor; the vendor SDK is hidden behind the adapter.
Why it exists. You constantly integrate code whose interface you don't control — a vendor sensor SDK, a legacy driver, an OS API. Adapter isolates that mismatch in one class, so the rest of your code depends only on your clean interface (and you can swap the vendor later).
Where you see it (Qualcomm). Wrapping a sensor-vendor SDK behind the HAL interface, fitting a legacy codec into a new media framework, bridging two driver models, making a C library look like your C++ interface.
Answer. "Adapter wraps a class with the wrong interface so it satisfies the interface your code expects — a translator. I use it to bring a vendor sensor SDK or a legacy driver behind my ISensor HAL interface: the adapter implements read() by calling the vendor's differently-shaped API and reshaping the result. The pipeline only ever sees my clean interface, so the third-party mismatch is isolated in one class and the vendor is swappable."
Follow-ups / gotchas. Object adapter (wrap an instance, composition — preferred) vs class adapter (multiple inheritance — C++ only, rigid). Adapter changes interface; Decorator adds behavior with the same interface; Facade simplifies a subsystem — don't confuse them. Keep the adapter thin (translation only, no business logic).
Seen in: sensor-SDK integration (C1, #1); standard pattern expectation.
§ Encyclopedia — searchable glossary¶
Every bold-italic term used above is defined here, alphabetically, with why it exists / where you see it and a micro-example. Use your editor's find (⌘F / Ctrl-F) to jump to a term.
A* (A-star) — a shortest-path search = Dijkstra + an admissible heuristic (a lower bound on remaining cost) that biases exploration toward the goal. Why: explores far fewer nodes than Dijkstra while staying optimal. Where: map routing (B2), grid/scene pathfinding. Micro: f(n) = g(n) + h(n), expand lowest f first.
Adapter — a structural pattern that wraps an incompatible interface to match the one your code expects (E6). Why: reuse third-party/legacy code unchanged. Where: vendor sensor SDK behind your ISensor. Micro: VendorSensorAdapter::read(){ vendor.grab(...); return Frame(...); }.
Admissible heuristic — an estimate that never overestimates the true remaining cost. Why: keeps A* optimal. Where: straight-line travel time in map routing (B2). Micro: Euclidean distance ÷ max speed.
Aggregation — a "has-a" with shared ownership; the part can outlive and be shared by the whole (A4). Why: model shared parts. Where: a pipeline holding a shared_ptr<Sensor>. UML: hollow diamond.
Association — a plain "uses/knows" link, no ownership, independent lifetimes (A4). Why: model collaboration without ownership. Where: an object holding a non-owning pointer/reference to a logger. UML: plain line.
Back-pressure — when a full bounded queue blocks/slows the producer so a fast stage can't outrun a slow one (D4). Why: bounds memory and latency. Where: preview pipeline, codec/audio stage queues, rate limiting.
Bounded queue — a fixed-capacity producer–consumer queue; producers block when full, consumers when empty (D4). Why: decouple stages with back-pressure. Where: every pipeline. Micro: mutex + not_full/not_empty condition variables.
Buffer pool — a set of pre-allocated, reused buffers cycled between free and filled states (C2). Why: zero per-frame allocation → deterministic, no fragmentation. Where: camera/video frame buffers (ION/DMA-BUF).
Command — a behavioral pattern wrapping an action as an object with execute()/undo() (B5). Why: enables undo/redo, queuing, replay. Where: text editor (B5), reversible config changes. Micro: InsertCmd::undo(){ doc.erase(pos, len); }.
Composition — a "has-a" with exclusive ownership and coincident lifetime; destroy the whole and the parts die (A4). Why: model owned parts; cleanup is automatic (RAII). Where: a session owning its buffers (unique_ptr/by value). UML: filled diamond.
Condition variable — a sync primitive a thread waits on until another signals a predicate became true (D4). Why: block efficiently instead of busy-waiting. Gotcha: always use the predicate-loop form (spurious wake-ups). Theory → 04_os.md.
Defensive copy — copying a mutable reference field on the way in (constructor) and out (getter) so no external alias can mutate an immutable object's internals (D1). Why: true immutability. Micro: this.tags = tags.clone(); and return tags.clone();.
Dependency Inversion (DIP) — the "D" in SOLID: high-level policy depends on abstractions, not concrete low-level modules; inject the concretion (A2). Where: the camera ops table — the core depends on sensor_ops, drivers implement it (C1).
Dijkstra's algorithm — single-source shortest paths on non-negative weights, O((V+E) log V) with a binary heap (B2). Why: optimal routing baseline. Where: map routing before adding the A* heuristic. Internals → 03_dsa.md.
Double buffering — two buffers, one being written, one being read/displayed, swapped on completion (C3). Why: the consumer always sees a complete frame → no tearing. Where: display page-flip, preview. Micro: swap(front, back) during VSync.
Factory — a creational pattern that picks the concrete class at runtime and returns it behind an interface (E2, C1). Why: centralize creation, satisfy Open/Closed. Where: create the right sensor driver from a probed ID. Micro: makeSensor(id) -> unique_ptr<ISensor>.
Finite state machine (FSM) — a model of states + events + transitions; behavior depends on the current state (B3, E5). Why: make illegal transitions impossible, replace boolean-flag tangles. Where: elevator car, capture session, link state. See State.
Fisher–Yates — an unbiased in-place shuffle / non-repeating draw: pick a random index, swap to the end, shrink (B4). Why: uniform, O(1) per draw, never repeats. Where: the lottery non-repeating selection. Micro: swap(a[rand(0,n-1)], a[n-1]); n--;.
Frame dropping — discarding the oldest pending frame when the consumer falls behind (C2). Why: preview prefers fresh over complete → bounded latency. Where: camera preview, real-time video.
Function pointer (as design) — a stored function address enabling runtime dispatch; the C realization of Strategy/Observer/State and the ops table (C1, E3, E5). Where: driver/HAL ops, callbacks. Mechanics → 01_c_programming.md.
Golden / reference model — the obviously-correct software model that defines correct behavior, used to verify the hardware model (C4). Why: judge fixed-point hardware against float intent. Where: ISP/DV node verification.
Hall call vs cabin call — an elevator request from a floor button (has a direction) vs an in-car floor button (no direction) (B3). Why: they're scheduled differently. Where: elevator dispatch.
Immutable — an object whose state can't change after construction; "modifications" return new objects (D1). Why: inherently thread-safe, cacheable, alias-safe. Where: config/metadata shared across threads without locks. Micro: final fields + no setters + defensive copies.
Interface Segregation (ISP) — the "I" in SOLID: prefer many small, specific interfaces over one fat one (A2). Where: split a control interface from a streaming interface so a read-only sensor isn't forced to implement write().
Josephus problem — people in a circle, every k-th eliminated until one remains — the circular-elimination model (B4). Where: the lottery "continue from the last position" requirement. Micro: circular linked list + a stepping cursor.
Leaky bucket — a rate-limit algorithm: a FIFO queue drains at a constant rate; overflow rejected (D3). Why: smooths traffic, no bursts. Where: protecting a downstream needing stable throughput. Contrast token bucket.
Liskov Substitution (LSP) — the "L" in SOLID: a subtype must work anywhere its base type is expected, honoring the contract (A2). Where: every ISensor subclass returns a valid Frame. Gotcha: a subclass that throws on a base method violates it.
Lock-free (SPSC) ring — a single-producer/single-consumer circular buffer using atomic head/tail, no mutex (C2). Why: lowest-latency hand-off. Gotcha: only safe for one producer and one consumer. Micro: head/tail with acquire/release ordering.
LRU cache — caches up to a capacity, evicts the least-recently-used, O(1) get/put via hash map + doubly linked list (D5). Where: buffer/page/mode caches. Contrast LFU. Coding → 03_dsa.md.
LFU cache — evicts the least-frequently-used item; needs frequency buckets (D5). Why: favors hot items over merely-recent ones. Where: an alternative eviction policy when recency isn't the right signal.
Min-heap (timer) — a binary heap keyed by absolute expiry: O(log n) insert, O(1) peek-soonest (B1). Why: exact ordering for a moderate number of arbitrary-delay timers. Contrast timing wheel.
Observer — a behavioral pattern where a subject notifies subscribed observers on state change, without knowing their types (E3). Why: decouple an event source from many/changing listeners. Where: frame-ready callbacks, lottery log, button events. Micro: subscribe(o); ... for(o:obs) o->onFrame(f);.
Open/Closed (OCP) — the "O" in SOLID: open for extension, closed for modification (A2). Where: add a sensor by registering a driver, not by editing the core (C1). Realized by Factory/Strategy/registration.
Ops table — a struct of function pointers a driver fills and registers; the framework calls through it (C1). Why: Dependency Inversion / Open/Closed in C. Where: V4L2 v4l2_subdev_ops, Camera HAL3 camera3_device_ops. Micro: dev->ops->read(dev, buf).
Page flip — atomically switching which buffer the display scans out, done during VSync (C3). Why: tear-free buffer swap. Where: DPU/DRM-KMS display path. Micro: panel_set_scanout(front) after swap.
Producer–consumer — a pattern where producers create items and consumers process them, decoupled by a queue/buffer (C2, C3, D4). Why: parallelism + back-pressure. Where: every camera/display/codec pipeline.
Rate limiter — caps actions per time window via token bucket (burst-tolerant) or leaky bucket (smooth) (D3). Where: API throttling, bit-rate control, interrupt pacing. Micro: lazy-refill token bucket, O(1) per request.
Reader–writer problem — a synchronization problem of coordinating concurrent reads with exclusive writes to shared data (C3). Why: the screen-tearing buffer is exactly this. Theory → 04_os.md.
Rope / gap buffer — text data structures giving efficient inserts/deletes vs an O(n) flat string (B5). Why: scale a text editor. Where: editor buffer storage.
SCAN ("elevator algorithm") — keep moving one direction serving all requests that way, then reverse (B3). Why: no starvation, low wait-time variance, minimal travel. Where: elevator dispatch and disk-I/O scheduling (04_os.md). Sibling: LOOK (reverse as soon as no requests ahead, not at the physical end).
Singleton — a creational pattern guaranteeing one instance with a global access point (E1). Why: genuinely singular resources (logger, HW manager). Thread-safe form: C++11 Meyers (function-local static) or double-checked locking. Gotcha: hidden global state, hard to test.
Single Responsibility (SRP) — the "S" in SOLID: one reason to change per class (A2). Where: separate the lottery's RNG, pool, elimination, and logger into distinct classes (B4).
SOLID — five OOD principles (Single Responsibility, Open/Closed, Liskov, Interface Segregation, Dependency Inversion) for maintainable, extensible designs (A2). Why: the vocabulary for "why is this design good?"
State — a behavioral pattern where an object changes behavior as its internal state transitions; an FSM as objects or a jump table (E5, B3). Why: readable, illegal-transition-proof stateful logic. Where: elevator, capture session. Contrast Strategy (client-chosen, not self-driven).
Strategy — a behavioral pattern encapsulating interchangeable algorithms behind one interface, chosen at runtime (E4). Why: Open/Closed for behavior; swap/AB-test algorithms. Where: elevator scheduling, rate-limit algorithm, pricing. Micro: inject SchedulePolicy.
Tearing — a display artifact: the panel shows parts of two frames because the consumer read a buffer mid-write (C3). Why it happens: producer–consumer race on a shared frame buffer. Fix: double/triple buffering + VSync.
Timing wheel (hashed) — a circular bucket array with a cursor; timers hash to (cursor+ticks) % N with a rounds counter — O(1) insert/cancel/expire amortized (B1). Why: beats min-heap's O(log n) at high timer counts. Where: network/RTOS/driver timeouts; Linux uses hierarchical wheels.
Token bucket — a rate-limit algorithm: tokens refill at a fixed rate up to a capacity, each request spends one (D3). Why: allows bursts up to capacity while bounding the average. Where: API/client limiting. Micro: lazy refill: tokens += elapsed*rate.
Triple buffering — three buffers so the producer needn't wait for the consumer to release one (C2, C3). Why: removes producer stalls, smooth at the cost of one buffer and up to a frame of latency. Where: preview, display.
UML diamond — notation for ownership: hollow = aggregation (shared), filled = composition (exclusive) (A4). Why: communicates lifetime ownership in a class diagram.
VSync (vertical sync) — the interval between display refreshes (vertical blanking) when it's safe to swap the scan-out buffer (C3). Why: swapping outside it tears. Where: page-flip timing in the display pipeline.
Zero-copy — moving data by passing pointers/handles, never copying the payload (C2). Why: an 18 MB frame copy destroys latency and power. Where: camera/video buffer hand-off via DMA-BUF/ION.
§ Last-5-minutes cheat sheet¶
- Method: clarify → entities (nouns→classes) → relations & APIs (verbs→methods) → data structures + Big-O → edge cases → concurrency/ownership → trade-offs. Think aloud; give 2 approaches + complexity.
- SOLID: Single responsibility · Open/closed (extend, don't modify) · Liskov (subtypes substitutable) · Interface segregation (small interfaces) · Dependency inversion (depend on abstractions, inject).
- Patterns: Singleton (one instance) · Factory (create-by-type) · Observer (pub/sub callbacks) · Strategy (swap algorithm) · State (FSM/behavior-by-state) · Adapter (fit an alien interface) · Command (undo/redo).
- Timer module: min-heap by expiry (O(log n), exact, few timers) vs hashed timing wheel (O(1), many timers, bounded range); callbacks = function pointers +
void* ctx. - Google Maps road-block: weighted graph; A* = Dijkstra + admissible straight-line heuristic; road block = dynamic edge-weight (∞ closed / +delay) → reroute only affected routes.
- Elevator: per-car FSM (IDLE/UP/DOWN/DOORS_OPEN) + SCAN scheduling (no starvation); two heaps per car (min up-stops, max down-stops); policy = Strategy.
- Lottery: Fisher–Yates non-repeating draw (O(1)) + circular elimination; inject RNG + logger (Observer); modular single-responsibility classes.
- Camera driver (multi-sensor): ops table of function pointers + registration/Factory → Open/Closed + Dependency Inversion (V4L2/HAL3 model). Per-instance state in
void* priv. - Preview pipeline: producer–consumer + pre-allocated buffer pool + queues; zero-copy (move handles), drop oldest if slow; triple-buffer to avoid tearing.
- Screen tearing: producer/consumer race → double buffer + VSync page-flip (atomic swap in blanking); triple buffer to avoid producer stall. Underlying: reader–writer.
- HW vs SW model: golden (float) reference vs hardware (fixed-point) model; same stimulus → compare bit-exact or by tolerance/PSNR/±1 LSB; directed + random; first-diff triage.
- Immutable class: no setters · all fields
final/constset in ctor · classfinal· defensive copies in & out → inherently thread-safe. - Warm-ups: parking lot (per-size free queues, O(1)) · rate limiter (token=burst, leaky=smooth; lazy refill) · bounded queue (mutex + 2 condvars) · LRU (hash map + DLL, O(1)).
- Singleton thread-safe: C++11 Meyers (local
static) or double-checked locking (atomic + mutex); in C,pthread_once. - Ownership: association (no own) · aggregation (shared,
shared_ptr) · composition (exclusive,unique_ptr). Wrong choice → leak or dangling.
Evidence base: qualcomm_camera_interview_experiences.md. Frequencies are approximate (sample = 75 reports, some via aggregator pages). Diagrams in assets/ (filenames lld_*). Cross-references: C language / function pointers / void* / ownership → 01_c_programming.md · C++ OOP / vtable / RAII / smart pointers → 02_cpp_oop.md · algorithms (Dijkstra, heaps, LRU mechanics, graphs) → 03_dsa.md · threads / mutex / semaphore / scheduling / reader-writer → 04_os.md · camera/ISP pipeline domain → 05_camera_isp_multimedia.md · kernel / drivers / HAL / ioctl → 07_embedded_linux_kernel.md · fixed-point / number representation / DV → 09_computer_arch_digital_design.md.