Junior Embedded Developer Interview Preparation Guide - FAANG Standards
This guide is based on general FAANG interview practices and may not reflect specific company procedures.
FAANG companies conduct a rigorous multi-stage interview process for embedded developer roles. For junior-level candidates (1-2 years experience), the process begins with a recruiter screen to assess background and motivation, followed by a technical phone screen to evaluate core programming competency. This culminates in 5 on-site interview rounds covering coding fundamentals, embedded systems concepts, low-level C programming, real-time systems, and behavioral/cultural fit. Junior embedded developers at FAANG are evaluated primarily on hands-on technical ability, problem-solving approach, and learning potential rather than architectural expertise. The focus is on verifying strong fundamentals in C/C++, microcontroller programming, low-level debugging, and hardware-software interaction.
Interview Rounds
Recruiter Screening
What to Expect
Initial phone screen with a recruiter to assess your background, technical foundation, and cultural fit for the embedded developer role. The recruiter reviews your resume, discusses your experience with embedded systems and microcontroller programming, confirms basic technical qualifications, and explains the interview process and company. This conversational round evaluates communication skills, genuine interest in embedded development, and alignment with company culture. For junior candidates, recruiters assess learning mindset and enthusiasm for the field.
Tips & Advice
Prepare 2-3 specific examples of embedded projects or coursework demonstrating microcontroller experience, firmware development, or hardware-software interaction. Clearly articulate why you're interested in embedded systems and why this company specifically. Practice explaining technical concepts in accessible language. Have thoughtful questions prepared about the team, project types, and learning opportunities. Be honest about your experience level while showing enthusiasm to learn. Highlight internships, hackathons, personal projects, or certifications relevant to embedded systems. Show awareness of what embedded development entails—working with hardware constraints, real-time requirements, and resource limitations.
Focus Topics
Communication and Problem-Solving Approach
Demonstration of clarity in explaining technical concepts, logical thinking, asking clarifying questions, and willingness to learn. Enthusiasm for solving technical problems. Ability to discuss challenges and how you overcame them.
Practice Interview
Study Questions
Career Motivation and Embedded Systems Interest
Clear articulation of your interest in embedded systems development, what excites you about the field, and specific experiences that led you to embedded work. Understanding of embedded systems scope: IoT, microcontrollers, firmware, real-time systems. Ability to discuss relevant coursework, internships, or personal projects.
Practice Interview
Study Questions
Technical Foundation Summary
Concise overview of programming experience (C/C++ proficiency), microcontroller exposure, understanding of embedded systems concepts, and tools used (debuggers, development boards, IDEs). Specific project examples demonstrating these skills.
Practice Interview
Study Questions
Technical Phone Screen
What to Expect
A 45-60 minute technical interview with a senior engineer or hiring manager conducted over phone or video. This round tests fundamental C/C++ programming skills, data structures knowledge, and embedded systems understanding. You'll solve 1-2 coding problems using a collaborative online editor (Google Docs, CoderPad, etc.) and answer conceptual questions about embedded systems. Problems are typically medium difficulty, focusing on algorithmic thinking, code correctness, and ability to communicate your approach. This is a go/no-go gate to on-site interviews.
Tips & Advice
Start by clarifying problem requirements and asking questions before coding. Think aloud throughout the problem-solving process so the interviewer understands your reasoning. Write clean, readable code with proper variable naming and comments. Test your code with examples and discuss edge cases. For conceptual questions, focus on practical understanding rather than memorization—relate concepts to real embedded scenarios. If stuck, explain your approach and ask for hints rather than remaining silent. Manage time strategically: ~10 minutes understanding, ~30 minutes coding, ~10 minutes testing/optimization, ~10 minutes for questions. For embedded questions, discuss trade-offs (e.g., polling vs. interrupts, memory vs. performance). Show genuine interest in learning from the interviewer's experience.
Focus Topics
Real-Time Operating System (RTOS) Concepts
Basic understanding of RTOS role in embedded systems, task/thread concept, context switching, scheduling basics, semaphores and mutexes for synchronization. Awareness of popular RTOS like FreeRTOS. Understanding why RTOS is chosen for certain applications.
Practice Interview
Study Questions
Algorithms: Searching, Sorting, Recursion, Complexity Analysis
Familiarity with binary search, sorting algorithms (bubble, insertion, merge sort), recursion concepts, and Big O notation. Ability to analyze time/space complexity and choose appropriate algorithms. Understanding algorithm trade-offs.
Practice Interview
Study Questions
Microcontroller Basics and Hardware Integration
Foundational understanding of microcontroller architecture (CPU, ALU, control unit), memory types (program, RAM, EEPROM), memory addressing, and how code interfaces with hardware. Basic knowledge of GPIO, analog/digital conversion, and peripheral initialization. Familiarity with common architectures like ARM Cortex-M or AVR.
Practice Interview
Study Questions
Memory Management and Pointers
Deep understanding of stack vs. heap memory, pointer operations (dereferencing, arithmetic, arrays of pointers), dynamic memory allocation, memory leaks, and garbage collection concepts. Comfort with pointer-to-pointer, function pointers, and pointer casting.
Practice Interview
Study Questions
Data Structures: Implementation and Complexity
Solid understanding and implementation ability for arrays, linked lists, stacks, queues, and basic trees. Time/space complexity analysis for each structure. Understanding when to use each data structure. Implementation in C with manual memory management.
Practice Interview
Study Questions
C/C++ Language Fundamentals and Syntax
Deep understanding of C and C++ syntax including pointers, references, memory allocation (malloc/free, new/delete), structs, enums, preprocessor directives, const/volatile keywords, and function declarations. Differences between C and C++. Ability to write syntactically correct code without extensive debugging.
Practice Interview
Study Questions
On-Site: Coding and Data Structures Round
What to Expect
First on-site interview round lasting 45-50 minutes focused on general programming competency and problem-solving. You'll solve 1-2 medium difficulty coding problems on a whiteboard or laptop with an interviewer. Problems test understanding of data structures, algorithms, and fundamental programming concepts. While not necessarily embedded-specific, these problems assess your ability to write clean, correct, efficient code under time pressure. Evaluation criteria include problem-solving approach, code quality, testing, communication, and ability to discuss trade-offs and optimizations.
Tips & Advice
For whiteboard coding, prioritize logic and algorithm clarity over perfect syntax—interviewers understand this medium has limitations. For laptop coding, write production-quality code that compiles cleanly. Before coding, fully understand requirements and discuss your approach with the interviewer. Write pseudocode first if it helps organize your thinking. Code systematically and methodically. After implementing, test with multiple examples including edge cases and discuss potential errors. When you notice a mistake, fix it promptly and explain the correction. Maintain ongoing communication—don't code in silence. After solving, discuss complexity, potential optimizations, and alternative approaches. For embedded-relevant problems, discuss implications for memory and performance constraints.
Focus Topics
Testing, Debugging, and Verification
Ability to test code with various inputs including edge cases, boundary conditions, and invalid inputs. Identifying and fixing bugs. Tracing through code mentally or on paper. Verifying solutions work correctly before considering them complete.
Practice Interview
Study Questions
Time and Space Complexity Analysis
Understanding and articulating time and space complexity using Big O notation. Comparing different approaches and selecting efficient solutions. Knowing the complexity of common data structure operations. Optimization techniques and when to apply them.
Practice Interview
Study Questions
Data Structure Implementation and Selection
Ability to implement fundamental data structures from scratch: arrays, linked lists (singly and doubly), stacks, queues, binary trees, and basic graphs. Understanding operations, complexity, edge cases, and knowing when to use each structure. Clean implementation with proper memory management in C/C++.
Practice Interview
Study Questions
Code Quality, Readability, and Correctness
Writing code that is readable (clear variable names, appropriate comments), well-structured (modular, logical flow), and correct (handles edge cases, no bugs or memory issues). Code should compile without warnings in strict mode. Avoiding common pitfalls like off-by-one errors, null pointer dereferences, and memory leaks.
Practice Interview
Study Questions
Systematic Problem-Solving Methodology
Structured approach to coding problems: understand requirements completely, identify appropriate data structures and algorithms, write clean code incrementally, handle edge cases, test thoroughly, and optimize. Breaking complex problems into manageable pieces. Discussing trade-offs.
Practice Interview
Study Questions
On-Site: Embedded Systems and Microcontroller Fundamentals Round
What to Expect
A 50-60 minute technical round focused on embedded systems concepts, microcontroller programming, and low-level hardware understanding. This round features conceptual questions, practical scenarios, code reading/debugging exercises, and discussions of hardware-software interaction. You might analyze register configurations, explain interrupt handling, debug timing issues, or discuss peripheral control. The interviewer assesses understanding of microcontroller architecture, memory organization, interrupt mechanisms, peripheral control, and how software interacts with hardware at the lowest levels.
Tips & Advice
Be prepared to explain concepts clearly with concrete examples and diagrams. Draw block diagrams for memory layout, interrupt vectors, or hardware organization when helpful. Use specific microcontroller examples (ARM Cortex-M, AVR, PIC). If you don't know something, acknowledge it honestly, explain how you would learn it, and discuss related concepts you do understand. Compare approaches (polling vs. interrupts, different memory types) and discuss trade-offs. Be familiar with basic assembly language and able to read simple assembly code. Practice reading datasheets and technical documentation—this is a core embedded skill. Discuss how software changes translate to hardware behavior. Show understanding of embedded constraints (limited memory, power, real-time requirements).
Focus Topics
Analog-to-Digital and Digital-to-Analog Conversion
Basic understanding of ADC (Analog-to-Digital Converter): sampling, resolution, conversion time, multiplexing channels. DAC (Digital-to-Analog Converter) concepts. Understanding when and how to use these peripherals. Practical considerations like sampling rate, noise, and accuracy.
Practice Interview
Study Questions
Assembly Language Fundamentals and Code Translation
Basic understanding of assembly language syntax, common instructions (MOV, ADD, JUMP, CALL, RETURN), CPU registers, and flags. Ability to read simple assembly code and understand what it does. Understanding how C code translates to assembly. Function prologue/epilogue and stack usage at assembly level.
Practice Interview
Study Questions
Timers, Counters, and PWM Fundamentals
Understanding timer modules in microcontrollers: timer modes (overflow, compare, capture), prescalers, counting, and interrupt generation. PWM (Pulse Width Modulation) concepts and configuration. Clock sources and timing accuracy. Practical use cases for timers and PWM (LED brightness, motor speed, waveform generation).
Practice Interview
Study Questions
Registers, Peripheral Configuration, and GPIO Control
Understanding microcontroller registers (general purpose, special function registers), memory-mapped I/O, how to configure peripherals by writing to registers, GPIO operations (input/output, pull-ups/pull-downs), and how software controls hardware at register level. Ability to read and interpret datasheets.
Practice Interview
Study Questions
Interrupts, Exception Handling, and ISRs
Understanding interrupt concepts: interrupt sources, interrupt vectors, interrupt service routines (ISRs), interrupt priorities, nesting, and context switching. Polling vs. interrupt-driven approaches. How interrupts work in practice: saving/restoring context, interrupt latency, and ISR best practices. Examples of using interrupts for real events (button press, timer overflow, serial data).
Practice Interview
Study Questions
Microcontroller Architecture and Memory Organization
Understanding microcontroller structure: CPU core, memory types (program memory/flash, SRAM, EEPROM), memory addressing schemes, memory layout, and how code executes from memory. Knowledge of common architectures (ARM Cortex-M for IoT/embedded, AVR for Arduino). Understanding how code sections (text, data, BSS) are organized in memory.
Practice Interview
Study Questions
On-Site: Embedded C Programming and Low-Level Concepts Round
What to Expect
A focused 50-minute round testing deep C programming mastery specific to embedded systems. This round features coding exercises, code debugging, and questions about embedded C idioms. Topics include pointer operations, memory management, const/volatile qualifiers, bit manipulation, struct packing, hardware register definitions, embedded patterns, and lower-level concepts. You might debug problematic code, implement solutions with specific constraints, or explain why certain embedded C patterns are used.
Tips & Advice
Master pointer concepts thoroughly—they're foundational and frequently tested deeply. Understand const and volatile keywords in different contexts and why volatile is critical for hardware access. Practice bit manipulation problems (setting/clearing/toggling bits, bit fields). Know how structs are laid out in memory and why struct packing matters for hardware registers. Be familiar with common embedded patterns like defining hardware registers as structs or using callbacks. For debugging exercises, trace through code methodically and identify issues. Discuss the embedded implications of your solutions—memory usage, execution speed, hardware interaction. Be comfortable with inline assembly if the company uses it. Show understanding of why embedded C differs from desktop C (resource constraints, real-time requirements, hardware interaction).
Focus Topics
Embedded C Patterns and Best Practices
Common embedded C patterns: hardware register definitions, driver structures, callback functions, state machines, circular buffers. Understanding embedded coding conventions and best practices. Why certain patterns are preferred in embedded systems (readability, safety, performance).
Practice Interview
Study Questions
Bit Manipulation and Bitwise Operations
Competency with bitwise operations: AND, OR, XOR, NOT, left/right shift. Bit fields and struct bit-packing. Bit manipulation techniques and algorithms. Using bitwise operations for efficiency and flag management. Solving bit manipulation problems.
Practice Interview
Study Questions
Struct Packing, Memory Layout, and Hardware Registers
Understanding how structs are laid out in memory: alignment, padding, and sizeof calculations. Using struct packing pragmas to control memory layout. Designing structs for embedded systems. Defining hardware registers as structs with volatile members. Avoiding common struct layout errors.
Practice Interview
Study Questions
Const and Volatile Qualifiers in Embedded Context
Deep understanding of const keyword: const variables, const pointers, pointer-to-const, const functions. Volatile keyword: preventing compiler optimizations for hardware access, volatile variables and pointers. Using volatile for memory-mapped I/O and hardware registers. Understanding why volatile is crucial in embedded systems but often misunderstood.
Practice Interview
Study Questions
Memory Management and Dynamic Allocation in Embedded Systems
Comprehensive understanding of memory allocation (malloc/free): memory layout (stack, heap, static areas), memory fragmentation, memory leaks, and out-of-memory handling. Techniques for managing limited memory: fixed-size allocation pools, stack allocation, static allocation. Memory-efficient data structure design.
Practice Interview
Study Questions
Pointers and Pointer Arithmetic
Complete mastery of pointers: pointer-to-pointer, arrays of pointers, pointer arithmetic, void pointers, pointer-to-function. Understanding pointer size and alignment. Using pointers for dynamic data structures. Pointers in embedded context: accessing hardware registers, DMA, and peripheral control. Generic programming with void pointers.
Practice Interview
Study Questions
On-Site: Real-Time Systems and Debugging Scenario Round
What to Expect
A 50-minute technical round focused on real-time systems concepts and practical problem-solving under constraints. You'll analyze scenarios involving race conditions, synchronization issues, timing problems, or performance optimization. The round tests your understanding of RTOS, concurrency, synchronization primitives, real-time constraints, and systematic debugging. You might identify bugs in multi-threaded code, suggest optimization strategies, or discuss how to diagnose timing issues using hardware tools.
Tips & Advice
Think systematically about debugging: understand the symptom, form hypotheses about causes, and design experiments to test them. Be familiar with common embedded issues: race conditions, stack overflow, deadlocks, interrupt storms, watchdog resets. Discuss trade-offs when proposing solutions—embedded solutions rarely have perfect answers. Know RTOS basics (FreeRTOS is common) even if you haven't used them extensively. Be comfortable discussing real-time constraints and how to meet them. For code with bugs, trace through carefully step-by-step. Discuss which debugging tools (debugger, logic analyzer, oscilloscope) would help diagnose specific problems and why. Show understanding of testing strategies for embedded systems where reproducing bugs can be difficult.
Focus Topics
Performance Optimization and Resource Constraints
Techniques for optimizing code for memory, CPU, and power consumption. Understanding trade-offs: speed vs. size, performance vs. power, real-time vs. efficiency. Profiling and identifying bottlenecks. Optimization strategies: compiler flags, algorithm selection, data structure design. When to optimize vs. premature optimization.
Practice Interview
Study Questions
Common Embedded System Issues and Prevention
Recognition of common embedded problems: stack overflow, heap fragmentation, race conditions, interrupt storms, watchdog resets, brownout conditions, and EMI issues. Understanding why these occur and how to prevent or detect them. Defensive programming practices specific to embedded systems.
Practice Interview
Study Questions
Real-Time Constraints, Deadlines, and Timing
Understanding hard real-time, firm real-time, and soft real-time requirements. Concepts of deadlines, jitter, latency, and response time. How to design systems to meet timing constraints. Using timers and timing analysis. Discussing trade-offs between real-time guarantees and other system properties.
Practice Interview
Study Questions
Systematic Debugging Methodology for Embedded Systems
Structured approach to debugging: reproducing the issue consistently, isolating the problem, forming and testing hypotheses, and verifying fixes. Debugging techniques: adding instrumentation/logging, binary search for finding issues, analyzing crash dumps. Using hardware debuggers, breakpoints, and watch variables. Limitations of debugging with limited resources.
Practice Interview
Study Questions
Concurrency, Synchronization, and Race Conditions
Understanding concurrent execution in multi-tasking systems, race conditions, and synchronization mechanisms (semaphores, binary semaphores, mutexes, message queues). Identifying race conditions in code. Critical sections and atomic operations. Deadlock concepts and avoidance. Practical synchronization patterns.
Practice Interview
Study Questions
Real-Time Operating System (RTOS) Fundamentals
Understanding RTOS concepts: task/thread concept, task states (running, ready, blocked, suspended), scheduling algorithms (preemptive, cooperative, priority-based). Context switching mechanics. Familiarity with a specific RTOS like FreeRTOS: task creation, scheduling, basic API. Understanding when RTOS is appropriate and its benefits/drawbacks compared to bare-metal.
Practice Interview
Study Questions
On-Site: Behavioral and Cultural Fit Round
What to Expect
A 45-50 minute behavioral interview assessing soft skills, teamwork ability, problem-solving approach, learning agility, and alignment with company culture. The interviewer uses behavioral questions to understand how you work in teams, respond to challenges, handle feedback, and learn from failures. For junior roles, FAANG focuses on coachability, collaboration, taking ownership, communication, and demonstrating company values (e.g., Amazon's Leadership Principles: ownership, bias for action, learn and be curious, etc.). This round determines cultural fit and predicts success in the company environment.
Tips & Advice
Use the STAR method (Situation, Task, Action, Result) to structure answers clearly. Prepare 5-7 specific examples from coursework projects, internships, or personal projects demonstrating key competencies. Be authentic and specific; generic answers weaken your response. Focus on your role and what you learned, not just the outcome. Discuss failures honestly and emphasize what you learned—companies value this more than perfection. Show enthusiasm for learning and growth; junior roles value learning potential highly. Ask thoughtful questions about the team, company culture, and learning opportunities. Be aware of the company's core values and weave them naturally into your examples. Practice active listening and responding thoughtfully to interviewer's experiences. Demonstrate respect for different perspectives and willingness to collaborate.
Focus Topics
Company Values and Cultural Alignment
Understanding and demonstrating alignment with the company's core values through specific examples. For Amazon: customer obsession, ownership, bias for action, learn and be curious. For Google: focus on user, it's best to do one thing really, really well. For other companies: research and understand their stated values. Showing how you embody these values.
Practice Interview
Study Questions
Taking Ownership and Initiative
Examples of taking responsibility for problems, going beyond assigned tasks to improve systems, identifying issues proactively, and following through on commitments. Showing pride in work quality and wanting to leave code better than you found it. Small examples of initiative appropriate to junior level (not organizational transformation).
Practice Interview
Study Questions
Handling Challenges and Problem-Solving Approach
Specific examples of overcoming technical or interpersonal challenges, adapting to changing requirements, learning from difficult situations, and solving problems creatively. Discussing your approach to hard problems and what you learned from challenges.
Practice Interview
Study Questions
Clear Communication and Articulation
Ability to explain technical concepts clearly to diverse audiences, listen carefully to understand others, provide and receive feedback respectfully, and document work clearly. Examples of successfully communicating across teams. Writing and presentation skills. Asking clarifying questions.
Practice Interview
Study Questions
Learning Agility and Coachability
Demonstrated ability to learn quickly, adapt to new technologies, ask good questions to understand gaps, take feedback well, and improve based on feedback. Examples of learning from mistakes, acquiring new skills outside formal training, and applying lessons learned. Openness to mentoring and working with more experienced engineers.
Practice Interview
Study Questions
Teamwork, Collaboration, and Communication
Ability to work effectively with diverse team members, communicate clearly both verbally and in writing, listen actively, and contribute to team goals. Examples of successful collaboration, handling disagreements constructively, supporting teammates, and knowing when to ask for help. Understanding the value of collaboration in embedded systems where hardware and software teams must coordinate.
Practice Interview
Study Questions
Frequently Asked Embedded Developer Interview Questions
Design a wear-leveling and atomic configuration-update scheme for a device that stores critical configuration in EEPROM with only three 512-byte pages. Requirements: atomic update even if power fails, ability to rollback to last-known-good, and minimize erase cycles. Describe layout and update/rollback algorithm.
Sample Answer
Overview / goals
Provide atomic configuration updates across power-fail, support rollback to last-known-good (LKG), and spread wear across three 512‑byte EEPROM pages to minimize erases.
Layout (per 512B page)
- Header (16B): magic (4B), version/counter (4B, monotonic), flags (1B: VALID/COMMIT/ERASED), CRC32 (4B), reserved.
- Payload (~480B): configuration blob.
- Footer (last 12B): copy of version and CRC for quick scan.
Always maintain at most one page marked COMMIT (new valid) after update. At boot, pages with VALID/COMMIT indicate current and candidate.
State machine & invariants
- States per page: ERASED, VALID (stable committed config), CANDIDATE (being written), COMMIT (write completed and atomic marker set).
- Invariant: there must always be at least one VALID page containing LKG config.
Update algorithm (write new config)
- Choose next ERASED page in circular order (wear-leveling).
- Write header with magic + version (version = prev_version + 1) and flags = CANDIDATE (no CRC yet).
- Write payload.
- Compute CRC, write CRC fields.
- Atomically set flags = COMMIT (single-byte write). If flag flip succeeds, this page is new candidate committed.
- Set previous VALID page's flags = ERASED_MARK (or simply invalidate with a single-byte flag), then erase that page in background when safe to reclaim.
If power fails:
- If a COMMIT page exists (CRC matches), treat it as VALID.
- If only CANDIDATE with missing CRC or bad CRC, ignore and keep previous VALID.
Rollback
- LKG is the highest-version page with valid CRC and flags VALID or COMMIT. If new COMMIT fails CRC or incomplete, boot uses LKG. Provide explicit rollback command: mark current page INVALID and revert to previous version by marking previous VALID/COMMIT.
Minimizing erases
- Only erase one page per full update (the one being reclaimed), rotate pages circularly to spread wear.
- Use single-byte flag updates to change state (no full erase).
- Batch erases during idle time; keep at least one ERASED page ready.
Boot scan
- Scan three pages, validate magic+CRC, pick highest version with VALID/COMMIT. If none valid, fallback to factory default in ROM.
Notes
- Use monotonic 32-bit version counter (wrap handling via compare-by-distance).
- Protect flag writes with read-verify to ensure atomicity.
- Ensure EEPROM supports atomic single-byte write; otherwise use checksum + dual-marker technique.
During a longer spoken explanation, what deliberate delivery choices help a live audience keep following you, beyond just the words you choose? Pick two or three techniques and describe how you would actually use them.
Sample Answer
Direct answer
Beyond word choice, deliberate pacing, brief pauses at key transitions, and periodic checkpoints where you invite a question all help a live audience stay oriented during a longer explanation.
Structured elaboration
- Pacing: slowing down slightly at the most important sentence (a conclusion, a number, a decision point) signals to the listener that this part matters more than the surrounding context, the same way bolding a phrase does on a page.
- Pauses at transitions: a brief pause when moving from one idea to the next gives the listener a moment to finish processing the previous point instead of having it run together with the next one.
- Checkpoints for questions: explicitly stopping every few minutes to ask "does that make sense so far, any questions before I move on?" catches confusion early, while it's still cheap to address, rather than at the end when the listener has been lost for a while.
- Choosing two or three of these deliberately, rather than trying to do everything at once, is more sustainable; trying to consciously manage every aspect of delivery simultaneously tends to make a speaker sound stilted.
Worked example
During a fifteen-minute technical walkthrough: slow down and pause briefly right before stating the recommendation ("...and so, the option we're proposing is [pause] option two"), then at the two natural section breaks (after background, and after the options), stop explicitly and ask "any questions before I move to the next part?" rather than only checking in at the very end.
Trade-offs and pitfalls
- Overusing dramatic pauses or slowing down on things that aren't actually the key point dilutes the technique; it works because it's used selectively.
- Checkpoints can eat into your time budget if the audience takes them as an invitation for a lengthy tangent; it can help to explicitly frame them as "quick check" rather than opening the floor fully.
- These techniques don't substitute for a clear structure; a well-paced explanation of a confusing structure is still confusing, just more pleasant to listen to.
Explain the difference between a hardware interrupt and an exception (fault) on a CPU such as ARM Cortex-M. Give examples of exceptions and describe how their handling and semantics differ from asynchronous external interrupts.
Sample Answer
The distinction
If you remember three things: a hardware interrupt is asynchronous (it arrives at some instruction boundary regardless of what the code is doing), a fault is synchronous (one particular instruction caused it, so returning without fixing the cause repeats it), and a fault whose own handler cannot run is escalated to HardFault. The rest of this card shows each in a program.
On Cortex-M everything the core can be diverted to is called an exception, and each has a number (the value in the IPSR register, the Interrupt Program Status Register, a read-only register that holds the number of the exception being handled, or 0 in ordinary code): 1 Reset, 2 NMI, 3 HardFault, 4 MemManage, 5 BusFault, 6 UsageFault, 11 SVCall, 14 PendSV, 15 SysTick, and 16 and up the external interrupts (IRQ0 is exception 16). In ordinary usage, "interrupt" means the asynchronous kind raised by hardware outside the instruction stream (a peripheral line, a timer), and "fault" means the synchronous kind: a direct consequence of the instruction the core is executing (divide by zero, bad address, undefined instruction). Synchronous means the exception is raised by the instruction being executed; asynchronous means it arrives independently of the instruction stream. The Cortex-M3 Technical Reference Manual (ARM DDI 0337G) tags each one asynchronous or synchronous, and calls a BusFault synchronous when it is precise and asynchronous when it is imprecise. A precise BusFault is reported at the very instruction that made the bad access, so the stacked PC points at it. An imprecise one is reported later, typically because a store went into a write buffer and the bus error came back after the core had moved on, so the stacked PC points somewhere after the offending store.
The differences that matter in firmware:
- Cause and timing. An interrupt arrives at an arbitrary instruction boundary and has no relationship to what the code is doing. A fault is caused by one particular instruction.
- Where execution resumes. After an interrupt the core continues after the interrupted instruction. After a MemManage or UsageFault the manual says the return PC points to the faulting instruction, so simply returning repeats it and faults again unless the handler removed the cause (or skips the instruction, or resets the system).
- Enabling. An external interrupt is enabled per source in the NVIC. MemManage, BusFault and UsageFault each have an enable bit in SHCSR; while disabled, that fault goes to HardFault instead. SVCall, PendSV and SysTick are always available and only gated by priority.
- Escalation. Escalation means a fault being handled as HardFault instead of by its own handler. The manual describes HardFault as taking all classes of fault when the fault cannot activate, either because its priority does not allow it to run right now or because its configurable handler (the MemManage, BusFault or UsageFault one) is disabled. Interrupts never escalate.
- Diagnostics. A fault comes with status registers (CFSR, the Configurable Fault Status Register, with one bit per cause; HFSR, the HardFault Status Register; and the stacked registers, meaning the copies of r0-r3, r12, LR, PC and xPSR the core pushes on entry) saying what happened. An interrupt carries no such record.
- Software-triggered exceptions. SVC (a supervisor call, for example an RTOS service entry) is synchronous, and PendSV (a pended request used for deferred work such as context switching) is set by software but runs when its priority allows, like an interrupt.
Run it
The program triggers each kind and prints its exception number, then tests what PRIMASK (the global mask bit set by cpsid i) does to each.
#include <stdint.h>
#define REG(a) (*(volatile uint32_t *)(a))
#define NVIC_ISER REG(0xE000E100)
#define NVIC_ISPR REG(0xE000E200)
#define NVIC_IPR ((volatile uint8_t *)0xE000E400)
#define SCB_ICSR REG(0xE000ED04)
#define SCB_CCR REG(0xE000ED14)
#define SCB_SHCSR REG(0xE000ED24)
#define SCB_CFSR REG(0xE000ED28)
#define SCB_HFSR REG(0xE000ED2C)
static void puts_(const char *s) { while (*s) REG(0x4000C000) = *s++; }
static void putu(uint32_t v) { char b[11]; int i = 10; b[i] = 0; do { b[--i] = '0' + v % 10; v /= 10; } while (v); puts_(&b[i]); }
static void puth(uint32_t v) { puts_("0x"); for (int i = 28; i >= 0; i -= 4) REG(0x4000C000) = "0123456789abcdef"[(v >> i) & 15]; }
static void done(void) {
register uint32_t r0 __asm("r0") = 0x18, r1 __asm("r1") = 0x20026;
__asm volatile("bkpt 0xAB" :: "r"(r0), "r"(r1));
for (;;) {}
}
static uint32_t ipsr(void) { uint32_t v; __asm volatile("mrs %0, ipsr" : "=r"(v)); return v; }
static void log_(const char *who) { puts_(" "); puts_(who); puts_(": IPSR (exception number) = "); putu(ipsr()); puts_("\n"); }
static void sync(void) { __asm volatile("dsb\n isb" ::: "memory"); }
void nmi(void) { log_("NMI"); }
void svc(void) { log_("SVCall"); }
void pendsv(void) { log_("PendSV"); }
void systick(void) { log_("SysTick"); }
void irq0(void) { log_("external IRQ0"); }
void usagefault(void) {
log_("UsageFault"); puts_(" UFSR/CFSR = "); puth(SCB_CFSR); puts_("\n");
SCB_CFSR = SCB_CFSR; /* write 1 to clear the sticky bits */
SCB_CCR &= ~(1u << 4); /* stop trapping, so the retried divide completes */
}
void hardfault(void) {
log_("HardFault"); puts_(" HFSR = "); puth(SCB_HFSR); puts_(" CFSR = "); puth(SCB_CFSR); puts_("\n");
SCB_HFSR = SCB_HFSR; SCB_CFSR = SCB_CFSR;
SCB_CCR &= ~(1u << 4);
__asm volatile("cpsie i"); /* clear PRIMASK so the program can finish */
}
int main(void) {
NVIC_IPR[0] = 0x80; NVIC_ISER = 1;
volatile uint32_t zero = 0, q;
puts_("1. software-triggered:\n");
__asm volatile("svc 0");
SCB_ICSR = 1u << 28; sync(); /* PENDSVSET */
SCB_ICSR = 1u << 26; sync(); /* PENDSTSET */
NVIC_ISPR = 1; sync(); /* external interrupt */
puts_("2. fault with its handler enabled (UsageFault, divide by zero):\n");
SCB_SHCSR |= 1u << 18; SCB_CCR |= 1u << 4; /* USGFAULTENA, DIV_0_TRP */
q = 99; q = 10 / zero;
puts_(" divide retried after the handler, result (was 99) = "); putu(q); puts_("\n");
puts_("3. same fault with its handler disabled:\n");
SCB_SHCSR &= ~(1u << 18); SCB_CCR |= 1u << 4;
q = 10 / zero;
puts_("4. PRIMASK set, then NMI, PendSV, SysTick and IRQ0 are all requested:\n");
__asm volatile("cpsid i" ::: "memory");
SCB_ICSR = (1u << 31) | (1u << 28) | (1u << 26); NVIC_ISPR = 1; sync(); /* NMIPENDSET too */
puts_(" releasing PRIMASK\n");
__asm volatile("cpsie i" ::: "memory"); sync();
puts_("5. svc executed while PRIMASK is set:\n");
__asm volatile("cpsid i\n svc 0" ::: "memory");
done();
return 0;
}
void reset(void) { main(); }
__attribute__((section(".vectors"), used)) void (*const vectors[17])(void) = {
[0] = (void *)0x20010000, [1] = reset, [2] = nmi, [3] = hardfault, [6] = usagefault,
[11] = svc, [14] = pendsv, [15] = systick, [16] = irq0 };
Built with arm-none-eabi-gcc -mcpu=cortex-m3 -mthumb -O2 -nostartfiles -ffreestanding -Wl,--section-start=.vectors=0x0 -Wl,-Ttext=0x400 -Wl,-e,reset -Wl,-Tbss=0x20000000 exc_kinds.c -o exc_kinds.elf (GCC 14.2.1) and run under QEMU 10.0 (qemu-system-arm -M lm3s6965evb -nographic -semihosting-config enable=on,target=native -kernel exc_kinds.elf), it prints:
1. software-triggered:
SVCall: IPSR (exception number) = 11
PendSV: IPSR (exception number) = 14
SysTick: IPSR (exception number) = 15
external IRQ0: IPSR (exception number) = 16
2. fault with its handler enabled (UsageFault, divide by zero):
UsageFault: IPSR (exception number) = 6
UFSR/CFSR = 0x02000000
divide retried after the handler, result (was 99) = 0
3. same fault with its handler disabled:
HardFault: IPSR (exception number) = 3
HFSR = 0x40000000 CFSR = 0x02000000
4. PRIMASK set, then NMI, PendSV, SysTick and IRQ0 are all requested:
NMI: IPSR (exception number) = 2
releasing PRIMASK
PendSV: IPSR (exception number) = 14
SysTick: IPSR (exception number) = 15
external IRQ0: IPSR (exception number) = 16
5. svc executed while PRIMASK is set:
HardFault: IPSR (exception number) = 3
HFSR = 0x40000000 CFSR = 0x00000000
Reading the register pokes: SHCSR (System Handler Control and State Register) bit 18, USGFAULTENA, enables the UsageFault handler. CCR (Configuration and Control Register) bit 4, DIV_0_TRP, makes an integer divide by zero raise a fault instead of silently returning 0. ICSR (Interrupt Control and State Register) bit 28 (PENDSVSET) pends PendSV, bit 26 (PENDSTSET) pends SysTick and bit 31 (NMIPENDSET) pends the NMI; pending means requested but not yet running. Writing the CFSR or HFSR value back clears them, because their bits are sticky (they stay set until software writes a 1 to them). dsb and isb are barrier instructions that make sure the register write has completed before the next instruction. Decoding the printed values: CFSR 0x02000000 has only bit 25 set, which is UFSR bit 9, DIVBYZERO (the divide-by-zero cause); HFSR 0x40000000 has only bit 30 set, FORCED, meaning a configurable fault was escalated. In section 5 CFSR is 0 because an SVC is not a fault with its own status bit; only FORCED explains it. The HardFault handler there only clears PRIMASK so the program can finish: no SVCall line follows it in the output, so the SVC is not re-run in this run.
Section 2 shows a fault with its handler enabled; the divide was retried after the handler turned the trap off, so q changed from 99 to 0. Section 3 shows the same fault with the UsageFault enable bit cleared: it arrives as HardFault, with the FORCED bit (bit 30 of HFSR, 0x40000000) saying it was escalated and CFSR still naming the divide-by-zero. Section 5 shows that an SVC executed under PRIMASK does not reach the SVCall handler: a synchronous exception that cannot be taken because of its priority becomes a HardFault (the manual's exception-subtype table says the same for SVCall).
Maskability
PRIMASK blocks every exception whose priority is configurable and leaves the fixed-priority ones running:
| Exception | Number | Priority | Blocked by PRIMASK |
|---|---|---|---|
| Reset | 1 | -3, fixed | No |
| NMI | 2 | -2, fixed | No (ran in section 4) |
| HardFault | 3 | -1, fixed | No (ran in section 5) |
| SVCall | 11 | configurable | Yes: escalates to HardFault when issued (section 5) |
| PendSV | 14 | configurable | Yes: stays pending, runs on release (section 4) |
| SysTick | 15 | configurable | Yes: stays pending, runs on release (section 4) |
| External IRQs | 16 and up | configurable | Yes: stay pending, run on release (section 4) |
The fixed priorities are from the manual's exception table; the "ran" and "stays pending" entries are what the program printed. FAULTMASK, a stronger mask than PRIMASK (set with cpsid f), makes the code run at HardFault priority, so only NMI and Reset can preempt it.
What a production fault handler does
It should not return. It saves the stacked PC and LR, CFSR, HFSR and the fault address registers (MMFAR and BFAR) to a RAM area that survives reset, then resets the system (or enters a safe state), so the next boot can report what happened.
Implement a ring buffer in C for a memory-constrained microcontroller: a fixed-size array whose size is a power of two, with enqueue/dequeue safe to call from both interrupt and normal context. Explain how you detect full-versus-empty without a separate count variable, and how you would shrink the index footprint further (for example to 16-bit indices) if RAM is extremely tight.
Sample Answer
Direct answer
Give the buffer two free-running counters, head and tail, that only ever increment (never masked back into range) and mask them with & (N-1) purely to index into the array; since N is a power of two, this lets tail - head (computed in the counters' own wrapping integer width) give the exact number of stored elements without a separate count variable. The buffer is empty when head == tail and full when tail - head == N, both computed directly from the two counters, and the same trick works if the counters are shrunk to 16-bit width, as long as N still divides that width's wraparound point (for a power-of-two N, it always does).
Structured elaboration
The free-running-counter trick
Rather than storing head and tail as values already wrapped into [0, N), let them keep counting upward indefinitely (they wrap naturally when the integer type itself overflows, for example at 256 for uint8_t). Use the masked value (head & (N-1)) only when indexing into the array. Because N is a power of two, tail - head computed in that same wrapping arithmetic gives exactly the number of elements currently stored, regardless of how many times the counters have individually wrapped, as long as the true count never exceeds the counter type's range. Full is tail - head == N; empty is tail - head == 0, i.e. head == tail. This is the interrupt-service-routine (ISR, the short function a microcontroller runs when a hardware interrupt fires) friendly version of the fix, because a single producer (the ISR) and a single consumer (the main loop) can each own one counter without ever writing the other's counter, avoiding a shared count variable that both sides would need to update atomically.
Interrupt-safety for single-producer single-consumer
If the producer runs in an ISR and the consumer runs in normal (non-interrupt) context, and each side only ever writes its own counter (producer writes tail, consumer writes head) and only reads the other's, no lock is needed as long as: the counter type is read and written atomically by the target architecture (true for a single machine word on essentially all microcontrollers), and the compiler is told not to reorder or cache those reads (mark head and tail volatile). If a second producer or consumer is added on either side, that single-writer guarantee breaks, and real synchronization (disabling interrupts briefly, or a proper lock) becomes necessary.
Shrinking the index footprint
If even two full-width counters are too much RAM, the same free-running-counter trick works with 16-bit (or 8-bit) counters, provided N remains a power of two: the wraparound point of the counter type itself becomes the modulus, so tail - head in 16-bit arithmetic still correctly reports the count as long as it never exceeds 65535. Shrinking further to 8-bit counters (as in the code below) caps the maximum distinguishable count at 255, which is a real constraint to check against the largest N you will ever configure.
Worked example
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#define N 8 /* power of two */
#define MASK (N - 1)
typedef struct {
uint8_t buf[N];
uint8_t head; /* next byte to read */
uint8_t tail; /* next slot to write */
} ring_t;
/* Called from normal (non-ISR) context: the consumer. */
bool ring_dequeue(ring_t *r, uint8_t *out) {
if (r->head == r->tail) return false; /* empty */
*out = r->buf[r->head & MASK];
r->head++;
return true;
}
/* Called from ISR or normal context: the producer. */
bool ring_enqueue(ring_t *r, uint8_t b) {
uint8_t next_tail = r->tail + 1;
if ((uint8_t)(next_tail - r->head) > N) return false; /* full */
r->buf[r->tail & MASK] = b;
r->tail = next_tail;
return true;
}
int main(void) {
ring_t r = {0};
for (uint8_t i = 0; i < 8; i++) {
bool ok = ring_enqueue(&r, i);
printf("enqueue %u -> %s\n", i, ok ? "ok" : "full");
}
bool overflow = ring_enqueue(&r, 99);
printf("enqueue 99 -> %s\n", overflow ? "ok" : "full");
uint8_t v;
while (ring_dequeue(&r, &v)) {
printf("dequeue -> %u\n", v);
}
return 0;
}
Compiling and running this (clang -std=c11 -Wall -Wextra, no warnings) prints:
enqueue 0 -> ok
enqueue 1 -> ok
enqueue 2 -> ok
enqueue 3 -> ok
enqueue 4 -> ok
enqueue 5 -> ok
enqueue 6 -> ok
enqueue 7 -> ok
enqueue 99 -> full
dequeue -> 0
dequeue -> 1
dequeue -> 2
dequeue -> 3
dequeue -> 4
dequeue -> 5
dequeue -> 6
dequeue -> 7
With N=8, the buffer accepts exactly 8 enqueues before tail - head == 8 == N makes the 9th (99) report full, and draining afterward returns the original 8 values in first-in-first-out order, confirming both the wraparound (indices computed via & MASK) and the full/empty detection (computed via the raw counter difference) are correct.
Complexity
Time: O(1) for enqueue and dequeue. Space: O(N) for the data array, plus two small fixed-width counters, no separate count variable and no wasted slot.
Edge cases
- Enqueue on a full buffer and dequeue on an empty buffer both fail cleanly (return false) rather than corrupting head or tail.
- N must be a power of two for the mask-based indexing to be correct; a non-power-of-two N requires a true modulo operation instead, which is slower and not needed here.
- The counter width must be large enough that the true element count never exceeds it; with 8-bit counters and N=8, this is comfortably satisfied, but shrinking further while keeping N the same removes that margin.
- If a second producer is later added while the buffer is still designed for one, both producers writing the shared tail counter without synchronization is a race condition, not a variant of the existing design.
Trade-offs & pitfalls
The free-running-counter trick is preferable to the classic "reserve one slot" fix in an embedded context, because it wastes zero capacity and needs no branch on a comparison against capacity - 1; the cost is that it depends on the counter type actually wrapping the way the arithmetic assumes, which must be double-checked against the compiler's integer-promotion rules (a uint8_t subtraction can be promoted to int before the wraparound happens, so the subtraction and comparison should be done, or cast back, in the original unsigned width). A common wrong turn in the ISR-safety framing is assuming that "no lock is used" means "no synchronization discipline is needed": the single-writer-per-counter invariant, and the volatile qualifier that stops the compiler from caching stale copies of head or tail in a register, are both still required, and dropping either one reintroduces the exact race the design was meant to avoid.
What is the difference between a race condition and a data race? Give a small example of each, and explain why code can be free of data races and still contain a race condition.
Sample Answer
Direct answer
A data race is a memory-level fact: two threads access the same memory location at the same time with no ordering between them, at least one access is a write, and the accesses are not both atomic (an atomic access is one the language guarantees happens as a single indivisible step that other threads see either completely or not at all, such as a C11 atomic_int operation; a plain int access is not). In C and C++ the language definition makes the whole program's behaviour undefined if one occurs. A race condition is a logic-level fact: the program's correctness depends on the timing or interleaving of operations, so some interleavings produce a wrong result. A program can have either without the other: you can lock every single access (no data race) and still check a balance in one critical section and withdraw in another (race condition).
The precise definitions
In plain words for the next paragraph: an evaluation is one execution of an expression, such as a read or a write of a variable; a memory location is a variable (or a distinct piece of one) that has its own address; and undefined behaviour means the language places no limit on what the program does. cppreference's statement of the C++ memory model says two evaluations conflict if one modifies a memory location and the other reads or modifies the same location, and a program with two conflicting evaluations has a data race unless both run on the same thread (or in the same signal handler), both are atomic operations, or one happens-before the other. It also says: "If a data race occurs, the behavior of the program is undefined." (Happens-before is the ordering a mutex unlock/lock pair, a thread join, or an atomic release/acquire pair gives you: everything before the unlock is visible after the matching lock.)
| Data race | Race condition | |
|---|---|---|
| Level | Memory accesses (language rule) | Program logic (an invariant about outcomes) |
| Definition | Conflicting accesses, no happens-before, not both atomic | Outcome depends on timing of operations |
| Consequence in C/C++ | Undefined behaviour (compiler may assume it never happens) | A wrong but well-defined result |
| Found by | Race detectors such as ThreadSanitizer (TSan) | Reasoning about invariants, stress tests, review |
| Fixed by | Making accesses atomic or ordering them with a lock | Making the check and the act one atomic step |
Worked example: both bugs in one program, run in a Linux container
One file, two parts. Part 1 is a data race (two threads increment a plain int). Part 2 is a race condition with no data race: every access to balance is under a mutex, but the check and the withdrawal are separate critical sections. A barrier forces both threads to finish their check before either acts, so the bad interleaving happens on every run instead of rarely.
#include <pthread.h>
#include <stdio.h>
/* Part 1: a data race. Two threads write the same int with no synchronization. */
static int hits = 0;
static void *bump(void *arg) { (void)arg; for (int i = 0; i < 100000; i++) hits++; return NULL; }
/* Part 2: a race CONDITION with no data race. Every access is under the mutex,
but check and act are in separate critical sections. */
static pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
static pthread_barrier_t both_checked;
static int balance = 100;
static int withdraw(int amt) {
pthread_mutex_lock(&m);
int ok = balance >= amt; /* check */
pthread_mutex_unlock(&m);
pthread_barrier_wait(&both_checked); /* force the bad interleaving for the demo */
if (!ok) return 0;
pthread_mutex_lock(&m);
balance -= amt; /* act on a stale check */
pthread_mutex_unlock(&m);
return 1;
}
static void *w(void *arg) { (void)arg; withdraw(80); return NULL; }
int main(void) {
pthread_t a, b;
pthread_create(&a, NULL, bump, NULL); pthread_create(&b, NULL, bump, NULL);
pthread_join(a, NULL); pthread_join(b, NULL);
printf("hits = %d (expected 200000)\n", hits);
pthread_barrier_init(&both_checked, NULL, 2);
pthread_create(&a, NULL, w, NULL); pthread_create(&b, NULL, w, NULL);
pthread_join(a, NULL); pthread_join(b, NULL);
printf("balance = %d (should never be negative)\n", balance);
return 0;
}
Compiled and run with gcc:14 (GCC 14.4, aarch64 Linux container), five runs of gcc -O1 -pthread race.c -o r && ./r (each run prints both lines; the hits line is timing-dependent, so your five runs will differ):
hits = 100000 (expected 200000)
balance = -60 (should never be negative)
hits = 100000 (expected 200000)
balance = -60 (should never be negative)
hits = 100000 (expected 200000)
balance = -60 (should never be negative)
hits = 200000 (expected 200000)
balance = -60 (should never be negative)
hits = 100000 (expected 200000)
balance = -60 (should never be negative)
Note the fourth run: the plain int race printed the "right" answer once. That is the point of the next paragraph: the program is wrong on every run, and only the symptom varies.
Why 100000 in four of five runs at -O1? A register is a storage cell inside the CPU that is much faster than memory. The compiler is allowed to assume no data race, so it kept the counter in a register (it hoisted the load and store out of the loop, meaning it moved them before and after the loop instead of repeating them every iteration): the generated bump loads hits once, adds 100000, and stores once (I read the gcc -O1 -S output: one ldr, one str, a register loop between them). Walk through it with illustrative timing: thread A loads hits (0) into a register and adds 1 a hundred thousand times in the register, so the register holds 100000, then stores 100000 to memory; thread B did the same, starting from its own load of 0, and stores 100000 too. If the two threads overlap, both loaded 0, so whichever store lands last writes the same 100000 and one thread's whole contribution is overwritten. If one thread happens to finish completely before the other starts (thread start-up is slow compared with a 100000-iteration register loop, but it can happen, as in the fourth run), the second loads 100000 and stores 200000 and the symptom disappears for that run. So the result is 100000 or 200000 depending on timing, never a reliable total. In the ldr/str reading, ldr is the Arm instruction that loads from memory into a register and str stores a register back, so seeing only one of each around the loop is the evidence that the counter lived in the register. At -O0 the same program loses a variable amount: three runs printed 118833, 135721 and 125027. Both are "correct" outcomes of undefined behaviour, which is the practical meaning of UB: you cannot predict the symptom.
Under TSan (gcc -O1 -g -fsanitize=thread -pthread race.c -o rt && ./rt) the first part is reported as a data race at race.c:6 in bump (a read and a previous write by the two threads) and the count prints 200000, because instrumentation changes the code the compiler generates. A TSan data-race report names the kind of problem, then gives two blocks, one for the access that triggered it (read or write, its thread, its function and file:line) and one for the earlier conflicting access in the other thread, plus the location of the variable; two accesses to one address from two threads with no ordering between them is the whole diagnosis. The summary line is ThreadSanitizer: reported 1 warnings. Part 2 produced balance = -60 in that run too, and TSan said nothing about it: the accesses are all ordered by the mutex, so there is no data race to report. TSan's documentation describes the tool as one that "detects data races", so a clean TSan run says nothing about check-then-act bugs.
Why -60: both withdrawals checked 100 >= 80 before either subtracted, then 100 - 80 - 80 = -60. The fix is to make check and update one critical section (or a compare-and-swap loop on the balance):
lock; if (balance >= amt) balance -= amt, ok = 1; unlock
Why code can be free of data races and still be wrong
Synchronizing each variable protects the memory, not the rule that relates several operations. Typical shapes: check-then-act (above), read-modify-write split across two lock regions, "if absent then insert" on a locked map, two separately atomic variables that must change together, and iterating a collection whose size was read earlier.
The same race between a task and an interrupt service routine (ISR)
A counter updated by both a task and an ISR is the same defect. volatile stops the compiler from caching the variable, but cppreference notes that volatile access is suitable for communication with a signal handler, "but not with another thread of execution". count++ is still a load, an add and a store, and an ISR that fires between the load and the store loses an update; the fix is a short critical section (a stretch of code only one thread or interrupt handler may be inside at a time) with interrupts masked, or a hardware atomic read-modify-write where the core has one.
Trade-offs and pitfalls
- "Benign" data races do not exist in C/C++: even a racy flag can be hoisted out of a loop, as the register-resident counter above shows.
- Removing a data race with atomics does not fix a race condition; ask what invariant ties the operations together.
- Do not rely on a test passing: with a two-instruction window, a failure may need millions of iterations; use TSan for data races and invariant checks plus forced interleavings (as the barrier does) for logic races.
Design a CAN bus architecture for a distributed real-time control system with 20 ECUs sending periodic control messages and occasional emergency messages that must preempt normal traffic. Include message prioritization, bus loading analysis, fault containment, and diagnostics you would implement.
Sample Answer
Requirements & assumptions
- 20 ECUs, each periodic control messages (typ. 10–100 ms), emergency messages must preempt.
- Classical CAN (or CAN FD) at 500 kb/s (or 2 Mb/s for FD).
- Hard real-time deadlines known per message.
High-level architecture
- Single CAN bus with 3 protected segments via high-speed transceivers and terminating resistors; optional gateway ECU for segmentation/failover.
- Use CAN IDs for static priority (lower numeric ID = higher priority). Reserve ID ranges:
- 0x000–0x0FF: Emergency/heartbeat preemptive
- 0x100–0x3FF: High-rate control
- 0x400–0x7FF: Low-rate telemetry
Message prioritization & arbitration
- Assign top 8 IDs to emergency classes (e.g., brake cut, fault stop). Configure each ECU to use emergency ID only on assertion; emergency frames are short and retransmitted with backoff.
- Periodic messages scheduled with static offsets to avoid coincident arbitration losing. Use time-triggered slotting (TT-CAN) for tight determinism or staggered periodic offsets.
Bus loading analysis
- Use utilization U = sum( C_i / T_i ), where C_i is transmission time (including worst-case arbitration and ACK).
- Example: 500 kb/s, 8 byte payload, CAN frame ~128 bit -> C_i ≈ 256 μs. For 20 ECUs at 50 ms: U ≈ 20*(0.000256/0.05)=0.102 ~10.2% — safe headroom for emergency bursts.
- Ensure U < ~50% for mixed-critical systems; use CAN FD or higher bitrate if near limit.
C_i = (bits_per_frame) / bitrate
U = sum( C_i / T_i )
Fault containment
- Hardware: per-ECU transceivers with bus-off recovery policy, isolating transceivers with FET switches on repeated errors.
- Software: monitor error counters; force ECU into Listen-Only or bus-off on persistent faults; gateway to quarantine misbehaving node by filtering its IDs.
- Use CRC checks, sequence counters in payload for ECUs to detect silent failures or replay.
Diagnostics & monitoring
- Central logger ECU sampling bus load, error counters (TEC, REC), and arbitration losses; expose diagnostics via UART/OTA.
- Health messages: periodic heartbeat IDs; NACK/ack protocol for critical commands.
- Implement on-ECU self-tests reporting via diagnostic IDs (DTCs). Store event timestamps for post-mortem.
- Watchdog integration: if heartbeat missed > N thresholds, trigger safe state.
Trade-offs
- Single bus simplicity vs. segmentation for safety. Use CAN FD + TT scheduling for high utilization/determinism.
You're juggling an urgent request from security and a feature sales needs for a big demo, both today. How do you decide what goes first and communicate that back to both sides?
Sample Answer
Direct answer
When an urgent security issue and a sales-critical demo land the same day, the deciding factor is exposure, not who asked more forcefully: what could go wrong if the security issue waits, and what can still be preserved for the demo without touching the risky path. Usually both can be partially served: contain or fix the security issue first, and give sales something real to show that doesn't depend on the vulnerable code.
Structured elaboration
1. Triage both in parallel, fast
Read the security bulletin and the demo request together. Identify exactly which services, data, or endpoints the vulnerability touches, and exactly what the demo needs to show.
2. Weigh exposure, not urgency of the ask
A security issue usually carries broader exposure (any affected customer, potential data risk) than a single demo (one prospective deal). That asymmetry is normally the tiebreaker, but it should be checked rather than assumed: a demo that's the last step before a major renewal can occasionally weigh more than a low-severity, well-contained finding.
3. Look for a path that serves both
A scoped hotfix with a canary rollout (releasing the fix to a small slice of traffic first, watching it closely, then rolling out to everyone once it looks clean) for the security issue, paired with a sandboxed or stubbed version of the feature for the demo, often means sales isn't actually blocked on the mainline fix landing first.
4. Communicate the decision and the reasoning immediately
Both sides need a concrete plan with timestamps, not just a priority call: what's happening, by when, and what the other side gets in the meantime.
Worked example
| Factor | Security issue | Demo request |
|---|---|---|
| Who's exposed | Any customer using the affected service | One prospective account |
| Risk if delayed | Potential data or access exposure | Deal risk, reschedulable |
| Fix effort | Scoped patch plus canary rollout | Sandboxed feature stub |
| Decision | Goes first | Served via a safe workaround, in parallel |
The patch ships to a small share of traffic first while being monitored, then rolls out fully once confirmed clean. In parallel, a second engineer builds a stubbed version of the requested feature specifically for the demo environment, so sales can present it without depending on the code currently under remediation. Both sides get an update within a couple of hours: security gets an ETA for full rollout, sales gets confirmation the demo will work and exactly how.
Trade-offs and pitfalls
- Defaulting to whichever request comes from the louder or more senior stakeholder, rather than actual exposure, is the most common failure mode here.
- Building a demo-only workaround without labeling it clearly as temporary risks it quietly becoming the real implementation, skipping the proper fix.
- Failing to give both sides a concrete timeline turns a reasonable prioritization call into a trust problem, even when the call itself was correct.
- Treating this as strictly either/or, instead of looking for a path that partially serves both, wastes an option that's usually available.
Compare C-style manual resource cleanup with RAII in C++. In a codebase where exceptions are disabled, what idiomatic patterns manage resources deterministically, and what would a small RAII wrapper look like?
Sample Answer
Direct answer
C-style cleanup is manual: acquire resources, and on every exit path (success, each early return, each error) release exactly the ones already acquired, usually by jumping to one goto out; label at the end. RAII (resource acquisition is initialisation) ties each resource's release to an object's destructor. A destructor is a function the language calls automatically when an object's lifetime ends, and for a local variable that happens when it leaves its scope (the { } block it was declared in). So the release runs on every path, in reverse order of construction. Turning exceptions off (-fno-exceptions) removes only exception unwinding, which is the compiler-generated cleanup that runs destructors while an exception travels up the call stack; destructors still run on return, break, goto and falling off the end of a scope, so RAII keeps working. What exceptions-off changes is how failure is reported: constructors cannot throw, so you use a factory (a static function that builds and returns the object) that returns an empty or failed object, check it, and keep destructors that cannot fail. The small wrapper below is a move-only owner of a FILE* (move-only means it cannot be copied, only handed over, so there is never a second owner), plus std::unique_ptr with a custom deleter (a small function object telling the pointer how to release this kind of resource) for a malloc buffer.
Structured comparison
C: single-exit goto | C++: RAII objects | |
|---|---|---|
| Who releases | the programmer, at the label | the destructor, by the language |
New early return added later | easy to forget cleanup (leak) | still correct, nothing to update |
| Order | you write reverse order by hand | automatic reverse of construction |
| Ownership transfer | a convention in comments | a move-only type or unique_ptr, enforced by the compiler |
| Partial acquisition | NULL-initialise everything, free what is non-null | an object that failed to acquire is empty, its destructor does nothing |
Patterns that work without exceptions
Patterns 1 to 3 cover most code; 4 to 6 handle particular situations.
- Scope-owned wrapper per resource (the
Fileclass below): constructor or factory acquires, destructor releases, copying is deleted, moving transfers ownership. std::unique_ptr<T, Deleter>for any C handle: a deleter functor callsfree,fclose,close,munmap.- Fallible construction through a factory (fallible: it can fail):
static File open(path, mode)returns an object that is empty on failure; the caller tests it (if (!f) ...). No constructor ever needs to fail. - Explicit status where close can fail: a destructor cannot report an error, so give the class a
close()that returns thefclosestatus for code that cares (writes to disk), and let the destructor be the safety net. The second example below shows it. - Scope guard (a tiny object running a lambda, i.e. a small inline function, in its destructor) for one-off cleanups that do not deserve a class; the second example below shows one. Arenas and pools (one object that owns many allocations and releases them all in one place) fit when many small objects share a lifetime.
- Allocation failure: use the
std::nothrowform ofnew(the version that returns a null pointer instead of throwing) ormalloc, and test the result, since there is no handler to throw to. A function markednoexceptpromises not to throw, which is what the move operations below declare.
Worked example
Compiled with g++ -std=c++17 -O2 -fno-exceptions -Wall -Wextra -fsanitize=address,undefined raii.cpp (GCC 14, Linux; run in a container). The C-style function is compiled as C++ here only so both styles share one file; in a C project it is plain C.
// build: g++ -std=c++17 -fno-exceptions -Wall -Wextra raii.cpp
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <utility>
// 1. C-style: one exit label, cleanup in reverse order of acquisition
int process_c(const char* path) {
int rc = -1;
FILE* f = nullptr;
char* buf = nullptr;
f = std::fopen(path, "r");
if (!f) goto out;
buf = static_cast<char*>(std::malloc(64));
if (!buf) goto out;
if (!std::fgets(buf, 64, f)) goto out;
rc = 0;
out:
std::free(buf); // free(NULL) is a no-op
if (f) std::fclose(f);
return rc;
}
// 2. Small RAII wrapper: owns one FILE*, move-only, no exceptions
class File {
public:
File() = default;
static File open(const char* path, const char* mode) { File f; f.fp_ = std::fopen(path, mode); return f; }
File(const File&) = delete;
File& operator=(const File&) = delete;
File(File&& o) noexcept : fp_(std::exchange(o.fp_, nullptr)) {}
File& operator=(File&& o) noexcept { if (this != &o) { reset(); fp_ = std::exchange(o.fp_, nullptr); } return *this; }
~File() { reset(); }
explicit operator bool() const { return fp_ != nullptr; }
FILE* get() const { return fp_; }
private:
void reset() { if (fp_) { std::fclose(fp_); std::puts(" (File closed)"); fp_ = nullptr; } }
FILE* fp_ = nullptr;
};
// 3. unique_ptr with custom deleter for a C handle
struct FreeDeleter { void operator()(void* p) const { std::free(p); std::puts(" (buffer freed)"); } };
using CBuf = std::unique_ptr<char, FreeDeleter>;
int process_cpp(const char* path) {
File f = File::open(path, "r");
if (!f) return -1; // nothing to clean by hand
CBuf buf(static_cast<char*>(std::malloc(64)));
if (!buf) return -1;
if (!std::fgets(buf.get(), 64, f.get())) return -1; // early return: both destructors still run
std::printf(" read: %s", buf.get());
return 0;
}
int main() {
std::FILE* t = std::fopen("sample.txt", "w"); std::fputs("hello\n", t); std::fclose(t);
std::printf("C style rc=%d\n", process_c("sample.txt"));
std::printf("RAII rc=%d\n", process_cpp("sample.txt"));
std::printf("RAII missing file rc=%d\n", process_cpp("nope.txt"));
}
C style rc=0
read: hello
(buffer freed)
(File closed)
RAII rc=0
RAII missing file rc=-1
Reading it: in process_cpp, f was constructed before buf, and the output shows (buffer freed) before (File closed), so destruction ran in reverse order of construction with no code written for it. In the missing-file call the function returned before buf existed; the empty File destructor printed nothing, because it had nothing to close. No leak report appeared from the sanitizer run. The goto out version works too, but each new resource and each new early exit is a place to make a mistake.
The non-obvious lines of File:
std::exchange(o.fp_, nullptr)storesnullptrino.fp_and returns the old value (cppreference: "Replaces the value ofobjwithnew_valueand returns the old value ofobj"). In the move constructor it takes the handle and leaves the source empty, so only one object will ever close it.File(File&& o) noexceptis the move constructor;noexceptpromises it never throws, which it cannot, since it only copies a pointer.reset()closes the file if there is one and sets the pointer to null, so calling it twice is harmless. The destructor and the move assignment both use it.explicit operator bool()letsif (!f)ask "did the open succeed?";explicitstops aFilefrom silently converting to a number elsewhere.
Scope guard and a checked close
The same approach applies to a one-off cleanup and to a close that can fail. Built the same way as above (g++ -std=c++17 -O2 -fno-exceptions -Wall -Wextra -fsanitize=address,undefined, GCC 14, Linux):
#include <cstdio>
#include <utility>
// Runs a callable when the object leaves scope.
template <class F>
class ScopeGuard {
public:
explicit ScopeGuard(F f) : f_(std::move(f)) {}
ScopeGuard(const ScopeGuard&) = delete;
ScopeGuard& operator=(const ScopeGuard&) = delete;
~ScopeGuard() { f_(); }
private:
F f_;
};
// A file wrapper whose close() reports the fclose result.
class OutFile {
public:
OutFile() = default;
OutFile(const OutFile&) = delete;
OutFile& operator=(const OutFile&) = delete;
OutFile(OutFile&& o) noexcept : fp_(std::exchange(o.fp_, nullptr)) {}
static OutFile open(const char* path) { OutFile f; f.fp_ = std::fopen(path, "w"); return f; }
explicit operator bool() const { return fp_ != nullptr; }
std::FILE* get() const { return fp_; }
int close() { // 0 on success, EOF on failure; safe to call twice
if (!fp_) return 0;
int rc = std::fclose(fp_);
fp_ = nullptr;
return rc;
}
~OutFile() { close(); } // safety net: result ignored here
private:
std::FILE* fp_ = nullptr;
};
int save(const char* path) {
OutFile out = OutFile::open(path);
if (!out) return -1;
ScopeGuard log([] { std::puts(" (save() finished)"); });
std::fputs("data\n", out.get());
return out.close() == 0 ? 0 : -2; // the caller learns whether the flush worked
}
int main() {
std::printf("save rc=%d\n", save("out.txt"));
std::printf("save to missing dir rc=%d\n", save("no_such_dir/out.txt"));
}
(save() finished)
save rc=0
save to missing dir rc=-1
The guard's lambda ran when save returned, without any cleanup call in the body. The checked close() returns the fclose result, so a failed flush becomes the return code -2 instead of being lost. The missing directory made open fail, and the early return -1 ran no guard because it had not been constructed yet.
Pitfalls
- Copying a handle wrapper would double-close the same
FILE*; that is why copy is= deleteand move usesstd::exchangeto null the source. - A destructor that does real work and can fail has nowhere to report it with exceptions off; keep it to the release call and expose
close()for checked shutdown. - Skipped destructors: RAII does not run on
exit()called mid-function,abort(),_exit()or a crash, andlongjmp(the C function that jumps straight back to an earlier saved point, abandoning the frames in between) over C++ frames is undefined behaviour if it skips non-trivial destructors (destructors that do real work). Return error codes up the stack instead. - Two-phase initialisation (default-construct then
init()) recreates the C problem of half-built objects; the factory approach avoids it. - Mixing styles: when a C API requires a callback with a raw pointer, keep the owner object alive in the caller's scope and pass
.get().
Judgement
In a codebase with exceptions disabled, commit to RAII wrappers with factory-style construction and explicit status codes; keep the goto cleanup idiom only in actual C files or in a C library you must match. If a resource is used once in a tiny function, a goto is fine; as soon as there are two resources or more than one exit, wrap them.
On an 8-bit AVR microcontroller, show how to safely read and write a 16-bit shared variable that can be modified in an ISR. Provide concise C examples using cli()/sei() (or equivalent atomic block macros) and discuss pros and cons of disabling interrupts briefly versus other synchronization techniques.
Sample Answer
Approach (brief)
On 8-bit AVR a 16-bit variable is not atomic; an ISR can interrupt a multi-byte access. Safest simple method is to disable interrupts around the read/write or use AVR-provided atomic macros.
Example — disable/restore interrupts (cli()/sei())
#include <avr/io.h>
#include <avr/interrupt.h>
volatile uint16_t shared = 0;
uint16_t read_shared(void) {
uint16_t val;
uint8_t sreg = SREG; // save global interrupt flag
cli(); // disable interrupts
val = shared; // atomic read of 16-bit
SREG = sreg; // restore interrupts (restores I-bit)
return val;
}
void write_shared(uint16_t v) {
uint8_t sreg = SREG;
cli();
shared = v;
SREG = sreg;
}
Example — using <util/atomic.h>
#include <util/atomic.h>
uint16_t read_shared2(void) {
uint16_t val;
ATOMIC_BLOCK(ATOMIC_RESTORESTATE) {
val = shared;
}
return val;
}
Pros/Cons
- Disabling interrupts: simple, minimal code, deterministic. Con: increases interrupt latency; avoid long critical sections.
- Atomic macros: safer (handles SREG), clearer intent.
- Alternatives: use double-buffering + version counters or message queues/flags to avoid long disable periods; use minimal critical sections or task-level synchronization in RTOS. Those reduce latency but add complexity and possibly more memory.
Explain how the binary search algorithm works on a sorted array. Describe required preconditions, the standard iterative implementation steps, the loop invariants you would maintain, and its time and space complexity. Give two concrete examples of problems where binary search is appropriate and two where it is not, and explain why.
Sample Answer
Direct answer
Big-O notation says how the work grows with the number of items n: O(n) is proportional to n, O(log n) grows by one step each time n doubles, and O(1) is a fixed amount. Binary search finds a target in a sorted array by repeatedly looking at the middle element and throwing away the half that cannot contain the target. Each step halves the remaining window, so it takes O(log n) comparisons and O(1) extra space in its iterative form. It needs two preconditions: the data is sorted by the same ordering the comparison uses, and you can jump to any position in O(1) time (random access).
The idea in plain words
Think of guessing a number from 1 to 1000 when each answer is "higher" or "lower". Guess 500; if told "higher", you now know the number is in 501 to 1000 and never look at 1 to 500 again. Each guess removes half of what is left, so ten guesses are enough (2^10 = 1024). A sorted array gives exactly this: if the middle value is smaller than the target, then everything to its left is smaller too (that is what "sorted ascending" means), so the target cannot be there.
Preconditions
- The array is sorted in ascending order (or the comparison is flipped for descending). If it is not sorted, "everything to the left is smaller" is false and discarding half is wrong.
- Random access in O(1): the array must let you read
arr[mid]directly. A linked list does not. - Comparisons are consistent: the same ordering that sorted the data decides "less than" during the search. Sorting strings case-insensitively and searching case-sensitively breaks it.
- Duplicates are allowed, but then the plain version returns any matching index, not necessarily the first or last one.
Iterative implementation, step by step
- Keep a window
arr[lo..hi], both ends inclusive, starting as the whole array:lo = 0,hi = n - 1. - While the window is not empty (
lo <= hi), computemid = lo + (hi - lo) // 2. - If
arr[mid]equals the target, returnmid. - If
arr[mid]is smaller than the target, the target can only be to the right: setlo = mid + 1. Otherwise sethi = mid - 1. - When the loop ends, the window is empty, so return -1.
The loop invariant (a statement that is true before and after every iteration, which is what proves the loop correct): if the target is anywhere in the array, it is inside arr[lo..hi]. It holds at the start because the window is the whole array. Each update keeps it true because only positions that are provably too small (lo = mid + 1) or too big (hi = mid - 1) are dropped, and mid itself is excluded because it was just checked. It also guarantees the loop ends, because the window shrinks by at least one element each round. When the loop stops with lo > hi, the window is empty, and since the target would have to be inside it, the target is absent.
Writing mid = lo + (hi - lo) // 2 rather than (lo + hi) // 2 matters in languages with fixed-width integers: in a 32-bit signed int, lo + hi can exceed 2,147,483,647 once the array has more than 2^30 (1,073,741,824) elements, and in Java it then wraps to a negative number: with lo = 1_100_000_000 and hi = 1_200_000_000, (lo + hi) / 2 is -997,483,648 while lo + (hi - lo) / 2 is 1,150,000,000. In C and C++ the signed overflow is undefined behaviour. Python integers never overflow, so either form works there, but the safe form is the habit to keep.
Code
The function returns the index and the number of comparisons it made, and the driver prints lo, hi and mid at every step.
from typing import List, Tuple
def binary_search(arr: List[int], target: int, trace: bool = False) -> Tuple[int, int]:
"""Return (index or -1, number of comparisons with target).
Invariant: if target is in arr at all, it is inside arr[lo..hi] (inclusive).
"""
lo, hi = 0, len(arr) - 1
comparisons = 0
while lo <= hi:
mid = lo + (hi - lo) // 2
comparisons += 1
if trace:
print(f" lo={lo} hi={hi} mid={mid} arr[mid]={arr[mid]}")
if arr[mid] == target:
return mid, comparisons
if arr[mid] < target:
lo = mid + 1 # everything at or left of mid is too small
else:
hi = mid - 1 # everything at or right of mid is too big
return -1, comparisons # lo > hi: the window is empty, so target is absent
if __name__ == "__main__":
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("search 23 in", arr)
print(" result:", binary_search(arr, 23, trace=True))
print("search 40 (absent):")
print(" result:", binary_search(arr, 40, trace=True))
cases = [
("empty", [], 5),
("one element, hit", [7], 7),
("one element, miss", [7], 3),
("all equal, hit", [4, 4, 4, 4], 4),
("target absent", arr, 40),
("target at left end", arr, 2),
("target at right end", arr, 91),
("smaller than all", arr, -1),
("larger than all", arr, 1000),
]
print("\nedge cases")
for name, data, t in cases:
idx, c = binary_search(data, t)
ok = (data[idx] == t) if idx != -1 else (t not in data)
assert ok
print(f" {name:20s} -> index {idx}, comparisons {c}")
print("\nworst-case comparisons (target absent, larger than all)")
for n in (10, 1000, 1_000_000):
_, c = binary_search(list(range(n)), n + 5)
print(f" n={n:>9,}: {c} comparisons")
Run in a python:3.12 container, it prints:
search 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
lo=0 hi=9 mid=4 arr[mid]=16
lo=5 hi=9 mid=7 arr[mid]=56
lo=5 hi=6 mid=5 arr[mid]=23
result: (5, 3)
search 40 (absent):
lo=0 hi=9 mid=4 arr[mid]=16
lo=5 hi=9 mid=7 arr[mid]=56
lo=5 hi=6 mid=5 arr[mid]=23
lo=6 hi=6 mid=6 arr[mid]=38
result: (-1, 4)
edge cases
empty -> index -1, comparisons 0
one element, hit -> index 0, comparisons 1
one element, miss -> index -1, comparisons 1
all equal, hit -> index 1, comparisons 1
target absent -> index -1, comparisons 4
target at left end -> index 0, comparisons 3
target at right end -> index 9, comparisons 4
smaller than all -> index -1, comparisons 3
larger than all -> index -1, comparisons 4
worst-case comparisons (target absent, larger than all)
n= 10: 4 comparisons
n= 1,000: 10 comparisons
n=1,000,000: 20 comparisons
Worked trace
Searching for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]: the window starts as positions 0 to 9, mid is 4 and arr[4] is 16, which is smaller than 23, so lo becomes 5. The window 5 to 9 gives mid 7 and arr[7] is 56, larger, so hi becomes 6. The window 5 to 6 gives mid 5 and arr[5] is 23, a match: index 5 after 3 comparisons. Searching for the absent 40 follows the same first three steps, then the window shrinks to position 6 (value 38, smaller than 40), lo becomes 7 which is past hi = 6, and the function returns -1 after 4 comparisons.
Complexity
Time is O(log n): each round halves the window, so at most floor(log2 n) + 1 rounds are needed. The run shows 4 comparisons for n = 10, 10 for n = 1,000 and 20 for n = 1,000,000 in the worst case (target larger than everything), which matches that formula. Space is O(1): three integers and a counter. A recursive version would use O(log n) stack. The cost of sorting first, O(n log n), is only worth paying when many searches follow.
The mistakes listed at the end can be tried directly. The function below is the same search with one mistake switched on at a time, and gives up after 50 rounds so that a stuck loop shows up as loops; it runs on every array of 1, 2 and 3 elements (values 0 to n - 1) with every target from -1 to n.
def variant(arr, target, mistake=None, limit=50):
lo, hi = 0, len(arr) - 1
for _ in range(limit):
if (lo >= hi) if mistake == "lo < hi" else (lo > hi):
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid if mistake == "lo = mid" else mid + 1
else:
hi = mid if mistake == "hi = mid" else mid - 1
return "loops"
for mistake in (None, "lo < hi", "lo = mid", "hi = mid"):
bad = []
for n in (1, 2, 3):
data = list(range(n))
for target in range(-1, n + 1):
expected = target if 0 <= target < n else -1
got = variant(data, target, mistake)
if got != expected:
bad.append(f"n={n} target={target} -> {got}")
print(f"{str(mistake):9s}", bad if bad else "all correct")
Output (python:3.12):
None all correct
lo < hi ['n=1 target=0 -> -1', 'n=2 target=1 -> -1', 'n=3 target=0 -> -1', 'n=3 target=2 -> -1']
lo = mid ['n=1 target=1 -> loops', 'n=2 target=1 -> loops', 'n=2 target=2 -> loops', 'n=3 target=2 -> loops', 'n=3 target=3 -> loops']
hi = mid ['n=1 target=-1 -> loops', 'n=2 target=-1 -> loops', 'n=3 target=-1 -> loops']
Two problems where binary search fits
- Looking up an ID or timestamp in sorted data. A log file or table sorted by timestamp, searched for the first entry at or after a time: the order exists and positions are directly reachable, so 20 comparisons cover a million records. The same idea works on an answer space: to find the smallest speed at which a task finishes within a deadline, "finishes in time" is false below some speed and true above it, so you can binary search the speed values without any array. Both ideas run on small data below.
- Finding the first bad commit or build. If every commit after a certain one is bad and every commit before it is good, the sequence good...good, bad...bad is ordered by the property being tested, and testing the middle commit halves the range (this is how
git bisect, the Git command that finds the commit that introduced a bug, narrows down a regression). Testing is expensive, so using only about log2(n) tests instead of n matters a lot.
from bisect import bisect_left
# 1. First entry at or after a time, in a log sorted by timestamp (seconds since midnight).
stamps = [100, 160, 160, 250, 400, 900]
want = 200
i = bisect_left(stamps, want)
print(f"first entry at or after {want}: index {i}, timestamp {stamps[i]}")
# 2. Binary search on an answer space: smallest speed so that all piles are finished within 8 hours.
piles = [3, 6, 7, 11] # units of work; at speed s a pile takes ceil(pile / s) hours
deadline = 8
def hours(s):
return sum(-(-p // s) for p in piles)
lo, hi = 1, max(piles) # the answer is somewhere in 1..11; no array exists
while lo < hi:
mid = (lo + hi) // 2
ok = hours(mid) <= deadline
print(f"speed {mid:2d}: {hours(mid):2d} hours -> {'fast enough' if ok else 'too slow'}")
if ok:
hi = mid
else:
lo = mid + 1
print("smallest speed that finishes within", deadline, "hours:", lo)
Output (python:3.12):
first entry at or after 200: index 3, timestamp 250
speed 6: 6 hours -> fast enough
speed 3: 10 hours -> too slow
speed 5: 8 hours -> fast enough
speed 4: 8 hours -> fast enough
smallest speed that finishes within 8 hours: 4
The first part uses the library's bisect_left, which returns the first index whose value is at least the wanted time (the plain version above can only report an exact match, so it cannot answer "first at or after"). The second part never touches an array: the candidate speeds 1 to 11 act as the sorted range, "fast enough" is false below 4 and true from 4 up, and each probe (6, 3, 5, 4) halves the range until it is a single speed.
Two problems where it does not fit
- Unsorted data, such as a list of order IDs in arrival order. Learning that
arr[mid]is smaller than the target says nothing about the left half, because the left half is in no particular order, so you cannot discard anything. Use a linear scan (O(n)), or build a hash set (a structure that answers "is this value present?" in constant time on average) or dictionary once and get O(1) average lookups. Sorting first costs O(n log n), which only helps if you search many times. - A sorted singly linked list. The data is ordered, but there is no O(1) way to reach the middle: walking to
midcosts O(n) every round. The total becomes O(n) in pointer steps, no better than a plain scan, so the logarithmic advantage disappears. A skip list (a linked list with extra layers of forward links that skip over many nodes) or a balanced tree (a search tree whose height stays about log n) restores it, because they add the shortcuts a list lacks.
Edge cases and common mistakes
The run covers an empty array (0 comparisons, -1), one element (hit and miss), all-equal values (returns an index of a match, here 1, not the first), absent targets, targets at both ends, and values smaller or larger than everything.
- Using
lo < hiinstead oflo <= hiskips the last one-element window and misses targets such as the sole element or the last candidate (thelo < hirow of the mistakes run). - Setting
lo = midorhi = midinstead ofmid + 1/mid - 1can loop forever. The window of one element is already enough:midequalsloand the update leaves the window unchanged. Withlo = mida window of two elements sticks too (thelo = midandhi = midrows of the mistakes run). - Computing
(lo + hi) / 2with overflow in fixed-width integers, shown above. - Running it on unsorted data and trusting the answer; there is no error, just wrong output.
- Expecting the first or last duplicate from the plain version.
Running the code
python:3.12, standard library only.
Save the listing as binary_search.py and run: python binary_search.py
Recommended Additional Resources
- LeetCode (https://leetcode.com) - Focus on C/C++ problems, especially those tagged with arrays, linked lists, pointers, memory, and difficulty medium. Problems 1-300 are good for junior level preparation.
- Book: 'Embedded C Programming' by Mark Siegesmund - Practical embedded C patterns, memory management, and low-level concepts with real examples.
- Book: 'The Embedded Systems Book' by Jack Ganssle - Comprehensive overview of embedded systems design principles and best practices.
- Book: 'Computer Systems: A Programmer's Perspective' by Randal E. Bryant and David R. O'Hallaron - Low-level system concepts, assembly language, and memory hierarchy crucial for understanding embedded systems.
- Microcontroller Documentation - ARM Cortex-M Programming Guide, STM32 Reference Manuals, AVR Datasheets. Learning to read technical documentation is essential.
- FreeRTOS Official Documentation and Tutorials (https://www.freertos.org) - Practical RTOS learning with real examples and API reference.
- Development Boards and Simulators - Arduino (for beginners), STM32 Discovery boards, or TI Launchpad for hands-on embedded experience. Keil MDK or SEGGER Embedded Studio for professional IDEs.
- YouTube Channels - Embedded Systems and Peripheral Handling tutorials, microcontroller programming walkthroughs, and assembly language explanation videos.
- Online Courses - Coursera's 'Introduction to Embedded Systems' or 'Real-Time Operating Systems' courses. Udacity's 'Embedded Systems Fundamentals with ARM Cortex-M based Microcontrollers'.
- Bit Manipulation Practice - LeetCode bit manipulation problems, HackerRank bit manipulation challenges for strengthening low-level programming skills.
- HackerEarth and HackerRank - C/C++ programming challenges with embedded systems tags for targeted practice.
- SEGGER J-Link Debugger and SystemView - Industry-standard debugging tools with free educational versions for practicing embedded debugging.
- Practice Projects - Build a simple firmware for temperature monitoring using ADC, implement a small RTOS scheduler, create a device driver for a sensor, or develop IoT applications with limited resources to gain hands-on experience.
- Technical Interview Preparation - 'Cracking the Coding Interview' by Gayle Laakmann McDowell for behavioral and coding interview strategies applicable to technical interviews.
- Embedded Systems Communities - Embedded.fm podcast, EEVblog YouTube channel, and Embedded Systems Stack Exchange for staying current with industry trends and learning from experienced embedded engineers.
Search Results
How to Build Your Career in Embedded Software Engineering
Embedded software engineer interview questions are usually based on topics such as algorithms, system design, and embedded system concepts. As you start your ...
Top 50+ Software Engineering Interview Questions and Answers
Explain SDLC and its Phases? SDLC stands for Software Development Life Cycle. It is a process followed for software building within a software organization.
Meta Software Engineer Interview (questions, process, prep)
Ace the Meta software engineer interviews with this preparation guide. See updates to the interview process, example coding interview questions and ...
EMBEDDED C INTERVIEW QUESTIONS (0-2 YEARS EXP) - YouTube
Today we are going to crack the code on the most common questions and give you a solid blueprint for success.
50 Most Popular Salesforce Interview Questions & Answers ...
41. At a high level, can you describe the Software Development Lifecycle? · 42. Can you name a few ways to help improve Salesforce user adoption? · 43. What can ...
This interview preparation guide was generated using AI-powered research from the sources listed above. While we strive for accuracy, we recommend verifying critical information from official company sources.
Want to create your own tailored preparation guide using our deep research?
Get Started for FreeInterview-Ready Courses
Visual-first, interactive, structured learning paths
Browse Embedded Developer jobs
AI-enriched listings across hundreds of company career pages
Explore Jobs