All interview questions

Those layers need a stable ABI to assembly and to other languages, predictable codegen, no hidden allocations or exceptions, and a culture of explicit lifetime. The existing corpus (Linux, bionic, bootloaders, radio firmware) is C. C++ can wrap it (see C++) but the kernel and most firmware stay C by policy. Interviews want that layered picture: app/Java on top, native/HAL in the middle, kernel C below — see Linux kernel & BSP.

Open in C Language →

The preprocessor expands #include, macros and conditionals into one translation unit of C text. The compiler turns that into assembly for the target. The assembler emits an object file: machine code, symbols and relocations. The linker assigns addresses, patches relocations, pulls in static archives or records shared-library dependencies, and writes the executable or .so. The compiler never sees your other .c files; only the linker does.

Open in C Language →

A source file after preprocessing: every included header is pasted in, macros are expanded, and inactive #ifdef arms are gone. That blob is what the compiler type-checks and compiles to one .o. Two translation units communicate only through the linker (external symbols) and through the ABI of the types they share via headers.

Open in C Language →

Headers: prototypes, struct/enum/typedef, extern data declarations, macros, static inline helpers, include guards. Sources: function bodies with external linkage, the single definition of each global, file-scope static helpers. A non-inline function defined in a header is copied into every unit and usually becomes a multiple-definition error.

Open in C Language →

A declaration introduces a name and a type. A definition is the declaration that reserves storage or provides the function body. extern int n; declares; int n = 3; defines. A prototype declares a function; the body defines it. You may declare many times; you define an external object or function once (C also has tentative definitions for uninitialised file-scope objects).

Open in C Language →

A static library (.a) is an archive of object files. The linker copies the members it needs into your image; after that there is no runtime dependency on the archive. A shared library (.so) is a separate PIC image the dynamic linker loads; many processes can share the text. Shared libs give smaller binaries and updatable implementations; they add load-time cost, versioning and DT_NEEDED headaches. Android vendor HALs are typically shared objects.

Open in C Language →

Compiler/assembler output (.o / ELF relocatable): machine code, static data, a symbol table, and relocation records that say "patch this offset with the final address of foo". It is not runnable. Linking (static or dynamic) resolves those relocations.

Open in C Language →

In most expression contexts, integer types narrower than int (char, short, small bit-fields) are converted to int if int can represent every value of the original type, otherwise to unsigned int. So unsigned char a = 1, b = 2; a - b is int -1, not 255. Assignment into a narrow object converts back afterwards.

Open in C Language →

After promotions, a binary operator converts both operands to a common type: floating types win if present; otherwise the higher conversion rank wins; if ranks match but signedness differs, the signed operand converts to the unsigned type of that rank. That is why -1 < (size_t)1 is false: -1 becomes a huge unsigned value.

Open in C Language →

The standard defines unsigned arithmetic modulo 2ⁿ. Signed overflow is UB so compilers may assume it never happens: they delete "impossible" checks and rewrite loops. Two's-complement wrap is what the CPU does, but C does not give you that unless the implementation documents a dialect (-fwrapv). Write overflow-safe code with unsigned types, wider types, or explicit checks.

Open in C Language →

size_t is the unsigned type of object sizes: sizeof, strlen, malloc's argument, array counts in libc. Use it for sizes. Do not use it as a general integer: it cannot be negative, so a mistaken < 0 check is dead code, and mixing it with signed values triggers usual arithmetic conversions.

Open in C Language →

Integer types that can hold an object pointer. Used for tagged pointers, hashing addresses, and some handle encodings. Casting a pointer to an integer and back is allowed for void * via these types, but pointer provenance and alignment still matter; they are not a licence to fabricate pointers from arbitrary integers.

Open in C Language →

Plain char is either; the ABI chooses. Many ARM Android targets use unsigned char; many x86 hosts use signed. char c = 0xFF; if (c == 0xFF) may compare -1 with 255. For bytes use unsigned char or uint8_t. This is a classic "works on my laptop" bug.

Open in C Language →

Text is code (usually RX, shareable). rodata is const data and string literals. Data is initialised static-duration objects. BSS is zeroed static-duration objects (size in the file, not the zeros). Stack holds frames: locals, return addresses; automatic lifetime. Heap is malloc/free. Returning a pointer to a local, writing a string literal, or leaking heap are the usual mix-ups.

Open in C Language →

malloc(n) returns n uninitialised bytes or NULL. calloc zeros and can overflow nmemb * size. realloc(p, n) may move the block; on failure p is still valid — never write p = realloc(p, n) without a temporary. free(NULL) is safe; double-free and freeing a non-heap pointer are UB. malloc(0) is implementation-defined.

Open in C Language →

A type's alignment is the divisor required of its address. The compiler inserts unused bytes so each member (and the struct as a whole, for arrays) meets its alignment. offsetof and sizeof are authoritative. Padding is why you cannot treat a struct as a portable wire format and why memcmp of structs can see stale pad bytes.

Open in C Language →

Little-endian stores the least significant byte at the lowest address (ARM Android, x86). Big-endian stores the most significant byte first. Endianness is about integers in memory or on the wire, not about bitfields magically becoming portable. Convert explicitly at protocol boundaries.

Open in C Language →

An array is an object that contains N elements. In most expressions it decays to a pointer to the first element. sizeof on an array is the whole object; sizeof on a pointer is the pointer. A function parameter declared as an array is a pointer. &arr has type pointer-to-array, not pointer-to-element.

Open in C Language →

p + k advances by k * sizeof(*p) bytes, and is defined only for pointers into the same array object (or one-past-the-last). Dereferencing one-past-the-end is UB. Subtracting two pointers yields ptrdiff_t and has the same restriction. NULL + 1 is UB. char * arithmetic is in bytes.

Open in C Language →

The generic object pointer. In C you may convert to and from any object pointer without a cast. You may not dereference it or (portably) do arithmetic on it. It is the type of malloc's return and of untyped callbacks' context. Function pointers are not portably stored in void * even though POSIX code often does it.

Open in C Language →

A pointer whose type is a function type: return type plus parameter types. Used for qsort comparators, pthread start routines, HAL vtables, and JNI native method tables. Typedef the type. Calling through NULL is UB. You cannot portably perform data-pointer arithmetic on them.

Open in C Language →

const T *p (same as T const *p): you may not write *p; you may retarget p. T * const p: you may write *p but not change p. Both: const T * const p. APIs that only read should take const T *. Writing through a cast-away const is UB if the object was defined const (including string literals).

Open in C Language →

A C99 promise: for the lifetime of that pointer, accesses to the pointed-to object go through pointers based on it. The compiler may assume no aliasing and vectorise copies. memcpy is restrict; passing overlapping regions is UB. memmove has no restrict and is the overlap-safe copy.

Open in C Language →

When a callee must change the caller's pointer (allocate and hand back), when you walk a list by rewriting head, or when you have an array of pointers (argv). void ** is a pointer to void *, not a magic "pointer to any pointer".

Open in C Language →

A string is contiguous chars plus a terminating '\0'. There is no stored length: strlen walks until NUL. Length is how many payload characters you mean; capacity is how many bytes the buffer can hold (including the NUL if you store a string). Confusing capacity with sizeof(pointer) is a standard overflow.

Open in C Language →

strcpy writes until the source NUL with no destination bound. snprintf(buf, sizeof buf, "%s", src) will not write more than the size, NUL-terminates if size > 0, and returns the length that would have been written so you can detect truncation. strncpy is usually the wrong substitute (may omit NUL, zero-pads).

Open in C Language →

strcpy copies a C string (stops at NUL, no bound). memcpy copies n raw bytes and forbids overlap (restrict). memmove copies n bytes and allows overlap by copying forward or backward as needed. For unknown overlap, use memmove. For strings of unknown size, use a bounded formatter or an explicit length.

Open in C Language →

A struct lays members out in order (plus padding). A union overlays members in the same storage; size is the largest member (plus ABI tail padding). Reading a union member other than the one last written is implementation-defined in the standard; compilers you use document type punning. Do not memcmp structs with padding and expect a stable result.

Open in C Language →

A struct member with a bit width, e.g. unsigned ready : 1;. Useful for in-memory flags on one toolchain. Allocation unit, bit order and straddling are implementation-defined, so they are a bad wire format. They are not atomic; use atomics or a mutex for shared flags.

Open in C Language →

C99 last member T data[];. It is not a pointer and not a fixed array. sizeof does not include the flexible part. Allocate offsetof(struct s, data) + n * sizeof(T) and use s->data[i]. Prefer this over the old data[1] / GNU data[0] hacks in new userspace C.

Open in C Language →

Packed layout removes padding so the in-memory image is compact. Members can be unaligned. On ARM an unaligned word load can be slow or fault. Taking the address of a packed member and treating it as a normally aligned pointer is a common bug. Prefer explicit serialisation for protocols.

Open in C Language →

Guards are #ifndef FOO_H / #define FOO_H / #endif so a header's body is pasted once per translation unit. #pragma once is widely supported and fine in practice; interviews still expect guards because they are standard and ubiquitous in kernel/AOSP headers. Guards do not prevent multiple definitions across units.

Open in C Language →

Macros are untyped token substitution: arguments can be evaluated twice (MAX(i++, j)), errors are late, and you cannot take the address. static inline functions are typed, evaluate arguments once, and step in a debugger. Keep macros for guards, #ifdef, token pasting and a few patterns like container_of.

Open in C Language →

Ask where it is written. File-scope static on a function or object: internal linkage (not exported to the linker). Block-scope static: static storage duration, one instance, initialised once. extern: external linkage; extern int x; is a declaration. C++ adds a third meaning for class members (see C++).

Open in C Language →

Undefined: no requirements (signed overflow, UAF, data race). Unspecified: one of several allowed outcomes, need not be documented (argument evaluation order). Implementation-defined: the implementation chooses and documents (plain char signedness, sizeof(long)). Interviews want examples and the optimisation consequence of UB.

Open in C Language →

It forces the compiler to emit a real access for each abstract-machine read or write of that lvalue, and not to reorder those volatile accesses with each other. Use it for MMIO and signal-handler flags (sig_atomic_t). It does not provide atomicity, a CPU barrier, or defined behaviour for data races. For threads use C11 atomics or a mutex.

Open in C Language →

A file-scope declaration of an object with no initialiser and without extern, e.g. int g;. If the translation unit never provides a real definition, the compiler emits a zeroed g. Historically multiple units could each have int g; and the linker merged "common" symbols. Modern Clang/GCC default to -fno-common, so that becomes a multiple-definition error. Declare extern int g; in the header and define it in one .c.

Open in C Language →

An inline definition in a header may be used for inlining. If the function is used as a real function (address taken, or the compiler does not inline), there must be exactly one external definition in the program. The portable habit in many codebases is static inline in the header (possible duplicate copies). This is not the C++ ODR-inline rule; do not mix the stories (see C++).

Open in C Language →

Each external symbol should have one definition at link time. Two non-static functions named foo in two .c files fail. A function body in a header included by two units is the usual cause. Two static functions with the same name are different functions. Weak symbols and (historically) common symbols are the exceptions.

Open in C Language →

In a function-like macro, #param turns the argument's tokens into a string literal. a##b concatenates tokens into one token (e.g. a new identifier). They run in the preprocessor. Pasting must produce a valid token; stringizing does not evaluate the argument. Useful for test harnesses and enum-to-string tables; easy to make unreadable.

Open in C Language →

#include "foo.h" searches the directory of the including file first, then the include path. #include <foo.h> searches the system / -I path. The first file found wins, so -I order can silently pick a stale generated header. That shows up in Android when generated AIDL headers fight checked-in copies.

Open in C Language →

Closing a brace in only one #ifdef arm makes two different programs. Nested feature forests are untestable. #if FOO when FOO is undefined is 0; #ifdef FOO only tests whether it is defined. Prefer a single config header and small functions over scattering __ANDROID__ through logic.

Open in C Language →

The scalar i is modified twice (the increment and the assignment) with those side effects unsequenced relative to each other. C17's sequenced-before relation does not order them. The compiler may produce anything, including deleting nearby code. Write i += 1; or i = i + 1;. The same rule kills a[i] = i++ and printf("%d %d", i++, i++).

Open in C Language →

C89/C99 teaching used sequence points (semicolon, comma operator, &&/||/?:, after argument evaluation before a call). C11/C17 describe a sequenced-before partial order on evaluations. The rule you need: unsequenced conflicting accesses to the same scalar (two writes, or a write and an extra read) are UB. The vocabulary changed; the interview examples did not become defined.

Open in C Language →

• Out-of-bounds store or load, including missing NUL on a "string".
• Use-after-free, double-free, or using an uninitialised pointer.
• Signed integer overflow; bad shifts (negative, or shift ≥ width).
• Strict-aliasing / effective-type violations; overlapping memcpy.
• Data races; returning a pointer to a local; writing a string literal.

Open in C Language →

C11's memory model says a race (conflicting accesses, at least one a write, no happens-before) has no defined result. The compiler may keep a copy in a register forever, tear a store, or invent loads. "I only write a byte flag" is not enough unless that object is atomic or you used a lock. x86 TSO hides many missing barriers; ARM will not. Use TSan in tests.

Open in C Language →

Pass an array to a function and it is a pointer: sizeof inside the function is the pointer size. Macros like #define COUNT(a) (sizeof(a)/sizeof (a)[0]) are only valid on a real array object, not on a parameter. Keep an explicit length. sizeof on a VLA is evaluated at runtime; on other types it is a constant.

Open in C Language →

The standard defines a[i] as *((a)+(i)). Addition commutes, so i[a] is the same if one operand is a pointer and the other an integer. It is trivia. The useful lesson is that subscripting is pointer arithmetic, which is why a decaying array and an index are symmetric in the abstract machine.

Open in C Language →

Start at the identifier, go right as far as you can (arrays, function params), then left (pointers, const), then out through parentheses. int *(*fp)(void) is "fp is a pointer to a function taking void returning pointer to int". Prefer a typedef. Interviewers use this to see if you panic or methodically decode.

Open in C Language →

Read it backwards from the star: const T * is pointer to const T (pointee frozen). T * const is const pointer to T (pointer frozen). Both frozen: const T * const. A function that only reads should take the first so callers can pass const data and literals.

Open in C Language →

An object's effective type (how it was created or last written, roughly) is the type you may use to read it. Reading an int through a float * is UB; the compiler assumes they cannot alias and reorders loads. Exceptions include character types (you may inspect any object's bytes via unsigned char *) and unions in the compiler dialect you actually use. Portable punning is memcpy into an object of the other type.

Open in C Language →

C11 malloc is aligned for any object whose alignment is not greater than max_align_t (typically 8 or 16). SIMD types, some hardware descriptors and cache-line aligned structs need aligned_alloc, posix_memalign, or a compiler-aligned allocator. Free with the matching API. Over-aligned new in C++ is a different chapter.

Open in C Language →

p = realloc(p, n) if realloc returns NULL: you overwrite the only pointer to the old block and leak it. Keep the old pointer, check the result, then assign. On success the old pointer is invalid if the block moved — do not use both.

Open in C Language →

On success it returns the number of characters that would have been written excluding the NUL. If that value is negative, there was an encoding/output error. If (size_t)n >= size, the output was truncated (the buffer is still NUL-terminated when size > 0). That return is also how you size a correctly large second buffer.

Open in C Language →

• Missing NUL after memcpy of text.
• sizeof(ptr) as a count.
• Off-by-one: i <= n on an n-byte buffer.
• Modifying a string literal.
• Using strncpy as "safe strcpy".
• Assuming char is unsigned when scanning bytes.

Open in C Language →

Padding, endianness, bitfield layout and the size of long are ABI-specific. The receiver may be another architecture, a Java layer, or a different compiler. Define a protocol: fixed-width types, explicit endian conversion, no hidden pads (or a documented packed format you serialise carefully). Binder/AIDL exist so you do not invent this every time — see Binder & AIDL.

Open in C Language →

The standard says reading a member other than the one last stored is implementation-defined (except you may read a common initial sequence of structs in a union). GCC and Clang document that union punning works as people expect. The strictly portable approach is memcpy between objects. Never use a union to keep a pointer alive after free.

Open in C Language →

The fd is the kernel object; FILE* buffers in libc. fileno and fdopen bridge them. Mixing read and fread without fflush/lseek coordination desynchronises the buffer. If you fdopen, fclose closes the fd — do not close it again (fdsan will punish you on Android). Use raw fds for ioctl, mmap, poll loops and Binder-adjacent code.

Open in C Language →

Failing POSIX functions typically return -1 or NULL and set a positive E* code. Success does not clear errno. Modern libc makes errno a macro that refers to thread-local storage so two threads do not clobber each other. Look at it only when the function said it failed. Save it before you log, because logging can clobber it. strerror is not reliably thread-safe; prefer strerror_r.

Open in C Language →

A rule is target: prerequisites plus a recipe. Make rebuilds the target if it is missing or older than a prerequisite. .PHONY marks a name that is not a file (clean). $@ is the target, $< the first prerequisite, $^ all of them. AOSP uses Soong/Android.bp; Make is still the mental model and appears in small native projects.

Open in C Language →

bt first. Then frame N, info locals, print, x/16xb ptr to dump memory, info registers. watch *addr for who-writes-this. You need -g and preferably an unstripped binary. Optimised builds skip around; that is normal. On Android start with the tombstone backtrace; attach lldb/gdbserver if you need live state.

Open in C Language →

ASan: OOB and UAF, needs a rebuilt binary, ~2× memory. UBSan: language UB (overflow, bad shift), cheap, rebuild. LSan: leaks at exit, often with ASan. TSan: races, heavy, all code instrumented. Valgrind memcheck: no rebuild, very slow, excellent on host, awkward on Android user builds. Kernel memory bugs need KASAN, not ASan — see kernel & BSP.

Open in C Language →

A mutex gives mutual exclusion: one holder, unlock happens-before the next lock, so data touched under the lock is visible. A condvar lets a thread wait for a condition: always wait in a while (!pred) loop with the mutex held; the signaler changes the pred under the same mutex and then signals. Spurious wakeups happen. Do not use a condvar as a semaphore without a predicate.

Open in C Language →

Relaxed: atomicity of that location only; no publication of other memory. Use for independent counters. Release store: "all my earlier writes become visible to someone who acquire-loads this flag." Acquire load: "I see the writer's payload." Default seq_cst if you do not want to think. Never publish a pointer to a struct with a relaxed store of the pointer.

Open in C Language →

Bionic is smaller: not the full POSIX/glibc surface (locale, NSS, some pthread extras). The dynamic linker is Android's linker64 with library namespaces, not ld-linux. Android has fdsan; glibc does not. Allocators differ (jemalloc-derived / scudo vs historical ptmalloc). Do not assume glibc-only functions exist on the device.

Open in C Language →

Android's file-descriptor sanitizer. libc tags fds with an owner. Closing an fd the runtime believes another owner still holds, or using a closed fd, aborts the process. It catches "I closed the fd I passed to fdopen" and "I closed an fd the framework still owns". Fix ownership, do not disable fdsan to hide the bug.

Open in C Language →

JNIEnv is a per-thread pointer to the JNI function table (and VM thread state). Another thread has a different env. Caching it in a global and using it from a worker is a crash. A thread you created must AttachCurrentThread before JNI and DetachCurrentThread before it exits. The Java-side native story is on the Java page.

Open in C Language →

From a thread attached natively, FindClass uses the system class loader, which cannot see app classes. Cache a global jclass (or a ClassLoader object) while you are still in a JNI call that arrived from Java with the app loader. Also check exceptions: a failed FindClass leaves a pending exception you must handle before more JNI.

Open in C Language →

In the C abstract machine a pointer is tied to the object it was derived from, not just to an integer address. Using a pointer invented from an integer, or one that came from a different object, to access another object can be UB even if the bits match. Compilers use this to assume that a pointer derived from a cannot reach b. Interview answer: "address equality is not a full story; do not manufacture pointers; uintptr_t round-trips are for tagging, not for forging access to a sibling object."

Open in C Language →

A bit pattern that is not a valid value of the type. Loading it can be UB. Modern two's-complement int usually has no trap representations; the idea still matters for some padding bits and for "I memcpy'd garbage into an enum / pointer." Uninitialised automatic objects can behave as if they had a trap or an unstable value. Initialise, or copy bytes via unsigned char.

Open in C Language →

memcpy is specified with restrict: the implementation may read all of the source and write all of the destination as if they were distinct. If they overlap, those assumptions fail (torn copies, vectorised wrong direction). memmove is specified to handle overlap. If you do not know, call memmove.

Open in C Language →

C99 FAM T data[] is the language feature: sizeof excludes it, allocate with offsetof. GNU data[0] is an extension used in older kernels. data[1] is the pre-C99 hack and overstates sizeof by one element, which people then subtract. New userspace C: FAM. Kernel C: you will still see all three — language history, not a new algorithm (kernel internals stay on kernel & BSP).

Open in C Language →

Which end of the storage unit gets bit 0, whether fields straddle units, and how they interact with endianness are implementation-defined. Two compilers or -fshort-enums-style flags can disagree. Fine for private flags. For a register map or a modem payload, use explicit shifts and masks on a uint32_t you serialise yourself.

Open in C Language →

Packed members need not be naturally aligned. The compiler emits safe accesses if it knows the pointer came from a packed struct. If you take &s->unaligned_u32 and pass it as uint32_t * to a function compiled as aligned, ARM may fault or tear. Fix: memcpy into an aligned local, or read bytes. This is a common "works on x86" HAL bug.

Open in C Language →

volatile constrains the compiler's treatment of that lvalue only. A 64-bit store can still tear. Surrounding non-volatile writes can still move relative to it in ways that surprise you (more so at the CPU). Another thread racing on a plain volatile int is still a data race. Use atomic_store_explicit / mutexes. Leave volatile for MMIO and signals.

Open in C Language →

It assumes that stores through one restrict pointer are invisible to loads through another restrict pointer (and through unrelated pointers) during that invocation. Overlapping buffers, or writing the same object via a global and a restrict parameter, let it generate a wrong vectorised copy. The bug is silent. Mark only true non-aliasing parameters; otherwise omit restrict.

Open in C Language →

They implement a non-local jump: setjmp saves a stack context, longjmp restores it. Locals not marked volatile can be stale after a jump back. You must not longjmp into a function that has already returned. There is no automatic cleanup — in C++ that skips destructors (see C++). Prefer explicit error returns and goto cleanup in C APIs.

Open in C Language →

A handler can interrupt almost any code, including malloc internals. The safe subset is small: write to an fd, sig_atomic_t / C11 lock-free atomic flags, a few listed POSIX functions. Do not call printf, malloc, or locks. The usual pattern is "set a flag, return"; the main loop handles the work. Android also delivers some signals for crashes (debuggerd) — do not install clever handlers that allocate.

Open in C Language →

Position-independent code uses relative addressing so a .so (and a PIE executable) can load at any address. Global data goes through the GOT (a table of addresses the loader fills). External calls often go through the PLT (a trampoline that resolves on first call, then jumps). -fPIC is required for shared objects. This is the cost of dynamic linking and of ASLR, not a DSA topic.

Open in C Language →

A weak definition can be overridden by a strong symbol of the same name at link or load time. Used for default implementations you expect a vendor library to replace, and for hooks. Interposition (LD_PRELOAD, linker namespaces) can replace strong symbols too, which is why hidden visibility and symbol versioning exist on Android. Do not rely on weak aliases as a security boundary.

Open in C Language →

ASan maps a compact shadow byte for every 8 bytes of application memory. Poisoned shadow means "this is redzones, freed, or out of bounds." Each load/store is instrumented to check the shadow. Freed heap is poisoned and often put on a quarantine so UAF still hits poison. That is why ASan needs extra RAM and a rebuild, and why it can miss bugs in uninstrumented assembly or a different allocator.

Open in C Language →

UAF: the slot is poisoned after free; a later access trips ASan/Valgrind. Double-free: the allocator or ASan sees a free of a pointer already on the freelist / not marked allocated. Both are UB even if they "sometimes work" because the bytes still look intact. Debug with the sanitizer stack of the free and the use; gdb watchpoints if you cannot rebuild.

Open in C Language →

seq_cst puts all sequentially-consistent operations in a single total order, which is easier to reason about and can require extra fences (especially on ARM for stores). acq_rel on an RMW only pairs with that location's acquire/release story; it does not automatically order unrelated seq_cst-free atomics the way people hope. Use seq_cst as a default for small flags; drop to acq_rel/release-acquire when you have measured and can draw the happens-before edges.

Open in C Language →

Two threads write different variables that live on the same cache line. The line ping-pongs between cores even though there is no data race on the same object. Fix: align/pad hot atomics to the cache-line size (typically 64 bytes) or keep writers on separate lines. This is a performance bug that looks like "atomics are slow" in a profiler.

Open in C Language →

One producer, one consumer, power-of-two size. Producer writes the slot, then release-stores the write index. Consumer acquire-loads the write index, reads the slot, then relaxed/release-stores the read index. Do not let the two indices live on one cache line if this is hot. No mutex. If you need MPMC, do not invent it on a whiteboard — use a mutex or a known algorithm and state the hazards (ABA).

Open in C Language →

Local refs are valid until the native method returns (or you pop a frame / delete). They overflow if you allocate in a loop. Global refs keep the object alive and must be DeleteGlobalRef'd. Weak global refs do not keep it alive; you must promote carefully and handle a cleared ref. Never store a local ref in a C global for later. Java GC details: Java.

Open in C Language →

Java strings are UTF-16. JNI "UTF" is modified UTF-8: U+0000 and supplementary characters are encoded differently from standard UTF-8. Round-tripping arbitrary Unicode or binary through these APIs corrupts data. For bytes use jbyteArray. Always pair Get with Release, check NULL, and check exceptions. Prefer GetStringCritical only for short, no-JNI, no-blocking regions — it can pin or copy and has strict rules.

Open in C Language →

The kernel is not a POSIX process: no user-space loader, no heap that malloc knows about, no errno, small stacks, and a rule against floating point in many contexts. It has its own allocators (kmalloc), printing (printk) and string helpers. That is policy and environment, not "C is different in the kernel." Full story: Linux kernel & BSP.

Open in C Language →

Legacy: a shared object exports HAL_MODULE_INFO_SYM, hw_module_t.open returns an hw_device_t whose ops are a C function-pointer table. Calls are in-process or through an old wrapper. Treble: the HAL is a Binder server; you implement an AIDL interface (C++ NDK stubs are still "struct of methods" plus parcels). Prefer AIDL over a new ioctl ABI. IPC details: Binder & AIDL; framework callers: Android frameworks.

Open in C Language →

Every pointer in the prototype needs a sentence: caller allocates / callee allocates; who frees; may be NULL; borrowed vs stolen. Use names (out_, _owned) plus a comment. Error paths must free what they allocated — goto cleanup is idiomatic. C has no unique_ptr; the comment is the contract. Interviewers read it before they read the loop.

Open in C Language →

Walk unsigned char or char until '\0', return the count as size_t. State that a missing terminator is UB if you do not have a bound — then the real API is memchr(s, 0, cap). libc may read a word at a time; you write the obvious loop. NULL input is UB in the C standard for strlen; ask whether they want a defensive check.

size_t my_strlen(const char *s)
{
    const char *p = s;
    while (*p) p++;
    return (size_t)(p - s);
}

Open in C Language →

Prototype with restrict. Copy bytes via unsigned char *. Return dst. Overlap is UB — send them to memmove (if d is after s in the same object, copy backwards). Real libc aligns and copies words; do not pretend your loop is that. n == 0 is a no-op. NULL with n > 0 is UB.

void *my_memcpy(void *restrict d, const void *restrict s, size_t n)
{
    unsigned char *cd = d;
    const unsigned char *cs = s;
    while (n--) *cd++ = *cs++;
    return d;
}

Open in C Language →

If size != 0 && count > SIZE_MAX / size, fail before calling malloc. A wrapped product makes a small allocation and a later write smashes the heap — a security bug. calloc is supposed to check, but you still think about it. The same check applies to realloc and to FAM sizing: offsetof + count * elem.

Open in C Language →

stdarg.h macros walk the argument area in an ABI-specific way. You must have a prototype with an ellipsis, start with va_start on the last named parameter, and va_end. You cannot assume arguments are on the stack in order (registers, spilling). Passing the wrong type after default promotions is UB. Prefer explicit counted arrays over varargs in new HAL APIs.

Open in C Language →

Link-time optimisation inlines across units and applies the same UB assumptions more aggressively. Signed overflow checks, NULL checks after a dereference, and type-pun loads that "worked" at -O0 get deleted. The program was always undefined; the optimiser just started believing the standard. Reproduce with -O2 -flto, then UBSan/ASan, then fix the UB — do not add volatile as a superstition.

Open in C Language →

Classic strerror writes a shared buffer. Two threads can interleave and see a garbled or swapped message. errno itself is thread-local, but the string helper may not be. Use strerror_r (POSIX or GNU variant — check which) or format the integer. On Android, prefer the bionic-documented thread-safe form and still save errno before any other call.

Open in C Language →

Classic UAF: something still holds the pointer. Rebuild with ASan; the report gives the use stack and the free stack. If you cannot rebuild, gdb watch on the chunk or a debug malloc that paints freed memory (0xDD). Check all error paths for a free that the success path also does. On Android, also check that you did not free a buffer still owned by a HAL or a Binder parcel.

Open in C Language →

Undefined behaviour that the optimiser exploited: signed overflow, strict aliasing, an uninitialised variable, a missing sequence, a NULL check after dereference, or a race that only appears when the compiler keeps a register copy. Rebuild with UBSan and ASan at -O2, read the warning set (-Wall -Wextra), and look at the crashing expression, not at "the optimiser is buggy".

Open in C Language →

List the deltas: ARM vs x86 (unaligned access, char signedness, weaker memory model), bionic vs glibc, fdsan, 32-vs-64 if any, and real concurrency on a big.LITTLE phone. Enable ASan/UBSan in an NDK debug build, capture the tombstone, and check for missing acquire/release on a flag. Host is TSO and often signed char; the device is not your laptop.

Open in C Language →

LSan/ASan on a debug build for leaks that survive until exit. For long-running processes (system_server, a HAL), use heap snapshots, malloc debug (libc.debug.malloc / heapprofd / Perfetto), and ask whether the "leak" is a cache. Check JNI global refs: they leak Java objects and native peer structs together. Do not confuse still-reachable singleton buffers with a true leak.

Open in C Language →

Stack overflow: huge locals or deep recursion; tombstone often in a guard page just below the stack; frames look smashed near the current function. Heap smash: ASan redzone, corrupted malloc metadata, crash in malloc/free, or a wild pointer far from the stack. ulimit -s / thread stack size matters on native threads you created. VLAs and alloca of untrusted sizes are suspects.

Open in C Language →

You created local refs in a loop (NewObject, FindClass, GetObjectArrayElement) and never deleted them or popped a frame. The default table is small (a few hundred). DeleteLocalRef each iteration or PushLocalFrame/PopLocalFrame. Returning to Java clears the table; a long-lived native loop never does. This is a C-side bug even though the table is in the VM.

Open in C Language →

Assume the system class loader and a pending exception. Check ExceptionDescribe/ExceptionClear. Cache a global jclass from a JNI entry that ran on a Java thread with the app loader, or cache the app ClassLoader and call loadClass. Also verify the class name uses slashes (com/foo/Bar) not dots. Java-side registration: Java.

Open in C Language →

Most often modified UTF-8 vs real UTF-8 vs UTF-16, or treating binary as a string. Use jbyteArray for bytes. Check that you called the matching Release function and that you did not write through a pointer after Release. Embedded NUL in modified UTF-8 is a special encoding; strlen on JNI UTF is the wrong length API.

Open in C Language →

Someone closed an fd the runtime tagged as owned by someone else: double close, close after fdopen (let fclose own it), or closing an fd you handed to another component. The abort includes the owner tag and a stack. Fix the ownership contract; do not close fds you do not own. This is Android-specific; glibc would have silently reused the number and corrupted a later client.

Open in C Language →

ASan: the access type, the address, the allocation stack, the free stack (for UAF), and the offending thread. TSan: two stacks that raced and the location. Symbolise with llvm-symbolizer / ndk-stack if you only have PCs. Fix the lifetime or add the missing lock/atomic; do not "make the race smaller" with volatile.

Open in C Language →

Two non-static definitions of the same external symbol: a function body in a header, int g; in a header under -fno-common, or linking the same object twice. Fix: declarations in the header, one definition in one .c, or static inline / internal linkage. Check you did not add the same source to two libraries that then both link into the binary.

Open in C Language →

A declaration without a definition, a missing object or library on the link line, C++ name mangling if one side is C++ without extern "C" (see C++), or a static function you tried to call from another unit. Link order can matter with static archives: the archive must come after the objects that need it. On Android, also check the shared-lib is in the right linker namespace.

Open in C Language →

Forward-declare struct foo; when you only need a pointer. Include the full header only where you need the layout. Guards stop double-paste, not cycles of incomplete types. Split "public API" headers from "impl" headers. If two headers each need the other's size, the types are too entangled — introduce an opaque pointer.

Open in C Language →

Check the return value against the buffer size. Truncation still NUL-terminates (if size > 0) but the semantic payload is incomplete. Size the buffer from the return, or fail closed. Do not use sprintf. If you chained two snprintf calls, the second must use the remaining space, not sizeof buf again.

Open in C Language →

The multiplication wrapped: you allocated a tiny block and wrote n * size bytes. Check n > SIZE_MAX / size (when size != 0) before allocating. Treat this as a security defect. Same bug exists in FAM size expressions and in realloc growth: new_cap = old_cap * 2 can wrap.

Open in C Language →

Likely an unaligned load: a packed struct, a cast of a byte pointer to uint32_t *, or a DMA buffer with a misaligned offset. x86 would have tolerated it. memcpy into an aligned local, or read bytes and shift. Check the ABI alignment of the type and whether the buffer came from the network or a file with no padding.

Open in C Language →

List padding (did both sides pack?), endian, char signedness, enum size, and bitfield order. Dump sizeof and offsetof on both. Then stop using a raw struct as the protocol: write a serialiser with uint8_t / uint32_t and explicit endian helpers. If this crosses Binder, you wanted AIDL — Binder & AIDL.

Open in C Language →

Tombstone / logcat in the HAL process first: native crash, fdsan abort, SELinux deny, or an assert. Then the last Binder transaction (onTransact / AIDL method). Check thread-pool exhaustion and TransactionTooLarge. Framework-side death is a symptom; the C/C++ HAL is the patient. How death is delivered: Binder & AIDL. Who called: Android frameworks.

Open in C Language →

If you can rebuild: ASan already has the free stack. If not: a watchpoint on the first word of the chunk, or a breakpoint on free with a condition on the argument. Debug allocators log a stack at free. After the fact, a tombstone plus maps only tells you it was heap; you need a reproducer. Do not guess from "it looks like a libc address".

Open in C Language →

NDK ASan/UBSan/LSan builds, heapprofd / malloc debug, tombstones, and host-side Valgrind on a unit-test binary compiled against a host libc (knowing bionic differences). Kernel issues: KASAN, kmemleak — kernel & BSP. "We only have logcat" is not a strategy; ask for a sanitizer build flavour.

Open in C Language →

Write prototypes first. List edge cases out loud: n == 0, overlap (memcpy vs memmove), NULL (standard says UB), signed char if they asked for a byte API, and a missing NUL if the buffer is bounded. Code the obvious loops in unsigned char. State O(n) / O(1). Mention real libc does word-wise copies. Do not wander into graph algorithms — those are on DSA.

Open in C Language →

Every pointer is borrowed, copied, or stolen — write it in the comment. Return 0 / -errno or an explicit status enum; do not mix errno-on-success. No hidden threads unless documented. Prefer AIDL types over raw structs across processes. Cleanup with goto so every allocate has one free. Version the ABI. If the framework will call you, stay off the Binder thread for long work — Binder & AIDL.

Open in C Language →

Java is the language and its standard library contracts. The JVM is the specification of a virtual machine that loads class files, executes bytecode and manages a garbage-collected heap. The JRE is a product you run programs on (a JVM plus class libraries). The JDK is the JRE plus tools: javac, javap, jar, a debugger. Saying "I installed Java" without distinguishing JDK from JRE is incomplete.

Open in Java Language →

ART is Android's runtime. It still executes a Java-like language, but apps ship dex, compilation is dex2oat plus a JIT and profiles, the collector on modern releases is moving Concurrent Copying, and processes are forked from Zygote so a warm heap and boot image are shared copy-on-write. HotSpot loads .class files, uses Metaspace, and typically G1 (or Parallel/ZGC). ART is not "HotSpot with a different name".

Open in Java Language →

Kotlin is a different language that compiles to JVM bytecode and then to dex on Android. It interops with Java types and the same ART heap, GC and Binder stubs. This page is Java: memory, concurrency and collections do not change because the source was .kt. A Kotlin-only syntax lecture is the wrong answer unless they asked for it.

Open in Java Language →

javac produces class files: constant pool plus bytecode. Nothing CPU-native is required at that step. HotSpot interprets and JIT-compiles bytecode. On Android, d8/r8 turn class files into dex; ART interprets, JITs and/or runs oat code from dex2oat.

Open in Java Language →

A portable instruction set for a stack machine specified by the JVM spec: loads, stores, arithmetic, invokes, object allocation. It is verified at link time. It is not ARM or x86 machine code. Dex is a related but register-based format used on Android.

Open in Java Language →

A magic/version header, the constant pool (literals and symbolic refs), access flags, this/super/interfaces, field and method descriptors, and attributes (Code with bytecode, Exceptions, Signature for generics, and so on). javap -c -v dumps it.

Open in Java Language →

An object that finds class bytes and calls into the VM to define a Class. A class's identity is its binary name plus its defining loader. Two loaders can each define com.example.Foo; those are different types and a cast between them fails.

Open in Java Language →

A loader asks its parent to load a class before defining it itself. Bootstrap loads java.lang.*; the application loader loads your classpath only if parents do not. This keeps one String and prevents a JAR from replacing core types. Break the model only for plugins, and then watch for leaks.

Open in Java Language →

First the superclass is initialized (its statics), then this class's static fields and static blocks in source order. On new: the super constructor chain runs, then this class's instance fields and instance blocks in source order, then the rest of the constructor. Compile-time constants (static final primitives and strings initialized with literals) can be inlined and do not trigger class init.

Open in Java Language →

Static fields and methods belong to the class; there is one copy per class (per loader). Instance fields belong to each object. Static methods cannot use this or instance fields. Overriding is an instance-method concept; a static method with the same signature in a subclass hides, it does not override.

Open in Java Language →

Each thread's Java stack holds frames: local primitives and references. Objects and arrays live on the heap. Two locals can point at one heap object. Class metadata lives in Metaspace (HotSpot) or native alloc (ART), not in an ordinary Java object slot.

Open in Java Language →

The fixed prefix of every heap object: typically a mark word (hash, age, lock bits) and a class pointer, then fields, then alignment padding. Arrays add a length. Compressed oops / compressed class pointers may shrink the pointer words. The header is why a one-boolean object is still many bytes.

Open in Java Language →

The VM finds objects not reachable from GC roots (locals, statics, JNI globals, some VM handles) and reclaims them. How it does that (copying, marking, concurrent vs STW) depends on the collector. Java has no deterministic destructor for ordinary objects.

Open in Java Language →

On HotSpot, most objects die young. A minor collection copies or discards Eden/survivors cheaply. Objects that live long enough are promoted to old space, collected less often. G1 uses regions with young/old roles. ART's CC is also generational in spirit (bump-allocate young, copy survivors) but is not "G1 Eden".

Open in Java Language →

For references, == is identity: the same object. equals is the value contract if the class overrode it (and Object.equals is identity). For primitives, == is the only comparison. Always use equals for String and boxed numbers unless you are discussing intern or the Integer cache on purpose.

Open in Java Language →

equals must be reflexive, symmetric, transitive, consistent, and false for null. If a.equals(b) then a.hashCode() == b.hashCode(). Unequal objects may share a hash (collisions). A mutable key whose equals-fields change while it is in a HashMap is lost.

Open in Java Language →

Hash-based collections find a bin with the hash, then confirm with equals. If two equal objects have different hashes they never meet. If you override only equals, you inherit Object.hashCode (identity), so equal value objects miss each other in a HashSet.

Open in Java Language →

The character data cannot change after construction. That makes sharing and the intern pool safe, lets hashCode be cached, and makes strings usable as map keys. Security-sensitive APIs can treat a string as a snapshot. The cost is that concatenation creates new strings; use StringBuilder in loops.

Open in Java Language →

It returns the canonical pooled instance equal to the receiver. Literals are interned automatically. The pool is on the heap (since Java 7, not PermGen). Interning every request or UUID is a leak. == after intern is identity of the pool entry, not a general string test.

Open in Java Language →

String is immutable. StringBuilder is a mutable buffer for building text on one thread. StringBuffer is the old synchronized builder; do not use it in new code. A single + expression is rewritten by the compiler; a + inside a loop is not.

Open in Java Language →

private: same class. Package-private (no modifier): same package. protected: package plus subclasses. public: everywhere. A subclass in another package does not see package-private members. Nested classes can see the outer class's privates (the compiler emits accessors).

Open in Java Language →

Inherit when you have a true subtype and callers should use the subtype wherever the parent is accepted (Liskov). Compose when you want reuse of behaviour: hold a helper and delegate. Inheritance of implementation couples you to the parent's internals and is the wrong tool for "I needed one method".

Open in Java Language →

An abstract class can hold fields, constructors and protected state; you get only one superclass. An interface defines a capability; a class may implement many. Modern interfaces may have default, static and private methods, but still no instance fields. Share a skeleton with an abstract class; share a role with an interface.

Open in Java Language →

Overload: same name, different parameter types; resolved at compile time from the static types of the arguments. Override: same signature in a subclass; resolved at runtime from the dynamic type of the receiver. Static methods hide; they do not override. Use @Override so a signature mismatch fails to compile.

Open in Java Language →

Pass-by-value. For objects, the value is a copy of the reference. The callee can mutate the object. Reassigning the parameter does not change the caller's variable. Primitives are copied. There are no C++-style reference parameters.

Open in Java Language →

Checked: Exception minus RuntimeException; you must catch or declare them (I/O, many library failures). Unchecked: RuntimeException and Error; used for bugs and VM failures. The compiler does not force you to handle unchecked types. InterruptedException is checked because cancellation is part of the contract.

Open in Java Language →

Both extend Throwable. Error means the VM or linkage is in a bad state (OutOfMemoryError, StackOverflowError, NoClassDefFoundError); catching it to continue is usually wrong. Exception is the application-level branch, including both checked types and RuntimeException.

Open in Java Language →

A try that declares AutoCloseable resources and closes them in reverse order, even if the body throws. If close throws too, that exception is suppressed on the primary exception (getSuppressed()). It avoids the classic finally that hides the original failure.

Open in Java Language →

A List is ordered and allows duplicates; index access depends on the implementation. A Set forbids duplicates under equals (or identity for special sets). A Map is a key-to-value dictionary. Pick the interface by the contract, then the implementation by cost and concurrency.

Open in Java Language →

ArrayList: contiguous array, O(1) index, O(1) amortized add at the end, O(n) insert in the middle, cache-friendly. LinkedList: O(1) splice at a known node, O(n) index, pointer-heavy, rarely faster in real apps. Prefer ArrayList; use ArrayDeque for a queue or stack.

Open in Java Language →

HashMap is unsynchronized, allows one null key, fail-fast iterators. Hashtable is an old synchronized map, no nulls, coarse lock. ConcurrentHashMap is the modern concurrent map: no nulls, concurrent reads, weakly consistent iterators. Do not share a HashMap across threads.

Open in Java Language →

HashSet is a HashMap of keys: O(1) average, no order. TreeSet is a red-black tree: O(log n), sorted by Comparable or a Comparator, and compareTo must agree with equals or the set will lie. Use LinkedHashSet when you need insertion order.

Open in Java Language →

synchronized is mutual exclusion plus a happens-before on unlock/lock of that monitor. volatile is a lighter happens-before on each write/read of that field and forbids some reorderings; it does not make i++ atomic and does not protect a whole invariant across several fields unless you design it that way.

Open in Java Language →

run() is an ordinary method: it executes on the caller. start() asks the VM to create an OS thread that will then invoke run. Calling run by mistake is a classic "why is this single-threaded" bug. Calling start twice throws IllegalThreadStateException.

Open in Java Language →

Two or more threads each hold a resource the other needs and wait forever. The usual Java shape is two monitors acquired in opposite order. Diagnose with thread dumps: Blocked threads and the monitors they hold vs want. Prevent with a global lock order, try-lock, or fewer locks.

Open in Java Language →

A return type that makes "absent" explicit instead of null. Use orElse, orElseGet, orElseThrow, ifPresent. It is a poor field type (allocation, serialization) and a poor parameter type (the caller already knows). Never call get() blindly.

Open in Java Language →

A lazy pipeline of intermediate operations (filter, map) that runs when a terminal operation (collect, reduce, forEach) is invoked. It is not a data structure and it is single-use. Use it when the pipeline is clearer than a loop and the size justifies the allocation; see when they hurt in the streams section.

Open in Java Language →

Declare native with no body. In a static initializer call System.loadLibrary("foo") to load libfoo.so (Android/Linux). Missing library or missing symbol is UnsatisfiedLinkError. The C implementation and JNIEnv rules are on C language.

Open in Java Language →

The main thread is a Looper that must dispatch input, lifecycle and frames. A long message (disk, network, a stuck synchronous Binder call) delays everything behind it and becomes an ANR after a timeout (input ~5 s, broadcast 10 s, service 20 s). The idle loop itself sleeps in epoll and is not an ANR. Details: Android frameworks.

Open in Java Language →

Parcelable is explicit write/read for Android IPC: fast, no reflection, not a stable disk format. Serializable is Java reflection-based flattening: convenient, slow, constructor-skipping, a security hazard on untrusted bytes. Use Parcelable (or AIDL-generated parcelables) on Binder; see Binder and AIDL.

Open in Java Language →

Load: the classloader finds bytes and defines a Class. Link: verify bytecode, prepare statics to defaults, resolve symbolic refs (often lazily). Initialize: acquire the class init lock, initialize the superclass, run static initializers in order. The JLS makes initialization thread-safe: other threads wait rather than seeing a half-initialized class.

Open in Java Language →

You get two Class objects. A Foo instance from loader A is not assignment-compatible with loader B's Foo. Passing it across the boundary throws ClassCastException. This is how plugin isolation works and how "same name, different type" bugs appear in app-in-app or hot-fix loaders.

Open in Java Language →

The JIT proves an object does not escape the method or thread (no store to a heap field, no unknown call). It may then scalar-replace the object: fields become registers or stack slots and the heap allocation disappears. It is a compiler optimization, not a language guarantee. Profile before rewriting code to "avoid allocations" the JIT already removed.

Open in Java Language →

Young: Eden plus two Survivor spaces; most objects die in Eden; survivors are copied and aged; promotion to old after a threshold. Old: tenured objects, collected less often. G1 uses equal-sized regions that play young or old roles, plus a concurrent mark. Metaspace is native class metadata, not a Java heap generation. PermGen is gone as of Java 8.

Open in Java Language →

STW stops all mutators at safepoints for a phase (root scan, some compacting). Concurrent collectors do most marking and relocation beside the application but still pause briefly. "Concurrent" is not "zero pause". A moving concurrent collector (ART CC, ZGC) must still coordinate with mutators when it updates references.

Open in Java Language →

finalize is queued on a special thread at an unspecified time, can resurrect the object, and can deadlock the finalizer thread. Cleaner (or a PhantomReference plus a reference queue) runs after the object is phantom-reachable and cannot resurrect it. Use Cleaner for native resources; prefer explicit close and try-with-resources first.

Open in Java Language →

Weak: cleared when only weakly reachable; next GC can drop the referent. Soft: kept longer, cleared under memory pressure; cache-like. Phantom: get() is always null; enqueued after the object is otherwise unreachable, for cleanup. None of them are strong roots. WeakHashMap is weak on keys only.

Open in Java Language →

Local variables and operand-stack slots of live frames; static fields of loaded classes; JNI global references; the running Thread objects and their monitors; a few VM-internal handles (including interned strings as a historical example). Everything else is kept only if a path from a root remains.

Open in Java Language →

G1 is a region-based collector with young collections and mixed old collections, default on server Java. ART CC is a moving collector tuned for phone heaps and UI jank: bump-pointer young allocation, concurrent copy, short STW. Zygote's image space is almost never compacted so COW pages stay shared. Do not describe Eden/Survivor spaces as the Android heap.

Open in Java Language →

Java 8 removed PermGen. Class metadata lives in Metaspace (native memory, can still OOM). ART never had PermGen; class data is native linear-alloc. Compressed class pointers are a HotSpot packing trick for the class word, not an Android interview requirement, but you may mention them as an optional HotSpot detail.

Open in Java Language →

Antisymmetric: sgn(a.compareTo(b)) == -sgn(b.compareTo(a)). Transitive. Consistent. If you use the class in a SortedSet/SortedMap, compareTo == 0 should match equals, or the collection will treat unequal objects as the same key. A Comparator that returns 0 for unequal elements collapses them in a TreeSet.

Open in Java Language →

Make the class final (or seal it), fields private final, no mutators, defensive copies of mutable constructor args and of returned internals, and do not publish this from the constructor. Then equals/hashCode can use those fields safely. Records give a shallow version of this for simple carriers.

Open in Java Language →

Interface methods with a body. They let you add API to an interface without breaking every implementor (evolution). They are not multiple inheritance of state: no instance fields. If two interfaces provide conflicting defaults, the class must override and pick. Abstract classes remain the tool for shared state.

Open in Java Language →

A class or interface that lists its permitted subtypes. The compiler can check that a switch is exhaustive. They are relatively new Java; Android API levels may not expose them to app source even if the toolchain knows them. Mention as a language feature, not as a platform guarantee.

Open in Java Language →

Static nested: no enclosing instance; a namespaced helper. Inner: hidden this$0; keeps the outer object alive. Local: named class inside a method; captures effectively-final locals. Anonymous: one-off inner class; same leak as inner. Android Handlers should be static nested plus a WeakReference.

Open in Java Language →

A final, transparent carrier: a canonical constructor, accessors, and generated equals/hashCode/toString. Fields are shallowly immutable. It is not a substitute for a full domain object with invariants beyond what the constructor checks. Mention-level on older Android Java.

Open in Java Language →

Generic type arguments exist for the compiler. At runtime a List<String> is a List; the compiler inserts casts. You cannot instantiate T, create T[], or overload two methods that erase to the same descriptor. Reflection sees raw types plus a Signature attribute if you ask for generic metadata.

Open in Java Language →

Producer Extends, Consumer Super. If you only read Ts, take Collection<? extends T>. If you only write Ts, take Collection<? super T>. If you read and write, use Collection<T>. ? extends T forbids add (except null); ? super T only lets you get as Object.

Open in Java Language →

List<? extends Number> src can be a List<Integer>; you may read Number, you may not add an Integer. List<? super Integer> dest can be a List<Number>; you may add Integer, you cannot treat get as Integer.

Open in Java Language →

A variable whose static type is List<String> but whose runtime list contains a non-String, usually because of raw types or an unchecked cast. The add may succeed; a later get throws ClassCastException. Generic varargs (T...) allocate an erased array and are a common source; prefer List<T>.

Open in Java Language →

The JVM was designed before generics; erasure kept migration compatible and avoided reified instantiations of every List<T>. Arrays store their component type at runtime (reified) and are covariant: a String[] is an Object[], so a bad store throws ArrayStoreException. Generic lists are invariant and erased.

Open in Java Language →

Empty lists share an empty array. The first add allocates capacity 10. Later growth is old + (old >> 1) (1.5×), then a copy. Amortized add is O(1). If you know n, pass it to the constructor. This is the same amortized idea as a doubling buffer, with a 1.5 factor instead of 2.

Open in Java Language →

On ArrayList, HashMap and friends, the iterator snapshots modCount. A structural modification (add/remove other than Iterator.remove) makes the next use throw ConcurrentModificationException. It is best-effort, including on a single thread. It is not a concurrency protocol. ConcurrentHashMap iterators are weakly consistent instead.

Open in Java Language →

The wrapper holds one lock around every method; compound actions (check then put) still need external synchronization, and iteration must lock the wrapper. CHM allows concurrent reads and finer-grained updates, forbids nulls, and offers atomic putIfAbsent/compute. Use CHM for concurrent maps; use the wrapper only when wrapping a non-concurrent map you do not control.

Open in Java Language →

A bin treeifies when the chain length is at least 8 and the table capacity is at least 64. If the chain is long but capacity is under 64, HashMap resizes instead. Trees untreeify when they shrink to 6. Hash is mixed with h ^ (h >>> 16); index is (n-1) & h because n is a power of two. Load factor defaults to 0.75.

Open in Java Language →

It is the JMM's visibility/order relation: if A happens-before B, B sees A's writes (and later actions). Edges: program order in one thread; unlock happens-before later lock of the same monitor; volatile write happens-before later read of that variable; thread start happens-before the first action in the child; last action happens-before a successful join. Transitive.

Open in Java Language →

synchronized (lock) { while (!condition) lock.wait(); }. You must hold the monitor. wait releases it and reacquires before returning. A while (not if) re-checks after spurious wakeup and after a notifyAll meant for a different predicate. notify wakes one; notifyAll wakes all.

Open in Java Language →

ReentrantLock can try-lock, lock interruptibly, and be fair. You can attach several Conditions (several wait-sets) to one lock, which is awkward with a single Object monitor. You must unlock in finally; the language will not do it. Prefer synchronized when those extras are unused.

Open in Java Language →

A latch is one-shot: threads wait until a count hits zero (start gate, or "N workers done"). A barrier is reusable: N parties await, then all proceed, optionally running a barrier action; then they can cycle. Do not use a latch for multi-phase algorithms; do not use a barrier as a one-shot completion flag.

Open in Java Language →

A bag of permits. acquire blocks until one is free; release returns one. Use it to bound concurrency (at most 3 downloads, at most 1 writer). It is not a mutex unless you treat it as a single permit and remember it is not reentrant in the monitor sense.

Open in Java Language →

A pool that accepts Runnable/Callable and returns Futures. Creating a thread per task is expensive, unbounded, and hard to cancel. Shut down the pool (shutdown / shutdownNow) or you leak threads. Prefer bounded queues and a rejection policy over a cached pool for server-like loads.

Open in Java Language →

Core size, max size, keep-alive, work queue, thread factory, rejected-execution handler. Order: if workers < core, add a worker; else offer the queue; if the queue is full and workers < max, add a worker; else the handler runs (abort, caller-runs, discard). An unbounded LinkedBlockingQueue never fills, so max is unused. SynchronousQueue is a handoff (cached-thread style).

Open in Java Language →

The value is stored in the worker thread, not in the task. The next task on that worker still sees it (wrong user, wrong Looper-adjacent state, retained Activity). Always remove() in finally. Android's Looper itself is a ThreadLocal; that is why each thread needs Looper.prepare().

Open in Java Language →

A composable promise: supplyAsync, thenApply (map), thenCompose (flatMap), thenCombine, exceptionally, whenComplete. Pass an executor; the common ForkJoin pool is wrong for blocking I/O. get() blocks and wraps failures in ExecutionException. Do not get() on the Android main thread.

Open in Java Language →

Check a cached instance without a lock; if null, lock, check again, construct. Without volatile on the field, another thread can see a non-null reference whose constructor stores have not happened-before its reads (partially constructed object). volatile publishes the object safely. A static holder class is simpler for static singletons.

Open in Java Language →

If a constructor writes final fields and does not leak this, any thread that later sees the object reference sees those finals initialized. That is why immutable objects can be published through a data race on the reference. Leaking this (registering a listener in the constructor) voids the guarantee.

Open in Java Language →

Tiny collections (pipeline objects cost more than the work); boxed Stream<Integer> instead of IntStream; parallel() on small or blocking work (common ForkJoin pool); side effects inside map/filter; reusing a consumed stream. Prefer a loop when the pipeline is not the domain language.

Open in Java Language →

It skips constructors, so invariants must be re-checked in readObject. Untrusted bytes are a gadget/RCE risk; use filters. Default serialVersionUID breaks when you add a field. It is a bad Binder format (reflection, allocations). Prefer an explicit versioned format on disk and Parcelable on Android IPC.

Open in Java Language →

Copy mutable arguments before storing them, and copy mutable internals before returning them, so the caller cannot change your object. List.copyOf after you still hold a mutable list is not enough if you mutate the original. Unmodifiable wrappers share the backing store.

Open in Java Language →

A Looper is one-per-thread (ThreadLocal), looping on a time-ordered MessageQueue. A Handler bound to that Looper enqueues work; any thread may post, only the Looper thread runs it. The main thread's Looper is prepared in ActivityThread.main. Binder incoming calls are not on that Looper. Full detail: Android frameworks.

Open in Java Language →

An Integer or Boolean is an object: extra allocations on both sides, and null is a legal value. Auto-unbox of null is NPE. A primitive cannot express "unset". Hot paths should use primitives or a proper Parcelable with an explicit presence flag. See Binder and AIDL.

Open in Java Language →

Dex is the APK bytecode. Vdex caches verification. Oat/odex is dex2oat output: native code and metadata. A .art image is a prebuilt heap of classes Zygote maps. Compiler filters trade CPU, disk and install time. This is ART, not javac emitting machine code.

Open in Java Language →

It becomes the method's return and discards any pending return value or exception from try/catch. That is why it is a puzzle and why it is forbidden in serious code. A throw from finally similarly hides the original exception unless you were using try-with-resources suppression.

Open in Java Language →

Autoboxed int values in a configured range (default −128..127) are interned. Integer a = 80; Integer b = 80; a == b is true; 200 is typically false. Always equals for boxed numbers. The high bound can be raised with a VM flag; do not depend on it.

Open in Java Language →

HotSpot can pack heap references into 32 bits when the heap is within a limited range (typically under ~32 GB), scaling the pointer. Compressed class pointers pack the class-word the same way, pointing into a class space. They save memory and cache traffic. They are a HotSpot detail; ART has its own header packing. Mention as optional; do not invent them on Android.

Open in Java Language →

Within one thread, the appearance of program order for that thread's own reads and writes is preserved (intra-thread semantics). Across threads, independent accesses to non-volatile locations may be reordered, buffered, or optimized into registers. A reader may see stale values or, for non-volatile long/double, a torn value on some implementations. Only happens-before edges restore a cross-thread order.

Open in Java Language →

Program order; monitor unlock → later lock; volatile write → later read of that field; Thread.start → first action in the child; last action → successful join; interrupt → detection of the interrupt; default zeroing of fields → any use; write of a final in a constructor → freeze at the end of construction for safely published objects; transitivity. Also the synchronizer edges documented for j.u.c (release/acquire on locks, latches, and so on).

Open in Java Language →

Construction is several stores (header, fields). The store of the reference to inst can be reordered with those field stores in a racy publication. Thread B can load a non-null inst and then read default field values. A volatile store of inst cannot be reordered with the preceding constructor writes in a way that breaks that publication, and the matching volatile load acquires them. A local variable on the fast path still does one volatile read.

Open in Java Language →

ForkJoin is for divide-and-conquer: tasks spawn subtasks; idle workers steal from others' deques (work stealing). The common pool also runs parallel() streams. A ThreadPoolExecutor is a producer-consumer pool with an external queue and a rejection policy, better for independent I/O or heterogeneous tasks. Blocking inside ForkJoin tasks without ManagedBlocker can stall the pool.

Open in Java Language →

Deadlock: circular wait, no progress, threads typically Blocked on monitors. Livelock: threads keep reacting and retrying, CPU is used, no useful progress (two people stepping aside forever). Starvation: a thread never obtains a lock or CPU because of unfairness, priority, or a flood of other work. Fair locks reduce starvation and can reduce throughput.

Open in Java Language →

AtomicInteger, AtomicReference, LongAdder and friends expose CAS and atomic updates without a monitor. They are for a single variable (or a marked reference). They do not make a multi-field invariant atomic. incrementAndGet is atomic; two separate atomics are not a transaction. Use them for counters and lock-free flags, not as a substitute for a lock around a map plus a list.

Open in Java Language →

Blocking methods that throw it have cleared the interrupt status. If you cannot handle cancellation, catch, restore Thread.currentThread().interrupt(), and exit or rethrow. Swallowing it makes the next blocking call ignore cancellation. Do not use interrupt as a normal boolean if you can use an explicit flag plus interrupt together.

Open in Java Language →

A class holds statics; a class is reachable from its loader; a loader is reachable from every class it defined. If any thread, cache, or JNI global still points at one object from a discarded plugin APK, the entire loader and all its classes stay alive. Android hot-fix and webview-style loaders are the usual story. Metaspace / native class OOM is the symptom on HotSpot.

Open in Java Language →

A power-of-two table of bins; bins are lists or trees similar in spirit to HashMap. Updates use CAS on bin heads and synchronized-on-bin for lists/trees; gets are typically wait-free if a bin is stable. Resizing is cooperative: threads help transfer bins. Size is estimated with a striped counter. Nulls are banned so get can use null as "absent" without ambiguity. It is not a composite atomic for "check two maps".

Open in Java Language →

WeakHashMap: cache-like entries that should die with the key; remember values must not strongly point back at keys. IdentityHashMap: keys compared with ==, used for topology (visiting objects, serialization graphs). EnumMap: array-backed, fastest and smallest when keys are an enum; always prefer it then.

Open in Java Language →

Cloneable is a marker; Object.clone is a shallow field copy; mutable children are shared; inheritance of clone is fragile (you must remember to deep-copy every new field). Use a copy constructor, a static factory, or a builder. If you must clone, document depth and copy every mutable field.

Open in Java Language →

Instead of serializing the real object (which skips constructors), you write a private static nested DTO that holds the logical data. writeReplace emits the DTO; readResolve on the DTO constructs a real instance through the normal constructor, restoring invariants. It is the adult alternative to a huge readObject.

Open in Java Language →

Java objects in native code are handles. Local refs are freed when the native method returns; leaking many locals in a tight C loop OOMs. Global refs are GC roots until deleted. A raw pointer into a Java array is only valid while pinned or in a critical section, especially under ART's moving CC. Details and JNIEnv belong on C language.

Open in Java Language →

Install or idle dexopt runs dex2oat at a compiler filter (verify, speed-profile, ...). Profiles from production or the cloud tell it which methods to compile. A JIT still compiles hot methods that were not AOT'd. After OTA, filters rerun (first-boot cost). Zygote's boot image is a pre-initialized set of framework classes. This is why "is the APK interpreted?" is the wrong binary question.

Open in Java Language →

Moving means object addresses change; native code that cached a pointer without pinning is use-after-free. Zygote shares pages copy-on-write; a compacting collection that rewrites the preloaded heap would dirty those pages for every app. ART keeps an image space that is rarely moved so COW survives. Frameworks coverage of Zygote is in Android frameworks.

Open in Java Language →

A single expression of + is compiled to a builder or, on recent JDKs, invokedynamic concat strategies. A loop of s = s + chunk is still O(n²) allocations of growing immutable strings. Use StringBuilder (or append on one builder) for loops. Do not use StringBuffer.

Open in Java Language →

Adding a default method to an interface is source- and binary-compatible for existing implementors (they inherit it). Adding an abstract method is not. If a class already has a method with that signature, it wins. If two interfaces add conflicting defaults, the class must override. It is evolution of behaviour, not of state.

Open in Java Language →

When try-with-resources has a primary exception from the body and close throws, the close exception is attached via addSuppressed rather than replacing the primary. Print the stack and getSuppressed(). A hand-written finally that throws loses the primary unless you add suppressed yourself.

Open in Java Language →

For final fields, after the constructor finishes, if the reference is published safely (or even racy, for those finals only). For other fields, you need a happens-before (lock, volatile publication, join, class init). "I constructed it on thread A, thread B read the reference from a plain field" is not enough for non-finals.

Open in Java Language →

A Future is a handle for a result: get, cancel. A ForkJoinTask is a Future specialized for fork/join: fork (async in the pool), join (wait, may steal work instead of blocking the worker). RecursiveTask/RecursiveAction are the usual subtypes. Do not get() a ForkJoin task from inside another if you can join.

Open in Java Language →

exceptionally recovers to a value; handle sees result or error; whenComplete is a side-effecting callback; thenApply is skipped if the previous stage failed. Exceptions are wrapped; unwrap CompletionException. Never ignore a failed stage and then join on the UI thread.

Open in Java Language →

The bin index is a mask, (n - 1) & hash, which is a cheap modulo when n is 2^k. Resizing doubles n and re-bins each key to the same index or index + oldCap depending on the extra hash bit. A prime table (as some older maps used) needs a real modulo.

Open in Java Language →

A file (.art) containing already-initialized framework classes and interned strings that Zygote maps before it forks. App processes inherit those pages. Java code sees ordinary Class objects and strings; the performance story is fewer first-use initializers and shared RAM. Do not confuse it with the APK's own oat file.

Open in Java Language →

Arrays were covariant from Java 1.0 so String[] could be passed as Object[]; the VM checks stores. Generics are invariant (List<String> is not a List<Object>) because erasure cannot check stores the same way. Wildcards restore controlled variance. Mixing them (T[] via unchecked cast) is a heap-pollution vector.

Open in Java Language →

ClassNotFoundException is a checked exception from a loader API (Class.forName) when the class cannot be found. NoClassDefFoundError is an Error: the VM already failed to initialize or find a class that the bytecode assumes exists (often a leftover from a failed static initializer, or a missing transitive class at runtime). Interviewers use this to see if you distinguish Error from Exception.

Open in Java Language →

The mark word stores lock state: unlocked, biased (historically), thin/inflated monitor. Contended locks inflate to a full monitor object. Exact biasing has been disabled or removed on recent HotSpot releases; the interview point is that an uncontended lock is cheap and a contended lock is not, and that the header is involved. Do not build a design on biased locking existing on ART.

Open in Java Language →

Heap buffers are Java arrays: movable by GC, extra copy at many JNI/OS boundaries. Direct buffers live off-heap; good for I/O, but allocation is expensive, and you must not leak them (Cleaner / explicit free APIs). ART and JNI still need care with addresses. Prefer heap buffers until you measure a copy on a hot path.

Open in Java Language →

A structural add/remove happened during iteration: another thread, or the same thread calling list.remove instead of iterator.remove. Fail-fast saw modCount change. Fix: iterate with an Iterator and remove through it; or collect indices/items to remove after; or use a concurrent collection if another thread mutates. Do not catch CME and retry as a protocol.

Open in Java Language →

Lost updates, reads of half-resized tables, and on very old implementations an infinite loop during resize. Even "we only write during startup" fails if a reader races the last put. Fix: build the map then publish an immutable copy behind a volatile or a lock; or use ConcurrentHashMap; or confine the map to one thread. Never use HashMap as a concurrent cache.

Open in Java Language →

Usually hashCode (or a hash that does not use the same fields as equals). Or you mutated the key after insert. Or you mixed interned and non-interned assumptions. Write a unit test: two equal keys must retrieve the same entry. Include the key in a HashSet as a second check.

Open in Java Language →

A non-static inner Handler holds the Activity (this$0). A delayed message holds the Handler. After onDestroy the message is still in the main queue. Fix: static nested Handler + WeakReference<Activity>, and removeCallbacksAndMessages(null) in onDestroy. Same pattern for anonymous Runnables posted delayed. See Android frameworks.

Open in Java Language →

The main Looper is stuck in one message. If the stack is a synchronous Binder call, the server (or a chain of servers) is slow or its pool is exhausted. If the stack is Blocked on a monitor, find the holder: often a background thread doing I/O inside the same lock. Fix: do not do disk/network/slow Binder on the main thread; do not hold a shared lock across I/O. Timeouts: input ~5 s. Do not start designing AMS here.

Open in Java Language →

Take a thread dump (jstack, or ART SIGQUIT / ANR traces). Find two (or more) Blocked threads, each holding a monitor the other wants. Draw the cycle. Fix: one lock order everywhere, or combine locks, or try-lock with timeout and backoff. Add a regression test that stresses the two paths. Logging "I took lock A" is not enough without the dump.

Open in Java Language →

The worker came from a pool and still held the previous task's ThreadLocal. Fix: remove() in finally on every task, or use a framework that wraps tasks. Treat leftover ThreadLocals as a security bug, not a nuisance.

Open in Java Language →

The first method returns 2; the 1 is discarded. The second returns 0 and swallows the exception. That is why return in finally is a defect. Use try-with-resources and let the primary exception propagate.

Open in Java Language →

The Integer was null (map miss, Binder boxed extra, failed parse). Auto-unbox compiles to intValue(). Fix: keep it boxed until you null-check, use int primitives, or OptionalInt / a clear default. The same bug happens with Boolean extras on Intents.

Open in Java Language →

Spurious wakeup, or notifyAll for another condition, or a missed notify before wait. You must wait in a while that re-reads the queue under the same monitor. Also check that notify happens under that monitor after the put.

Open in Java Language →

The JMM allows the reference store to become visible before constructor field stores. HotSpot or ART, ARM vs x86, and JIT tiering change whether you lose the race. The bug is real even if x86 TSO hid it in a desktop loop. Add volatile or use a static holder. This is a JMM question, not an Android frameworks question.

Open in Java Language →

A classloader leak: static caches, ThreadLocals, shutdown hooks, JNI globals, or a listener still holding a class from the old loader. Heap dumps show the loader as a GC root cluster. On Android, leftover dex loaders from plugins do the same. Fix the root; raising Metaspace size only delays the crash.

Open in Java Language →

Heap pollution: the varargs array is erased, a caller passed mixed types or a raw type, and the compiler-inserted cast failed. Recreate with -Xlint:unchecked. Change the API to List<T>, or use @SafeVarargs only when you truly do not leak the array.

Open in Java Language →

The Comparator or compareTo returns 0 for those elements. Sorted collections use ordering as equality. Fix the comparator to be consistent with equals, or do not use a sorted set if you need equals-based uniqueness plus a different display order.

Open in Java Language →

Library not packaged for the ABI; wrong name (must map to libx.so); load order (depends on another .so); the class's static init ran before extract completed; the native symbol name does not match (overload mangling, wrong package). Java cannot fix a missing JNI_OnLoad export; that is the C side (C language).

Open in Java Language →

Shallow copy: both objects hold the same list reference. Copy the list (new ArrayList<>(old) or List.copyOf if elements are immutable) in the clone or, better, a copy constructor. Deep-copy elements if they are mutable. Document the depth.

Open in Java Language →

Allocations on the main thread: boxing in a draw loop, hidden StringBuilder via +, stream pipelines, iterator objects, autoboxing in HashMap of Integer. Fix by reusing buffers, primitive collections or arrays, moving work off the main Looper. Then look at ART collector pauses as a second-order effect. Do not start rewriting AMS.

Open in Java Language →

Boxed extras can be missing. == true unboxes. Use a primitive getter with a default, or null-check. Do not put boxed types on a hot AIDL API; use boolean plus a separate "was set" if you need three-state, or a small Parcelable. See Binder and AIDL.

Open in Java Language →

Optional is an object (and the boxed payload may be too). In a per-pixel or per-message loop, use primitives, -1 sentinels, or a preallocated holder. Keep Optional on API boundaries, not in the inner loop. Same story for stream pipelines over a 4-element list.

Open in Java Language →

Parallel streams use the common ForkJoinPool. Blocking or CPU-heavy work there starves other parallel streams and some library tasks. On a phone you also fight the UI for cores. Fix: do not use parallel() for I/O or tiny data; use a dedicated bounded executor for background Java work; never parallelize on the main thread.

Open in Java Language →

"x" is the pooled literal. new String("x") copies it into a new heap object. == is identity. a.intern() == b is true because intern returns the pooled instance. Production code should use equals. Interning arbitrary input fills the heap pool.

Open in Java Language →

Defensive copy on the way in (List.copyOf(in) or new ArrayList<>(in) then wrap). Return an unmodifiable view of your private copy, or another copy. If you only wrap the caller's list as unmodifiable, the caller still mutates the backing list. Document whether the class takes ownership.

Open in Java Language →

Overload resolution uses the static type. If the argument is a String variable that happens to be null, log(String) is chosen. If the argument is null with no type (a raw null literal) and both apply, the most specific method wins (String is more specific than Object). This is compile-time; override would be runtime. Interviewers use this to mix overload with null.

Open in Java Language →

Tests called run on the test thread. Production must start(). The task never raced, so race bugs hid. Also check that the production path does not run a Runnable that was meant for an executor. Add a test that asserts work happened on a different thread name if the contract requires it.

Open in Java Language →

Deterministic destruction (RAII), a type system that can encode ownership and interfaces (references, const, overloading, templates), and the STL. You write fewer manual acquire/release pairs and you can express generic algorithms without macros. You still compile to the same kind of machine code and you still have UB if you break the abstract machine.

Open in C++ Language →

Pointers and arrays, struct layout and padding, stack vs heap, the compilation and linking model, calling conventions, syscalls and file descriptors, and C undefined behavior (use-after-free, overflows, data races). Android native work constantly drops to that layer. See C.

Open in C++ Language →

Resource Acquisition Is Initialization: the constructor acquires a resource (memory, fd, lock, mapping) and the destructor releases it. Scope exit, return and exception unwind all run destructors, so you do not write a cleanup path for every exit. Smart pointers and lock_guard are RAII. The kernel, being C, uses other patterns (devm_*, goto cleanup); that is a different world (Linux kernel & BSP).

Open in C++ Language →

The text the compiler actually compiles: one source file after the preprocessor has expanded #include, macros and conditionals. Each .cpp is typically one translation unit and becomes one object file. Templates and inline exist because the compiler does not automatically see the whole program.

Open in C++ Language →

Each function, variable, class and template specialization may have only one definition in the program. Inline functions, inline variables and templates may be defined in multiple translation units if those definitions are identical. Two different definitions (often from a header compiled with different macros) are an ODR violation and undefined behavior, even if the linker is silent.

Open in C++ Language →

It means the definition is allowed to appear in more than one translation unit and the linker must merge them. It is not a command to put the body in every call site; the optimizer inlines with or without the keyword. Put non-template function definitions in headers only if they are inline (or constexpr, which is implicit inline).

Open in C++ Language →

To give a function C linkage: no C++ name mangling, so a C caller, the dynamic linker, or the JVM (JNI) can find the symbol by its C name. It does not make the function "C" internally; it can still use C++ types in the body. You cannot overload two extern "C" functions with the same name.

Open in C++ Language →

The compiler encodes parameter types (and some qualifiers) into the linker symbol so foo(int) and foo(double) can both exist. On Android/Linux this is the Itanium ABI scheme (_Z...). nm or llvm-cxxfilt demangles. C symbols are not mangled this way, which is why mixed-language APIs need extern "C".

Open in C++ Language →

Virtual bases (from the most-derived constructor), then direct bases in base-list order, then members in declaration order, then the constructor body. Destruction is the exact reverse. Initializer-list order does not change member construction order. If a later member throws, already-constructed members and bases are destroyed.

Open in C++ Language →

A per-class table of pointers to virtual functions (plus RTTI and offset-to-top for multiple inheritance). A polymorphic object typically holds a hidden vptr to the vtable of its dynamic type. A virtual call loads the vptr, indexes a slot, may adjust this, and performs an indirect call.

Open in C++ Language →

A non-virtual call is resolved at compile time from the static type (and can be inlined easily). A virtual call is resolved at run time from the dynamic type through the vtable. Use virtual for "is-a" interfaces you will call through a base; do not make everything virtual (cost + it becomes part of your ABI).

Open in C++ Language →

A virtual function declared = 0. A class with at least one unimplemented pure virtual is abstract: you cannot instantiate it. Derived classes must override it (or stay abstract). A pure virtual destructor still needs a definition, because derived destructors call it.

Open in C++ Language →

Copying or assigning a derived object into a base value copies only the base subobject. Virtual overrides and derived members are gone. Avoid it: pass polymorphic types by pointer or reference, and store unique_ptr<Base> in containers, not Base by value.

Open in C++ Language →

An lvalue names an object that has identity and is not treated as expiring (a variable, *p). An rvalue is either a prvalue (a temporary / initializer like T{}) or an xvalue (something that is about to expire, like std::move(x)). Rvalues bind to T&& and can be moved from. "Left of equals" is the pre-C++11 slogan and is incomplete.

Open in C++ Language →

It is a cast to an rvalue reference: static_cast<T&&>(t). It does not move memory. Overload resolution may then pick a move constructor or move assignment. If none exists, or the object is const, a copy is used. After a move, STL objects are valid but unspecified (usually empty, still destructible).

Open in C++ Language →

Copy when you need two independent objects. Move when you are finished with the source and want to transfer its resources in O(1) (buffers, unique ownership). Pass cheap types by value; pass large read-only objects by const T&; pass transferable sinks by value or T&&. Return locals by name so NRVO / elision can apply.

Open in C++ Language →

If every resource is already owned by a member that knows how to copy, move and destroy itself (string, vector, unique_ptr), do not write a destructor or copy/move members. The compiler-generated ones are correct. This is the default for new C++ classes.

Open in C++ Language →

Rule of Three (C++98): if you need a custom destructor, copy constructor or copy assignment (raw owning pointer), you need all three, or copies will double-free or leak. Rule of Five (C++11): writing any of those suppresses implicit moves, so you must also write or = delete the move constructor and move assignment. All five, or none.

Open in C++ Language →

unique_ptr is exclusive, move-only, zero overhead beyond the pointer (empty deleter can EBO). shared_ptr shares ownership with an atomic strong count in a control block; copies are not free. weak_ptr observes without keeping the object alive; lock() tries to promote to shared_ptr. Default to unique_ptr.

Open in C++ Language →

They pair allocation with construction so you do not write naked new. make_shared usually does one heap allocation for the object and the control block, and is exception-safer than shared_ptr<T>(new T) in expressions with multiple arguments. Use a custom deleter when you cannot.

Open in C++ Language →

Copying an auto_ptr transferred ownership and nulled the source, so passing by value silently emptied the caller. It did not work in standard containers. unique_ptr is move-only and correct. C++17 removed auto_ptr.

Open in C++ Language →

new allocates and constructs; delete destroys and deallocates. malloc/free only deal in raw bytes and do not call constructors or destructors. Mixing them ( free of new, delete of malloc) is undefined. Prefer containers and smart pointers over both in C++ code.

Open in C++ Language →

A new that constructs an object in storage you already have: new (buf) T(args). It does not allocate. You destroy with p->~T(), not delete p. Used by vector, optional and variant. The buffer must be aligned for T.

Open in C++ Language →

vector is the default: contiguous, O(1) index, amortized O(1) append, best cache behavior. deque when you need O(1) insert/erase at both ends and still want random access. list when you need stable iterators and O(1) splice given a position; it is node-based and usually the wrong default because of cache misses. Interview default is vector unless you can name the extra need.

Open in C++ Language →

map is an ordered tree (typically red-black): O(log n), no hash, iterates in key order, stable iterators except for the erased node. unordered_map is a hash table: average O(1), worst O(n), needs a hash and equality, rehash invalidates iterators. Use map for order or for types that are painful to hash; use unordered_map for average speed and call reserve when you know the size.

Open in C++ Language →

std::string stores a short string inside the string object (commonly 15 characters on 64-bit libc++, sometimes more) and heap-allocates only when it grows past that. Moving a short string may copy those bytes; moving a long string steals a pointer. A char* obtained from c_str() dangles if the string reallocates or dies.

Open in C++ Language →

const means this access path will not mutate (plus some compiler assumptions for objects that were defined as const). constexpr means the function or variable can participate in constant evaluation: it may run at compile time if the arguments allow, and the same function can still run at runtime. A constexpr variable is implicitly const.

Open in C++ Language →

It promises the function will not throw. If it does, the program calls terminate. The promise is used by the type system: vector relocates by move only when the move constructor is noexcept; otherwise it copies so a throw can still leave the container valid. Mark genuine non-throwing moves and swaps noexcept.

Open in C++ Language →

Two threads access the same memory location, at least one access is a write, the object is not atomic, and the accesses are not ordered by happens-before (a mutex, an atomic acquire/release pair, etc.). That is undefined behavior, not "last writer wins". Fix it with a mutex, with std::atomic, or by not sharing.

Open in C++ Language →

Use-after-free or a dangling reference; using a vector iterator after a reallocation; signed integer overflow; a data race; accessing an object through an incompatible type (strict aliasing). Also: mismatched new/delete[], calling a virtual through a dangling pointer, and writing through const_cast to a truly const object.

Open in C++ Language →

A compiler-generated function object: a unique class with operator() and optional capture members. [] captures nothing; [=] copies; [&] references; prefer explicit [x, &y]. A capture-less lambda can convert to a function pointer. If the lambda outlives the captured locals, you have a dangling reference.

Open in C++ Language →

The kernel needs a tiny stack, no hidden allocations, no exceptions, no RTTI, a stable C ABI for modules, and control over every instruction in atomic context. C++ features (exceptions, constructors in unexpected places, name mangling, a heavy runtime) fight that. Linux is a C abstract machine plus kernel APIs. Userspace Android (daemons, HALs, NDK) is where C++ belongs. See Linux kernel & BSP.

Open in C++ Language →

LLVM libc++, linked as c++_shared or c++_static. It is not GNU libstdc++. Do not pass std::string or containers across a boundary compiled with a different STL or ABI. Keep public .so APIs in C types, NDK binder types, or AIDL.

Open in C++ Language →

Almost always start with unique_ptr: exclusive ownership, no atomic traffic, clear lifetime. Use shared_ptr only when lifetime is genuinely shared and cannot be expressed as "parent owns child" (sometimes caches, graphs, or async callbacks). Shared ownership is a design smell if everything is shared.

Open in C++ Language →

A reference is an alias: it must be bound at initialization, cannot be reseated (except via implementation tricks you should not use), and is not nullable. A pointer is an object that holds an address: it can be null, reseated, and used in arithmetic. Use references for required aliases and function parameters; use pointers for optional or reseatable non-owning views, and smart pointers for ownership.

Open in C++ Language →

Each used specialization is instantiated in the translation units that need it. Identical instantiations are merged at link time. Instantiating a heavy template in many TUs explodes compile time and object size. Mitigations: explicit instantiation in one .cpp plus extern template in the header, thinner headers, and (C++20, optional in interviews) modules.

Open in C++ Language →

A compiler snapshot of a stable prefix of includes so later files skip re-parsing them. It is a build-speed tool, not a language feature. If anything in the prefix changes, the PCH rebuilds. Android/Soong and many desktop builds use them for the expensive STL and platform headers.

Open in C++ Language →

Compiled callers assume a layout and a calling convention. Adding a virtual function (vtable slots move), adding a data member, changing a member type, switching -fno-exceptions/-fno-rtti, or mixing libc++ with libstdc++ can break a shared library without a source-level error. PIMPL and C APIs are the usual firewalls. Android VNDK exists because this problem is real at OS scale.

Open in C++ Language →

D inherits B and C, both inheriting A. Without virtual inheritance, D contains two A subobjects; names and conversions become ambiguous. Virtual inheritance shares one A, found via a vbase offset. It is slower and more complex; most Android code prefers a single abstract interface or composition instead of diamonds.

Open in C++ Language →

In multiple inheritance, a pointer to the second base is not the address of the complete object. Converting Derived* to Base2* adds an offset. A virtual call through Base2 may apply a thunk that adjusts this before jumping to Derived::foo. Single inheritance usually has offset 0.

Open in C++ Language →

An empty class object still has size 1 so two instances have distinct addresses. An empty base can occupy zero bytes. unique_ptr<T, EmptyDeleter> can therefore be one pointer wide. C++20 [[no_unique_address]] allows a similar optimization for members. Interviewers use this to see if you know why a custom deleter's size matters.

Open in C++ Language →

A glvalue has identity (lvalue or xvalue). A prvalue is a pure initializer/temporary (literals, T{}, a function returning T by value) and is the thing C++17 materializes into an object. An xvalue is an expiring glvalue: std::move(x), or a member of an rvalue. Move constructors bind to rvalues (xvalue or prvalue).

Open in C++ Language →

Since C++17, initializing an object from a prvalue of the same type does not require a copy or move (the object is constructed in place). NRVO is optionally constructing a named local directly in the return slot; it is allowed but not required. return std::move(local) turns the local into an xvalue and blocks NRVO, so you may get a move instead of true elision. Return the name.

Open in C++ Language →

When the class owns a raw resource or maintains an invariant that member-wise copy/move would break, and you did not wrap that resource in an existing RAII type. Write a correct destructor, deep or deleted copies, and moves that steal and null the source. Self-assignment and moved-from destruction must be safe. Prefer wrapping and returning to Rule of Zero.

Open in C++ Language →

T& operator=(T other) { swap(*this, other); return *this; } — the parameter is copy-constructed or move-constructed. If that construction throws, *this is unchanged (strong guarantee). swap exchanges guts and should be noexcept. The parameter then destroys the old guts. Self-assignment is naturally safe because you work on a copy.

Open in C++ Language →

A strong (use) count, a weak count, a deleter, and an allocator (type-erased). When the strong count hits 0 the deleter runs and the object is destroyed. When both counts hit 0 the control block is freed. weak_ptr increments only the weak count. Formula: destroy object iff strong==0; free block iff strong==0 and weak==0.

Open in C++ Language →

The mixin stores a weak_ptr that shared_ptr's constructor arms when it takes ownership of an object that inherits the mixin. shared_from_this() locks that weak pointer. If no shared_ptr owns the object yet (stack object, raw new without immediately wrapping, or a second control block), you get bad_weak_ptr. Never construct shared_ptr<T>(this) yourself.

Open in C++ Language →

When release is not delete: fclose, close, free, ANativeWindow_release, HIDL release, or an arena. Put the deleter type in the unique_ptr signature. A function pointer costs a word; an empty functor can be EBO'd. shared_ptr type-erases the deleter in the control block so the pointer type stays shared_ptr<T>.

Open in C++ Language →

Breaking parent/child or observer cycles so refcounts can hit zero; caches that should not keep the object alive; "call me if I still exist" callbacks (Android listeners, Binder death). You lock() to get a shared_ptr or skip the callback if expired. Android's wp<T> is the same idea in the old RefBase world.

Open in C++ Language →

Containers allocate raw memory through an allocator, then placement-construct elements, and later destroy then deallocate. allocator_traits supplies defaults so a custom allocator can be small. vector<T, A> is a different type from vector<T>. C++17 pmr adds a runtime memory resource. Interviews want this mental model, not a full allocator implementation.

Open in C++ Language →

alignof(T) is the alignment the type requires. alignas(N) requests at least that alignment on a variable or type. Over-aligned types (SIMD, cache-line padded atomics) need C++17 aligned operator new or a custom allocator. Placement new into an under-aligned buffer is UB.

Open in C++ Language →

After you destroy an object and placement-new a new one in the same bytes, old pointers can be assumed by the compiler to still refer to the old object (especially with const or reference members). std::launder(p) returns a pointer the compiler must treat as pointing at the new object. You rarely write it by hand; know the sentence for lifetime-reuse questions.

Open in C++ Language →

In template<class T> void f(T&& x), T&& is a forwarding (universal) reference: lvalues make T a reference, rvalues make T a non-reference. std::forward<T>(x) casts x back to that category so a callee can move only from rvalues. A non-template T&& is just an rvalue reference and binds only rvalues.

Open in C++ Language →

Prefer extra function overloads (including additional function templates). Full specialization of function templates does not participate in overload resolution the way people expect and is easy to get wrong. For classes, full and partial specialization are the normal tools (vector<bool> is the infamous partial-specialization example; do not imitate its proxy-reference design).

Open in C++ Language →

Substitution Failure Is Not An Error: if substituting template arguments into a function template's declaration fails, that candidate is discarded. enable_if, void_t and decltype in the signature are the pre-C++20 tools for "this overload exists only if T has X". Hard errors inside the body are still hard errors; the failure must be in the immediate context of the signature.

Open in C++ Language →

Concepts name requirements (std::integral, std::ranges::range) and participate in overload resolution with better diagnostics. They replace most enable_if boilerplate. You should still recognize SFINAE in older codebases (including a lot of Android). Interviews often ask you to constrain a template both ways.

Open in C++ Language →

Derived inherits Base<Derived>. Base calls static_cast<Derived*>(this)->impl(): compile-time polymorphism, no vtable, easy inlining, but each Derived is a different type so you cannot put them in one vector<Base*>. Use CRTP for mixins and static interfaces; use virtual when you need runtime heterogeneity.

Open in C++ Language →

A parameter pack class... Ts holds zero or more types or values and expands with Ts.... Recursive instantiations used to process packs; C++17 folds reduce them: (0 + ... + args), (os << ... << args). make_unique and tuple factories forward packs with std::forward<Args>(args)....

Open in C++ Language →

When capacity is exhausted, the vector allocates a larger buffer (libc++ doubles; some libraries use 1.5×), move-or-copies elements, and frees the old buffer. The cost of copies across a sequence of n pushes is a geometric series, so the average extra cost per push is constant. reserve(n) removes the reallocations if you know n.

Open in C++ Language →

Any insert or push_back that grows past capacity reallocates and invalidates everything. Even without reallocation, insert in the middle invalidates from the insert point to the end. Erase invalidates from the erase point to the end. reserve that grows also invalidates. Holding data() across a growing push_back is the same bug.

Open in C++ Language →

Separate containers from operations. Iterators are the glue. Name the algorithm (find_if, transform, lower_bound) instead of an ad-hoc loop so intent and edge cases stay correct. Algorithms require an iterator category (sort needs random access). Do not hand-roll a binary search in an interview if lower_bound applies.

Open in C++ Language →

Ranges algorithms take a range, not two iterators. Views (filter, transform) are lazy and usually non-owning: they dangle if the underlying container dies. They compose with |. You are not expected to implement a view; you should know they do not copy the data by default and that some views are not sized or not random-access.

Open in C++ Language →

On a data member, it may be modified from a const member function. Legitimate uses: a mutex protecting logical const, or a cache. On a lambda, mutable makes operator() non-const so by-value captures can be updated. It is not a way to dodge thread safety.

Open in C++ Language →

If the object was defined as const (or is a const member of a const object, or lives in ROM), any write through a stripped pointer is UB. Casting away const to call a C API that does not mutate is a common non-UB use. Prefer const-correct overloads so you do not need the cast.

Open in C++ Language →

consteval (C++20): the function can only be called at compile time. constinit: this variable must be statically initialized (no dynamic constructor order surprises). Both are light interview topics; mention them as C++20 tools, not everyday NDK vocabulary.

Open in C++ Language →

No-throw: cannot throw. Strong: completes or leaves state as before (copy-and-swap). Basic: no leaks and invariants hold, but state may have changed (typical STL container guarantee). No guarantee: leaks or corruption; unacceptable. State which one your function offers.

Open in C++ Language →

Unwind tables cost size; an uncaught exception in a daemon or through JNI/Binder is fatal; APIs already use status codes (status_t, ScopedAStatus). The same builds often use -fno-rtti. App NDK modules may enable exceptions, but you must not throw into the VM or across a C callback. Destructors still must not throw.

Open in C++ Language →

lock_guard is the default RAII lock: lock in the constructor, unlock in the destructor; no API to unlock early. unique_lock can defer lock, unlock/relock, and is what condition_variable::wait requires because wait must unlock the mutex while sleeping. Prefer lock_guard unless you need those features. C++17 scoped_lock locks multiple mutexes deadlock-avoidingly.

Open in C++ Language →

relaxed: atomic RMW or load/store with no inter-thread happens-before. release store pairs with an acquire load: writes before the release become visible after the acquire. acq_rel is both on an RMW. seq_cst is the default single total order; easiest to reason about. Mutex lock/unlock already provide acquire/release.

Open in C++ Language →

Hold a unique_lock on the same mutex that protects the predicate. Wait in a loop or with a predicate: cv.wait(lk, [&]{ return ready; });. The wait unlocks, sleeps, re-locks, and rechecks because of spurious wakeups and lost-wakeup races. Notify with notify_one or notify_all after changing the predicate under the mutex.

Open in C++ Language →

Not automatically. The object is still alive and must be destructible and usually assignable. STL types specify "valid but unspecified" (often empty). Calling methods that assume old invariants (dereference a moved-from unique_ptr, use a moved-from container as if full) is a logic bug and can become UB. Do not rely on the source still holding its value unless the type documents it (e.g. moved-from unique_ptr is null).

Open in C++ Language →

Captures by value of the data you need, or shared_ptr / weak_ptr to the object, or C++17 [*=this] if a copy is correct. [&] and [this] require the referenced objects to outlive the task. This is a common SurfaceFlinger / thread-pool / Binder callback bug.

Open in C++ Language →

Type erasure: a vtable-like call and, if the callable does not fit the small buffer, a heap allocation. Copying a function may allocate again. In a hot loop use a template, a function pointer, or a concrete functor. Fine for infrequent callbacks (UI, setup). std::move_only_function is C++23 (optional) for move-only callables.

Open in C++ Language →

Export extern "C" JNI functions or RegisterNatives from JNI_OnLoad. Do not let a C++ exception escape into ART; catch and ThrowNew. Manage local refs in long loops. Own Java objects with global refs inside RAII. Own native heaps that Java holds via a jlong and a disposer. See Java for the VM side.

Open in C++ Language →

At template definition time the compiler looks up non-dependent names. Dependent names (those that depend on a template parameter) are looked up again at instantiation. That is why you often need this->member or a using in a dependent base, and why a missing typename on a dependent type is an error. It explains "it compiled until I instantiated it" bugs.

Open in C++ Language →

template class Foo<int>; in one .cpp forces that specialization to be emitted there. extern template class Foo<int>; in headers tells other TUs not to emit it. This cuts compile time for widely used specializations. It is an ODR/build-hygiene tool, not a new language meaning of the template.

Open in C++ Language →

Each base that introduces virtuals typically has its own vptr. A call through Base2* uses Base2's vtable. The slot may point at a thunk that subtracts (or adds) the this offset and then jumps to Derived::fn. Offset-to-top in the vtable recovers the complete object for dynamic_cast and delete. Formula: (*vptr[i])(this + δ).

Open in C++ Language →

Trivial: the compiler can treat copy/move/destroy as memcpy-ish (no user special members, no virtuals, trivial members). Standard-layout: C-like layout (one control block of access, no virtuals, consistent types) so you can interoperate with C and offsetof. POD is the old name for roughly both. A virtual function kills both. Android HAL C structs should stay standard-layout.

Open in C++ Language →

The destructor starts (or the storage is reused / released). Storage duration is separate: automatic, static, thread, dynamic. A pointer to storage is not a pointer to an object after lifetime ends. Placement new starts a new lifetime in the same bytes. Returning a reference to an automatic object ends lifetime at the } and dangles.

Open in C++ Language →

Optional/variant/union-like types destroy T and construct U in the same buffer. After that, the compiler may assume a pointer still refers to the old T if T had const or reference members. std::launder is the standard way to get a pointer to the new object. In interviews, pairing "placement new + explicit dtor + alignment + launder if needed" is a complete answer.

Open in C++ Language →

Defaults: construct/destroy via placement new and explicit dtor, rebind to allocate a different type (list nodes), pointer typedefs, and propagation traits (whether a container copy copies the allocator). You can write a minimal allocator with just allocate/deallocate and let the traits fill the rest.

Open in C++ Language →

A uniform value type that can hold many concrete types via a hidden vtable or function pointers: std::function, std::any, shared_ptr's deleter, some Binder type-erased callbacks. You pay an indirect call and often a heap allocation. Contrast with templates (open at compile time, no single type) and virtual bases (intrusive, one hierarchy).

Open in C++ Language →

When you are on C++17 (common in older NDK and vendor trees), when you must match an existing trait-based API, or when the constraint is a quick void_t detect-member trait. In C++20 new code, prefer a concept or a requires clause. Both implement "this overload exists only if".

Open in C++ Language →

(std::cout << ... << args); is a binary left or right fold depending on placement. A unary fold over an empty pack is ill-formed for most operators; &&, || and , have defined empty values. Always think about the zero-argument call of a variadic function.

Open in C++ Language →

A replacement for textual includes: a module is compiled once and imported as a semantic unit, which can cut compile time and stop macro leakage. Android builds are still header-dominated; treat modules as optional knowledge. Do not claim the NDK is modules-first unless the interviewer is exploring the standard, not the platform.

Open in C++ Language →

C++20 operator<=> returns a comparison category (strong_ordering, partial_ordering, …). The compiler can synthesize == and the relational operators. Useful for writing one comparison instead of six. Optional follow-up: partial_ordering for floats because NaN.

Open in C++ Language →

It is the partial order that makes a write visible to a later read. Sequenced-before (same thread) plus synchronize-with (mutex unlock/lock, release/acquire atomics, thread create/join) compose into happens-before. If a write does not happen-before a read of the same location, and they conflict, you have a data race unless the location is atomic.

Open in C++ Language →

A lock-free algorithm reads A, another thread changes A to B and back to A, and a compare-exchange succeeds as if nothing happened even though the meaning of A changed (for example a freed-and-reallocated node). Tagged pointers, hazard pointers, epoch reclamation (RCU-like) or just using a mutex are the usual answers. Mention it if they ask about lock-free stacks.

Open in C++ Language →

It captures the current exception (current_exception) so you can store it, pass it across threads, and rethrow_exception later. Useful when a worker cannot throw into the thread that must handle the error. On -fno-exceptions builds this machinery is not available; you pass error codes instead.

Open in C++ Language →

If move can throw, vector reallocation copies instead, so a throw mid-copy can destroy the extra elements and still leave the original buffer intact (strong guarantee). If you mark a throwing move noexcept, a throw during reallocation calls terminate. Implement moves that only steal pointers and mark them noexcept.

Open in C++ Language →

Unqualified lookup also searches namespaces associated with the argument types. using std::swap; swap(a, b); finds a friend swap for your type if you provided one, otherwise std::swap. That is why a hidden friend swap is the recommended customization point. The same mechanism finds operator<<.

Open in C++ Language →

T x(U()); is parsed as a function declaration (x returns T, takes a function taking U), not an object. Fix with braces: T x{U{}}; or extra parentheses. It is a C++03 leftover that still bites people who write functional casts as constructors.

Open in C++ Language →

Binding a temporary to a local const T& or T&& extends its lifetime to that reference. The extension does not pass through a function that returns a reference to its parameter: const T& f(const T& x){ return x; } const T& r = f(T{}); dangles. Member references and std::tuple of references also do not extend in the way people hope.

Open in C++ Language →

You may access an object only through a glvalue of a compatible type (same type, similar, or char/unsigned char/std::byte). Casting a float* to int* and dereferencing is UB; the compiler will assume they cannot alias and reorder loads. Use memcpy, std::bit_cast (C++20), or a union only in the narrow cases the standard allows (and prefer memcpy/bit_cast).

Open in C++ Language →

The standard says unsigned arithmetic is modulo 2ⁿ. Signed overflow is UB so compilers can assume x + 1 > x for signed x and can widen to a larger register. Use unsigned (or a checked API) for wraparound; use a wider type if you need to detect overflow. Sanitizers flag signed overflow.

Open in C++ Language →

Lambdas are readable, have obvious capture lifetimes, and compose without nested bind placeholders. bind copies arguments, is hard to overload, and surprises people with nested binds. Read bind in old code; write a lambda. std::bind_front (C++20) is a narrower, saner leftover for partial application.

Open in C++ Language →

HIDL: hidl_string/hidl_vec, sp<IFoo>, hwbinder, hwservicemanager, no new HALs. AIDL NDK: ordinary std::string/vector (with ABI caution), ndk::ScopedAStatus, AIBinder, servicemanager or vndbinder, required for vendor. Both are Binder; the type system and process rules differ. Details: Binder & AIDL.

Open in C++ Language →

They are long-lived, privileged, performance-sensitive userspace daemons: composition every vsync, and networking policy/ioctls. C++ gives RAII and types without the GC pauses of Java. They are not the kernel; they talk to drivers through HAL and syscalls. See Android frameworks.

Open in C++ Language →

Different ABIs: layout of string (SSO, pointers), vector, typeinfo, and exception types. The symbols are mangled in related but not interchangeable ways. The call may link if you are unlucky and then corrupt the heap. Use a C API, a POD struct, or a serialization format at the boundary.

Open in C++ Language →

A class holds a unique_ptr to an incomplete Impl defined only in the .cpp. Clients do not rebuild when Impl changes; the public class's size stays one pointer. Cost: an extra allocation and a pointer hop. Used to stabilize ABI and to hide platform headers from public headers.

Open in C++ Language →

C++20 non-owning view: pointer plus length (or a static extent). It does not allocate and does not extend lifetime. Use it for function parameters that need a contiguous range without forcing vector. Dangling is the same as a pointer. Prefer it over raw pointer + size pairs.

Open in C++ Language →

Optional: std::expected, std::mdspan, std::print / println, explicit object parameters ("deducing this"), std::flat_map / flat_set, std::move_only_function. Android NDK language level often lags. Lead with C++11–20 unless they ask about 23.

Open in C++ Language →

Construction runs base then members then derived. While the base constructor runs, the object's dynamic type is the base; the vptr points at the base vtable. The derived object is not yet formed, so calling a virtual "hook" from the base constructor will not reach derived. Use a two-phase init or a factory after construction completes.

Open in C++ Language →

Light/optional: co_await / co_return split a function into a state machine on the heap (unless optimized). They need a promise type and an executor/awaitable. Android framework code does not generally use them yet. If asked, say they are for async state machines and that lifetime of captured frames is the hard part; do not pretend they are how Binder works.

Open in C++ Language →

Members: T* ptr and a deleter. Delete copies. Move steals and nulls. Destructor calls the deleter if non-null. reset deletes then replaces; release returns the pointer and nulls. Provide *, ->, get. Mention array specialization and EBO for empty deleters. Then say you would use the standard type.

Open in C++ Language →

The local's lifetime ends at the closing brace. The returned reference dangles. Any use is UB (often a use-after-free when SSO spilled to the heap, or a wild stack read). Fix: return std::string by value and let elision/move handle it, or take an output parameter. Binding the return to a const string& in the caller does not extend a lifetime that already ended.

Open in C++ Language →

The original is valid but unspecified: it may be empty. Logging it is not necessarily UB, but you will not see the old text. If you then call an API that assumes a non-empty path (open a file), you get a logic failure. If you had a raw pointer into the old buffer, that pointer is now dangling. Do not use the source except to assign or destroy, unless the type documents more.

Open in C++ Language →

Look for cycles: parent owns child and child owns parent, or two listeners hold shared_ptrs to each other. Break one edge with weak_ptr. Tools: ASan leak mode, heap dumps, or logging custom deleters. Also check enable_shared_from_this callbacks that keep a shared_ptr in a global list forever.

Open in C++ Language →

Classic vector reallocation: capacity grew, the buffer moved, the iterator is dangling. Fix: reserve first, use indices, or structure the loop so you do not hold iterators across growth. The same bug happens with a pointer from data() or a reference to an element.

Open in C++ Language →

Two objects share one allocation. The first destructor frees it; the second is a double-free (UB). Assignment leaks the destination's pointer then double-frees later. This is the Rule of Three/Five failure. Fix: unique_ptr (Rule of Zero) or write all five members correctly (deep copy or deleted copies).

Open in C++ Language →

No. It is a data race and therefore UB. You may see lost updates, torn reads, or "impossible" optimizations. Use std::atomic<int> (relaxed is enough for a pure counter) or a mutex. "It works on x86" is not a C++ answer.

Open in C++ Language →

Completed bases and members are destroyed in reverse order. The object never started its lifetime, so the destructor of the class itself does not run. Resources held only as raw pointers assigned in the body can leak; RAII members do not. This is a standard argument for acquiring resources in member constructors, not in the body after a naked new.

Open in C++ Language →

If another exception is already in flight, std::terminate is called. Even without that, throwing from a destructor is banned by style and by noexcept destructors (the implicit destructor is noexcept if all members are). Swallow, log, or abort deliberately; do not throw.

Open in C++ Language →

Slicing: the vector holds Base values. Use vector<unique_ptr<Base>> (or a pointer/reference wrapper to existing objects). Also ensure Base has a virtual destructor if you delete through Base*.

Open in C++ Language →

Classic AB-BA: thread 1 holds A waits for B; thread 2 holds B waits for A. Fix: a global lock order, std::scoped_lock(a, b) (tries to avoid deadlock), or one mutex. On Android also think about Binder: do not hold a lock across an outgoing transaction that may re-enter. See Binder & AIDL.

Open in C++ Language →

Local references are only batched until the native method returns. In a tight loop, create a local frame or DeleteLocalRef each iteration. Also check for ExceptionOccurred after JNI calls. This is a C++ / JNI lifetime problem, not a Java GC mystery.

Open in C++ Language →

Exclusive session: unique_ptr with a custom deleter that powers down the device, or an RAII class. Shared between callbacks: shared_ptr plus weak_ptr for listeners so the HAL can die. Do not use raw new with a manual close on some paths only. AIDL NDK types like ndk::ScopedAStatus already follow RAII for the IPC result.

Open in C++ Language →

If push_back reallocated, v[0]'s address changed. The pointer is dangling. reserve before taking the pointer, or take the pointer only after the vector is stable, or use an index.

Open in C++ Language →

ABI break: vtable layout and object size (hidden vptr if it was the first virtual) changed. Old binaries still use the old offsets. This is why public NDK APIs and VNDK freeze layouts, and why PIMPL or a C API is used at stable boundaries.

Open in C++ Language →

Each copy is an atomic increment/decrement on the control block: cache-line ping-pong. Prefer a raw observer with a documented lifetime, a weak_ptr locked rarely, or a unique owner on the real-time thread. Measure; do not sprinkle shared_ptr in per-frame code out of habit. SurfaceFlinger-style paths care about this.

Open in C++ Language →

The object is not yet owned by a shared_ptr; the mixin’s weak pointer is empty. Construct with make_shared (or a factory that wraps immediately) and call shared_from_this only after that. Do not call it from the constructor of the object being made.

Open in C++ Language →

new T[n] must be released with delete[] so the compiler can destroy every element and pass the right size to the deallocator. delete on an array is UB. Prefer unique_ptr<T[]> or vector<T> so the pairing is automatic.

Open in C++ Language →

The thread still runs this->... on freed memory: use-after-free, UB. Join the thread in the destructor (and define a shutdown order), or capture a shared_ptr / weak pointer, or do not start a thread that outlives the object. Detached threads make this worse because you cannot join.

Open in C++ Language →

There is no unwind through that TU: terminate, or a worse abort if the exception personality is missing. Treat it as a process killer. The fix is to keep exceptions inside the library, compile the whole program consistently, or use error codes at the boundary. This is why Android native APIs prefer status returns.

Open in C++ Language →

Read the first instantiation that failed and the bottom note (the actual constraint or missing member). The middle is the call stack of templates. With C++20, a concept failure names the requirement. In C++17, look for enable_if / no type named .... Do not start rewriting from a random line in the STL.

Open in C++ Language →

If the object was born const, that write is UB. The compiler may keep the original value in a register or place the object in read-only memory (crash on write). If they needed mutation, the object should not have been const, or they should use mutable for a real cache under a lock.

Open in C++ Language →

Relaxed gives atomicity of the flag or pointer word, not visibility of the fields written before it. The writer must release-store the pointer (or the flag) after initializing the object; the reader must acquire-load. A mutex around both sides also works. This is the "publish a pointer" interview pair.

Open in C++ Language →

Slicing at the call boundary: the parameter is a new Base. Change the helper to Base& or const Base&, or pass unique_ptr<Base>. This is the same bug as vector<Base>.

Open in C++ Language →

Missing deleted copies (double close), missing move that sets the source to -1 (double close again), closing -1, not handling self-move, and throwing from the destructor if close fails. Show the five members or a unique_ptr with a deleter that calls close. See the sketch on this page.

Open in C++ Language →

When the problem needs index access, binary search, or cache-friendly scans: vector wins. list is for splice and stable node pointers. Saying "list because insert is O(1)" without "given an iterator" and without cache cost is a weak answer. See DSA for complexity framing.

Open in C++ Language →

Lost wakeup: notify happened before wait, and you did not check the predicate under the mutex. Always change the predicate under the lock, then notify; wait with a predicate loop so a notification that already happened is still seen. Also: using a different mutex on the two sides, or notify_one when several waiters need to run.

Open in C++ Language →

Often it is correct: the object died and lock() failed. Confirm the owner's lifetime (was the shared_ptr dropped too early?). If the callback must run, you needed shared ownership or a queued teardown. If it must not keep the object alive, empty lock is the feature, not the bug.

Open in C++ Language →

The old object's destructor never runs: leaks (if it owned heap), skipped side effects, and then you construct a second object in the same bytes without ending the first lifetime (UB). Pair every placement new with p->~T() before reuse or scope exit. Prefer optional<T> or a container.

Open in C++ Language →

Often yes: you block NRVO, so you force a move instead of constructing in place. Return local;. std::move on a return is for returning a member or a parameter you want to treat as an rvalue, not for a local of the return type.

Open in C++ Language →

Undefined behavior if the dynamic type is derived: only ~Base runs, derived members leak, and the deallocation size may be wrong. Make the destructor virtual (or protected-nonvirtual if you never delete through Base). This is asked constantly.

Open in C++ Language →

A future from std::async with default launch may block in its destructor until the task finishes. async(f).get() or even discarding the future can run the work synchronously from the caller's point of view. Prefer an explicit thread pool or store the future if you wanted overlap. Mention this when they ask about async.

Open in C++ Language →

A bad or colliding hash (all keys in one bucket), an adversarial key set, or a custom hash that is constant. Fix the hash, use a better mixer, or switch to map if n is moderate and you need worst-case bounds. reserve does not fix a broken hash. Mention load factor and bucket count.

Open in C++ Language →

a = a; (or overlapping aliases) frees the resource then copies from the freed pointer. Copy-and-swap is naturally self-assignment safe. A handwritten assign should either check this != &other or copy to a temporary first. Interviewers still like the explicit check plus a correct order: copy, then release, then take.

Open in C++ Language →

You held the mutex, made an outgoing Binder call, the other side called back into the same process on a binder thread, and that thread tried to take the same non-recursive mutex. Fix: never hold the lock across IPC; copy the data, drop the lock, then transact; or document a lock order that excludes Binder. Same pattern as Java lock + Binder. See Binder & AIDL.

Open in C++ Language →

Two copies of libc++ (or mixed ABIs) mean two heaps and two string layouts. Crossing the boundary can free with the wrong allocator or corrupt SSO. Keep STL types inside one linkage domain; expose C or AIDL types at the .so edge. This is an Android-specific ABI question.

Open in C++ Language →

Big-O is an asymptotic upper bound on how an algorithm's cost grows as the input size n grows. Constants and smaller terms are dropped because for large n they do not change which algorithm wins: O(3n + 100) and O(n) both double when n doubles, while O(n^2) quadruples. It lets you compare algorithms independent of hardware and language. In practice constants still matter for small inputs, so mention them when relevant (for example, insertion sort beats merge sort on tiny arrays).

Open in Data Structures & Algorithms →

Time complexity counts how the number of basic operations grows with n; space complexity counts how extra memory grows with n (auxiliary space, excluding the input and usually the output). Include hidden costs in space: the recursion stack (O(h) for tree DFS), copies from slicing, and hash maps or visited sets. Many problems trade one for the other, for example Two Sum goes from O(n^2) time and O(1) space to O(n) time and O(n) space with a hash map.

Open in Data Structures & Algorithms →

Amortized cost is the average cost per operation over a worst-case sequence. A dynamic array doubles its capacity when full, copying all elements (O(n)). But copies happen at sizes 1, 2, 4, ..., n/2, which sum to less than n. So n appends do at most about 3n work in total, which is O(1) per append on average. It is a guarantee over the sequence, not a probability, unlike "average case".

Open in Data Structures & Algorithms →

• Quicksort: O(n log n) average, O(n^2) worst when pivots are always the smallest or largest (for example, a naive first-element pivot on sorted input).
• Hash map lookup: O(1) average, O(n) worst if every key lands in one bucket. Java 8+ HashMap converts a bin of 8+ entries into a red-black tree only when table capacity is at least 64 (otherwise it resizes), so that bucket becomes O(log n).
• Quickselect: O(n) average, O(n^2) worst.
• Unbalanced BST: O(log n) average for random inserts, O(n) for sorted inserts.

Always say which case you are quoting; interviewers probe the worst case.

Open in Data Structures & Algorithms →

Array: O(1) random access, contiguous memory (cache friendly, fast scans), O(1) amortized append, but O(n) insert or delete in the middle. Linked list: O(1) insert after a known node; delete is O(1) on a doubly linked list or if you hold the previous node on a singly linked list, otherwise O(n). No resizing, but O(n) access and poor cache locality, plus pointer overhead per node. Default to arrays; choose linked lists when you splice at known positions often, as in an LRU cache's recency list or an OS free list.

Open in Data Structures & Algorithms →

A hash function turns the key into an integer, which is reduced modulo the table size to pick a bucket. On lookup the map hashes the key, goes to the bucket and compares keys with equality. Collisions are handled by:

• Chaining: each bucket holds a list of entries. Java 8+ HashMap treeifies a bin into a red-black tree when it has 8+ entries and the table capacity is at least 64; a smaller table resizes instead.
• Open addressing: probe for another slot (linear, quadratic, double hashing), as Python's dict does; deletions leave tombstones.

When the load factor (entries / buckets) passes a threshold (0.75 in Java), the table doubles and all keys are rehashed, which keeps operations O(1) amortized.

Open in Data Structures & Algorithms →

Java 8+ HashMap treeifies a bin into a red-black tree only when both conditions hold: the bin has at least TREEIFY_THRESHOLD (8) entries, and the table capacity is at least MIN_TREEIFY_CAPACITY (64). If the chain is long but the table is still smaller than 64, treeifyBin resizes the table instead of building a tree, because a tiny table with one long chain almost always means a poor hash and growing the table usually spreads the keys. After treeify, lookups in that bin are O(log n). The bin converts back to a list when it shrinks below UNTREEIFY_THRESHOLD (6), typically during a resize. Interviewers who only hear "8 entries" are looking for this capacity-64 nuance.

Open in Data Structures & Algorithms →

If you override equals() you must override hashCode() so that equal objects have the same hash. The contract: reflexive, symmetric, transitive, consistent; x.equals(y) implies x.hashCode() == y.hashCode(); unequal objects may share a hash (that is a collision). Breaking it puts equal keys in different buckets, so a map can store two "equal" keys or fail to find one you just inserted. Keys must be immutable while they sit in a map: changing a field that participates in the hash loses the entry. Python's rule is the same: objects used as dict keys must be hashable and their hash must not change.

Open in Data Structures & Algorithms →

A stack is LIFO: function call stack, undo history, browser back button, DFS, expression evaluation, matching parentheses, monotonic-stack problems. A queue is FIFO: BFS, job and print queues, producer-consumer buffers, request handling in order, level-order tree traversal. In Python use a list for a stack and collections.deque for a queue.

Open in Data Structures & Algorithms →

Use a heap when you only ever need the minimum or maximum: top-k, scheduling, Dijkstra, merging k lists. It gives O(1) peek, O(log n) push and pop, O(n) build, and is a compact array. Use a balanced BST when you need sorted iteration, floor or ceiling, range queries, or deletion of arbitrary elements, all in O(log n).

Open in Data Structures & Algorithms →

A trie is a prefix tree where each edge is a character; words that share a prefix share a path. Insert and search are O(L) for a word of length L, independent of the dictionary size. It beats a hash set when you need prefix operations: autocomplete, "does any word start with ...", word search on a grid with pruning, longest common prefix. A hash set can only answer exact membership. The cost is memory: many nodes, each with a child map or array.

Open in Data Structures & Algorithms →

BFS uses a queue and explores level by level, so it finds the shortest path in an unweighted graph and suits level-order problems and multi-source spreading. DFS uses recursion or a stack and goes deep, which suits path existence, connected components, cycle detection, topological sort and backtracking. BFS memory is the widest frontier; DFS memory is the maximum depth. Both are O(V + E).

Open in Data Structures & Algorithms →

Pre-order (node, left, right) for copying or serialising; in-order (left, node, right), which visits a BST in sorted order; post-order (left, right, node) for computing values from children such as height or diameter; and level-order (BFS with a queue) for per-level views. The first three are DFS variants and can be written recursively or with an explicit stack.

Open in Data Structures & Algorithms →

An adjacency list stores each vertex's neighbours: O(V + E) space, iterating neighbours costs O(degree), ideal for sparse graphs (most real graphs). An adjacency matrix is V x V: O(V^2) space, O(1) "is there an edge u-v?" check, better for dense graphs or algorithms like Floyd-Warshall. Interviews almost always expect an adjacency list built with a dict of lists.

Open in Data Structures & Algorithms →

Each comparison discards half the remaining range, so after k steps n/2^k elements remain; that reaches 1 when k = log2(n). A million elements need about 20 comparisons. It requires random access and a monotonic property: sorted data, or a yes/no predicate that flips from false to true exactly once. It does not work efficiently on linked lists because finding the middle is O(n).

Open in Data Structures & Algorithms →

A stable sort keeps elements with equal keys in their original relative order. Stable: merge sort, insertion sort, bubble sort, counting sort, radix sort, TimSort (Python's sorted, Java's object sort). Unstable: quicksort, heap sort, selection sort. Stability matters for multi-key sorting done in passes and is required inside radix sort.

Open in Data Structures & Algorithms →

Open in Data Structures & Algorithms →

A recursive function solves a problem by calling itself on smaller inputs until it reaches a base case. Each call uses a stack frame, so space is O(depth). Pitfalls: a missing or wrong base case (infinite recursion), exponential blow-up from recomputing the same subproblems (fix with memoisation), and stack overflow on deep inputs (Python's default limit is about 1000 frames). Convert to an explicit stack or iteration when depth can be large.

Open in Data Structures & Algorithms →

Optimal substructure: the optimal answer can be built from optimal answers to subproblems. Overlapping subproblems: the same subproblems are solved repeatedly by naive recursion. If subproblems are independent (merge sort's halves), it is divide and conquer, and caching does not help.

Open in Data Structures & Algorithms →

Memoisation is top-down: write the recursion and cache results by argument; it computes only the states you need and is easiest to derive. Tabulation is bottom-up: loops fill a table in dependency order; no recursion overhead or depth limit, and it enables rolling-array space savings. Both have the same time complexity, which is the number of states times the work per state.

Open in Data Structures & Algorithms →

One pass with a hash map from value to index. For each x, check whether target - x has been seen. O(n) time, O(n) space (brute force is O(n^2)). If the array is sorted and you need values, two pointers give O(1) space.

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

Open in Data Structures & Algorithms →

Duplicate: add to a set and return True on the first repeat; O(n) time and space (sorting gives O(n log n) time with O(1) extra). Anagram: equal lengths and equal character counts; O(n) with a 26-slot array or Counter.

def contains_duplicate(nums):
    return len(set(nums)) != len(nums)

def is_anagram(s, t):
    from collections import Counter
    return Counter(s) == Counter(t)

Open in Data Structures & Algorithms →

Push opening brackets on a stack; on a closing bracket, the stack top must be its matching opener. The stack must be empty at the end. O(n) time, O(n) space. Edge cases: empty string (valid), starting with a closer, leftover openers.

def is_valid(s):
    match = {')': '(', ']': '[', '}': '{'}
    st = []
    for c in s:
        if c in match:
            if not st or st.pop() != match[c]:
                return False
        else:
            st.append(c)
    return not st

Open in Data Structures & Algorithms →

Iterative: three pointers; save next, flip curr.next to prev, advance. O(n) time, O(1) space. Recursive: reverse the rest, then make the next node point back at the current one; O(n) stack space.

def reverse(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

def reverse_rec(head):
    if not head or not head.next:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head
    head.next = None
    return new_head

Open in Data Structures & Algorithms →

Use a dummy node and a tail pointer; repeatedly attach the smaller head; attach whatever remains. O(m + n) time, O(1) extra space.

def merge(a, b):
    dummy = tail = ListNode()
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

Open in Data Structures & Algorithms →

Post-order recursion: depth is 1 plus the larger child depth; null has depth 0. O(n) time, O(h) space. BFS counting levels also works and avoids deep recursion.

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Open in Data Structures & Algorithms →

Track the minimum price so far; the best profit is the maximum of price - min_so_far. O(n) time, O(1) space.

def max_profit(prices):
    lo, best = float('inf'), 0
    for p in prices:
        lo = min(lo, p)
        best = max(best, p - lo)
    return best

Open in Data Structures & Algorithms →

Swap the left and right children of every node, recursively or with BFS. O(n) time, O(h) space.

def invert(root):
    if root:
        root.left, root.right = invert(root.right), invert(root.left)
    return root

Open in Data Structures & Algorithms →

• HashMap: unsynchronized, no insertion-order guarantee, null key and values allowed. Default map in a single thread.
• LinkedHashMap: HashMap plus a doubly linked list of entries; iteration is insertion order (or access order, which is how Java implements LRU with removeEldestEntry).
• Hashtable: legacy, fully synchronized on every call, no nulls. Do not use it in new code.
• ConcurrentHashMap: thread-safe without locking the whole table (bin-level / CAS); no nulls. Use it for shared maps across threads. Iteration is weakly consistent (may miss or see concurrent updates) rather than fail-fast.

Python's dict is insertion-ordered and not thread-safe; use a lock or a concurrent structure if several threads mutate it.

Open in Data Structures & Algorithms →

Use an in stack for enqueue and an out stack for dequeue. Enqueue: push onto in, O(1). Dequeue: if out is empty, pop every element from in onto out (this reverses the order so the oldest item is on top), then pop out. Each element is moved at most twice, so dequeue is O(1) amortized. This is how some libraries hide a queue behind stack-only primitives, and it is a favourite interview question.

Open in Data Structures & Algorithms →

The number of edges (or nodes, clarify) on the longest path between any two nodes. It may not pass through the root. Recurse: for each node, compute the height of both children; the longest path through that node is left_height + right_height; the answer is the max of that over every node. Return height upward and thread the diameter through an outer variable or a pair. O(n) time, O(h) space. A common bug is returning only the path through the root.

Open in Data Structures & Algorithms →

It stores prefix sums in an array where index i (1-based) is responsible for a block of i & -i elements ending at i. A point update adds delta to i and then walks i += i & -i to update every block that contains i. A prefix query walks i -= i & -i and sums those blocks. Both are O(log n). Range sum is prefix(r) - prefix(l-1). Use it when you need many point updates mixed with prefix or range sums. A segment tree is more general (min, max, range updates with lazy propagation) but longer to write.

Open in Data Structures & Algorithms →

When you cannot binary search the input directly but the answer space is monotonic (if capacity x works, any larger capacity also works), binary search the answer value and test feasibility with a helper. Total cost is O(log(range) x cost of check). Example: Koko eating bananas. The minimum speed k such that all piles finish in h hours: ok(k) is sum(ceil(p / k)) <= h; search k in [1, max(piles)].

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        k = (lo + hi) // 2
        if sum((p + k - 1) // k for p in piles) <= h:
            hi = k
        else:
            lo = k + 1
    return lo

Open in Data Structures & Algorithms →

Keep a min-heap of (distance, node). Pop the closest unsettled node; its distance is now final. Relax each outgoing edge: if dist[u] + w < dist[v], update and push. O((V + E) log V) with a binary heap. It relies on the fact that once a node is popped, no later path can be shorter, which is only true with non-negative weights. With negative edges use Bellman-Ford (O(V x E), also detects negative cycles). For unweighted graphs plain BFS is enough; for 0/1 weights use 0-1 BFS with a deque.

Open in Data Structures & Algorithms →

Model as a directed graph and check for a cycle with Kahn's topological sort: compute in-degrees, enqueue zero in-degree nodes, pop and decrement neighbours. If every course gets processed, there is no cycle. O(V + E).

def can_finish(n, prereqs):
    g = [[] for _ in range(n)]; indeg = [0] * n
    for course, pre in prereqs:
        g[pre].append(course); indeg[course] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    done = 0
    while q:
        u = q.popleft(); done += 1
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return done == n

Course Schedule II returns the order itself (the popped sequence).

Open in Data Structures & Algorithms →

Union-Find (disjoint set union) keeps a parent pointer per element; the root identifies the group. find follows parents to the root; union links two roots. Two optimisations make it effectively constant time: path compression (flatten the path during find) and union by rank or size (attach the smaller tree under the larger). Together they give O(alpha(n)) amortized, where alpha is the inverse Ackermann function (at most 4 in practice). Uses: dynamic connectivity, cycle detection in undirected graphs, Kruskal's MST, number of provinces, accounts merge.

Open in Data Structures & Algorithms →

Greedy is correct when a locally optimal choice is provably part of some globally optimal solution, usually shown with an exchange argument (for example, choosing the meeting that ends earliest never hurts). If choices interact so that a good choice now can block a better combination later, you need DP to consider alternatives. A quick test: look for a small counterexample. Coin change with {1, 3, 4} and amount 6 breaks greedy (4+1+1) while DP finds 3+3.

Open in Data Structures & Algorithms →

Bottom-up heapify sifts down each internal node, starting from the last parent. Sift-down cost is proportional to a node's height, and most nodes are near the bottom: about n/2 nodes have height 0, n/4 height 1, n/8 height 2, and so on. The total is n x sum(h / 2^(h+1)), which converges to O(n). Inserting n items one by one is O(n log n).

Open in Data Structures & Algorithms →

Quicksort is in place (O(log n) stack), cache friendly, and usually fastest in practice, but O(n^2) worst case and not stable; random or median-of-three pivots and introsort fix the worst case. Merge sort is always O(n log n), stable, suits linked lists and external sorting, but needs O(n) extra memory for arrays. Libraries use hybrids: TimSort (merge + insertion) and introsort (quick + heap + insertion).

Open in Data Structures & Algorithms →

Directed: DFS with three states: unvisited, visiting (on the current recursion path), done. Reaching a "visiting" node means a back edge, which is a cycle. Or run Kahn's algorithm: if not all nodes are output, a cycle exists. Undirected: DFS where a visited neighbour that is not your parent means a cycle, or Union-Find where an edge joins two nodes already in the same set. A simple visited set is not enough for directed graphs, because two paths reaching the same node (a diamond) is not a cycle.

Open in Data Structures & Algorithms →

Sliding window with a last-seen index map. When the current character was seen inside the window, move left just past its previous occurrence. O(n) time, O(alphabet) space.

def length_of_longest(s):
    last, left, best = {}, 0, 0
    for r, c in enumerate(s):
        if last.get(c, -1) >= left:
            left = last[c] + 1
        last[c] = r
        best = max(best, r - left + 1)
    return best

Open in Data Structures & Algorithms →

Sort, fix index i, then two-pointer the rest for -nums[i]. Skip duplicate values for i and after each found triplet. O(n^2) time, O(1) extra apart from output and sorting.

def three_sum(nums):
    nums.sort(); res = []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i - 1]: continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0: l += 1
            elif s > 0: r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l - 1]: l += 1
                r -= 1
    return res

Open in Data Structures & Algorithms →

Two pointers at both ends. Area = min(h[l], h[r]) x (r - l). Move the shorter wall inward, because moving the taller one can never increase the area (width shrinks and the height is still capped by the shorter wall). O(n) time, O(1) space.

def max_area(h):
    l, r, best = 0, len(h) - 1, 0
    while l < r:
        best = max(best, min(h[l], h[r]) * (r - l))
        if h[l] < h[r]: l += 1
        else: r -= 1
    return best

Open in Data Structures & Algorithms →

The answer at i is (product of everything left of i) x (product of everything right of i). Fill left products in a forward pass, then multiply by a running right product in a backward pass. O(n) time, O(1) extra besides the output.

def product_except_self(nums):
    n = len(nums); out = [1] * n
    for i in range(1, n):
        out[i] = out[i - 1] * nums[i - 1]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

Open in Data Structures & Algorithms →

Map each word to a canonical key: its sorted letters (O(k log k)) or a tuple of 26 counts (O(k)). Group with a dict of lists. Total O(n x k log k) or O(n x k).

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = [0] * 26
        for c in w: key[ord(c) - 97] += 1
        groups[tuple(key)].append(w)
    return list(groups.values())

Open in Data Structures & Algorithms →

Count with a hash map, then either keep a min-heap of size k keyed by count (O(n log k)) or bucket-sort by frequency (O(n), because frequency is at most n). Quickselect on counts is O(n) average.

def top_k(nums, k):
    c = Counter(nums)
    return heapq.nlargest(k, c, key=c.get)

Open in Data Structures & Algorithms →

Min-heap of size k: push each element and pop when the size exceeds k; the heap top is the answer. O(n log k) time, O(k) space, works on streams. Quickselect gives O(n) average and O(1) extra space but O(n^2) worst case; randomise the pivot. Sorting is O(n log n) and acceptable as a baseline.

Open in Data Structures & Algorithms →

Sort by start. Walk through; if the current interval starts at or before the end of the last merged one, extend that end; otherwise start a new merged interval. O(n log n) time.

def merge(intervals):
    out = []
    for s, e in sorted(intervals):
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

Open in Data Structures & Algorithms →

Scan every cell; on unvisited land, flood-fill its whole island (DFS or BFS) marking cells visited, and count one island. O(R x C) time; recursion depth can reach R x C, so use BFS or an explicit stack for big grids. Union-Find is an alternative, useful when land is added dynamically (Number of Islands II).

Open in Data Structures & Algorithms →

Recurse with an allowed (low, high) range: the root has (-inf, +inf); a left child inherits (low, node.val), a right child (node.val, high). Alternatively an in-order traversal must be strictly increasing. O(n) time, O(h) space. Clarify how duplicates are treated.

def is_bst(node, lo=float('-inf'), hi=float('inf')):
    if not node: return True
    if not lo < node.val < hi: return False
    return is_bst(node.left, lo, node.val) and is_bst(node.right, node.val, hi)

Open in Data Structures & Algorithms →

General binary tree: if the root is null, p or q, return it; recurse left and right; if both sides return non-null, the root is the LCA; otherwise return the non-null side. O(n) time, O(h) space. For a BST, walk from the root: if both values are smaller go left, if both larger go right, otherwise the current node is the LCA, O(h).

Open in Data Structures & Algorithms →

Modified binary search. At each mid, one half is sorted. If the left half is sorted and the target lies inside it, search left; otherwise search right. Mirror for the right half. O(log n). With duplicates, the worst case degrades to O(n) because you may not be able to tell which half is sorted.

def search(a, t):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t: return mid
        if a[lo] <= a[mid]:                  # left half sorted
            if a[lo] <= t < a[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                                # right half sorted
            if a[mid] < t <= a[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

Open in Data Structures & Algorithms →

State dp[a] = fewest coins for amount a. Transition dp[a] = 1 + min(dp[a - c]) over coins c no larger than a. Base dp[0] = 0; unreachable amounts stay infinity, return -1. O(amount x coins) time, O(amount) space. BFS over amounts is an equivalent view (fewest steps). Greedy is wrong for arbitrary coin systems.

Open in Data Structures & Algorithms →

dp[i] = max(dp[i-1], dp[i-2] + nums[i]): either skip house i or rob it plus the best up to i-2. Only two previous values are needed, so O(n) time and O(1) space. House Robber II (circular) runs this twice, excluding the first house and then the last.

Open in Data Structures & Algorithms →

O(n^2) DP: dp[i] = LIS ending at i = 1 + max dp[j] over j < i with smaller value. O(n log n): maintain tails, where tails[k] is the smallest possible tail of an increasing subsequence of length k+1; for each x, binary search the first tail at least x and replace it (or append). The length of tails is the answer; tails itself is not necessarily a valid subsequence.

Open in Data Structures & Algorithms →

Prefix sums with a hash map of how many times each prefix sum has occurred. At each position, the number of subarrays ending here with sum k equals the count of earlier prefixes equal to running - k. Seed the map with {0: 1}. O(n) time and space. Sliding window does not work because negatives break monotonicity.

Open in Data Structures & Algorithms →

Monotonic decreasing stack of indices. For each day, pop all colder days from the stack; for each popped index the answer is the current index minus it. Push the current index. Each index is pushed and popped once: O(n).

def daily_temperatures(t):
    res, st = [0] * len(t), []
    for i, x in enumerate(t):
        while st and t[st[-1]] < x:
            j = st.pop(); res[j] = i - j
        st.append(i)
    return res

Open in Data Structures & Algorithms →

Backtracking. Subsets: at each start index record the current path, then try adding each later element; there are 2^n subsets, so O(n x 2^n). Permutations: try every unused element at each position; n! results, O(n x n!). With duplicates, sort first and skip an element equal to its predecessor at the same depth. An iterative alternative for subsets: for each number, add it to every existing subset. Bitmask enumeration also works for n up to about 20.

Open in Data Structures & Algorithms →

Use a dummy head and two pointers. Move fast n+1 steps ahead from the dummy, then move both until fast is null; slow.next is the node to delete. One pass, O(1) space. The dummy handles deleting the head.

def remove_nth_from_end(head, n):
    dummy = slow = fast = ListNode(0, head)
    for _ in range(n + 1): fast = fast.next
    while fast:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next
    return dummy.next

Open in Data Structures & Algorithms →

Floyd's algorithm: slow moves 1, fast moves 2. If they meet, reset one pointer to head and move both one step at a time; they meet at the cycle entry (because head-to-entry distance equals meeting-point-to-entry distance modulo the cycle length). O(n) time, O(1) space. A visited set also works in O(n) space.

Open in Data Structures & Algorithms →

Multi-source BFS: enqueue all rotten oranges at time 0, spread to fresh neighbours level by level, counting minutes. If fresh oranges remain at the end, return -1. O(R x C). The key insight is that starting BFS from all sources at once gives each cell its distance to the nearest source.

Open in Data Structures & Algorithms →

DFS or BFS with a hash map from original node to its copy. When visiting a node, create its clone if absent, then clone and link each neighbour. The map doubles as the visited set, which handles cycles. O(V + E).

def clone_graph(node):
    copies = {}
    def dfs(n):
        if n in copies: return copies[n]
        c = Node(n.val); copies[n] = c
        c.neighbors = [dfs(x) for x in n.neighbors]
        return c
    return dfs(node) if node else None

Open in Data Structures & Algorithms →

Store pairs (value, minimum so far). getMin reads the second field of the top pair. O(1) for everything, O(n) space. A space-saving variant keeps a second stack that only pushes when a new value is less than or equal to the current minimum.

class MinStack:
    def __init__(self): self.s = []
    def push(self, x):
        self.s.append((x, min(x, self.s[-1][1]) if self.s else x))
    def pop(self): self.s.pop()
    def top(self): return self.s[-1][0]
    def getMin(self): return self.s[-1][1]

Open in Data Structures & Algorithms →

dp[i] is true if the prefix s[:i] can be split into dictionary words: true if some j < i has dp[j] true and s[j:i] in the word set. O(n^2) substring checks (each O(L) to hash); limit j to the maximum word length to speed up. A trie or BFS over indices are alternatives. Word Break II (all sentences) adds memoised backtracking and can be exponential in output size.

Open in Data Structures & Algorithms →

Kadane's algorithm: the best sum ending at i is either nums[i] alone or the best ending at i-1 plus nums[i]. Track the global maximum. O(n) time, O(1) space. Handles all-negative arrays if you initialise with the first element, not zero. A divide-and-conquer O(n log n) solution exists but is rarely preferred.

Open in Data Structures & Algorithms →

A tree is balanced if at every node the heights of the two children differ by at most 1 (AVL-style). Do a post-order walk that returns height, or -1 if that subtree is already unbalanced. If either child returns -1, or |lh - rh| > 1, return -1; otherwise return 1 + max(lh, rh). The root is balanced iff the walk does not return -1. O(n) time, O(h) space. Computing height separately at every node is the slow O(n^2) version; interviewers notice.

Open in Data Structures & Algorithms →

Both support O(log n) point updates and range queries after O(n) build. Write a Fenwick tree when the query is a prefix or range sum (or any invertible group operation): it is about 15 lines, one array, and uses i & -i. Write a segment tree when you need range min/max, gcd, or range updates (lazy propagation: store a pending update on a node and push it to children only when you recurse). Segment trees use about 4n nodes and more code. For static range sums with no updates, neither: use a prefix-sum array.

Open in Data Structures & Algorithms →

Combine a hash map (key to node) with a doubly linked list ordered by recency (most recent at the front). get: look up the node, move it to the front. put: update or insert at the front; if over capacity, remove the node at the back and delete its key from the map. Both are O(1). In Python, OrderedDict with move_to_end and popitem(last=False) does this; in Java, LinkedHashMap with access order and removeEldestEntry.

from collections import OrderedDict
class LRUCache:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()
    def get(self, k):
        if k not in self.d: return -1
        self.d.move_to_end(k)
        return self.d[k]
    def put(self, k, v):
        self.d[k] = v
        self.d.move_to_end(k)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)   # evict least recently used

Interviewers often want the manual version: sentinel head and tail nodes plus _remove(node) and _add_front(node) helpers.

Open in Data Structures & Algorithms →

Two heaps: a max-heap low (stored negated in Python) for the smaller half and a min-heap high for the larger half. Keep len(low) equal to or one more than len(high), and every element of low no larger than every element of high. Add: push to low, move low's max to high, and if high grows larger, move its min back. Median: top of low, or the average of both tops. O(log n) add, O(1) median.

class MedianFinder:
    def __init__(self): self.low, self.high = [], []
    def addNum(self, x):
        heapq.heappush(self.low, -x)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))
    def findMedian(self):
        if len(self.low) > len(self.high): return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

Open in Data Structures & Algorithms →

Min-heap of the current head of each list, keyed by value (add an index as a tie breaker so nodes are never compared). Pop the smallest, append it, push its successor. O(N log k) time for N total nodes, O(k) heap space. Alternative: pairwise divide-and-conquer merging, also O(N log k). Merging one list at a time is O(N x k).

def merge_k(lists):
    h = [(n.val, i, n) for i, n in enumerate(lists) if n]
    heapq.heapify(h)
    dummy = tail = ListNode()
    while h:
        _, i, n = heapq.heappop(h)
        tail.next = tail = n
        if n.next: heapq.heappush(h, (n.next.val, i, n.next))
    return dummy.next

Open in Data Structures & Algorithms →

Water above index i is min(max_left, max_right) - height[i]. Two pointers avoid the prefix arrays: move the side with the smaller maximum inward, because that side's water level is fully determined by its own maximum. O(n) time, O(1) space. A monotonic stack solution also runs in O(n).

def trap(h):
    l, r = 0, len(h) - 1
    lmax = rmax = water = 0
    while l < r:
        if h[l] < h[r]:
            lmax = max(lmax, h[l]); water += lmax - h[l]; l += 1
        else:
            rmax = max(rmax, h[r]); water += rmax - h[r]; r -= 1
    return water

Open in Data Structures & Algorithms →

Sliding window with counts. need holds required counts of t; missing counts characters still needed. Expand right, decrementing need; when missing reaches 0 the window is valid, so shrink left as far as possible while still valid, recording the smallest window. O(|s| + |t|) time.

def min_window(s, t):
    need = Counter(t); missing = len(t)
    left = start = 0; best = float('inf')
    for right, c in enumerate(s):
        if need[c] > 0: missing -= 1
        need[c] -= 1
        while missing == 0:
            if right - left + 1 < best:
                best, start = right - left + 1, left
            need[s[left]] += 1
            if need[s[left]] > 0: missing += 1
            left += 1
    return "" if best == float('inf') else s[start:start + best]

Open in Data Structures & Algorithms →

Binary search a cut in the smaller array A at i; the cut in B is j = (m + n + 1) // 2 - i, so the left side holds half the elements. The cut is correct when A[i-1] <= B[j] and B[j-1] <= A[i] (use -inf / +inf beyond the ends). If A[i-1] > B[j] move i left, else move it right. The median is the max of the left side (odd total) or the average of the max-left and min-right (even total).

Open in Data Structures & Algorithms →

dp[i][j] = edits to turn the first i characters of a into the first j of b. If the characters match, dp[i][j] = dp[i-1][j-1]; otherwise 1 + min(delete dp[i-1][j], insert dp[i][j-1], replace dp[i-1][j-1]). Base: dp[i][0] = i, dp[0][j] = j. O(m x n) time; O(min(m, n)) space with two rows. Used in spell checkers and DNA alignment.

Open in Data Structures & Algorithms →

Pre-order traversal writing a sentinel (for example #) for null children, joined by commas. Deserialise by reading tokens from an iterator and rebuilding recursively in the same order. O(n) both ways. Level-order with nulls (LeetCode's format) also works. Without null markers, you need two traversals (pre-order plus in-order) and unique values.

def serialize(root):
    out = []
    def go(n):
        if not n: out.append('#'); return
        out.append(str(n.val)); go(n.left); go(n.right)
    go(root); return ','.join(out)

def deserialize(data):
    it = iter(data.split(','))
    def build():
        v = next(it)
        if v == '#': return None
        n = TreeNode(int(v)); n.left = build(); n.right = build()
        return n
    return build()

Open in Data Structures & Algorithms →

BFS over words, where neighbours differ by one letter. Generating neighbours by trying 26 letters at each position is O(L x 26) per word; alternatively precompute wildcard buckets like h*t mapping to words. Total O(N x L^2) including string building. Bidirectional BFS from both ends dramatically cuts the explored frontier. Remove words from the set when enqueued to avoid revisits.

Open in Data Structures & Algorithms →

Monotonic deque of indices whose values are decreasing. For each new index: pop from the back while the back's value is no larger than the new value (it can never be a maximum again), append, pop the front if it has left the window, and once the window is full, the front is the maximum. O(n) total, O(k) space. A heap gives O(n log n).

def max_sliding_window(a, k):
    dq, out = deque(), []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x: dq.pop()
        dq.append(i)
        if dq[0] <= i - k: dq.popleft()
        if i >= k - 1: out.append(a[dq[0]])
    return out

Open in Data Structures & Algorithms →

Monotonic increasing stack of indices. When a bar lower than the stack top arrives, pop: the popped bar's height extends from just after the new stack top to just before the current index. Append a 0-height sentinel to flush the stack at the end. O(n). Maximal rectangle in a binary matrix applies this row by row to column heights, O(R x C).

Open in Data Structures & Algorithms →

Expand around centre: for each of the 2n-1 centres (each character and each gap), expand while characters match, tracking the longest. O(n^2) time, O(1) space, and simpler than the O(n^2)-space DP (dp[i][j] true if s[i] == s[j] and dp[i+1][j-1]). Manacher's algorithm achieves O(n) but is rarely expected.

def longest_palindrome(s):
    best = ""
    for c in range(len(s)):
        for l, r in ((c, c), (c, c + 1)):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1; r += 1
            if r - l - 1 > len(best): best = s[l + 1:r]
    return best

Open in Data Structures & Algorithms →

Backtrack row by row. Keep three sets: used columns, used "r - c" diagonals and used "r + c" anti-diagonals. For each column in the current row, skip if any set conflicts; otherwise place, recurse to the next row, and remove. Record a board when all rows are placed. Roughly O(n!) with heavy pruning; bitmasks make the sets faster.

Open in Data Structures & Algorithms →

Plain Dijkstra fails because a cheaper path with more stops can block a pricier path with fewer stops. Use Bellman-Ford limited to K+1 rounds: in each round relax all edges using a copy of the previous round's distances, so each round adds at most one edge. O(K x E). Alternatively, Dijkstra or BFS over (node, stops) states.

def find_cheapest(n, flights, src, dst, k):
    dist = [float('inf')] * n; dist[src] = 0
    for _ in range(k + 1):
        nxt = dist[:]
        for u, v, w in flights:
            if dist[u] + w < nxt[v]: nxt[v] = dist[u] + w
        dist = nxt
    return -1 if dist[dst] == float('inf') else dist[dst]

Open in Data Structures & Algorithms →

Compare each adjacent pair of words; the first differing character gives an edge (a before b). If a word is followed by its own proper prefix (for example "abc" then "ab"), the input is invalid. Then topologically sort the letters with Kahn's algorithm; if a cycle prevents outputting every letter, return "". O(total characters).

Open in Data Structures & Algorithms →

Build a trie of the words, then DFS from every cell following trie edges; this searches all words simultaneously instead of once per word. Mark cells visited during a path and restore them on backtrack. Prune: remove a word from the trie once found, and delete leaf nodes that have no remaining words. Worst case roughly O(R x C x 4 x 3^(L-1)).

Open in Data Structures & Algorithms →

Treat the array as a linked list where index i points to nums[i]. A duplicate value means two indices point to the same node, which creates a cycle; the cycle entry is the duplicate. Run Floyd's tortoise and hare. O(n) time, O(1) space. Binary search on the value range with counting is an O(n log n) alternative.

Open in Data Structures & Algorithms →

A comparison sort can be modelled as a binary decision tree where each internal node is one comparison and each leaf is one output ordering. It must distinguish all n! permutations, so it needs at least n! leaves, and a binary tree with n! leaves has height at least log2(n!), which is Theta(n log n) by Stirling's approximation. Counting, radix and bucket sorts avoid the bound because they do not rely only on comparisons.

Open in Data Structures & Algorithms →

Both are greedy and correct by the cut property (the lightest edge crossing any cut belongs to some MST). Kruskal: sort edges by weight; add each edge if Union-Find says its endpoints are in different components; O(E log E). Best for sparse graphs or edge lists. Prim: grow one tree from a start vertex, repeatedly adding the cheapest edge leaving the tree via a min-heap; O(E log V). Best for dense graphs with adjacency lists.

Open in Data Structures & Algorithms →

Keep an array of values plus a hash map from value to its index. Insert: append and record the index. Delete: swap the element with the last one, update the moved element's index in the map, pop the end and delete the key. getRandom: pick a random index. All O(1) average.

import random
class RandomizedSet:
    def __init__(self): self.a, self.pos = [], {}
    def insert(self, x):
        if x in self.pos: return False
        self.pos[x] = len(self.a); self.a.append(x); return True
    def remove(self, x):
        if x not in self.pos: return False
        i, last = self.pos[x], self.a[-1]
        self.a[i], self.pos[last] = last, i
        self.a.pop(); del self.pos[x]; return True
    def getRandom(self): return random.choice(self.a)

Open in Data Structures & Algorithms →

Put all numbers in a set. For each number that has no predecessor (x - 1 not in the set), count upward while x + 1 is present. Each number is visited at most twice, so O(n) even though there is a nested loop. Sorting gives O(n log n).

def longest_consecutive(nums):
    s, best = set(nums), 0
    for x in s:
        if x - 1 not in s:
            y = x
            while y + 1 in s: y += 1
            best = max(best, y - x + 1)
    return best

Open in Data Structures & Algorithms →

Either store the choice made at each state (a parent pointer array) or walk backwards through the filled table, re-checking which transition produced each value. For LCS: start at dp[m][n]; if the characters match, emit it and go diagonal; otherwise move to whichever neighbour holds the larger value. For knapsack: if dp[i][w] != dp[i-1][w], item i was taken. Note that rolling-array space optimisation usually discards the information needed for reconstruction, so keep the full table (or use Hirschberg's divide-and-conquer trick for LCS).

Open in Data Structures & Algorithms →

First estimate: at 10^5, O(n^2) is 10^10 operations, far too slow; you need O(n log n) or O(n). Find the nested loop or repeated work: can a hash map replace the inner search, can sorting enable two pointers or binary search, can prefix sums answer range queries in O(1), is there a monotonic structure (stack or deque), or are there repeated subproblems to memoise? Also check hidden costs: x in list, list.pop(0), string concatenation in a loop, slicing inside recursion, and recursion without memoisation.

Open in Data Structures & Algorithms →

External merge sort. Pass 1: read about 1 GB at a time, sort it in memory, and write each sorted run to disk (about 10 runs). Pass 2: k-way merge all runs using a min-heap holding the current smallest line of each run, with buffered reads and writes. Total I/O is about two reads and two writes of the data; time is O(N log N). If there are too many runs for buffers, merge in multiple passes. If keys are small integers, a counting approach may need only one pass.

Open in Data Structures & Algorithms →

If the distinct queries fit in memory: hash map counts, then a size-10 min-heap, O(N + D log 10). If not: hash-partition the logs by query into many files so each query lands in exactly one file, count and take the top 10 per partition, then merge the candidates (this is what MapReduce does). For a live stream with limited memory, use approximate structures: Count-Min Sketch for counts plus a small heap of heavy hitters, or the Space-Saving / Misra-Gries algorithms, accepting bounded error.

Open in Data Structures & Algorithms →

The input is deeper than the call stack allows (for example a skewed tree or long linked chain). Options: rewrite the DFS iteratively with an explicit stack stored on the heap; switch to BFS if order does not matter; in Python, raising sys.setrecursionlimit is a stopgap that can still crash the interpreter; in C or Java, run on a thread with a larger stack. Add a test with a degenerate input of maximum size so it cannot regress.

Open in Data Structures & Algorithms →

Keep talking. Restate what you know and what is blocking you. Work a small example by hand and look for a pattern. Walk the pattern checklist: sorted, contiguous, shortest, dependencies, overlapping subproblems. Offer the brute force and code it if time is short, since a working suboptimal solution beats an unfinished optimal one. Accept hints gracefully and build on them; interviewers score how you use hints.

Open in Data Structures & Algorithms →

A billion URLs of about 100 bytes is roughly 100 GB, too large for a hash set in RAM. Options: hash-partition the URLs into, say, 1,000 files by hash(url) % 1000 (duplicates always land in the same file), then dedupe each file with an in-memory set; or external sort then remove adjacent duplicates. If a small false-positive rate is acceptable, a Bloom filter (about 1.2 GB for a 1 percent error rate at 10^9 items) answers "probably seen" in O(1) with no false negatives. Storing a 64-bit hash instead of the full URL reduces memory at the cost of rare collisions.

Open in Data Structures & Algorithms →

Write down the invariant: what does lo mean, what does hi mean, and is the interval closed or half-open? Infinite loops usually come from lo = mid when mid rounds down and hi = lo + 1; use lo = mid + 1 or round mid up. Test tiny cases exhaustively: empty array, one element, two elements, target smaller than all, larger than all, and duplicates. Compare against a linear-scan reference on random inputs.

Open in Data Structures & Algorithms →

Keep a hash map from player to score plus an ordered structure keyed by (-score, player): a balanced BST or skip list (Redis sorted sets use a skip list plus hash). Update: remove the old key, insert the new, O(log n). Top k: iterate the first k, O(k + log n). Rank: an order-statistic tree or skip list with span counts gives O(log n). A heap alone cannot answer rank or update arbitrary players efficiently. If scores are bounded integers, a Fenwick tree over score values gives O(log S) rank queries.

Open in Data Structures & Algorithms →

Exact but small memory: a circular buffer of 300 one-second buckets, each storing (timestamp, count). On a hit, if the bucket's timestamp is stale, reset it; increment. To count, sum buckets whose timestamps are within 300 seconds: O(300) per query, O(1) per hit, constant memory. A deque of timestamps is simpler but grows with traffic. For multiple servers, aggregate per-server buckets or use a shared store with per-second keys and expiry.

Open in Data Structures & Algorithms →

A trie where each node caches the top 5 completions (by popularity) for its prefix, so a query is O(prefix length) plus reading 5 cached entries. Updating popularity requires refreshing cached lists up the path, so rebuild or update in batches offline from query logs. Compress chains of single-child nodes (radix tree) to save memory. For very large vocabularies, shard by first characters and cache hot prefixes.

Open in Data Structures & Algorithms →

Likely many keys landing in the same bucket: a poor custom hashCode (for example returning a constant or ignoring most fields), keys that are mutable and changed after insertion (entries become unreachable, causing leaks and misses), or deliberate hash-flooding with crafted keys. Check the hash distribution, fix hashCode/equals consistency, use immutable keys, and rely on randomised hashing. Also check for resize storms if the map is repeatedly created at a small capacity; presize it when the size is known.

Open in Data Structures & Algorithms →

Look at which cells each state reads. If dp[i][j] only needs row i-1 and the current row, keep two rows, or one row if you order the loop so that values you still need are not overwritten (for the diagonal dependency, save dp[i-1][j-1] in a temporary before overwriting). Choose the shorter dimension as the row length. Mention that this loses the ability to reconstruct the path unless you store choices separately.

Open in Data Structures & Algorithms →

It depends on the ratio of adds to queries. If adds dominate, store counts in a hash map (O(1) add) and answer a query by scanning distinct values for their complement (O(D) query). If queries dominate and the target is fixed, maintain a set of achievable pair sums on each add (O(D) add, O(1) query). Stating this trade-off and asking about the workload is exactly what interviewers want.

Open in Data Structures & Algorithms →

The frontier grows exponentially with depth (average degree to the power d). Options: bidirectional BFS from source and target, which explores about two frontiers of size b^(d/2) instead of b^d; limit the depth (degrees of separation rarely need more than 6); store visited nodes compactly (bitsets or integer IDs instead of objects); or switch to iterative deepening DFS, which trades time for O(depth) memory. For truly huge graphs, partition across machines and run level-synchronous BFS.

Open in Data Structures & Algorithms →

An OS is the privileged program that owns the machine. It multiplexes CPU, memory and devices among programs, isolates those programs from each other and from raw hardware, and abstracts devices behind a stable interface (files, processes, sockets, virtual memory). Interviews that ask "is it just a library?" want this: a library cannot enforce isolation because it does not control the mode bit or the page tables.

Open in Operating System Concepts →

The CPU has a privilege bit (or exception level). In user mode the running code cannot execute privileged instructions: no device I/O, no page-table writes, no halt, no flip of the mode bit. In kernel mode those instructions are legal. The hardware switches mode on a syscall, interrupt or exception and switches back on return-from-exception. User programs include shells, apps and most daemons; only the kernel (and a hypervisor at a higher level) is trusted with the MMU and devices.

Open in Operating System Concepts →

A hardware lattice of privilege. The textbook x86 picture has rings 0 (most privileged) through 3. Mainstream kernels use two: ring 0 / EL1 for the kernel and ring 3 / EL0 for user. Extra levels exist for a hypervisor (EL2) and firmware (EL3). The interview point is not the trivia of every ARM level; it is that isolation is hardware-enforced. If any program could raise its own privilege, a wild pointer could rewrite page tables or program DMA into another process.

Open in Operating System Concepts →

A numbered, documented request into the kernel: open, read, mmap, fork, clone, and so on. Userspace (usually libc) loads a number and arguments into ABI registers and executes a trap instruction (syscall, svc). Hardware raises privilege and vectors to a dispatcher. The kernel validates arguments — especially user pointers — does the work or sleeps, and returns a result. It is not a normal C function call: the stack, privilege and trust boundary all change. See C for the libc stub and Linux kernel & BSP for the entry path.

Open in Operating System Concepts →

Dual mode is the hardware rule that user code cannot perform privileged operations. Without it, isolation is a social convention: any process could disable interrupts, remap memory or write another process's pages. With it, the only crossings are well-defined vectors the kernel handles. That is why "run the whole OS in user mode on paper" is a research idea that still needs some trusted TCB, not a reason to drop the mode bit on a phone.

Open in Operating System Concepts →

An interrupt (IRQ) is asynchronous: a device or timer fires independently of the current instruction. A trap is synchronous and deliberate (syscall, breakpoint). An exception is synchronous but not "please do this POSIX service" — the instruction cannot complete as issued (page fault, divide-by-zero, illegal opcode). In interview English, sort by who caused it and whether you will retry the instruction.

Open in Operating System Concepts →

Both are exceptions. A fault is typically restartable: the kernel repairs the condition and retries the same instruction. A page fault is the important case — virtual memory is built on it. An abort is not restartable (serious hardware error, some double faults); the process or the machine is done. If you say "page fault kills the process", you have mixed a protection violation (bad address) with a not-present fault on a legal mapping.

Open in Operating System Concepts →

A program in execution: a private virtual address space, credentials, a file-descriptor table, signal state, resource limits, and one or more threads. It is the usual isolation boundary. The kernel's record of that bundle is the PCB. Two processes do not share memory unless they both map the same pages (shared memory, shared file maps) or they are still sharing COW pages after fork.

Open in Operating System Concepts →

The process control block is the kernel object describing a process or task. Interview contents: PID and parent, state, CPU context (often per-thread), pointer to page tables / mm, file table, credentials, scheduling parameters, accounting, and pending signals. On Linux the living form is task_struct plus satellite structs — that split is kernel material. Here: the PCB is what you context-switch and what ps is displaying.

Open in Operating System Concepts →

Classic five: new (being created), ready (runnable, waiting for a CPU), running (on a CPU), waiting/blocked (cannot run until an event), terminated (exited; may still be a zombie). Dispatch: ready → running. Preempt: running → ready. Block (I/O, lock, wait): running → waiting. Wake: waiting → ready. Exit: running → terminated. Some books add swapped-out suspended states; mention them only if asked.

Open in Operating System Concepts →

The kernel saves one thread's registers and kernel stack pointer and loads another's. If the next thread is in a different address space, it also switches the page-table root, which flushes or retags the TLB. Direct cost is thousands of cycles. Indirect cost is often larger: the next job does not share the previous job's hot cache lines. Same-process thread switches skip the mm switch and are cheaper. That is why a huge number of threads with a tiny RR quantum destroys throughput.

Open in Operating System Concepts →

fork creates a child that is a copy of the parent (modern kernels: COW pages). Child sees return value 0; parent sees the child's PID. exec replaces the current address space with a new program; the PID and most fds remain. exit releases memory and files and leaves an exit status. wait/waitpid lets the parent collect that status and free the zombie PCB. The usual "run another program" path is fork then exec; Android's zygote is fork without exec for a pre-warmed runtime — see Android frameworks.

Open in Operating System Concepts →

A zombie has already exited; the parent has not waited. Almost no memory remains — only a process-table slot so the exit code can be read. Ignore children and you leak PIDs, not RAM. An orphan is still running after its parent died. The OS reparents it (classically to PID 1) so someone will wait. An orphan is not a zombie; it may become one later, and the new parent will reap it.

Open in Operating System Concepts →

Threads in one process share the address space (code, heap, globals), file descriptors, and credentials. They do not share stacks or, by default, TLS values. Separate processes share nothing unless they set up IPC or inherited COW/mmap mappings. Threads are cheaper to create and switch and pass data by pointer; processes isolate faults and security domains. Browsers and sandboxed renderers pick processes on purpose.

Open in Operating System Concepts →

The unit the scheduler runs: a register set, a stack, TLS, and a scheduling state, living inside a process. "The process runs" is loose language — a thread runs on a core. A single-threaded process is just the special case of one thread. Java threads and the JVM memory model are on the Java page; here the OS fact is that a thread is a kernel-schedulable (1:1) or library-schedulable (N:1) execution context.

Open in Operating System Concepts →

User-level threads are scheduled by a library; the kernel sees one task. Switch is a function call (fast), but one blocking syscall or page fault blocks all of them, and you cannot use more than one core. Kernel-level threads are first-class tasks; blocking and SMP work. Modern POSIX pthreads on Linux are 1:1 kernel threads. Language runtimes that multiplex green threads are an M:N or N:1 story on top.

Open in Operating System Concepts →

Storage that looks like a global but has one instance per thread: errno, a thread id, a scratch buffer. The ABI keeps a register (FS/GS, TPIDR) pointing at a per-thread block; TLS symbols are offsets from that pointer. That is why errno is thread-safe without a lock. It is not a substitute for a mutex on heap data you actually share.

Open in Operating System Concepts →

A CPU burst is a stretch of execution that needs the processor. An I/O burst is a stretch waiting for a device (or a lock, or a sleep). Interactive jobs have short CPU bursts and frequent I/O; batch jobs have long CPU bursts. Schedulers estimate or observe the next CPU burst. Mixing them under FCFS is how you get the convoy effect.

Open in Operating System Concepts →

Non-preemptive (cooperative): a thread runs until it blocks, yields or exits. A runaway loop starves the machine. Preemptive: a timer tick or a higher-priority wake-up can seize the CPU. General-purpose OS schedulers are preemptive. Textbook numericals still use non-preemptive SJF or FCFS; say which you assumed when you draw the Gantt chart.

Open in Operating System Concepts →

FCFS (first-come first-served) runs ready jobs in arrival order until each CPU burst finishes. The convoy effect is a long CPU-bound job at the head; short I/O-bound jobs wait, run for a moment, block, then queue behind the long job again. Average waiting time explodes. RR, SJF and MLFQ exist in part to break convoys.

Open in Operating System Concepts →

Each ready job gets a time quantum q, then goes to the tail of the ready queue. Response time is good for interactive work. If q is tiny, context-switch overhead dominates (CPU spends its life saving registers). If q is huge, RR collapses to FCFS. Pick q large compared to a switch (milliseconds, not microseconds) but small compared to a human-noticeable delay. There is no universal number; state the trade-off.

Open in Operating System Concepts →

Turnaround = completion time − arrival time (how long the job was in the system). Waiting time = turnaround − CPU burst time (time in the ready queue, not I/O wait). Response time = first time on the CPU − arrival (how long until it first "twitches"). Quote averages over a set of jobs. Throughput is completed jobs per unit time; utilisation is the fraction of time the CPU is not idle.

Open in Operating System Concepts →

A situation where correctness depends on the interleaving of concurrent operations. The lost-update: two threads read the same counter, both add one, both write, and one increment vanishes. Shared memory plus no synchronisation is sufficient. Data races are undefined behaviour in C and C++ (C, C++); in OS language, they are the reason critical sections exist.

Open in Operating System Concepts →

The region of code that must appear atomic with respect to other threads that share the same data. Entry and exit protocols (a mutex, an atomic algorithm) implement that atomicity. The section should be as short as you can make it: hold time is contention and, if you spin, wasted CPU. I/O inside a critical section is a common design smell.

Open in Operating System Concepts →

A mutex is an owned lock: the thread that locks it must unlock it; it is for protecting a critical section. A semaphore is a counter plus a wait queue: P/wait decrements and may sleep, V/signal increments and may wake. No owner — any thread may V. A binary semaphore can mimic a mutex but can also be used as a pure signal ("this event happened"). A counting semaphore tracks N identical resources. Prefer a mutex for exclusion; use a semaphore when the count or the cross-thread signal is the point.

Open in Operating System Concepts →

Binary: the count is 0 or 1. Counting: the count is a non-negative integer. Use counting for N buffers, N devices, or the empty/full counts in producer-consumer. Use binary for a single-event signal or a crude mutex. Neither has ownership; if you need "only the locker may unlock" and priority inheritance, you want a mutex.

Open in Operating System Concepts →

Deadlock is a set of processes such that each is waiting for a resource another in the set holds, and none will release what they hold. The four conditions, all required: mutual exclusion (the resource is not shared), hold and wait (hold one, wait for another), no preemption (you cannot yank the held resource), circular wait (a cycle). Break any one and deadlock cannot occur. That is prevention. Avoidance (Banker's) and detection-plus-recovery are different policies.

Open in Operating System Concepts →

A logical (virtual) address is what the program issues. A physical address is a location in RAM (or device memory) on the bus. The MMU, using kernel-installed page tables, translates one to the other or raises a fault. Relocation and isolation both come from this: two processes can both use address 0x400000 and not collide. Without an MMU you bind at compile or load time and you do not get this isolation.

Open in Operating System Concepts →

External: free memory exists but is carved into holes too small for the next variable-size request (classic segments, a naive heap). Fix by compaction or by allocating only fixed frames (paging). Internal: you received a block larger than you needed; slack inside the page or slab is wasted. Paging has internal fragmentation on the last page of a mapping. You tolerate it; you do not compact it away.

Open in Operating System Concepts →

Paging splits memory into fixed-size pages and frames. The process sees a flat virtual array. No external fragmentation of RAM; some internal slack; the table can be huge unless it is hierarchical. Segmentation uses variable-size logical regions that match how programmers think (code, stack, heap). External fragmentation returns. Modern OS: paging is the mechanism; "segments" are just named mappings (VMAs) on top of pages.

Open in Operating System Concepts →

The CPU failed a translation: no valid PTE, or a permission violation, or a reserved bit. Hardware saves the faulting address and traps to the kernel. If the address is illegal, the process is signalled (UNIX: SIGSEGV). If the mapping is legal but not present, the kernel allocates a frame, fills it (zero, file, swap, COW copy), installs the PTE, and restarts the instruction. That restartable path is demand paging.

Open in Operating System Concepts →

Each process has a large, isolated logical address space. Only the pages it uses need RAM frames; the rest live on a backing store (the file, swap) or do not exist yet. Demand paging, the TLB, replacement, COW and mmap are the machinery. It is not "infinite RAM": thrashing and out-of-memory exist. On Android, the LMK may kill a process under pressure rather than swap forever — frameworks.

Open in Operating System Concepts →

A file is a persistent byte stream plus metadata. An inode is the identity: owner, mode, timestamps, size, and the map from offsets to disk blocks. A directory is a listing that maps names to inode numbers (or equivalent). The name is not stored in the inode. That split is why two names can refer to one file (hard links) and why renaming is a directory operation, not a rewrite of the data.

Open in Operating System Concepts →

A hard link is another directory entry for the same inode: same data, same inode number, cannot cross filesystems, usually forbidden for directories. The inode's link count drops on unlink; data is freed when the count is 0 and no fd remains. A symbolic link is a small file holding a path. It may dangle, may cross filesystems, and is resolved when you use it. Permissions on the target usually decide access.

Open in Operating System Concepts →

IPC is how separate address spaces exchange bytes or events. An anonymous pipe is a unidirectional kernel buffer, typically set up by a parent and inherited across fork — shell pipelines. A socket is bidirectional, has a richer API (connect, listen, datagram vs stream), and can leave the machine. Use a UNIX-domain socket when two local processes need a bidirectional channel or credentials passing; use a pipe for a simple one-way inherited stream. Shared memory wins for bulk data if you will write the synchronisation yourself.

Open in Operating System Concepts →

UID/GID are the credentials the kernel stamps on a process and compares to object ownership and mode bits (or ACLs). A process is an address space plus those credentials. A container is still processes on the same kernel, with extra namespace views and cgroup limits. A VM virtualises hardware and usually runs a guest kernel. Isolation strength and density go in opposite directions: process < container < VM for isolation; the reverse for density and start time.

Open in Operating System Concepts →

Libc places the syscall number and arguments in the architecture's ABI registers and executes a trap instruction. Hardware saves the user program counter and status, raises privilege, and vectors to the kernel entry. The kernel saves user registers, looks up the number, copies and checks user pointers (never trust a raw address), performs the work or sleeps, writes the return value, then return-from-exception drops privilege and resumes userspace. If the thread slept, another thread ran in between — that is the scheduler, not part of the stub. Kernel entry details: Linux kernel & BSP.

Open in Operating System Concepts →

Then every bug is a kernel bug. A wild pointer can rewrite page tables, program a DMA engine into another process, or disable the timer that preempts runaways. Dual mode plus a narrow syscall ABI is how we keep a browser tab from owning the machine. Microkernels move more policy to user servers, but they still have a privileged core that owns the MMU. The interview answer is isolation and a stable ABI, not "syscalls are fast".

Open in Operating System Concepts →

A same-process thread switch saves/restores registers and kernel stacks but keeps the same page-table root. A process switch also switches the address space: load a new CR3/TTBR, flush or retag the TLB, and lose cache warmth for the previous working set. File tables and credentials may be switched too. That is why "just use more processes" is the wrong default for fine-grain parallelism, and why browsers accept the cost only when they want a crash domain.

Open in Operating System Concepts →

Each child that exits becomes a zombie: the address space is gone, but the PCB slot and exit status remain. Enough of them exhaust the PID space; fork starts failing. Memory does not leak in the "child heap still allocated" sense. The fix is wait/waitpid (or a SIGCHLD handler that reaps), or to have the parent die so the children are reparented and reaped by init / a subreaper.

Open in Operating System Concepts →

When the parent exits first, the OS reparents the live child. Classically the new parent is PID 1 (init), which loops on wait and collects zombies. Linux can reparent to a designated subreaper instead. The guarantee is: someone will wait, so orphans do not become permanent zombies. Service managers that spawn workers rely on this if a worker outlives its launcher.

Open in Operating System Concepts →

N:1 multiplexes many user threads onto one kernel thread: cheapest switch, no parallelism, one blocking syscall freezes all. 1:1 maps each user thread to a kernel thread: blocking and SMP work; create/switch go through the kernel (still cheap). This is POSIX on modern Linux and the usual Android/ART native thread. M:N parks M green threads on N kernel workers: can hide I/O and use several cores, but you now have two schedulers, messy signals, and hard stop-the-world cases. Interviewers want the trade-off, not a brand name.

Open in Operating System Concepts →

Threads: shared working set, cheap hand-off of pointers, need many concurrent I/O or parallel CPU workers inside one program (a server, a UI plus workers). Processes: fault isolation (a renderer crash must not take the browser chrome), different credentials, a sandbox, or a blast radius you can kill. The cost of IPC and of a heavier create/switch is the price of that isolation. See system design for multi-process services and frameworks for app process policy.

Open in Operating System Concepts →

The kernel deschedules the one task it sees. Every user thread in that process stops, including ones that were ready to run. The library cannot context-switch them because it is not running. Page faults have the same effect. That is the historic reason N:1 died for general-purpose servers. Workarounds (non-blocking I/O plus a user scheduler) reinvent M:N.

Open in Operating System Concepts →

Both pick the job with the shortest next CPU burst. SJF is non-preemptive: once a burst starts, it finishes. SRTF is preemptive: a newly arrived shorter remaining burst seizes the CPU. Both minimise average waiting time if you know the future. You do not; you estimate (exponential average of past bursts, or "interactive vs batch" feedback). Long jobs can starve; aging or a lower bound on share is the patch. These are textbook policies, not Linux CFS.

Open in Operating System Concepts →

If a high-priority stream is always ready, a low-priority job never runs. That is starvation, not deadlock (the system is making progress). Aging increases priority as wait time grows, so the low job eventually outranks the chatter and gets a turn. Mention aging whenever you mention priority, SRTF, or an MLFQ without boosts.

Open in Operating System Concepts →

A multilevel queue has fixed classes (interactive, batch, RT). A job is assigned a queue and stays there; each queue may have its own policy and a priority between queues. Misclassification is permanent. MLFQ lets jobs move: burn your quantum and you are demoted (you look CPU-bound); block early and you stay high (you look interactive). You need aging or periodic boosts so a long job is not buried forever. MLFQ is the "learn the workload" textbook design behind a lot of interactive OS folklore.

Open in Operating System Concepts →

Write arrival times and burst lengths. Draw the chart under the policy (watch preemption points). For each job: completion is the time its last slice ends; turnaround = completion − arrival; waiting = turnaround − burst (only CPU burst; do not subtract I/O unless the problem included I/O in the "burst" column). Average the columns. Response is the start of the first slice minus arrival. State whether the policy is preemptive. A common arithmetic bug is using finish − burst and forgetting a late arrival.

Open in Operating System Concepts →

Mutual exclusion: at most one thread in the section. Progress: if the section is free and someone wants in, selection cannot be postponed by threads that are not interested. Bounded waiting: a bound on how many times others may enter after you have requested entry. Peterson's algorithm is the software classic; hardware atomics plus an OS sleep queue are what you ship. A spin-forever lock can fail bounded waiting if a thread is never scheduled.

Open in Operating System Concepts →

You need exclusion on the buffer and "do not write when full" / "do not read when empty". One mutex (or a binary semaphore used as a mutex) protects put/get. A counting semaphore empty starts at N; a producer P(empty) before filling and V(full) after. A consumer P(full) before taking and V(empty) after. Invert the P order (mutex first, then empty/full) and you can deadlock: you hold the mutex while sleeping for a slot. Always take the "resource count" semaphores outside the mutex, or use a mutex plus two condition variables and wait in a loop on the predicate.

Open in Operating System Concepts →

Many readers may hold the data at once; a writer needs exclusive access. Readers-preference: a waiting writer can starve if readers keep arriving. Writers-preference: readers can starve. A fair queue (one waiter line, or a ticket) avoids both at the cost of extra state. Always state which policy you chose. Implementation is usually a mutex, a reader count, and a write lock (or two condition variables).

Open in Operating System Concepts →

A monitor is a language construct: data plus operations that run with implicit mutual exclusion, plus condition variables. Java synchronized methods are the interview example (Java). A condition variable is not a lock. wait atomically releases the mutex and sleeps; signal/broadcast wakes waiter(s). Under Mesa semantics (the one you will ship), a wake is a hint: re-test the predicate in a loop. Hoare semantics hands the mutex to the waiter immediately; textbooks mention it, kernels and pthreads do not implement it that way.

Open in Operating System Concepts →

Spin when the critical section is a handful of instructions and the holder is running on another core (so the flag will clear soon) and you are not allowed to sleep (hard IRQ context on Linux — kernel). Sleep (mutex) when the hold may include I/O or a long computation, or you are on a uniprocessor (spinning waits for a holder that cannot run until you deschedule). Adaptive mutexes spin a little, then sleep. Priority inversion is worse with a spinlock held while a low-priority holder is preempted.

Open in Operating System Concepts →

Prevention designs out a Coffman condition: global lock order (breaks circular wait), allocate everything up front (breaks hold-and-wait), or make the resource preemptive. Avoidance (Banker's) checks each grant against a safe-state test; needs declared maxima; rare for mutexes, common as a numerical. Detection builds a wait-for graph or runs a reduction, then kills or rolls back a victim. Many desktops are "ostrich": ignore and hope. Databases detect; lock-heavy servers prevent with ordering.

Open in Operating System Concepts →

Each process declares a maximum claim per resource type. The allocator tracks Allocation, Need = Max − Allocation, and Available. When a process requests units, pretend you granted them. Then search for a safe sequence: an order of processes that can each finish with Available + what they would free. If no such order exists, refuse (the waiter sleeps) even if the units are free right now. You stay in a safe state. Real lock libraries do not run this; they use lock ranking. Be ready to walk a 3×3 matrix if they put one on the board. Searching for a sequence is a graph/greedy exercise; see DSA if you want the loop structure.

Open in Operating System Concepts →

Deadlock: a cycle of waiting; no one in the set changes state in a useful way. Livelock: everyone keeps reacting (retry, backoff together, step aside the same way) but nobody makes progress. Starvation: the system progresses, but one participant never gets a turn. Fixes differ: break a Coffman condition or recover; add randomness/exponential backoff; age priorities or fair-queue. Do not use the three words as synonyms.

Open in Operating System Concepts →

Compile-time binding assumes a known physical address (no MMU, or a fixed embedded map). Load-time binding patches the binary when it is loaded. Execution-time binding (virtual memory) translates every access; the program never sees physical addresses. Relocation is why the same ELF can run in many processes at once. PIC/PIE is the userspace cousin (see C); the OS story is the MMU.

Open in Operating System Concepts →

Compaction slides allocated regions together so free holes become one region. It requires the ability to move a live object and fix every pointer or to rewrite translations. With variable-size physical partitions, you compact or you fail to place the next job. Paging allocates fixed frames: any free frame will do, so external fragmentation of RAM disappears (internal slack remains). Userspace heaps still fragment; that is a malloc problem, not an OS placement problem.

Open in Operating System Concepts →

A 64-bit space with 4 KiB pages has an absurd number of virtual pages. A flat array of PTEs would be huge even if the process uses a few megabytes. A radix tree (3–4 levels) stores only the branches you populated: unused quadrants cost a null upper pointer, not a forest of empty leaves. The cost is L dependent memory loads on a TLB miss. That cost is why the TLB — and huge pages that shorten the walk — exist.

Open in Operating System Concepts →

The TLB caches recent VPN → PFN translations (and permissions). Hit: about t_TLB + t_mem for the data. Miss: t_TLB + L memory references for the walk + t_mem for the data. EAT = h(t_TLB + t_mem) + (1−h)(t_TLB + (L+1)t_mem). A hit-rate drop from 99% to 90% is painful because misses are so expensive. A process switch that flushes an untagged TLB resets h. If they give numbers, plug them in and keep L explicit.

Open in Operating System Concepts →

Hardware: TLB miss, walker finds invalid PTE or no PTE, fault with the VA and the PC. Kernel: is this a bad address, a permission error, or a legal not-present mapping? Bad → signal/kill. Legal: find or allocate a frame. File-backed: schedule disk I/O and sleep (major fault). Anonymous: zero a frame. COW write: copy the page. Install a valid PTE, update TLB, return so the instruction retries. Minor faults (page already in cache, just not mapped here) skip the disk. Linux VMA details: kernel.

Open in Operating System Concepts →

Do not load a program's pages at exec time. Map the address space as not-present (or file-backed holes) and fill a frame on the first touch. Startup is faster and unused code/data never occupies RAM. The downsides are a fault storm at first use (working-set warm-up) and the need for a replacement policy when frames run out. Prefetch / readahead is a policy on top, not a different mechanism.

Open in Operating System Concepts →

FIFO evicts the oldest loaded page: simple, can evict a hot page, Belady-anomaly. OPT evicts the page whose next use is farthest in the future: unrealisable, the lower bound you compare against. LRU evicts the least recently used: good approximation to OPT; exact LRU needs a stack or timestamps on every reference. Clock / second chance walks a ring; if the referenced bit is set, clear it and skip (a second chance). Hardware gives you the bit; Clock is the LRU you actually implement.

Open in Operating System Concepts →

For some reference strings, FIFO produces more page faults with more frames. More memory is not always fewer faults under FIFO. OPT and stack algorithms (LRU) do not have this anomaly: a stack algorithm's resident set of size n is nested, so growing n only adds pages. If they give a string, simulate FIFO at two frame counts and show the fault counts. Mention it whenever you mention FIFO replacement.

Open in Operating System Concepts →

Share a physical page among several mappings, marked read-only. The first store faults; the kernel copies the page, assigns a private writable frame, and resumes. fork uses this so the child is logically a full copy without a full copy. exec soon after means almost no copies happen. MAP_PRIVATE mmap of a file is the same idea: reads share the page cache; writes break off a private page. Snapshots and some VM balloon tricks use the same primitive.

Open in Operating System Concepts →

mmap maps the file into the address space. You can parse in place (no extra userspace copy) and let the page cache be the buffer. Random access is pointer arithmetic. Costs: first-touch faults (latency jitter), harder error reporting (a fault vs a return code), and you must still msync if you need durability. read is simpler, copies into a buffer you control, and reports errors on the call. Large read-mostly files and shared mappings as IPC are the usual mmap wins. Implementation: kernel.

Open in Operating System Concepts →

PIO: the CPU moves every word and often polls a status register — simple, burns a core, fine for tiny or boot-time transfers. Interrupt-driven: the CPU does other work; an IRQ says "a byte/packet is ready"; the handler or a deferred path still copies. DMA: the CPU programs a controller (addresses, length); the device is bus master; an IRQ means done or error. DMA still needs cache maintenance and an interrupt. Do not start a Linux probe lecture.

Open in Operating System Concepts →

These describe how the thread waits, not how bytes move (DMA can back any of them). Blocking: the syscall sleeps until it can complete (or a signal hits). Non-blocking: return data or EAGAIN now; you poll or use select/epoll. Asynchronous: submit a request and be notified later (completion queue, callback) without sitting in the syscall. One thread can overlap compute and I/O with async; with blocking you use more threads. Do not call epoll "async I/O" unless you are precise: it is readiness, then you still read.

Open in Operating System Concepts →

Contiguous: start + length. Great sequential I/O; external fragmentation; growth is painful. Linked: each block points to the next (or a FAT does). Easy growth; random access is a chain walk; one bad pointer loses the tail. Indexed: an index block (or a tree, or extents) lists data blocks. Random access is good; small files pay index overhead if you are naive. Real filesystems mix ideas: extents are "indexed, but runs of contiguous blocks".

Open in Operating System Concepts →

FAT keeps a table with one entry per cluster: 0 means free, EOF ends a file, a number is the next cluster. Directories store the first cluster. Random access walks the table. The table is a single point of corruption. A UNIX inode stores a few direct block pointers and then single/double/triple indirect blocks, plus metadata (owner, mode, times, link count). Names live in directory entries that point at the inode. Extents replace many pointers with (start, length) runs on modern layouts.

Open in Operating System Concepts →

A crash mid-update can leave bitmaps, trees and directories disagreeing. A journal writes intended changes to a log, commits, then writes home locations. After a crash, replay committed records. That restores crash consistency of metadata (and of data if you journal data too). It does not make every write durable the instant it returns — that is fsync / barriers. It does not fix a disk that lies about flush. Soft updates and copy-on-write filesystems are other consistency designs; mention them as alternatives, not as Linux driver trivia.

Open in Operating System Concepts →

The kernel presents one inode / open-file / directory API so read does not care whether the backing store is a disk filesystem, a pipe, a socket, or a pseudo-fs. Each implementation fills in operations (read, write, lookup). Userspace sees fds. That is why you can cat a file and also read from a pipe with the same syscall. Linux dentry/inode objects are kernel material; the interview word is "one surface, many implementations".

Open in Operating System Concepts →

Pipe: inherited one-way stream (parent-child, shell). Named pipe: same stream, unrelated processes, still local. Message queue: record boundaries and maybe priorities; multiple consumers selecting by type. Shared memory: bulk and latency; you must add a mutex/futex protocol and think about visibility. Signal: "please die", job control, a timer — not a payload path. Socket: bidirectional, credentials, and a path to the network if you ever need it. On Android, app-to-system RPC is Binder, not POSIX queues — frameworks.

Open in Operating System Concepts →

An ACL lives on the object: "these principals may do these ops". Easy to audit one file; hard to list everything a process can still do. Revocation is "edit the list". A capability is a token the subject holds; possession is authorisation. UNIX fds are capability-like for open files (passing an fd delegates). POSIX process capabilities are a different thing: they split root into bits. Say which you mean. Isolation still starts with page tables; ACLs and capabilities decide authorised crossings.

Open in Operating System Concepts →

Time-of-check to time-of-use: you stat a path, decide it is safe, then open the same path. An attacker swaps the name for a symlink in the gap. The check did not bind to the same kernel object as the use. Fixes: open then fstat on the fd; openat with a directory fd; O_CREAT|O_EXCL for exclusive create; never follow user-controlled paths from a privileged process if you can take a handle instead. The pattern is general, not only files.

Open in Operating System Concepts →

Cores have store buffers and private caches. Thread A may execute data = 42; ready = 1 and thread B may observe ready == 1 while data is still stale, unless a happens-before edge orders those writes. Unlock/lock on a mutex (or a matching release/acquire atomic pair) is that edge: the locker publishes, the acquirer observes. volatile in C is not a lock and not a portable barrier (C). The OS contributes the sleep/wake side (a futex wait sees the same write that the waker published). Interview sentence: "locks give exclusion and publication."

Open in Operating System Concepts →

Userspace hold times are unpredictable (you might call into a library that pages or does I/O). Sleeping is the default. The kernel has paths that must not sleep (interrupt handlers, code that already holds a spinlock on Linux) and paths whose critical sections are a few instructions with the holder running on another CPU. There, spinning is correct and cheaper than a full deschedule. Mixing the two — spinning in userspace on a lock whose holder is preempted — wastes a core and can invert priorities. Hybrid locks exist because the first dozen cycles of a short hold look like a spin win.

Open in Operating System Concepts →

Low-priority L holds a lock. High-priority H blocks on that lock. Medium-priority M runs and preempts L. H is now stuck behind M even though H outranks M. That is inversion. Inheritance lets L run at H's priority until it unlocks, so M cannot sneak in. Ceiling boosts anyone who takes the lock to a predeclared ceiling. On phones this is an audio/camera/RT story: a SCHED_NORMAL thread holding a lock that an RT or audio thread needs produces glitches. Android and real-time Linux use inheritance (including PI futexes) so the UI or audio path does not wait on a background job. Keep it light unless they are hiring for RT; power interaction is power & thermal.

Open in Operating System Concepts →

Instead of one tree per process indexed by VPN, keep one entry per physical frame: "this frame is (pid, vpn)" plus a hash to find a VPN quickly. Table size tracks RAM, not virtual space — attractive on huge address spaces. The downsides are: translate-this-VA becomes a search, shared pages need extra care, and the radix-tree plus TLB design is already good enough on the machines you will discuss. Mention it as an alternative organisation, not as "what Linux uses on ARM".

Open in Operating System Concepts →

W(t, Δ) is the set of pages referenced in the last Δ time. If the sum of working sets exceeds RAM, almost every reference misses, the disk is saturated, and CPU utilisation falls (the CPU is waiting on paging). That is thrashing. Fixes: admit fewer processes, enlarge RAM, shrink the working set (leak, oversized cache), or a working-set / page-fault-frequency policy that suspends a job until there are frames. A trap: "the box is slow, add CPU" when the iowait and fault rates say otherwise.

Open in Operating System Concepts →

Frames sit in a ring with a clock hand. On a need for a victim, look at the page under the hand. If the referenced (access) bit is 0, evict. If it is 1, clear it and advance — that page got a second chance. A hot page keeps getting its bit set by hardware and is skipped. This approximates LRU without a timestamp on every load. A dirty bit can add a third chance (prefer clean victims to skip a writeback). If the hand spins too fast, you are already thrashing.

Open in Operating System Concepts →

OPT (MIN) is the offline lower bound: evict the page whose next use is farthest in the future. You cannot know the future in a general-purpose OS, but you can measure how close LRU or Clock came on a trace. If OPT still faults a lot, the working set does not fit — no clever replacement will save you. If OPT is fine and FIFO is terrible, the policy is the problem. That is why it appears in every numerical and in every "which algorithm is best" discussion.

Open in Operating System Concepts →

A translator: device registers, DMA descriptors and IRQs on one side; a uniform kernel interface on the other (block, character, network). The filesystem should not know the SSD brand; the scheduler should not know the NIC. Drivers are trusted because they run with kernel privilege (or in a userspace I/O server with a narrow DMA API). How Linux binds a compatible string and runs probe is Linux kernel & BSP. Here the point is the abstraction boundary and why a bug in a driver is a kernel bug.

Open in Operating System Concepts →

Several designs: fsck walks the tree after a crash and repairs (slow, last-century default). Soft updates order metadata writes so a crash leaves a reachable, slightly leaked state rather than a broken pointer. Copy-on-write / shadow paging (new tree, then an atomic root swap) never overwrites the old consistent tree. Journaling is the common middle path: a log plus home-location writes. Interviewers want you to name the problem (metadata graph torn by a crash) and at least two remedies, not a vendor's on-disk format.

Open in Operating System Concepts →

A signal is an asynchronous control event with almost no payload. It can interrupt a thread between any two instructions (except where masked). The handler may call only async-signal-safe functions; malloc, printf and most locks are unsafe. Re-entrancy and interrupted syscalls (EINTR) are the tax. Use signals for "terminate", "job control", "a timer fired". Use a pipe, socket or a dedicated thread waiting on a signalfd-style descriptor if you need to turn the event into ordinary control flow. See C for the safe-function rule.

Open in Operating System Concepts →

Two processes mapping the same pages are just threads with a more expensive create path: they can tear structs, lose updates, and see stale stores. You need a mutex, a process-shared futex, a semaphore, or a carefully ordered lock-free protocol — plus the same visibility story. You also need a way to agree that the mapping exists (a POSIX shm name, an inherited fd, a mapped file). Fast path is loads/stores; the hard part is the protocol. Binder exists on Android in part so most app code never writes that protocol — frameworks.

Open in Operating System Concepts →

Run the guest in a deprivileged mode. Ordinary instructions execute natively. Privileged operations (load a page-table root, mask IRQs, issue I/O) trap to the hypervisor, which emulates the effect on virtual hardware and resumes the guest. This is the classic model. It requires that every sensitive instruction actually traps. Historic x86 had sensitive instructions that ran silently in user mode; that broke the model until hardware added a guest mode. Modern CPUs provide that mode; software VMMs still emulate devices.

Open in Operating System Concepts →

It fails when a guest instruction is sensitive (it would reveal or change privileged state) but is not privileged (it does not trap). The hypervisor never gets control, so the guest sees the host's truth or changes state it must not. Fixes: rewrite those instructions (binary translation), or use hardware virtualization extensions that make them trap or that give the guest its own view. Interviewers want the definition of "sensitive but unprivileged", not a product name.

Open in Operating System Concepts →

Namespaces virtualise names: PID (you can be PID 1 in a box), mount (your own filesystem view), network (your own interfaces and addresses), UTS, IPC, user. cgroups limit and account resources: CPU, memory, I/O, freezer. Together they are the usual container recipe. They do not give you a second kernel or a second scheduler. A kernel bug is still a host bug. Implementation knobs: Linux kernel & BSP. The concept: names vs quotas vs hardware virtualization.

Open in Operating System Concepts →

Userspace: C read in libc (C); Java would sit above this via ART/JNI (Java). Trap into the kernel (dual mode). Current thread's PCB → fd table → open file (offset, vnode). VFS read: pipe/socket may block (IPC + scheduler). Regular file: page cache lookup. Hit: copy to the validated user buffer. Miss: allocate a frame, submit block I/O, state = waiting, another thread runs. DMA + IRQ complete; waiter goes ready; scheduler eventually runs it; copy out; return. Kernel path: Linux kernel & BSP. Do not continue into device tree.

Open in Operating System Concepts →

One paragraph, then stop. CFS (and its fair-class successors) approximate ideal fair sharing: each task has a virtual runtime; the task that has been cheated the most runs next, so over a window everyone gets a weight-adjusted share. It is not FCFS and not textbook RR. POSIX FIFO/RR real-time classes sit above the fair class. Energy-aware scheduling, cgroup cpu controllers and Android binder-thread pools are kernel / power material. If they want a Gantt chart, they want a textbook policy, not CFS.

Open in Operating System Concepts →

Dual mode keeps user code from installing its own translations. Page tables keep process A from issuing loads that resolve to process B's frames (unless a shared mapping exists). Credentials and ACLs decide authorised kernel crossings (files, IPC). Namespaces and VMs add more views or another kernel. If the MMU story is broken, none of the higher policy matters: a write goes wherever the attacker maps it. That is why "isolation" answers should start with translations, not with a firewall.

Open in Operating System Concepts →

The device writes RAM. The CPU may still hold a stale line in cache, or the CPU may write back over a just-arrived packet. You need coherent interconnects or explicit cache flush/invalidate around the buffer. The device also needs a physical (or IOMMU-translated) address, not the process's virtual address. Bounce buffers exist when the device cannot reach the memory. This is still conceptual: IOMMU and Linux DMA APIs live on Linux kernel & BSP.

Open in Operating System Concepts →

Split the VA into unused high bits, three VPN indices, and a page offset. The page-table base register points at the L2 table. Index 1 selects an L1 table; index 2 selects a PTE; the PTE's PFN concatenated with the offset is the PA. Permissions live in the PTE (and sometimes in upper levels for entire regions). A TLB hit skips this. Draw the boxes; name "dependent loads". If they want Linux's 4-level/5-level names, send them to the kernel page.

Open in Operating System Concepts →

The child contains one thread: the one that called fork. Every other thread vanishes. If one of those threads held a mutex, the mutex stays locked in the child with no owner running to unlock it. The safe patterns are fork-then-exec (the new image has one thread and fresh locks) or to use pthread_atfork handlers that you actually understand. This is a favourite follow-up after "fork is just COW".

Open in Operating System Concepts →

A wait-for graph has processes as nodes and an edge P_i → P_j if P_i waits for a resource P_j holds. With single-instance resources, a cycle is deadlock. A full resource-allocation graph also has resource nodes and assignment/request edges. With multiple instances, a cycle is necessary but not sufficient — you may still reduce the graph (Banker's-style) and finish. Detection is cycle-find plus, for multi-instance, a safe-sequence search. Graph algorithms: DSA.

Open in Operating System Concepts →

Stores go to the page cache. Durability happens on writeback, msync, fsync, or eviction — not on the store instruction. A crash can lose dirty pages. Journaling of data (or a COW filesystem with a committed root) changes the story; metadata-only journals can leave a file whose size updated but whose new data did not, or the reverse, depending on mode. Interviewers want "mmap is not fsync" and a sentence on ordered vs data=journal, not an ext4 mount-option recitation.

Open in Operating System Concepts →

Metadata-only: fast; after a crash the tree is consistent but file contents may be stale or contain stale junk in freshly allocated blocks if you are sloppy. Ordered: write data blocks to their home locations before committing the metadata that points at them — the usual middle path. Data=journal: log data too; safest and heaviest. Pick by whether "file contains zeros or old bytes after a crash" is acceptable. Databases often do their own WAL and want the FS out of the way (fsync semantics), which is a system design conversation.

Open in Operating System Concepts →

A container calls the host kernel. The syscall ABI is large. A kernel memory-safety bug is often a host compromise. Namespaces hide names; they do not give you a second MMU for the kernel itself. A VM fails closed at the hypervisor and (usually) a guest kernel: the attack surface is virtual devices plus hypercalls, which is smaller if you keep the VMM tight. Density and start time go the other way. Use both: VMs as tenant boundaries, containers as deploy units, if the threat model says so.

Open in Operating System Concepts →

Batch: readv/writev, one mmap instead of many reads, io_uring-style submission queues (Linux-specific; name the idea: amortise the crossing). Avoid: stay in userspace with a cache, use huge pages to cut TLB misses, use shared memory for a hot IPC path. The OS topic is the crossing cost (mode switch + validation + possible schedule). Micro-optimising a single getpid is not the point; the point is that a chatty ABI kills throughput. See also system design for batching at service level.

Open in Operating System Concepts →

Classic VM thrashes: it keeps everyone alive and pages. A phone would feel frozen and burn flash. Android prefers to kill a cached process (oom_adj / LMK policy) and keep the foreground working set in RAM. That is admission control by death, not a different page-replacement algorithm. The theory is still working sets; the product policy is on Android frameworks.

Open in Operating System Concepts →

A mutex in shared memory must live in memory both processes can see and must wake a waiter in another address space. Fast path is still an atomic in userspace. Slow path (contention) needs the kernel to sleep and wake — Linux's futex is that wait queue keyed by an address. You do not implement a futex in an OS-concepts interview; you say "userspace atomic plus a kernel sleep queue" and send details to the kernel page. Language wrappers: C++, Java (monitors are in-process unless you add IPC).

Open in Operating System Concepts →

A 2 MiB or 1 GiB page occupies one TLB entry instead of 512 or more 4 KiB entries, so the TLB covers more of the working set and hit rate rises. The walk is shorter (you stop at a leaf that describes a large page). Costs: internal fragmentation, harder to move/evict, and allocation can fail if physical memory is fragmented. Mention as a TLB-capacity tool, not as a Linux THP tuning session.

Open in Operating System Concepts →

If the CPU is idle, it is not "compute bound". Look at I/O wait and paging: thrashing (disk busy, high fault rate, load average high because tasks are stuck in D / uninterruptible I/O), a lock convoy, or a filesystem journal stuck on a dying disk. Memory pressure with swap or a storm of major faults matches the working-set story. On Android, LMK killing and restarting can feel like freeze-and-jank — frameworks. Do not start with a faster CPU.

Open in Operating System Concepts →

Those are zombies: children exited, the parent never waited. RAM is probably fine; PID space is not. The parent is buggy (no SIGCHLD reap, or it ignored children). Fix the parent, or kill the parent so the zombies are reparented and reaped. If the parent is stuck in an infinite loop that never waits, that is a process-lifecycle bug, not a memory leak.

Open in Operating System Concepts →

A fork bomb: exponential process create until the PID table, memory (even with COW, each task_struct and kernel stack costs something), or a cgroup/nproc limit stops you. The machine becomes unresponsive because the scheduler and memory allocator are drowning. Defence is a process limit (ulimit/cgroup pids), not a clever scheduler. This is a resource-isolation question as much as a fork question.

Open in Operating System Concepts →

Lost update: both read, both add, both write. It is a race on a critical section that is one increment. Fix: a mutex around the increment, or an atomic fetch-add. Do not use volatile as the fix in C. Mention visibility: after the lock, other threads must see the new value — a correct mutex already publishes. If they ask you to write the code, keep the critical section to the increment; do not hold the lock across I/O.

Open in Operating System Concepts →

Each philosopher picks up the left fork then waits for the right: hold-and-wait plus circular wait. Prevention: (1) a global lock order (even-numbered philosopher takes right first), (2) pick up both forks atomically (or via a waiter/arbitrator), (3) a counting semaphore of N−1 philosophers so one seat is always empty and the cycle cannot close. Detection is a wait-for cycle among five processes. This is the Coffman checklist in costume.

Open in Operating System Concepts →

The audio or RT thread is high priority and needs the lock. A low-priority worker holds it. A medium-priority batch job runs and preempts the worker. The audio thread waits — inversion. Fix: priority inheritance on that lock, or do not take a sleep-lock on the audio path (lock-free ring buffer, try-lock and drop a frame). This is the light Android/RT note; do not dive into scheduler classes unless they ask — then kernel.

Open in Operating System Concepts →

SIGKILL is not delivered until the thread returns to a killable context. If it is in uninterruptible sleep waiting on I/O (classic UNIX "D state"), it will not handle signals until the I/O completes or fails. The portable story: some waits are uninterruptible so a filesystem is not left half-updated. The Linux specifics (D state, hung task detector) are kernel. User takeaway: the disk or a driver is the suspect, not "kill −9 is broken".

Open in Operating System Concepts →

Without a consistency scheme, bitmaps, directory entries and inodes can disagree: a name that points at a free inode, or allocated blocks that no file owns. A metadata journal would replay committed operations and restore a tree that could have existed. You might still lose the last un-fsynced data. fsck is the slow alternative. This is crash consistency, not "the journal makes every write immortal".

Open in Operating System Concepts →

A context switch is thousands of cycles plus cache/TLB loss. If the quantum is on the order of the switch, the CPU spends its life in the scheduler. Response time may even get worse because of the overhead. RR needs a quantum large versus a switch and small versus a human delay. Snappy interactive behaviour is more MLFQ/fair+priority than "tiny q".

Open in Operating System Concepts →

Threads: cheaper, easy to share a cache, one wild pointer or one infinite loop (without preemption of that thread's siblings... actually 1:1 threads preempt) — more importantly, one memory-corruption bug in a renderer can take the chrome if they share an address space. Processes: crash and security isolation, separate UID/sandbox, higher RAM (duplicated heaps, unless you share via IPC or a zygote-style fork). Real browsers pick processes for renderers. That is isolation over IPC cost — system design plus this page's process vs thread table.

Open in Operating System Concepts →

They used a plain store to a flag without a release/acquire pair or a process-shared mutex. The payload write can stay in a store buffer or be reordered. Fix: put the payload write before a release-store on the flag, and load-acquire the flag before reading the payload; or just use a mutex around the publish. This is the visibility question in IPC clothing.

Open in Operating System Concepts →

First gather a wait-for graph: who holds which lock, who waits (thread dumps, lockdep-style traces). A cycle is the smoking gun for single-instance locks. Prevention going forward: lock ranking, smaller critical sections, try-lock with backoff. Recovery now: kill a victim thread or restart the process (databases roll back a transaction). Banker's is almost never how you fix a live mutex deadlock — you do not have declared maxima. Tools are platform-specific; the vocabulary is this page.

Open in Operating System Concepts →

A PID namespace: the box has its own PID 1 and its own numbering. It cannot name host tasks by their host PIDs. It still shares the kernel, so it can still issue the same syscalls (unless a filter is added) and a kernel bug still matters. Memory and CPU limits are cgroups, not namespaces. Network isolation is a network namespace. Keep the "names vs quotas vs kernel" triangle straight.

Open in Operating System Concepts →

The store dirtied a cache page. No msync/fsync means the disk may have old data, new data, or a mix if writeback raced the crash. The directory may already show the new size if metadata was journaled first (or the reverse). Tell them mmap is a cache, not a durability API. For a header that must be atomic, write to a temp file and rename (atomic dir update) after fsync, which is also a system design pattern.

Open in Operating System Concepts →

Demand paging: the working set is being faulted in (code, data, mapped libraries). Major faults hit disk; minor faults map pages already in the page cache (shared libs). Then the working set fits and the fault rate drops. Fixes: demand-paging is working as designed; if the storm is too long, reduce the working set, prefetch the hot path, or keep a process warm (Android zygote is this idea — frameworks). Do not call it thrashing unless the fault rate stays high and the CPU is idle.

Open in Operating System Concepts →

Log daemon on the same machine: UNIX-domain socket or a named pipe (records vs stream: prefer a socket or a message-oriented protocol so lines do not tear). Shared memory only if the volume is huge and you will write a ring buffer with a futex. Off-box later: start with a stream socket and a versioned protocol so the transport can become TCP. Signals are wrong (no payload). Android apps talking to system_server: Binder — frameworks.

Open in Operating System Concepts →

Between stat and chmod the user can replace the path with a symlink to /etc/passwd (or any sensitive file). The helper applied a user-controlled name twice. Fix: open the path once (with O_NOFOLLOW if needed), fstat the fd, then fchmod the same fd. Bind check and use to one object. This is the exam version of "never operate twice on a raw path from an untrusted client".

Open in Operating System Concepts →

Thrashing or a working set that did not fit: the job looked busy but much of the "CPU time" was wait-on-page-fault, or the disk was the bottleneck. Extra frames let the working set stay resident, faults dropped, useful CPU rose. Check major fault counts and iowait before and after. A true CPU-bound job would have been at 100% compute with few faults and would not have doubled in speed from RAM alone.

Open in Operating System Concepts →

Convoy effect under FCFS (or RR with a huge quantum). The long CPU burst blocks the short ones; they then all I/O-wait and rejoin behind it. Change to RR with a sane quantum, MLFQ (demote the compile), or a priority/fair class that reserves share for interactive work. CFS's fair share is the Linux example of "the compile does not own the machine" — one sentence, then stop.

Open in Operating System Concepts →

C program calls read (C). libc traps. Kernel: fd → file → VFS. Page cache miss: allocate a frame, attach a bio, submit to the block layer, put the thread in waiting. Scheduler runs someone else. Disk DMA fills the frame; IRQ signals completion; the waiter is marked ready. Later it runs, copies bytes to the user buffer, returns the count. Privilege dropped. If this were Java, ART and JNI sit above libc (Java). Hardware/driver objects: Linux kernel & BSP.

Open in Operating System Concepts →

MAP_SHARED: they share page-cache pages; a store is visible to the other and is a candidate for writeback to the file. MAP_PRIVATE: reads share until a write; the write COWs a private page that will not go back to the file (and the sibling still sees the old page). After fork, the child's private maps are COW against the parent as well. Ask which flags they used before you debug "why doesn't the other process see my write?".

Open in Operating System Concepts →

Causes: tiny RR quantum, too many runnable threads (1:1 thread-per-connection without a pool), lock ping-pong (threads wake each other for tiny critical sections), or blocking I/O with no batching. Fixes: fewer threads (event loop or a pool), longer quantum / fair scheduler, coarsen the locking, batch syscalls, use shared memory instead of a chatty pipe. Switching is not free; the indirect cache cost is why. DSA-level "too many workers" is the same idea as too many threads here.

Open in Operating System Concepts →

Vertical scaling (scale up) means a bigger machine: more CPU, memory or faster disks. It is simple and needs no code changes, but has a hard ceiling, rising cost, and remains a single point of failure. Horizontal scaling (scale out) means more machines behind a load balancer. It grows almost without limit and tolerates failures, but requires stateless services, data partitioning and handling of network and coordination complexity. Large systems scale out, though scaling a database up first is often the pragmatic early step.

Open in System Design →

If a server keeps no per-user state between requests, any server can handle any request. That lets you add or remove servers freely (autoscaling), replace a failed server without losing sessions, deploy with rolling restarts, and balance load evenly without sticky sessions. State moves to shared stores built for it: sessions in Redis or a database, or a signed token such as a JWT carried by the client; files in object storage.

Open in System Design →

Latency is the time one request takes; throughput is how many requests (or bytes) the system handles per unit time. They are related but distinct: batching raises throughput but can raise latency, and a system can have high throughput with poor latency. By Little's law, concurrency = throughput x latency, so for a fixed concurrency limit, lower latency means higher throughput. Optimise the one the product needs: interactive APIs care about latency, batch pipelines about throughput.

Open in System Design →

Latency distributions have long tails; the average hides the slow requests that users actually notice. p50 is the typical experience, p99 is the experience of 1 in 100 requests, which for a heavy user can mean several slow requests per session. When one page fans out to many backends, the page is as slow as its slowest call, so backend p99 becomes user-facing median. SLOs are usually written on p95 or p99.

Open in System Design →

About 53 minutes of downtime per year, or about 4.4 minutes per month. For comparison, 99.9% is about 8.8 hours per year and 99.999% about 5 minutes. Serial dependencies multiply: a service at 99.99% that depends on a database at 99.99% is about 99.98%. Achieving four nines requires redundancy with no single points of failure, automated failover, safe deployment practices, and often multiple zones.

Open in System Design →

A single point of failure (SPOF) is any component whose failure brings down the whole system: one database, one load balancer, one region, one DNS provider, even one engineer's credentials. Remove it with redundancy (multiple instances across zones), health checks with automatic failover (leader election for databases), replication of data, and avoiding shared mutable singletons. Test failover regularly, since untested redundancy often fails when needed.

Open in System Design →

When the network partitions, a distributed system must choose between consistency (every read returns the latest write) and availability (every request to a live node gets a successful response). A bank ledger chooses CP: the minority side rejects writes rather than let balances diverge. A shopping cart or social feed chooses AP: both sides keep accepting writes and reconcile later. Without a partition you can have both; CAP only forces the choice during partitions, which cannot be ruled out in real networks.

Open in System Design →

Strong consistency means every read reflects the latest committed write; it is needed for balances, inventory, uniqueness constraints (usernames) and authorisation changes. Eventual consistency means replicas converge over time; it is fine for likes, view counts, feeds, recommendations and presence, and gives better latency and availability at scale. Choose per data type within the same system, and use in-between guarantees such as read-your-writes where users would otherwise notice.

Open in System Design →

Start from access patterns and consistency needs. Choose relational (PostgreSQL, MySQL) for structured data with relationships, ad-hoc queries, joins, constraints and ACID transactions (orders, payments, accounts); it scales further than people assume with indexes, replicas and partitioning. Choose NoSQL when you need massive horizontal write throughput, simple key-based access, flexible schemas, or a specific model: key-value (sessions), wide-column (messages, time series), document (catalogues), graph (social connections). Many systems use both.

Open in System Design →

An index is an auxiliary data structure, usually a B+ tree, that keeps a column's values sorted with pointers to rows, turning a full table scan (O(n)) into an O(log n) lookup and enabling efficient range queries and sorting. Costs: every insert, update and delete must maintain each index (slower writes), extra storage, and the optimiser can pick badly with too many. Index columns used in WHERE, JOIN and ORDER BY, respect the leftmost-prefix rule for composite indexes, and avoid over-indexing write-heavy tables.

Open in System Design →

Replication copies the same data to multiple nodes, improving read throughput, availability and durability, but not write capacity (every replica still applies every write). Sharding splits different data across nodes by a key, scaling writes and storage, but adds cross-shard query complexity. Real systems combine both: each shard is replicated.

Open in System Design →

It distributes incoming requests across a pool of servers, runs health checks to remove unhealthy ones, and often terminates TLS. Algorithms: round robin, weighted round robin for mixed capacity, least connections for long or uneven requests (WebSockets), least response time, IP or consistent hashing for affinity and cache locality, and power-of-two-choices (pick two random servers, choose the less loaded). The balancer itself must be redundant (active-passive pair or a managed service).

Open in System Design →

Layer 4 balancers route by IP address and port without reading the payload: very fast, protocol agnostic, suitable for any TCP or UDP traffic. Layer 7 balancers understand HTTP: they route by path, host, header or cookie, terminate TLS, rewrite headers, retry, compress and support sticky sessions, at a bit more CPU cost. A common setup is L4 at the edge for raw scale, then L7 for application routing.

Open in System Design →

A content delivery network caches content on edge servers near users. It cuts latency (fewer long round trips), offloads the origin, absorbs traffic spikes and DDoS, and can terminate TLS near users. It helps most for static and cacheable content (images, video segments, JavaScript, CSS, public API responses) and globally distributed users. It helps little for personalised, rapidly changing or write-heavy traffic. Use versioned file names for cache busting and signed URLs for private content.

Open in System Design →

The application checks the cache first; on a miss it reads the database, stores the result in the cache with a TTL, and returns it. On a write it updates the database and deletes the cache entry. It is common because the cache only holds data that is actually requested, the application controls the logic, and if the cache fails the system still works (just slower). Downsides: the first request after a miss is slow, and there are brief windows of staleness.

Open in System Design →

LRU evicts the least recently used item and suits workloads where recent use predicts future use; it is O(1) with a hash map and a doubly linked list. LFU evicts the least frequently used item and suits stable popularity but needs ageing. FIFO and random are simple and sometimes adequate. TTL-based expiry bounds staleness independently of memory pressure. Redis offers approximate LRU and LFU policies that sample keys rather than tracking exact order.

Open in System Design →

To decouple producers from consumers (neither needs the other to be up), to absorb traffic spikes and level load, to move slow work off the request path (emails, image processing), to fan events out to several independent consumers, and to retry failed work durably. The cost is eventual consistency, operational overhead, and the need for idempotent consumers and careful ordering design.

Open in System Design →

An operation is idempotent if performing it several times has the same effect as once. Networks time out, clients retry, and queues redeliver, so duplicates are normal. Without idempotency, a retried payment charges twice or a redelivered message creates two orders. Achieve it with client-generated idempotency keys stored by the server, unique constraints on natural keys, conditional or versioned updates, and deduplication tables in consumers. HTTP GET, PUT and DELETE are defined as idempotent; POST is not.

Open in System Design →

REST (HTTP and JSON) is simple, universal, cacheable and ideal for public APIs. gRPC uses HTTP/2 and Protocol Buffers: compact, fast, strongly typed with generated clients and streaming, ideal for internal service-to-service calls, but less friendly to browsers and humans. GraphQL lets clients request exactly the fields they need in one round trip, great for mobile clients aggregating many resources, but caching, authorisation per field and query cost control are harder.

Open in System Design →

Offset pagination (?page=5&size=20) is simple and supports jumping to a page, but the database must skip all earlier rows (slow for deep pages), and inserts or deletes between requests cause skipped or duplicated items. Cursor (keyset) pagination returns an opaque cursor encoding the last seen sort key; the next query is "items after this key", which uses an index, stays fast at any depth, and is stable under concurrent writes. Use cursors for feeds and large lists.

Open in System Design →

Rate limiting caps how many requests a client may make per time window, protecting services from abuse, runaway clients and overload, and enforcing fair use or pricing tiers. Apply it at the API gateway or edge (per user, API key or IP), within services for expensive operations, and on the client side to be a good citizen. Common algorithms are token bucket, leaky bucket, fixed window, sliding window log and sliding window counter. Rejected requests get HTTP 429 with a Retry-After header.

Open in System Design →

ACID describes transactional guarantees in relational databases: atomicity (all or nothing), consistency (constraints hold), isolation (concurrent transactions behave as if serial, depending on the isolation level) and durability (committed data survives crashes, via a write-ahead log). BASE describes many large NoSQL systems: basically available, soft state, eventually consistent. ACID favours correctness; BASE favours availability and scale.

Open in System Design →

A monolith is one deployable unit: simple to develop, test, debug and deploy, with in-process calls and easy transactions; ideal for small teams and new products. Microservices split the system into independently deployable services owned by separate teams: independent scaling and releases, fault isolation and technology freedom, at the cost of network calls, partial failures, distributed data and a large observability and platform investment. A common path is a well-modularised monolith first, then extracting services where team or scaling boundaries demand it.

Open in System Design →

An SLI (service level indicator) is a measurement, such as the percentage of requests served successfully under 300 ms. An SLO (objective) is the internal target for that SLI, such as 99.9% over 30 days. An SLA (agreement) is an external contract with consequences, usually looser than the SLO. The error budget is 100% minus the SLO; while budget remains, teams can ship risky changes, and when it is exhausted they focus on reliability.

Open in System Design →

A forward proxy acts on behalf of clients: clients send requests through it to reach the internet (corporate egress filtering, anonymity, caching). A reverse proxy acts on behalf of servers: clients talk to it thinking it is the server, and it forwards to backend servers, providing load balancing, TLS termination, caching, compression and protection (Nginx, Envoy, HAProxy). Load balancers and API gateways are specialised reverse proxies.

Open in System Design →

The client asks a recursive resolver, which queries a root server, then the top-level domain server, then the domain's authoritative server, caching each answer for its TTL. In designs, DNS provides geographic or latency-based routing to the nearest region, weighted routing for gradual migrations, and failover by changing records. Low TTLs allow faster failover but increase query load, and some clients ignore TTLs, so DNS failover is never instantaneous.

Open in System Design →

A Bloom filter is a bit array plus k hash functions. Adding an item sets k bits; a lookup that finds any bit unset means the item was never added (no false negatives). If all k bits are set, the item is probably present (false positives). About 10 bits per item gives roughly a 1 percent false-positive rate. You cannot delete (unless you use a counting variant) and you cannot list the items. Use it to skip work: "this URL was definitely not crawled", "this key is definitely not in the database" (cache penetration), or "this key is definitely not in this SSTable" (LSM reads). If a false positive is expensive, keep the error rate low or confirm with the source of truth.

Open in System Design →

A write-ahead log (WAL) is an append-only file of changes written to durable storage before the corresponding in-memory structure (database page, memtable) is treated as committed. On crash, the store replays the log to recover. Sequential appends are fast; the log is the durability mechanism behind ACID's D and behind LSM memtable flushes. Related ideas: Kafka is a distributed WAL; the outbox pattern is a WAL of events next to business rows; Redis AOF is a WAL of commands.

Open in System Design →

PACELC says: if there is a Partition, choose Availability or Consistency; Else, in normal operation, choose Latency or Consistency. It captures the everyday trade-off CAP ignores: synchronous replication to other replicas or regions makes every write slower, while asynchronous replication is fast but readers can see stale data. DynamoDB and Cassandra are typically PA/EL; Google Spanner and synchronously replicated relational databases are PC/EC.

Open in System Design →

Each key is stored on N replicas. A write succeeds when W replicas acknowledge; a read queries R replicas and takes the newest version. If R + W > N, the set of replicas read must overlap the set written, so at least one replica in every read has the latest write. N=3, W=2, R=2 tolerates one failed replica for both reads and writes. W=1, R=1 is fast but may return stale data. Quorums alone are not full linearizability (concurrent writes and sloppy quorums complicate it), so systems add versioning and read repair.

Open in System Design →

Linearizable: the system behaves like a single copy; once a write completes, every later read sees it. Needed for locks, leader election, unique constraints; costs latency and availability. Causal: causally related operations are seen in order everywhere (a reply never appears before its post), but unrelated ones may differ; available under partitions. Read-your-writes: a user always sees their own updates, implemented by routing their reads to the leader or tracking replication position. Eventual: replicas converge if writes stop; cheapest, but readers can see old or out-of-order data.

Open in System Design →

Write-through: write to cache and database synchronously; the cache is always fresh, but writes are slower and the cache fills with data that may never be read. Write-back: write to the cache and flush to the database later; very fast and allows batching, but risks losing data if a cache node fails before flushing. Write-around: write only to the database; the cache fills on later reads, avoiding pollution by write-once data, at the cost of a miss on the first read. Most web systems use cache-aside reads with write-around plus invalidation.

Open in System Design →

When a popular key expires or is evicted, many concurrent requests miss at once and all hit the database to rebuild it, which can overload it. Prevention: request coalescing or a per-key lock so only one request rebuilds while others wait or get stale data; serving stale-while-revalidate; adding random jitter to TTLs so keys do not expire together; probabilistic early refresh of hot keys; and pre-warming caches after deploys or restarts.

Open in System Design →

Treat the database as the source of truth. On writes, commit to the database first, then delete (not update) the cache key, so the next read reloads fresh data; deleting avoids races where concurrent writers leave an older value cached. Bound staleness with TTLs. For stronger guarantees, drive invalidation from the database's change stream (change data capture) so every committed change invalidates the cache, or use versioned keys. Accept that perfect consistency between two systems without a transaction is not achievable; state how much staleness the product tolerates.

Open in System Design →

Nodes and keys are hashed onto the same circular space; each key belongs to the first node clockwise from it. When a node joins, it takes only the keys between it and its predecessor; when a node leaves, only its keys move to its successor, about 1/N of the data, whereas hash mod N remaps almost every key when N changes. Virtual nodes (many ring positions per physical node) even out the load and allow weighting by capacity. Used in distributed caches, Dynamo-style stores, and load balancers needing affinity.

Open in System Design →

A good shard key has high cardinality, distributes reads and writes evenly, and matches the dominant access pattern so most queries hit a single shard (user_id for user data, conversation_id for messages). Avoid monotonically increasing keys with range sharding (all new writes hit one shard). For hot shards: split the hot range, add a random suffix to hot keys and scatter-gather on read, cache hot entities aggressively, give celebrities special handling, or move a hot tenant to a dedicated shard via a directory service.

Open in System Design →

With asynchronous replication, followers apply the leader's changes after a delay, from milliseconds to seconds under load. A user who updates their profile and immediately reads from a follower may see the old value. Fixes: read the user's own data from the leader, or from the leader for a short window after they write; track the log position of the user's last write and only read from followers that have caught up; or pin a user to one replica for monotonic reads.

Open in System Design →

Followers or a coordinator detect that the leader has stopped heartbeating, elect a new leader (ideally the most up-to-date follower) through a consensus system, and redirect clients. Split brain happens when the old leader was only slow or partitioned, not dead, and keeps accepting writes, so two leaders diverge. Prevent it with majority-based election (a leader needs a quorum), leases that expire, and fencing tokens that storage checks to reject writes from a deposed leader. Asynchronous replication also means the newly promoted leader may be missing the last few writes.

Open in System Design →

Kafka is a distributed, partitioned, append-only log. Messages are retained for a configured time regardless of consumption; many consumer groups read independently by offset; ordering is per partition; throughput is very high; replay is easy. It suits event streaming, analytics pipelines, event sourcing and change data capture. RabbitMQ is a message broker with queues: messages are routed via exchanges, delivered to one consumer, and removed on acknowledgement; it supports per-message routing, priorities and delays. It suits task queues and complex routing at moderate scale.

Open in System Design →

At-most-once acknowledges before processing and can lose messages. At-least-once acknowledges after processing and can duplicate on retries or consumer crashes; it is the practical default. True exactly-once delivery across independent systems is not possible in general, but you can achieve exactly-once effects by combining at-least-once delivery with idempotent processing (dedupe by message ID, conditional writes) or with transactions that commit the consumer offset and the result atomically (as Kafka transactions do within Kafka).

Open in System Design →

A service that writes to its database and then publishes an event can fail in between, leaving the database updated but no event sent (or an event sent for a rolled-back write). The transactional outbox writes the business change and an event row into an outbox table in the same local transaction. A separate relay (polling or change data capture) reads the outbox and publishes to the queue, retrying until it succeeds. Delivery becomes at-least-once, so consumers must be idempotent.

Open in System Design →

Two-phase commit has a coordinator ask all participants to prepare, then commit; it gives atomicity but holds locks during the protocol and blocks if the coordinator fails, which hurts availability and couples services. A saga breaks the business transaction into local transactions, each publishing an event or called by an orchestrator; if a step fails, compensating transactions undo earlier steps (refund payment, release inventory). Sagas are available and loosely coupled but only eventually consistent, and compensations must be designed explicitly. Microservices generally prefer sagas.

Open in System Design →

Retry only transient failures (timeouts, 503s), never permanent ones (400s). Retry only idempotent operations or those protected by idempotency keys. Use exponential backoff (for example 100 ms, 200 ms, 400 ms) with random jitter so clients do not retry in lockstep, cap the attempt count and total time, and use a retry budget (for example retries at most 10 percent of requests). Retry at one layer only, to avoid multiplicative retry storms, and respect Retry-After headers.

Open in System Design →

It wraps calls to a dependency and tracks failures. In the closed state calls pass through. When failures or timeouts exceed a threshold, it opens and fails calls immediately (or serves a fallback) for a cooldown period, protecting both the caller's threads and the struggling dependency. After the cooldown it goes half-open and lets a few trial calls through; success closes it, failure reopens it. Pair it with timeouts, bulkheads and meaningful fallbacks such as cached data or a degraded feature.

Open in System Design →

Options: UUIDv4 (random 128-bit, no coordination, but not sortable and poor for B-tree locality; UUIDv7 adds a time prefix); Snowflake-style 64-bit IDs of timestamp + machine ID + per-millisecond sequence (sortable by time, compact, no coordination after machine ID assignment, but needs clock care); database ticket servers or range allocation where each server reserves a block of IDs (simple, few round trips). Choose by whether you need ordering, size limits, and guessability concerns.

Open in System Design →

B-trees (most relational databases) update pages in place: reads are fast and predictable with one tree lookup, and range scans are efficient, but random writes cause random I/O and write amplification. LSM trees (Cassandra, RocksDB) append writes to a log and an in-memory table, flush sorted immutable files, and merge them by compaction: writes are sequential and very fast, but reads may check several files (mitigated by Bloom filters) and compaction consumes I/O in the background. Choose LSM for write-heavy workloads, B-trees for read-heavy and transactional ones.

Open in System Design →

Lost updates can also be prevented with SELECT ... FOR UPDATE or optimistic version checks. Write skew example: two doctors both go off call because each saw the other still on call.

Open in System Design →

Short polling: the client asks every few seconds; simple but wasteful and laggy. Long polling: the server holds the request until there is data or a timeout; near real time over plain HTTP. Server-sent events: one long-lived HTTP response streaming server-to-client events; simple, auto-reconnect, one direction only. WebSockets: a full-duplex persistent connection; best for chat, games and collaborative editing, but stateful connections must be load-balanced, drained on deploy, and mapped to users in a session registry.

Open in System Design →

Assume an average stored photo of 2 MB after compression, plus about 3 smaller renditions totalling 0.5 MB, so 2.5 MB per upload. Daily: 10 M x 2.5 MB = 25 TB per day. Yearly: about 9 PB. With 3x replication that is about 27 PB per year, or about 1.5x with erasure coding (about 14 PB). Metadata is small by comparison (about 1 KB per photo, 3.6 TB per year). Conclusions: blob storage with erasure coding and cold tiers for old photos, a CDN for delivery, and metadata in a sharded database.

Open in System Design →

Assume each user posts 0.5 times a day and reads their timeline 20 times a day. Writes: 200 M x 0.5 / 86,400 is about 1,200 posts per second, peak about 3,000 to 5,000. Timeline reads: 200 M x 20 / 86,400 is about 46,000 per second, peak about 100,000 to 150,000. The system is read-heavy by about 40:1, so precomputed timelines in cache (fan-out on write) make sense, and the fan-out work is posts per second times average followers, which is where celebrities need special handling.

Open in System Design →

Use a system built on consensus (etcd, ZooKeeper, Consul) or a carefully designed Redis lock with a lease: acquire atomically with an expiry (SET key value NX PX 30000) and a unique owner value, release only if you still own it (compare-and-delete). Because a holder can pause (garbage collection, network) past its lease, the resource being protected must check a fencing token, a monotonically increasing number issued with each lock grant, and reject writes carrying an older token. Prefer designs that avoid locks, such as partitioning ownership or conditional writes.

Open in System Design →

The four golden signals: latency (percentiles, separately for successes and errors), traffic (requests per second), errors (rate by type), and saturation (CPU, memory, queue depth, connection pool usage). Add business metrics (orders per minute), dependency health, and for queues, consumer lag. Combine metrics with structured logs carrying request IDs and distributed traces. Alert on SLO burn rate and user-visible symptoms rather than every internal cause, and give each alert a runbook.

Open in System Design →

OLTP databases serve the application: many small, indexed reads and writes with low latency and transactions, stored row by row. OLAP systems serve analytics: few, large queries scanning and aggregating billions of rows, stored column by column with heavy compression. Running analytics on the OLTP database competes for resources and slows the product. Instead, stream changes (change data capture or ETL) into a warehouse or lakehouse such as BigQuery, Redshift, Snowflake or ClickHouse.

Open in System Design →

A central Redis counter updated atomically with a Lua script is accurate but adds a network round trip per request and becomes a hot dependency. Options to trade accuracy for latency: local token buckets on each gateway node with a share of the global limit, periodically rebalanced; batching increments asynchronously to the central store and enforcing slightly conservative local limits; sharding Redis by client key; and sticky routing of a client to the same gateway so local state suffices. Decide in advance whether to fail open or closed if the store is unavailable.

Open in System Design →

Each node is follower, candidate or leader. Followers expect heartbeats; on timeout a follower increments its term, becomes a candidate, and requests votes. A node votes for at most one candidate per term; majority wins and the leader starts heartbeats. Clients write to the leader, which appends to its log and replicates the entry. The entry is committed when a majority of nodes have stored it; the leader then applies it and replies. Safety: a candidate cannot win unless its log is at least as fresh as the voters', so committed entries are never overwritten. With 2f+1 nodes you tolerate f failures. Use Raft for metadata, leader election and small linearizable state (etcd, ZooKeeper-like systems), not as the data plane for high-QPS records.

Open in System Design →

Wall clocks drift and jump; do not order events across machines by timestamp alone (last-writer-wins can silently drop an update). Lamport clocks are a single counter incremented on every event and sent with messages; they preserve causality (if A happened-before B then L(A) < L(B)) but two equal counters can still be concurrent. Version vectors keep one counter per replica; comparing two vectors tells you happens-before or concurrent (a conflict to merge). Leaderless stores use version vectors or dotted version vectors; Spanner uses TrueTime (bounded clock uncertainty plus commit wait) when it needs a real-time order.

Open in System Design →

• Requirements: shorten a URL, redirect, optional custom alias and expiry, analytics. Read-heavy (10:1 or more), low-latency redirects, highly available; links must never point to the wrong target.
• Estimates: 100 M new links per day is about 1,200 writes per second and 12,000 reads per second; about 90 TB over five years; 7 base62 characters give 3.5 trillion keys.
• API: POST /v1/urls returns the short URL; GET /{key} returns 301 or 302.
• Keys: base62 of a unique 64-bit ID from a Snowflake-style generator or pre-allocated counter ranges (no collisions); hashing plus collision check is the alternative; custom aliases use a conditional insert.
• Data: KV store (key to long URL, owner, expiry), sharded by key and replicated.
• Reads: CDN and Redis cache-aside in front of the KV store; hot links give a high hit ratio.
• Analytics: click events to a stream asynchronously, aggregated offline.
• Trade-offs: 301 reduces load but hides repeat clicks from analytics; sequential IDs are guessable (shuffle bits if that matters); rate limit creation and scan for malicious links.

Open in System Design →

• Requirements: per-client limits by rule (for example 100 requests per minute per API key), about 1 ms of overhead, accurate within a few percent, highly available, clear client feedback.
• Algorithm: token bucket (bursts allowed, average enforced) or sliding window counter (accurate with O(1) memory).
• Where: middleware in the gateway, with rules loaded from configuration and cached locally.
• State: Redis keyed by client and rule; a Lua script atomically refills, checks and decrements, and sets an expiry. Shard Redis by key.
• Response: 429 with Retry-After and remaining-quota headers.
• Deep dive: race conditions without atomic scripts; local buckets synced periodically for very high QPS; multi-region limits (per region or asynchronously aggregated); fail open vs fail closed when Redis is down; hot keys for a single abusive client.

Open in System Design →

• Requirements: one-to-one and group chat, delivery and read receipts, presence, offline delivery, history across devices, media; messages never lost, ordered within a conversation, end-to-end latency under a few hundred ms.
• Estimates: 500 M daily users x 40 messages is 20 B messages per day, about 230,000 per second average; tens of millions of concurrent connections.
• Connections: WebSocket gateways; a session registry maps user to gateway node with TTL heartbeats.
• Send: gateway to chat service, which assigns a per-conversation sequence number, persists, acknowledges the sender ("sent"), then routes to the recipient's gateway or to push (APNs/FCM) if offline.
• Storage: wide-column store partitioned by conversation_id, clustered by sequence; clients sync with "messages after sequence N". Media in object storage via pre-signed URLs, sent as references.
• Groups: fan-out via a queue for small groups; pull model for very large channels.
• Deep dive: idempotent resends with client message IDs; ordering and multi-device sync; presence throttling; end-to-end encryption with the Signal protocol meaning the server sees only ciphertext; gateway draining during deploys.

Open in System Design →

• Requirements: post, follow, view a ranked home timeline quickly; eventual consistency is acceptable (seconds of delay).
• Estimates: read-heavy by roughly 40-100 to 1; a celebrity post may need to reach tens of millions of timelines.
• Data: posts store (sharded by post ID), social graph store, timeline cache (Redis lists of post IDs per user, capped to a few hundred), media on a CDN.
• Write path: post saved, event on a queue, fan-out workers push the post ID into followers' timelines (fan-out on write).
• Hybrid: skip fan-out for accounts with huge follower counts; at read time, merge their recent posts into the precomputed timeline (fan-out on read). Skip inactive followers.
• Read path: fetch timeline IDs, hydrate posts from cache, rank (recency, affinity, engagement model), cursor pagination.
• Trade-offs: write amplification vs read latency; storage for precomputed timelines; ranking freshness vs cost.

Open in System Design →

• Requirements: send to millions of users across channels, respect preferences and quiet hours, no duplicates, prioritise urgent messages, track delivery.
• Flow: producer services call a notification API with an idempotency key, or emit events; the service validates, checks preferences and rate limits, renders templates, and enqueues to per-channel, per-priority queues.
• Workers: channel workers call provider adapters (APNs, FCM, SMS gateways, email providers) with retries and exponential backoff, failover between providers, and a dead-letter queue.
• Data: device registry (tokens per user, pruned when providers report invalid tokens), preferences, templates, notification log for dedupe and audit.
• Scale: shard by user ID; bulk campaigns paced by a scheduler to respect provider quotas.
• Deep dive: exactly-once effect via dedupe on idempotency key; per-user frequency caps; delivery and open tracking; time-zone-aware scheduling.

Open in System Design →

• Requirements: upload, download, share, sync across devices, version history; files up to many GB; durable; works on flaky networks.
• Chunking: split files into about 4 MB chunks named by content hash; upload only missing chunks (deduplication and delta sync); resumable uploads.
• Services: metadata service (files, folders, versions, chunk lists, ACLs) in a sharded relational database; block storage in an object store; clients upload and download chunks directly via pre-signed URLs.
• Sync: a per-user change journal with increasing versions; devices hold a cursor and long-poll or subscribe for notifications, then pull changes after their cursor.
• Conflicts: optimistic concurrency on file version; on conflict create a "conflicted copy".
• Deep dive: durability through replication or erasure coding, cold storage tiers, garbage collection of unreferenced chunks, sharing permissions, and bandwidth throttling on the client.

Open in System Design →

• Requirements: upload, process, stream at scale globally with smooth playback on varying networks; search and recommendations are separate subsystems.
• Upload: resumable chunked uploads to object storage; an event starts processing.
• Processing: a DAG of jobs on queues: validate, split into segments, transcode into multiple resolutions and codecs in parallel, generate thumbnails, run content moderation, package HLS/DASH manifests.
• Delivery: CDN serves segments; adaptive bitrate players choose quality per segment; popular videos pre-positioned at edges, the long tail served from regional caches or origin.
• Metadata: video info, channels and comments in sharded databases with caches; view counts aggregated via streams.
• Trade-offs: storage and egress cost vs quality (encode popular videos with more renditions and better codecs); processing latency vs cost; eventual consistency for counts.

Open in System Design →

• Requirements: riders request trips, see nearby drivers, get matched quickly; drivers stream location; trips are tracked and billed.
• Estimates: 1 M active drivers updating every 4 seconds is about 250,000 location writes per second.
• Location service: in-memory geospatial index (geohash, quadtree, or S2/H3 cells) sharded by region; only latest position kept hot, history streamed to a log.
• Matching: query the rider's cell and neighbours, rank candidates by ETA, offer to one driver with a timeout, then the next; assignment must be exclusive (conditional update or lock on driver state).
• Trip service: durable state machine (requested, accepted, arriving, in trip, completed, cancelled); payments via a separate idempotent payment service.
• Deep dive: hot cells in city centres (split cells adaptively), surge pricing per cell from supply and demand, ETA from a routing engine, regional isolation for availability.

Open in System Design →

• Requirements: top 5-10 suggestions per prefix within about 100 ms end to end; popularity-based, optionally personalised; filtered for unsafe terms.
• Data collection: query logs aggregated offline (for example hourly) into prefix frequencies, with decay for freshness.
• Serving structure: a trie with the top-k completions precomputed at every node, so a lookup is O(prefix length); built offline and loaded into memory on serving nodes.
• Scale: shard by prefix range, replicate for reads, cache hot prefixes at the CDN or edge, and client-side debouncing and caching.
• Trade-offs: freshness vs build cost (add a small real-time trending layer), memory vs coverage (only keep prefixes above a frequency threshold).

Open in System Design →

• Requirements: get and put by key, horizontally scalable, highly available, tunable consistency, durable.
• Partitioning: consistent hashing with virtual nodes.
• Replication: N replicas on successive distinct nodes across zones.
• Consistency: configurable quorums (R + W > N for stronger reads); version vectors to detect concurrent writes; last-writer-wins or client merge for conflicts.
• Failures: gossip-based membership and failure detection, hinted handoff for temporarily down nodes, read repair, and Merkle-tree anti-entropy to reconcile replicas.
• Storage engine: write-ahead log, memtable, SSTables with Bloom filters, compaction, tombstones for deletes.
• Trade-offs: AP with eventual consistency by default vs CP via consensus per shard (Raft groups, like etcd or TiKV) for linearizable operations at higher latency.

Open in System Design →

• Requirements: sub-millisecond get and set, horizontal scale to terabytes of RAM, TTLs and eviction, survives node failures (data loss acceptable but should be limited).
• Partitioning: hash slots or consistent hashing; clients or a proxy route by key; slot map updates on resharding.
• Replication: each primary has replicas; automatic failover promotes a replica; asynchronous replication may lose recent writes.
• Node design: hash table in memory, approximate LRU or LFU eviction under a memory cap, lazy plus periodic TTL expiry, event-loop networking.
• Deep dive: hot keys (client-side near cache, key replication), cold-start protection for the database, cache stampede controls, and large values (compress or split).

Open in System Design →

• Requirements: crawl billions of pages, polite to sites, avoid duplicates, prioritise important and frequently changing pages, extensible for indexing.
• Components: seed URLs, URL frontier with priority queues and per-host queues (politeness delays, robots.txt cache), DNS cache, fetcher workers, parser and link extractor, URL normaliser and "seen" filter (Bloom filter or hash store), content dedupe (checksums, SimHash for near duplicates), page storage in object storage, index pipeline.
• Scale: partition the frontier by host hash so each host is handled by one worker group, enabling politeness without coordination.
• Deep dive: crawler traps (depth limits, URL patterns), recrawl scheduling by change frequency, handling JavaScript-heavy pages with a rendering tier, fault tolerance by checkpointing the frontier.

Open in System Design →

• Requirements: charge customers through external payment providers, never double-charge or lose money, full audit trail, strong consistency, reconcile with providers.
• API: POST /payments with a client-supplied idempotency key; asynchronous status via webhooks and polling.
• Flow: payment service records the intent (pending) in a relational database, calls the provider with the same idempotency key, updates status on the response or webhook; retries are safe because both layers dedupe.
• Ledger: double-entry bookkeeping (every movement debits one account and credits another), append-only, so balances are derived and auditable.
• Reliability: outbox pattern for events to downstream systems (orders, notifications); timeouts are "unknown" states resolved by querying the provider; daily reconciliation against provider settlement files flags mismatches.
• Trade-offs: choose CP for the ledger; accept higher latency; separate the synchronous authorisation path from asynchronous settlement; strict security (tokenised card data, PCI scope minimised).

Open in System Design →

• Requirements: schedule one-off and recurring jobs, run each at least once near its time, retries, visibility into history, millions of jobs.
• Data: jobs table with schedule, next_run_at, status, owner; index on next_run_at; execution history table.
• Scheduler: partitioned scheduler nodes each own a shard of jobs; they poll for due jobs and claim each atomically (conditional update of status and lease), then enqueue it.
• Execution: worker pools consume from queues, heartbeat while running; if a lease expires the job is retried on another worker; results recorded; next_run_at computed for recurring jobs.
• Deep dive: jobs must be idempotent (at-least-once); avoiding thundering herds at the top of the hour (jitter); priorities and quotas per tenant; job dependencies as a DAG; clock skew (use the database's clock or a single time source).

Open in System Design →

• Requirements: never oversell, handle huge spikes when sales open, fair, holds that expire if not paid.
• Inventory: seats or ticket counts in a strongly consistent store; reserve with a conditional update (UPDATE ... SET status='held' WHERE id=? AND status='free') or an atomic decrement in Redis backed by the database.
• Holds: a held seat has an expiry (for example 10 minutes); a background job or TTL releases unpaid holds.
• Spike handling: a virtual waiting room (queue with tokens) admits users at the rate the backend can handle; static pages on the CDN; rate limit per user and bot detection.
• Payment: idempotent payment call; on success confirm the booking; on failure release the hold (a saga).
• Trade-offs: strong consistency on inventory vs throughput (shard inventory by event or section, pre-split counts into buckets); fairness vs simplicity.

Open in System Design →

• Requirements: deliver signed OS updates safely to a heterogeneous fleet, never brick devices, control rollout, minimise bandwidth and user disruption, observe outcomes.
• Build side: full and delta payloads per source build fingerprint; signed payloads and metadata; stored in a payload store behind a CDN.
• Policy server: devices check in with fingerprint, model, carrier and region (with jitter); the server returns the eligible update according to rollout rules.
• Rollout: staged percentages (1, 10, 50, 100) per cohort, automatic halt when install failures, boot failures or crash rates exceed baseline, and a kill switch via a signed manifest.
• Device: resumable download preferring Wi-Fi and charging; signature and hash verification; install to the inactive A/B slot in the background; reboot into the new slot; if boot does not complete successfully, automatically fall back to the old slot; anti-rollback protection.
• Telemetry: report each stage's outcome to a pipeline that powers rollout dashboards and health gates.
• Trade-offs: delta size vs number of source builds to support; speed of rollout vs blast radius; storage cost of A/B vs virtual A/B snapshots.

Open in System Design →

• Device: an SDK logs events into a bounded ring buffer, aggregates locally (counts, histograms) instead of shipping raw events, samples high-volume events, scrubs personal data, and honours consent.
• Upload: batched, compressed uploads on Wi-Fi or charging or piggybacked on other traffic; exponential backoff; daily data cap.
• Ingest: regional HTTPS collectors authenticate devices, validate schema versions, and write to a partitioned stream.
• Processing: stream jobs for near-real-time dashboards and alerts; batch jobs into a warehouse partitioned by date, build, model, carrier and region.
• Analysis: compare a new build's metrics against a baseline cohort with confidence intervals to separate real regressions from noise; feed rollout health gates.
• Trade-offs: data freshness vs battery and bandwidth; detail vs privacy; sampling rate vs statistical power.

Open in System Design →

• Requirements: update scores in real time, show the global top 100, show a player's rank and nearby players, millions of players.
• Core structure: Redis sorted set (skip list plus hash): ZADD, ZREVRANGE for top N, ZREVRANK for rank, all O(log n).
• Durability: scores persisted in a database; Redis rebuilt from it if lost.
• Scale: one sorted set handles tens of millions of members; beyond that, shard by score range (rank = rank within shard + counts of higher shards) or compute approximate ranks with score histograms for players outside the top.
• Extras: per-region and per-period leaderboards (daily keys with expiry); friend leaderboards computed on demand from the friend list.

Open in System Design →

• Requirements: ingest millions of samples per second from services, query recent data fast for dashboards and alerts, retain history cheaply.
• Collection: agents scrape or receive metrics, pre-aggregate, and forward to ingesters; labels define series, and cardinality must be controlled.
• Storage: time-series database with per-series compressed chunks (delta-of-delta timestamps, XOR-compressed values), sharded by series hash, replicated.
• Retention: raw data for days, downsampled rollups (1 minute, 1 hour) for months, in object storage.
• Alerting: a rule engine evaluates queries periodically, deduplicates and routes alerts with silencing and escalation.
• Deep dive: high-cardinality labels (user IDs) explode series counts; the monitoring system must be more reliable than what it monitors, with a separate failure domain.

Open in System Design →

• Requirements: multiple users edit simultaneously with low latency, all converge to the same document, offline edits merge later, history and permissions.
• Concurrency control: operational transformation (a central server transforms concurrent operations against each other) or CRDTs (operations designed to commute, allowing peer-to-peer and offline merging).
• Architecture: clients apply edits locally immediately (optimistic), send operations over WebSocket to a document session server that owns the document (routed by document ID), which orders, transforms and broadcasts them.
• Storage: an operation log plus periodic snapshots for fast loading and version history.
• Extras: presence and cursors as ephemeral state; permission checks per operation; session server failover by replaying the log.

Open in System Design →

• Requirements: count clicks per ad per minute for billing and dashboards; billions of events per day; accurate (money is involved); results within minutes; handle late and duplicate events.
• Ingest: click events with unique IDs to a partitioned log (partition by ad ID).
• Processing: a stream processor (Flink-style) with event-time tumbling windows, watermarks for late data, and exactly-once state via checkpoints; dedupe by click ID.
• Output: aggregated counts to an OLAP store for queries; raw events archived to object storage.
• Correctness: a daily batch job recomputes counts from raw events and reconciles with the streaming results (lambda-style check); fraud filtering before billing.
• Trade-offs: latency vs completeness (how long to wait for late events); hot ads (split partitions with key salting).

Open in System Design →

1. Find the expensive queries (slow query log, query plans) and fix them: missing indexes, N+1 queries, unbounded scans.
2. Add caching for hot, read-mostly data (cache-aside with TTLs) and a CDN for cacheable responses.
3. Add read replicas and route read-only queries to them, handling replication lag for read-your-writes flows.
4. Move analytics and reporting queries to a warehouse fed by change data capture.
5. Scale up the instance as a short-term relief while doing the above.
6. If writes are also the bottleneck, split by function (separate databases per domain) and eventually shard by a well-chosen key.

Open in System Design →

First mitigate: if the timing correlates with the deploy, roll back or disable the feature flag; restore service before root-causing. Then compare the new and old versions: traces for the slow requests (which span grew), metrics for CPU, garbage collection, thread and connection pool saturation, and dependency latency. Common culprits: a new synchronous call on the hot path, a query without an index, a cache key change causing misses, a reduced pool size, or logging at high volume. Add a canary stage with automatic latency comparison so the next regression is caught at 1 percent of traffic.

Open in System Design →

This is a hot-key problem. Serve reads of the celebrity's profile and posts from caches replicated across many nodes (and a local in-process cache with a short TTL). For timelines, stop fanning out their posts on write; merge them at read time. For writes such as likes and counters, split the counter into many sub-counters (key salting) and sum them asynchronously. If one tenant is consistently hot, move it to a dedicated shard via a directory-based mapping.

Open in System Design →

A cold cache means every request misses and hits the database at once (a cache avalanche), far beyond its capacity. Prevention: replicas and persistence so the cache survives node restarts; rolling restarts one shard at a time; warming the cache from a snapshot or with the hottest keys before taking traffic; request coalescing so only one request per key goes to the database; circuit breakers and load shedding in front of the database; and admission control that ramps traffic up gradually.

Open in System Design →

Look for the retry path: a client or gateway retrying after a timeout, a queue redelivering a message, or a double-click in the UI. Confirm in logs that two provider charges share the same order but different requests. Fix: require an idempotency key per payment attempt, store it with a unique constraint before calling the provider, pass the same key to the provider (most support it), and return the stored result for duplicates. Make consumers dedupe by message ID. Then refund the affected customers and add reconciliation that alerts on duplicate charges.

Open in System Design →

Check whether producers increased their rate (a spike or a bug), whether consumers slowed down (a slow downstream database, expensive processing, garbage collection), and whether some partitions lag more than others (a hot partition key, or a consumer stuck on a poison message and retrying). Remedies: scale consumers up to the partition count (and add partitions for future scale), batch downstream writes, move poison messages to a dead-letter topic, fix skewed keys, and apply backpressure or load shedding upstream. Alert on lag growth, not just absolute lag.

Open in System Design →

1. Introduce a data-access layer that knows the shard key and routing.
2. Set up the new shards and start dual writes (or stream changes via change data capture) from the old database to the new cluster.
3. Backfill historical data in batches, then verify with checksums and sampled comparisons.
4. Shadow-read from the new cluster and compare results with the old.
5. Gradually switch reads, then writes, per tenant or percentage behind feature flags.
6. Keep the old database in sync for a rollback window, then decommission.

The same expand, migrate, contract approach applies to schema changes.

Open in System Design →

It depends on the multi-region design chosen in advance. Active-passive: health checks fail, DNS or global load balancing shifts traffic to the standby region, and a replica there is promoted; RPO equals the replication lag, RTO the failover time. Active-active: traffic is already served from several regions, so the remaining ones absorb load (they must have headroom), with data replicated asynchronously and conflicts resolved. Either way, stateless tiers must be pre-deployed, capacity reserved, and failover rehearsed regularly (game days); otherwise the plan fails when needed.

Open in System Design →

Classic replication lag or cache staleness: the write went to the leader, but the next read hit a lagging follower or a cache entry that was not invalidated. Fixes: read-your-writes by routing the user's reads to the leader for a short period after writing (or waiting for the follower to reach the write's log position); invalidate the cache after the database commit; pin a user's session to one replica for monotonic reads; and, on the client, optimistically show the edited value.

Open in System Design →

Requests to the slow dependency held threads or connections for a long time, exhausting a shared pool so every endpoint queued (a cascading failure), and retries multiplied the load. Prevent with tight timeouts, a circuit breaker around the dependency, bulkheads (a separate, bounded pool per dependency), a retry budget with backoff and jitter, load shedding when queues grow, and fallbacks such as cached or default responses.

Open in System Design →

The rollout health gate should already have paused the rollout automatically; if not, halt it immediately via the policy server or kill switch so no new devices receive the build. Affected devices with A/B updates should fall back to the previous slot automatically; confirm from telemetry that they do. Slice the failures by model, carrier, region and source build to find the common factor (for example a delta payload for one source build, or one hardware variant). Fix, rebuild, and restart the rollout from 1 percent for the affected cohort. Afterwards, tighten the gate thresholds and add the failing configuration to pre-release testing.

Open in System Design →

Compare battery and wakeup metrics between devices with and without the SDK version. Typical causes: frequent timers or alarms waking the CPU, uploads on every event instead of batching, holding wakelocks without timeouts, keeping the radio active with small periodic transfers, or retrying aggressively when offline. Fix by batching events in a bounded buffer, scheduling uploads with the OS job scheduler on Wi-Fi and charging, coalescing with other network activity, using backoff with a cap, and adding a remote kill switch or config to reduce sampling in the field.

Open in System Design →

• Layering: platform defaults, then carrier-specific values keyed by the SIM's network code, then server-pushed overrides, then a runtime cache that apps read through one API.
• Delivery: signed, versioned config bundles fetched from a CDN on check-in or pushed via a notification that triggers a fetch.
• Invalidation: recompute on SIM swap, roaming changes and OS updates; versions let devices detect staleness.
• Safety: staged rollout by percentage and cohort, validation on device with fallback to the last known good config, a kill switch, and telemetry on apply success and key quality metrics.

Open in System Design →

Register death notifications on each HAL service; when the HAL dies, immediately fail every in-flight request with a "radio not available" error so callers do not hang. Put timeouts on every request (and on any wakelock held while waiting) so a lost response cannot deadlock callers or pin the CPU awake. On HAL restart, re-initialise idempotently with bounded exponential backoff, and never crash the long-lived framework process on a transient error. Add backpressure by capping outstanding requests and coalescing duplicate polls. Emit metrics on HAL restarts and request timeouts so fleet dashboards catch regressions.

Open in System Design →

Measure first: break down cost by component (compute, storage, database, CDN egress, cross-zone traffic, logging). Then: right-size over-provisioned instances and use autoscaling; use spot or preemptible capacity for batch work; raise cache hit ratios to shrink database size; move cold data to cheaper storage tiers and set retention policies; compress payloads and cut egress with better CDN caching; reduce log and metric volume (sampling, lower cardinality); and remove idle environments. Name the reliability or latency trade-off for each change.

Open in System Design →

Walk the request path and ask where each component breaks. Stateless services: add instances behind the load balancer and confirm autoscaling limits. Cache: more nodes, check hot keys. Database: reads go to more replicas and cache; writes may now exceed one primary, so shard by the key identified earlier. Queues: add partitions and consumers. Fan-out-heavy paths (feeds, notifications) need hybrid strategies. Check limits you do not own: third-party API quotas, connection limits, cross-region bandwidth. Finally, revisit estimates and cost, since 10x traffic is usually 10x bill unless efficiency improves.

Open in System Design →

A Board Support Package is the software that makes a generic OS run on a specific SoC and board. It typically contains the bootloader (or its board port), the device tree describing the board's hardware, the kernel configuration (defconfig), and drivers for every peripheral (clocks, pinctrl, regulators, storage, display, sensors, modem interfaces). On Android it also extends into userspace: vendor HALs, init .rc files, ueventd.rc permissions and SELinux vendor policy. BSP work means board bring-up, driver and DT development, and debugging boot, power and peripheral issues.

Open in Linux Kernel & BSP →

The kernel is the privileged core that manages hardware and shares it safely among programs. Its main jobs are: process and thread management and CPU scheduling; memory management (virtual memory, allocation, protection); device management through drivers; filesystems and I/O; networking; inter-process communication; and security (permissions, isolation). Programs request these services through system calls rather than touching hardware directly.

Open in Linux Kernel & BSP →

Linux is monolithic: scheduler, memory management, filesystems, networking and drivers run together in kernel space and call each other directly, which is fast. The downside is weaker isolation: a bug in any driver can crash the whole system. A microkernel (QNX, seL4, Fuchsia's Zircon) keeps only scheduling, IPC and basic memory in the kernel and runs drivers and filesystems as user processes, giving better fault isolation at the cost of IPC overhead. Linux adds flexibility with loadable modules, so it is often called a modular monolithic kernel.

Open in Linux Kernel & BSP →

They are separate privilege levels and address-space regions. User space (EL0 on ARM64, ring 3 on x86) runs applications with no direct hardware access and a private virtual address space per process. Kernel space (EL1 / ring 0) runs the kernel with full access to memory and devices. A bug in user space kills only that process; a bug in kernel space can oops or panic the whole system. User code enters the kernel only through defined entry points: system calls, exceptions (like page faults) and interrupts.

Open in Linux Kernel & BSP →

A system call is the controlled way user code asks the kernel for a service (open a file, allocate memory, create a process). The libc wrapper places the syscall number and arguments in registers and executes a trap instruction (svc #0 on ARM64, syscall on x86-64). The CPU switches to kernel mode and jumps to the exception vector; the kernel saves registers, looks up the handler in the syscall table, runs it (copying data with copy_from_user/copy_to_user) and returns the result with eret. Errors come back as negative values that libc turns into -1 plus errno.

Open in Linux Kernel & BSP →

A device tree is a data structure (.dts source compiled to a .dtb blob) that describes a board's hardware: buses, register addresses, interrupts, clocks, regulators, GPIOs. It is kept separate from kernel code so one kernel image can support many boards. At boot the kernel creates devices from DT nodes and matches each node's compatible string to a driver's of_match_table, then calls probe(). Before DT, ARM used per-board C files, which did not scale. Overlays (.dtbo) patch the base tree for board variants.

Open in Linux Kernel & BSP →

A kernel module (.ko) is code that can be linked into the running kernel on demand, typically a driver. It has an init function (module_init) and exit function (module_exit). Load with insmod file.ko (no dependency handling) or modprobe name (resolves dependencies via modules.dep); unload with rmmod; list with lsmod; inspect with modinfo. In Kconfig, =y builds code into the kernel image and =m builds it as a module. With GKI, all vendor drivers must be modules.

Open in Linux Kernel & BSP →

• Character drivers: byte-stream devices accessed via /dev nodes and file_operations (open, read, write, ioctl, mmap), e.g. serial ports, input, sensors, Binder.
• Block drivers: random-access storage in fixed-size blocks, going through the page cache and block layer, e.g. UFS, eMMC, NVMe.
• Network drivers: packet interfaces (net_device) used via sockets, no /dev node, e.g. Wi-Fi, Ethernet.

Orthogonally, drivers sit on buses: platform (on-SoC, from DT), I2C, SPI, USB, PCI.

Open in Linux Kernel & BSP →

A platform driver handles a device on the "platform bus", a virtual bus for hardware that cannot be discovered by enumeration, typically IP blocks inside the SoC (UART, I2C controller, GPIO controller, watchdog). The devices are created from device-tree nodes (or ACPI, or board code). The driver registers a struct platform_driver with probe, remove and an of_match_table; when a matching node exists, probe() gets the platform_device, maps its registers (devm_platform_ioremap_resource), gets its IRQ (platform_get_irq) and clocks, and initializes the hardware.

Open in Linux Kernel & BSP →

An interrupt is a hardware signal that makes the CPU pause its current work and run a handler, so the device notifies the CPU when something happens. Polling means the CPU repeatedly checks a status register. Interrupts save CPU time and power when events are infrequent; polling can be better at very high event rates (it avoids per-event interrupt overhead) or when latency must be tightly controlled. Linux's network NAPI mixes both: interrupt to start, then poll while traffic is heavy.

Open in Linux Kernel & BSP →

The top half is the hard IRQ handler: it runs immediately in interrupt context, cannot sleep, and should do the minimum (acknowledge the hardware, read urgent data, schedule the rest). The bottom half does the remaining work later in a less time-critical context: a softirq (high-frequency, e.g. networking), a tasklet (simple, built on softirq), a workqueue (kernel thread, can sleep), or a threaded IRQ (dedicated kernel thread, can sleep). The split keeps interrupts-off time short so other interrupts are not delayed or lost.

Open in Linux Kernel & BSP →

A process is a running program with its own address space and resources (open files, credentials, signal handlers). A thread is an execution flow within a process that shares its address space and resources but has its own stack, registers and scheduling state. Threads communicate cheaply through shared memory but need locking; processes are isolated and need IPC, but a crash in one does not corrupt another. In Linux both are tasks (task_struct) created with clone(); the flags decide what is shared.

Open in Linux Kernel & BSP →

• R running or runnable (on a run queue).
• S interruptible sleep: waiting for an event, can be woken by signals.
• D uninterruptible sleep: usually waiting for I/O; ignores signals.
• T stopped (SIGSTOP) or traced by a debugger.
• Z zombie: exited but not yet reaped by its parent.

You can see them in ps output or /proc/<pid>/status.

Open in Linux Kernel & BSP →

A zombie has exited, but its parent has not yet called wait()/waitpid(), so the kernel keeps its PID and exit status in the process table. It uses no memory beyond that entry, but many zombies can exhaust PIDs; fix the parent to reap children (or handle SIGCHLD). An orphan is a running process whose parent died; it is re-parented to init (PID 1) or a designated subreaper, which reaps it when it exits.

Open in Linux Kernel & BSP →

Virtual memory gives each process its own address space that the MMU translates to physical memory using page tables. Benefits: isolation (processes cannot access each other's memory), protection (read-only code, no-execute data), simpler programming (each process sees a large contiguous space), lazy allocation (pages allocated on first use), sharing (libraries and COW pages mapped into many processes), memory-mapped files, and the ability to swap or compress rarely used pages.

Open in Linux Kernel & BSP →

Paging divides virtual and physical memory into fixed-size pages (typically 4 KB). A page table maps each virtual page to a physical frame and stores permission bits (read, write, execute, user/kernel) and status bits (valid, accessed, dirty). To save space, page tables are multi-level (4 levels on ARM64 with 48-bit addresses); the MMU walks them on a TLB miss. The kernel builds and updates the tables; the hardware reads them.

Open in Linux Kernel & BSP →

The Translation Lookaside Buffer is a small, fast cache in the MMU holding recent virtual-to-physical translations. A TLB hit translates an address in about a cycle; a miss requires a page-table walk of several memory accesses. When mappings change, the kernel must invalidate affected entries (TLB shootdown on SMP, using broadcast TLBI on ARM). ASIDs tag entries per address space so switching processes does not require flushing the whole TLB. Huge pages increase TLB coverage.

Open in Linux Kernel & BSP →

A page fault is an exception raised when the MMU cannot complete an access: the page is not present or the access violates permissions. The kernel handler checks whether the address belongs to a valid VMA. If yes, it resolves the fault: allocate a zero page, load a file page, swap in, or copy a COW page (minor fault if no I/O, major if I/O). If not, the process gets SIGSEGV, or the kernel oopses if it happened in kernel code. Faults are normal and frequent; excessive major faults indicate memory pressure or thrashing.

Open in Linux Kernel & BSP →

A context switch is the kernel stopping one task and running another on the same CPU. It saves the current task's registers, stack pointer and program counter, picks the next task, switches the address space if the new task is in a different process (page table base plus ASID), and restores the new task's registers. It is triggered by blocking, preemption (time slice expiry or higher-priority wakeup) or yielding. Direct cost is a few microseconds; the indirect cost of cold caches and TLB often dominates.

Open in Linux Kernel & BSP →

A mutex is a lock for mutual exclusion: only one holder at a time, it has an owner, only the owner can unlock it, and waiters sleep. A semaphore is a counter: down() decrements it and sleeps if it would go negative, up() increments it and wakes a waiter. A counting semaphore with N allows N concurrent holders (e.g. a pool of N buffers); a binary semaphore resembles a mutex but has no owner, so any task can signal it. In the Linux kernel, prefer mutex for exclusion and completions for signaling.

Open in Linux Kernel & BSP →

A spinlock is a lock where a waiting CPU busy-loops until the lock becomes free, instead of sleeping. It is used for very short critical sections and in contexts that cannot sleep (interrupt handlers, softirqs). In Linux, taking a spinlock disables preemption; the holder must not sleep. Variants like spin_lock_irqsave also disable local interrupts to prevent deadlock with an IRQ handler that takes the same lock. Spinning is only efficient if the hold time is shorter than the cost of sleeping and waking.

Open in Linux Kernel & BSP →

A deadlock is when a set of tasks each wait for a resource held by another task in the set, so none can proceed. All four Coffman conditions must hold: mutual exclusion (resources are held exclusively), hold and wait (tasks hold resources while waiting for more), no preemption (resources cannot be forcibly taken), and circular wait (a cycle in the wait-for graph). Breaking any one prevents deadlock; the most practical is a global lock ordering to prevent circular wait.

Open in Linux Kernel & BSP →

• Pipes and named pipes (FIFOs): one-way byte streams.
• Signals: asynchronous notifications carrying only a number.
• Shared memory (POSIX shm_open/mmap, System V, memfd): fastest, needs separate synchronization.
• Message queues (POSIX, System V): discrete messages.
• Sockets: Unix domain (local, can pass fds) and TCP/UDP (network).
• Netlink: kernel-userspace messaging.
• eventfd, futex, semaphores for notification and synchronization.

Android adds Binder as its main IPC.

Open in Linux Kernel & BSP →

Both are virtual filesystems generated by the kernel on the fly, with no storage behind them. /proc (procfs) exposes process information (/proc/<pid>/status, maps, fd) and kernel state (/proc/meminfo, /proc/interrupts, /proc/cmdline). /sys (sysfs) exposes the device model: devices, drivers, buses and classes, with one value per attribute file, many writable (e.g. cpufreq governor, power controls). debugfs (/sys/kernel/debug) is for developer-only debug data.

Open in Linux Kernel & BSP →

dmesg prints the kernel ring buffer: messages written with printk by the kernel and drivers, such as boot progress, driver probe results, errors, warnings, oopses and SELinux denials. Each line has a timestamp since boot and a log level. dmesg -w follows new messages. On Android, logcat -b kernel shows the same messages; logs from the previous boot after a crash are in pstore (/sys/fs/pstore/console-ramoops-0).

Open in Linux Kernel & BSP →

kmalloc returns memory that is physically contiguous and in the kernel's linear map. It is fast, suitable for DMA, but large requests can fail when memory is fragmented. vmalloc returns memory that is only virtually contiguous, built from scattered physical pages mapped into a separate kernel virtual range. It suits large buffers the CPU alone uses but is slower (page-table setup, more TLB pressure) and not directly DMA-able. kvmalloc tries kmalloc and falls back to vmalloc. In atomic context use kmalloc(..., GFP_ATOMIC); vmalloc may sleep.

Open in Linux Kernel & BSP →

Copy-on-write lets two processes share the same physical pages until one of them writes. After fork(), the kernel copies the page tables and marks shared pages read-only in both. A write triggers a page fault; the kernel then copies just that page, gives the writer a private writable copy, and resumes. This makes fork() fast and memory-efficient, especially when followed by exec(). Android's Zygote relies on it: apps forked from Zygote share its preloaded classes and resources.

Open in Linux Kernel & BSP →

fork() creates a new child process that is a copy of the parent (same code, same memory contents via COW, duplicated file descriptors). It returns twice: 0 in the child, the child's PID in the parent. exec() replaces the current process's program image with a new executable, keeping the PID and (unless close-on-exec) open file descriptors. The classic pattern for launching a program is fork then exec in the child, with the parent calling wait().

Open in Linux Kernel & BSP →

They are the three providers almost every SoC driver depends on. clk gates and rates clocks (clk_prepare_enable, clk_set_rate); prepare may sleep, enable is the cheap gate. pinctrl muxes SoC balls to a function (UART, I2C, GPIO) and sets pull and drive; GPIO via gpiod is only for lines used as GPIO. regulator turns PMIC rails on and sets voltage. In probe() the usual order is pinctrl default, enable supplies, enable clocks, deassert reset, then talk to the hardware. First dumps: clk_summary, regulator_summary, /sys/kernel/debug/pinctrl/.

Open in Linux Kernel & BSP →

It changed twice. Early Android used a userspace FUSE daemon (sdcard) so emulated storage could enforce per-app permissions on top of /data/media. Android 6 replaced that with sdcardfs, an in-kernel wrapfs, for much lower overhead. Android 11 removed sdcardfs and went back to FUSE, this time driven by MediaProvider, to implement scoped storage and richer permission checks. On a current device, /sdcard is FUSE; saying "we use sdcardfs" is an Android 6–10 answer.

Open in Linux Kernel & BSP →

Treble (Android 8) is an architecture that separates the Android framework (system partition) from the vendor implementation (vendor partition) through stable, versioned HAL interfaces (HIDL originally, stable AIDL now) over Binder. VINTF manifests and compatibility matrices check that system and vendor are compatible. The benefit is that Google or the OEM can update the framework without the SoC vendor rebuilding its code, which speeds up OS upgrades and is verified by running a Generic System Image with VTS/CTS.

Open in Linux Kernel & BSP →

GKI (Generic Kernel Image) is Google's approach to fragmentation in Android kernels. Google builds and signs one core kernel per Android release and kernel version from the Android Common Kernel. SoC and board support is delivered as vendor modules loaded from vendor_boot and vendor_dlkm, and they may use only the stable Kernel Module Interface (KMI). This lets the core kernel receive security fixes without vendors rebasing a fork. GKI 1.0 appeared optionally in Android 11; GKI 2.0 is required for new devices launching with Android 12+ on kernel 5.10+. The OEM still tests and ships the combined image; "independent update" means the core binary and vendor modules can move on different cadences as long as the KMI holds.

Open in Linux Kernel & BSP →

Use a spinlock for very short critical sections and whenever the code cannot sleep: interrupt handlers, softirqs, or data shared with them. The holder must not sleep, and preemption is disabled while it is held. Use a mutex for longer sections in process context where waiting by sleeping is cheaper than spinning; the holder may sleep (e.g. do I2C transfers or GFP_KERNEL allocations). Calling a sleeping function while holding a spinlock causes "BUG: scheduling while atomic". If data is shared with a hard IRQ handler, process context must use spin_lock_irqsave so the IRQ cannot interrupt the holder on the same CPU and deadlock.

Open in Linux Kernel & BSP →

• Mutex: sleepable, single owner, process context only; the default for protecting driver state touched only from syscalls, workqueues or threaded IRQs.
• Spinlock: non-sleeping, usable in IRQ context (with _irqsave), short sections; use in the top half and for any data shared with it.
• Semaphore: counting, no owner, up() can be called from IRQ; rarely used now for exclusion; completions or wait queues are preferred for signaling, and mutexes for exclusion.

Rule: in a hard IRQ handler use a spinlock; for long-held resources use a mutex in process context.

Open in Linux Kernel & BSP →

Softirqs are statically defined and reserved for core high-rate subsystems (network RX/TX, block completion, timers, RCU); drivers do not add new ones. Tasklets are dynamically created on top of softirqs; they cannot sleep and the same tasklet never runs concurrently on two CPUs; they are deprecated in favor of alternatives. Workqueues run in kernel worker threads in process context, so they can sleep, take mutexes and do I2C/SPI transfers. Threaded IRQs give the interrupt its own kernel thread, also able to sleep, and are the modern default for device drivers, especially for devices on slow buses. Choose by whether you need to sleep and how latency-sensitive the work is.

Open in Linux Kernel & BSP →

1. The bootloader passes the DTB; the kernel unflattens it into device_node structures.
2. The OF core creates platform_devices for nodes under simple buses with status = "okay"; bus controllers (I2C, SPI) create child devices when they probe.
3. Drivers register with their bus (platform_driver_register), providing an of_match_table.
4. When a device and driver are both present, the bus's match() compares compatible strings; on a match the core calls probe().
5. Probe returns 0 (bound), -EPROBE_DEFER (retried later when dependencies appear), or an error.
6. For modules, udev/ueventd uses the MODALIAS from MODULE_DEVICE_TABLE to autoload the right module.

Open in Linux Kernel & BSP →

Drivers often depend on other providers: clocks, regulators, GPIO or pinctrl controllers, PHYs. If a provider has not probed yet, the consumer's probe() gets -EPROBE_DEFER from calls like devm_clk_get() and returns it. The driver core puts the device on a deferred list and retries whenever another driver binds successfully. This avoids fragile hand-tuned init ordering. /sys/kernel/debug/devices_deferred lists devices still waiting, which is a quick way to find a missing dependency. fw_devlink now orders probing automatically from DT phandles, reducing deferral churn.

Open in Linux Kernel & BSP →

devm_* functions (e.g. devm_kzalloc, devm_ioremap_resource, devm_request_irq, devm_clk_get) register the resource with the device, and the driver core releases them automatically, in reverse order, when probe fails or the device is unbound. This eliminates most error-path cleanup code and leaks. The caution: release order matters, for example a devm-requested IRQ is freed after remove() runs, so the handler must not use resources remove() already freed.

Open in Linux Kernel & BSP →

Implement a struct file_operations with the callbacks you need (open, read, write, unlocked_ioctl, poll, mmap, release), then register it. The simplest way is a miscdevice with a dynamic minor, which creates /dev/name; the fuller way is alloc_chrdev_region + cdev_init/cdev_add + class_create/device_create. In read/write, move data with copy_to_user/copy_from_user, return bytes transferred or a negative errno, protect shared state with a mutex, and support blocking I/O with a wait queue plus poll.

static ssize_t foo_read(struct file *f, char __user *buf, size_t n, loff_t *off)
{
    struct foo *foo = f->private_data;
    size_t len;
    if (wait_event_interruptible(foo->wq, foo->count))
        return -ERESTARTSYS;
    mutex_lock(&foo->lock);
    len = min(n, foo->count);
    if (copy_to_user(buf, foo->data, len)) { mutex_unlock(&foo->lock); return -EFAULT; }
    foo->count -= len;
    mutex_unlock(&foo->lock);
    return len;
}

Open in Linux Kernel & BSP →

A wait queue sleeps until a condition becomes true: wait_event_interruptible(wq, foo->ready), with the IRQ or worker setting the flag and calling wake_up. Use it for recurring "data available" or "state changed" waits. Prefer the interruptible or killable variant so signals (including SIGKILL) can break the sleep; a plain wait_event is how tasks get stuck in D state. A completion is a one-shot "this finished" event (wait_for_completion / complete), ideal for "wait until this DMA or probe helper is done". Do not use a binary semaphore for that pattern; completions are the modern API.

Open in Linux Kernel & BSP →

The Contiguous Memory Allocator reserves a region of physical memory that can be lent to movable pages when idle and reclaimed for large physically contiguous DMA buffers when a device needs them (camera, display, codecs). Use it when a device cannot use the IOMMU / scatter-gather and needs big contiguous buffers that kmalloc cannot satisfy under fragmentation. Cost: that memory is less flexible for the rest of the system. On modern SoCs with an SMMU, prefer IOMMU + scatter-gather and keep CMA small.

Open in Linux Kernel & BSP →

ioctl(fd, cmd, arg) is a system call for device-specific operations that do not fit read/write, such as configuring a mode, starting a DMA, or querying capabilities. Commands are encoded with _IO, _IOR, _IOW, _IOWR macros that include a magic number, command number, direction and argument size. The driver implements unlocked_ioctl (and compat_ioctl for 32-bit apps on a 64-bit kernel), validates the command, and copies arguments with copy_from_user. For simple attributes, sysfs files are often cleaner; for streaming data, read/write or mmap.

Open in Linux Kernel & BSP →

Protect it with a spinlock. In the hard IRQ handler use spin_lock() (interrupts for that line are already masked on this CPU). In process context use spin_lock_irqsave(&lock, flags) / spin_unlock_irqrestore(), which disables local interrupts while holding the lock. Otherwise, if the IRQ fires on the same CPU while process context holds the lock, the handler spins forever. For single counters or flags, atomics may suffice; for producer/consumer data, a lock-free kfifo with one reader and one writer works without locking. Keep the locked region short and never sleep inside it.

Open in Linux Kernel & BSP →

An edge-triggered interrupt fires on a signal transition (rising or falling). It is raised once per event; if another edge happens while the first is being handled and the controller does not latch it, it can be missed. A level-triggered interrupt stays asserted as long as the line is at the active level; the handler must clear the source in the device, otherwise the interrupt fires again immediately (an interrupt storm). Level triggering is safer for shared lines. The DT interrupts property specifies the type, and getting it wrong is a common bring-up bug.

Open in Linux Kernel & BSP →

They are allocation flags. GFP_KERNEL is the normal flag: the allocator may sleep to reclaim memory, write back pages, or compact. Use it in process context when no spinlock is held and preemption is enabled. GFP_ATOMIC never sleeps and may use emergency reserves; use it in interrupt handlers, softirqs, timers, or while holding a spinlock. Atomic allocations fail more easily, so always handle NULL and avoid large atomic allocations. GFP_NOIO/GFP_NOFS prevent recursion into I/O or filesystem code during reclaim.

Open in Linux Kernel & BSP →

The buddy allocator manages physical memory as blocks of 2^order contiguous pages per zone. To allocate, it splits a larger free block into two "buddies" until it has the requested size; on free, it merges a block with its free buddy back into a larger block. That keeps external fragmentation manageable; /proc/buddyinfo shows free blocks per order. The slab allocator (SLUB in modern kernels) sits on top: it takes pages from the buddy allocator and carves them into caches of same-sized objects (e.g. task_struct, dentry), giving fast allocation, reduced internal fragmentation and per-CPU caching. kmalloc uses generic size-class slab caches. /proc/slabinfo and slabtop show usage.

Open in Linux Kernel & BSP →

With DMA, the driver gives the device a bus address and length; the device reads or writes RAM directly and interrupts when done, freeing the CPU. Problems arise because the CPU caches data: if the bus is not cache-coherent, the device may read stale memory (CPU's writes still in cache) or the CPU may read stale cache lines after the device wrote RAM. The DMA API handles this: streaming mappings (dma_map_single) clean caches before a device read and invalidate before a CPU read; coherent allocations (dma_alloc_coherent) use memory that is uncached or hardware-coherent. The API also translates to device addresses through the IOMMU if present.

Open in Linux Kernel & BSP →

An IOMMU is an MMU for devices: it translates device-visible addresses (IOVAs) to physical addresses using per-device page tables. Benefits: devices can use large buffers that are virtually contiguous but physically scattered (no need for big contiguous allocations); devices can be isolated so a buggy or malicious device cannot DMA into arbitrary memory; and 32-bit devices can reach memory above 4 GB. On ARM it is called SMMU. Faults show up as "smmu context fault" messages, which usually indicate a driver using an unmapped or freed buffer.

Open in Linux Kernel & BSP →

1. The MMU fails to translate an address (not present) or detects a permission violation and raises an exception with the faulting address (FAR_EL1 on ARM64) and cause.
2. The kernel's fault handler finds the VMA containing the address.
3. If there is no VMA, or the access violates VMA permissions, it sends SIGSEGV to the user process (or oopses if in kernel mode without an exception fixup).
4. If valid, handle_mm_fault() resolves it: allocate a zeroed anonymous page, map a page-cache page (reading from storage if needed = major fault), swap in from ZRAM, or break COW by copying.
5. It updates the PTE, and the faulting instruction is restarted.

Open in Linux Kernel & BSP →

A minor fault is resolved without I/O: the page is already in memory (page cache, shared with another process) or can be created (zero page, COW copy); the kernel only updates page tables. A major fault requires reading data from storage or swap, so the task sleeps for I/O and it is much slower (microseconds vs milliseconds). /proc/<pid>/stat fields and /usr/bin/time -v show counts. Many major faults during app start or scrolling indicate memory pressure or cold file cache.

Open in Linux Kernel & BSP →

CFS tracks a virtual runtime (vruntime) per task: actual CPU time scaled inversely by the task's weight (derived from its nice value, with each nice level about a 10% share change). Runnable tasks sit in a per-CPU red-black tree ordered by vruntime; the scheduler picks the leftmost (smallest vruntime), i.e. the task that has received the least fair share. A running task is preempted when another task's vruntime is smaller by more than a granularity. Waking tasks get a vruntime close to the minimum so they run soon, which favors interactive tasks. Periodic load balancing moves tasks between CPUs. Since Linux 6.6, EEVDF replaces CFS's pick logic, adding virtual deadlines for better latency control.

Open in Linux Kernel & BSP →

• SCHED_DEADLINE: EDF with runtime/period/deadline reservations; highest priority.
• SCHED_FIFO: real-time priority 1-99; runs until it blocks or a higher-priority RT task arrives.
• SCHED_RR: like FIFO with a time slice among tasks of equal priority.
• SCHED_NORMAL/SCHED_OTHER: fair scheduling with nice -20 to +19.
• SCHED_BATCH: CPU-bound, less frequent preemption.
• SCHED_IDLE: runs only when nothing else wants the CPU.

Set with sched_setscheduler() or chrt; RT tasks are throttled to 95% of CPU by default so they cannot hang the system completely.

Open in Linux Kernel & BSP →

Both save and restore registers and kernel stack. A process switch additionally changes the address space: it loads a new page table base (TTBR0 on ARM64, CR3 on x86), which may invalidate TLB entries (ASIDs/PCIDs mitigate a full flush) and leaves caches holding the old process's data. Threads of the same process share the address space, so page tables stay the same and the TLB and caches remain warm. Typical costs are a few microseconds for a process switch and noticeably less for a thread switch, plus indirect cache-miss costs afterwards.

Open in Linux Kernel & BSP →

fork() creates a child with a copy-on-write copy of the parent's address space and duplicated file descriptors. vfork() creates a child that borrows the parent's address space without copying page tables; the parent is suspended until the child calls exec() or _exit(). It is faster but dangerous if the child modifies memory; COW made it mostly unnecessary (though posix_spawn may use it internally). clone() is the underlying primitive: flags select what is shared (CLONE_VM, CLONE_FILES, CLONE_FS, CLONE_SIGHAND, CLONE_THREAD, namespaces). fork and pthread_create are both implemented with it.

Open in Linux Kernel & BSP →

Priority inversion happens when a high-priority task waits for a lock held by a low-priority task, and a medium-priority task preempts the low-priority one, so the high-priority task is effectively blocked by a less important task for an unbounded time. The fix is priority inheritance: the lock holder temporarily inherits the highest waiter's priority until it releases the lock. Linux implements it in rt_mutex and PI futexes (PTHREAD_PRIO_INHERIT); PREEMPT_RT converts most kernel locks to rt_mutexes. Priority ceiling is an alternative. The Mars Pathfinder resets in 1997 are the classic example; Android's Binder also propagates caller priority to the server thread.

Open in Linux Kernel & BSP →

Prevention: define and document a global lock order and always acquire in that order; keep lock scopes small; avoid calling unknown code (callbacks) with locks held; use trylock with back-off when ordering is impossible; avoid holding locks across sleeping calls that may need the same lock (e.g. flush_work). Detection: lockdep in debug kernels records lock-dependency chains and reports potential cycles even if the deadlock never actually happened; hung-task and soft-lockup detectors flag real hangs; echo w > /proc/sysrq-trigger dumps blocked tasks; in a ramdump, map lock owners to waiting tasks. In userspace, /data/anr traces and Java lock holders show similar cycles.

Open in Linux Kernel & BSP →

Read-Copy-Update is a synchronization mechanism for read-mostly data. Readers enter a read-side critical section (rcu_read_lock()) that costs almost nothing and never blocks; they access data through rcu_dereference(). A writer makes a new copy of the element, updates it, publishes it atomically with rcu_assign_pointer(), then waits for a grace period (synchronize_rcu(), or call_rcu/kfree_rcu asynchronously) until all readers that might see the old version have finished, and only then frees it. It scales extremely well for readers on many CPUs. Use it for lookup tables, lists and configuration that change rarely; writers still need their own lock among themselves.

Open in Linux Kernel & BSP →

Both compilers and CPUs reorder memory operations for performance. On a single CPU this is invisible, but on SMP another CPU may observe writes in a different order. ARM is weakly ordered, so this happens in practice. Memory barriers constrain ordering: smp_wmb() orders stores, smp_rmb() orders loads, smp_mb() orders both; acquire/release operations (smp_load_acquire, smp_store_release) give one-way ordering suited to flag-and-data patterns. For device registers, readl/writel include the needed I/O barriers and dma_wmb() orders descriptor writes before ringing a doorbell. Locks and atomic RMW operations with return values already imply barriers.

Open in Linux Kernel & BSP →

volatile only tells the compiler not to cache the variable in a register and not to optimize away or reorder accesses to that variable relative to other volatile accesses. It does not make operations atomic (x++ is still read-modify-write), does not prevent the CPU from reordering memory operations, and does not order non-volatile accesses around it. Use C11 atomics, kernel atomics, locks, or READ_ONCE/WRITE_ONCE plus barriers. volatile is appropriate for memory-mapped I/O registers, variables modified by signal handlers (volatile sig_atomic_t) and values changed by a debugger.

Open in Linux Kernel & BSP →

Binder is Android's IPC and RPC mechanism, implemented as a kernel driver (/dev/binder). A client's proxy marshals arguments into a Parcel and calls ioctl(BINDER_WRITE_READ); the driver copies the data once into the server's mmap'd buffer and wakes a thread from the server's Binder thread pool, which runs the method and replies. Compared to pipes or sockets, it provides: caller UID/PID filled in by the kernel (unforgeable identity for permission checks), object references with reference counting across processes, death notifications, priority inheritance, fd passing, synchronous and one-way calls, and a name service (servicemanager). It is the backbone of app-framework and framework-HAL communication.

Open in Linux Kernel & BSP →

A pipe needs two copies: from the writer's buffer into a kernel buffer, then from the kernel buffer into the reader's buffer. Binder needs one copy: the driver copies from the sender's user memory directly into a buffer that is mmap'd into the receiver, so the receiver reads it without a second copy. Shared memory needs zero copies after setup, since both processes map the same physical pages, but it requires separate synchronization (futex, semaphore, eventfd). For large data such as graphics buffers, Android passes a DMA-BUF or memfd file descriptor over Binder to get zero-copy with Binder's security.

Open in Linux Kernel & BSP →

The page cache holds file data in RAM in page-sized units, indexed per file. Reads hit the cache if possible; misses read from storage (with read-ahead for sequential access). write() copies data into the page cache and marks pages dirty, then returns; background writeback threads flush dirty pages to storage later based on age and dirty ratio thresholds. fsync()/fdatasync() force a file's dirty data (and metadata) to stable storage and issue a device cache flush. O_DIRECT bypasses the cache. Clean cache pages are the first thing reclaimed under memory pressure.

Open in Linux Kernel & BSP →

An inode is the filesystem structure that holds a file's metadata (type, permissions, owner, size, timestamps, link count) and where its data blocks are, but not its name. Names live in directory entries that map a name to an inode number. A hard link is another directory entry pointing to the same inode; the file exists until the link count drops to zero and no process has it open; hard links cannot span filesystems or (normally) point to directories. A symbolic link is a separate small file containing a path; it can cross filesystems and point to directories, but becomes dangling if the target is removed.

Open in Linux Kernel & BSP →

/data gets many small random writes. f2fs (Flash-Friendly File System) is log-structured: it turns random writes into sequential ones, which suits NAND flash and its flash translation layer, improves write performance and reduces wear; it also supports file-based encryption and compression. /system and /vendor are read-only and verified by dm-verity. erofs (Enhanced Read-Only File System) compresses data in fixed-size output blocks, saving significant space while keeping fast random reads, and its immutable layout fits verified boot. ext4 remains in use on many devices and was the historical default for both.

Open in Linux Kernel & BSP →

read() copies data from the page cache into a user buffer on each call; it is simple and efficient for sequential streaming. mmap() maps the file's page-cache pages directly into the process's address space; data is loaded lazily by page faults and accessed with normal pointers, avoiding the extra copy and suiting random access to large files and sharing between processes. Costs of mmap: page-fault overhead, TLB pressure, SIGBUS if the file shrinks, and harder error handling. Drivers also implement mmap to expose device memory or DMA buffers to user space.

Open in Linux Kernel & BSP →

When suspend is requested (on Android, autosleep once no wakelocks are held), the kernel freezes user tasks and freezable kernel threads, calls every driver's suspend callbacks (suspend, suspend_late, suspend_noirq) in child-before-parent order, takes secondary CPUs offline, and the last CPU enters a deep power state through PSCI firmware while RAM stays in self-refresh. A configured wake interrupt (RTC, button, modem, sensor hub) triggers resume in reverse order. A wakeup source is a kernel object (a kernel wakelock) that, while active, prevents suspend; drivers use pm_stay_awake/pm_relax or __pm_wakeup_event. If any driver's suspend callback fails, the whole suspend is aborted.

Open in Linux Kernel & BSP →

Runtime power management lets individual devices power down while the system is running. Drivers call pm_runtime_get_sync() before using the hardware and pm_runtime_put() / pm_runtime_put_autosuspend() when done; the core keeps a usage count and, when it reaches zero (after an optional autosuspend delay), calls the driver's runtime_suspend to gate clocks and regulators, and runtime_resume when needed again. Power domains (genpd) can turn off a whole domain when all its devices are idle. Runtime PM is key to low active and idle current on mobile devices.

Open in Linux Kernel & BSP →

When a driver registers a device, the kernel sends a uevent over netlink containing the device's name, major/minor numbers and attributes. On Android, ueventd (part of init) receives it, creates the /dev node, and sets owner, group and mode according to ueventd.rc files (e.g. /dev/foo 0660 system input) and the SELinux label from file_contexts. It also handles firmware loading requests. If a HAL cannot open a node, check the node's permissions, SELinux label, and avc: denied messages.

Open in Linux Kernel & BSP →

An oops is the kernel's report of a serious error (such as a bad memory access) in kernel code: it prints registers and a stack trace, kills the offending task, and the kernel may keep running, although it may be in an inconsistent state (for example a lock held forever) and is marked tainted. A panic is a fatal error after which the kernel stops; it halts or reboots after panic_timeout. The kernel default is panic_on_oops=0 (continue). Android typically sets /proc/sys/kernel/panic_on_oops to 1 from init (and ACK builds often also enable CONFIG_PANIC_ON_OOPS), so an oops becomes a panic and a ramdump or reboot rather than a half-dead system.

Open in Linux Kernel & BSP →

Process context (syscalls, kernel threads, workqueue items, threaded IRQ handlers) may sleep, as long as no spinlock is held and preemption or interrupts are not disabled. Hard IRQ, softirq and tasklet context, and any code holding a spinlock, must not sleep. Interrupt context borrows whatever task was running; it has no task of its own that the scheduler could put to sleep and wake later, and sleeping would leave the interrupted task and possibly held locks stuck. With a spinlock held, preemption is disabled, so sleeping could deadlock if the next task needs the same lock. might_sleep() annotations with CONFIG_DEBUG_ATOMIC_SLEEP catch violations at runtime.

Open in Linux Kernel & BSP →

Modern Linux uses queued spinlocks (qspinlock) on arm64; older kernels used ticket spinlocks. A ticket lock has "next" and "owner" counters: a CPU atomically takes a ticket and spins until owner equals its ticket, which gives FIFO fairness. Qspinlock keeps a 32-bit word for the fast uncontended path and, under contention, queues waiters in per-CPU MCS nodes, so each spins on its own cache line instead of hammering the shared lock line. Atomics use ARMv8.1 LSE instructions (like CAS, LDADD) or LDXR/STXR exclusive loops, and waiters use WFE to reduce power while spinning; acquire/release semantics provide the memory ordering. spin_lock also disables preemption.

Open in Linux Kernel & BSP →

PREEMPT_RT (fully merged in Linux 6.12) makes almost all kernel code preemptible to achieve bounded latency. Key changes: most spinlock_t locks become sleeping rt_mutexes with priority inheritance (raw_spinlock_t remains true spinning for the few places that need it); interrupt handlers are forced into threads so they can be prioritized and preempted; softirqs run in thread context; and long non-preemptible sections are broken up. The trade-off is slightly lower throughput for much better worst-case latency. Drivers must use raw_spinlock_t only where truly needed (e.g. inside irqchip code).

Open in Linux Kernel & BSP →

EAS adds an energy model (power and capacity per performance state per CPU cluster, from the DT or firmware) to the scheduler. When a task wakes, EAS estimates its utilization with PELT (per-entity load tracking) and evaluates candidate CPUs: which placement meets the task's capacity needs with the lowest total energy, considering the frequency each cluster would have to run at. Small tasks stay on little cores; heavy tasks go to big cores. It works with the schedutil governor, which sets frequency from utilization. It is active only when the system is not overutilized; otherwise normal load balancing takes over. Android steers it with uclamp (min/max utilization clamps per cgroup, e.g. boosting top-app) and cpusets.

Open in Linux Kernel & BSP →

Both aim for fair CPU sharing weighted by nice. CFS picks the task with the smallest vruntime and relied on heuristics (wakeup preemption granularity, sleeper credits) to give interactive tasks low latency. EEVDF (Earliest Eligible Virtual Deadline First, default since 6.6) computes a "lag" per task (how much service it is owed); only tasks with non-negative lag are eligible, and among them it picks the one with the earliest virtual deadline, where the deadline is eligible time plus requested slice divided by weight. A task requesting a shorter slice gets an earlier deadline and so runs sooner, without getting more total CPU. This replaces many CFS heuristics with a cleaner model and gives latency-sensitive tasks a proper knob.

Open in Linux Kernel & BSP →

Each memory zone has min/low/high watermarks. When free pages drop below low, kswapd wakes and reclaims in the background until high is reached: dropping clean page-cache pages, writing back dirty pages, and swapping anonymous pages (to ZRAM on Android). The LRU lists (active/inactive, or multi-gen LRU in newer kernels) choose victims. If an allocation cannot be satisfied, the allocating task does direct reclaim and compaction, causing latency stalls. If that fails, the OOM killer selects a process by oom_score (memory usage adjusted by oom_score_adj) and kills it. Android avoids reaching that point: LMKD monitors PSI memory stall levels and kills cached/background apps by oom_score_adj set by ActivityManager, keeping the foreground responsive.

Open in Linux Kernel & BSP →

Pressure Stall Information (/proc/pressure/cpu, memory, io) reports the percentage of time over 10, 60 and 300 second windows that some tasks ("some") or all non-idle tasks ("full") were stalled waiting for that resource. Unlike free-memory numbers, it measures the actual impact of pressure. Userspace can register triggers such as "notify me when memory some-stall exceeds 70 ms in a 1 s window". Android's LMKD registers PSI triggers; when they fire, it picks a victim with the highest oom_score_adj above a threshold that depends on the pressure level and kills it, replacing the old in-kernel lowmemorykiller that used free-memory thresholds.

Open in Linux Kernel & BSP →

ARM64 has two translation table base registers: TTBR0_EL1 for the lower range (user space, per process, tagged with an ASID) and TTBR1_EL1 for the upper range (kernel, shared). With 4 KB pages and 48-bit virtual addresses, translation uses four levels (9 bits each plus a 12-bit offset); block mappings at level 1 or 2 give 1 GB or 2 MB pages. The kernel has a linear map of all physical RAM, a vmalloc area, a fixmap, module space and so on. On a context switch only TTBR0 and the ASID change. Security features include PAN (kernel cannot access user memory without explicit uaccess), PXN/UXN (execute-never), KASLR, and on some systems KPTI (unmapping the kernel while in user space).

Open in Linux Kernel & BSP →

copy_from_user/copy_to_user (and get_user/put_user) first check that the pointer range lies in user space (access_ok), then perform the copy with privileged access temporarily enabled (on ARM64, clearing PAN with uaccess_enable). If the user page is not present, a normal page fault occurs and may sleep to bring it in, which is why these functions can sleep. If the address is invalid, the fault handler finds the faulting instruction in the exception table and jumps to a fixup that makes the function return the number of bytes not copied, so the driver returns -EFAULT instead of oopsing. Checks against kernel objects (hardened usercopy) catch overflows.

Open in Linux Kernel & BSP →

Implement file_operations.mmap(struct file *f, struct vm_area_struct *vma). For device registers or physically contiguous memory, validate the requested size and offset, set appropriate page protection (e.g. pgprot_noncached or pgprot_writecombine for MMIO), and call remap_pfn_range() or io_remap_pfn_range(). For DMA memory from dma_alloc_coherent, use dma_mmap_coherent(). For scattered pages, use vm_insert_page or a vm_operations_struct with a fault handler that supplies pages on demand. Never allow mapping beyond the buffer, and keep the buffer alive until the VMA is closed (reference counting in vm_ops->open/close). For sharing between devices, exporting a DMA-BUF is usually better.

Open in Linux Kernel & BSP →

The Kernel Module Interface is the set of exported kernel symbols plus the layouts of the data types they use that GKI vendor modules may rely on. For each GKI branch (e.g. android14-6.1), Google freezes the KMI after a stabilization period: symbols listed in the vendor symbol lists are guaranteed, and ABI tooling compares every build against the frozen ABI representation to reject incompatible changes. Vendors compile modules against the GKI source and headers; at load time, symbol CRCs (CONFIG_MODVERSIONS) must match. When vendors need a new symbol or a hook into core code, they upstream it to the Android Common Kernel (adding symbols or vendor hooks based on tracepoints) rather than patching the core kernel locally.

Open in Linux Kernel & BSP →

With GKI, vendors cannot modify core kernel code, but they sometimes need to change behavior in scheduler, memory or other core paths (e.g. custom task placement or thermal decisions). Vendor hooks are special tracepoints (DECLARE_HOOK / DECLARE_RESTRICTED_HOOK) added to the Android Common Kernel at agreed points; vendor modules register handlers that run there. Restricted hooks can sleep and attach once, normal hooks behave like regular tracepoints. They provide a controlled extension point that keeps the core kernel generic while preserving a stable KMI. They must be proposed and accepted into ACK.

Open in Linux Kernel & BSP →

A peripheral asserts a line into the GIC distributor (SPI for shared peripherals, PPI for per-CPU sources like the arch timer, SGI for inter-processor interrupts, LPI for MSI-style message interrupts via the ITS). The distributor routes it to a target CPU's redistributor/CPU interface based on priority and affinity. The CPU takes an IRQ exception, reads the interrupt ID from the acknowledge register, and Linux's generic IRQ layer maps the hardware ID to a Linux IRQ number through an irq domain, then calls the flow handler (e.g. handle_fasteoi_irq) and the driver's handler, and finally signals end of interrupt. irq domains also chain controllers: a GPIO controller or PMIC can be an irqchip whose domain translates its pins into Linux IRQs cascaded under a GIC interrupt, which is what interrupt-parent in the DT expresses.

Open in Linux Kernel & BSP →

Symptoms include rare corrupted state, list corruption (list_add corruption warnings), refcount underflows and crashes that move around. Tools: KCSAN detects data races dynamically by watching concurrent unsynchronized accesses; KASAN catches the resulting use-after-free; lockdep verifies locking assumptions (use lockdep_assert_held() in functions that require a lock). Review which contexts touch the data: process, softirq, hard IRQ, other CPUs. Fix by protecting all accesses with the same lock of the right type, converting counters to atomic_t/refcount_t, using RCU for read-mostly structures, or READ_ONCE/WRITE_ONCE for intentionally lockless flags with appropriate barriers.

Open in Linux Kernel & BSP →

A futex is a 32-bit integer in user memory plus a kernel wait queue keyed by its address. Acquiring an uncontended pthread_mutex is a single atomic compare-and-swap in user space, with no syscall. Only when the lock is contended does the thread mark it as contended and call futex(FUTEX_WAIT), which sleeps if the value is still as expected (avoiding lost-wakeup races). The unlocking thread, seeing the contended state, calls futex(FUTEX_WAKE). PI futexes (FUTEX_LOCK_PI) store the owner TID so the kernel can apply priority inheritance. Java monitors and ART locks are also built on futexes.

Open in Linux Kernel & BSP →

Latency comes from regions where interrupts are disabled (local_irq_save, spin_lock_irqsave), long hard IRQ handlers of other devices, higher-priority interrupts, softirq processing, preemption-disabled sections delaying threaded handlers, CPU idle exit latency from deep C-states, and frequency ramp-up. Measure with the ftrace irqsoff and preemptoff tracers (report the maximum disabled section and its call site), cyclictest for scheduling latency, IRQ and sched events in Perfetto, or a GPIO toggle measured on an oscilloscope for end-to-end latency. Fix by shortening disabled regions, moving work into threaded handlers, adjusting IRQ affinity, raising the priority of the IRQ thread, or limiting deep idle states when latency matters.

Open in Linux Kernel & BSP →

With CONFIG_FUNCTION_TRACER, the compiler inserts a call (or NOPs with patchable entries) at the start of every function; at runtime these are NOPs and ftrace patches selected sites to jump to the tracer, so overhead is near zero when disabled. The function_graph tracer also hooks returns to record durations. Tracepoints are static markers placed in code (TRACE_EVENT) that call registered probes via a static key when enabled, recording structured events into per-CPU lockless ring buffers exposed in tracefs. Kprobes dynamically insert a breakpoint at almost any instruction and run a handler; fprobes/fentry and eBPF programs can attach to these points too. Perfetto reads the same ftrace ring buffers plus userspace atrace markers.

Open in Linux Kernel & BSP →

Load the dump with the matching vmlinux (and module symbols) into crash or Trace32. First, read the kernel log buffer (log) for the last messages, watchdog reports or lockup warnings. Check each CPU's backtrace (bt -a): is one spinning on a lock, stuck with IRQs disabled, or in a tight loop? List tasks (ps) and focus on those in D state (foreach UN bt) to see what they wait on. For a mutex, inspect its owner field (struct mutex) and follow the owner's stack to find a lock cycle. Examine relevant driver structures with struct, memory usage with kmem -i, and runqueues with runq. The goal is to identify the stuck resource and which task or CPU holds it.

Open in Linux Kernel & BSP →

They were three implementations of the kernel's object allocator. SLAB was the original, with complex per-CPU and per-node queues; SLOB was a minimal allocator for tiny systems; SLUB simplified the design with per-CPU slabs and little metadata and became the default. SLOB and SLAB have since been removed, so SLUB is the only one in current kernels. With slub_debug (options like F sanity checks, Z red zones, P poisoning, U user tracking), SLUB detects buffer overruns into red zones, use-after-free via poison patterns, and double frees, and records allocation/free call sites; KASAN and KFENCE provide more precise detection.

Open in Linux Kernel & BSP →

ION was an Android-specific allocator (/dev/ion) that allocated buffers from heaps (system, carveout, CMA) and exported them as DMA-BUF file descriptors. Its single ioctl interface with heap IDs and flags was hard to keep ABI-stable and vendors added many incompatible changes. Mainline Linux adopted DMA-BUF heaps instead: each heap is its own character device under /dev/dma_heap/ (e.g. system, linux,cma, vendor heaps as modules), with a simple allocation ioctl returning a DMA-BUF fd. ION was removed from mainline in Linux 5.11 and deprecated in Android's GKI kernels; Android 12+ devices use DMA-BUF heaps through libdmabufheap. Cache maintenance and sharing semantics come from the standard DMA-BUF framework.

Open in Linux Kernel & BSP →

The vendor provides a device manifest listing HALs it implements (name, interface, version, instance) plus kernel requirements; the framework provides a compatibility matrix listing HALs and versions it needs and kernel config requirements. The build system checks that the vendor manifest satisfies the framework matrix and vice versa (the device matrix vs framework manifest), and VintfObject checks again at OTA time and boot. Failures happen when the framework requires a newer HAL version than the vendor provides, a required HAL is missing, a HAL is declared but not registered at runtime, or kernel configs/versions do not meet the matrix. Symptoms include OTA rejection, VTS failures, or a service failing to find a HAL.

Open in Linux Kernel & BSP →

The logo means the bootloader worked, so the problem is in the kernel or userspace. First get the kernel log: UART console, or /sys/fs/pstore/console-ramoops-0 after a reboot. Look for a panic, a driver hanging in probe, or a root mount failure. If the kernel reached init, check logcat -b all (via adb if available) for a critical service crash-looping (init: Service ... restarting), avc: denied blocking a daemon, a failed mount of /data or /vendor, or system_server/zygote crashing. Then bisect: try the other A/B slot or a known-good build, and diff DT, defconfig, modules and rc changes. For the full stage-by-stage method, see the Android boot page.

Open in Linux Kernel & BSP →

1. Read the header: faulting virtual address (a small value like 0x10 means NULL plus a struct field offset), the CPU, the task (Comm), taint flags.
2. Look at pc (e.g. foo_probe+0x48/0x1a0 [foo]) and lr, and the call trace.
3. Symbolize: addr2line -e vmlinux for built-in code, or gdb foo.ko then list *(foo_probe+0x48) for modules; scripts/decode_stacktrace.sh for the whole trace.
4. Identify which pointer was NULL and why: missing error check (e.g. of_get_property returned NULL), a dependency not yet probed, drvdata not set before the IRQ fired, or an early IRQ calling into uninitialized state.
5. Fix and harden: check returns, request the IRQ only after initialization, use -EPROBE_DEFER. Reproduce with KASAN if the pointer might be a freed object.

Open in Linux Kernel & BSP →

1. Probe: dmesg | grep for the driver; check /sys/bus/i2c/devices/ for the device and whether it is bound to a driver. No device means the DT node is missing, disabled, or under the wrong bus; device but no driver means a compatible mismatch or module not loaded; deferred means a missing dependency (/sys/kernel/debug/devices_deferred).
2. Bus: i2cdetect -y <bus> to see if the address ACKs. No ACK means wrong address, bus, wiring, or the chip is unpowered or held in reset.
3. Power: regulator_summary to confirm the vdd-supply is enabled at the right voltage; check the reset GPIO polarity.
4. Pins and clocks: pinctrl state for SDA/SCL, controller clock in clk_summary; a logic analyzer or scope on the bus if still unclear.
5. Interrupt: correct GPIO, trigger type and pull; watch /proc/interrupts.

Open in Linux Kernel & BSP →

1. Is it suspending? dmesg for "PM: suspend entry/exit"; /sys/kernel/debug/suspend_stats for success and failure counts.
2. Suspend aborted? suspend_stats shows last_failed_dev and the failing step; a driver returning an error from suspend() blocks every attempt.
3. Who holds it awake? /sys/kernel/debug/wakeup_sources: sort by active_since/total_time; dumpsys power for app partial wakelocks.
4. Who wakes it? /proc/interrupts deltas across a sleep period, "wakeup IRQ" messages, Battery Historian or a Perfetto trace. Suspects: chatty sensor or modem IRQ, a GPIO configured as wake source with a floating line, an RTC alarm set too often, an app wakelock.
5. Also check residency of CPU idle states and whether peripherals are runtime-suspended; a rail left on can drain even while suspended.

Open in Linux Kernel & BSP →

Code called something that can sleep while in atomic context: holding a spinlock, with preemption or interrupts disabled, or in a hard IRQ, softirq or tasklet. Typical offenders are mutex_lock, kmalloc(GFP_KERNEL), msleep, copy_to_user, wait_event, or a blocking I2C/SPI transfer inside an IRQ handler. The splat's stack trace shows the sleeping call and the preempt count. Fix by moving the work to a threaded IRQ or workqueue, using GFP_ATOMIC, releasing the spinlock before the sleeping call, or using a mutex when all users are in process context. Prevent recurrence by running debug builds with CONFIG_DEBUG_ATOMIC_SLEEP and lockdep.

Open in Linux Kernel & BSP →

1. Start from the recorded reboot reason: ro.boot.bootreason, bootloader logs, PMIC reset reason registers, pstore console and panic logs. Never guess.
2. Kernel panic: decode the oops from pstore.
3. Watchdog bite: a CPU stopped petting the watchdog, typically stuck in a spinlock, an IRQs-disabled loop, or a deadlock. Collect a ramdump and inspect per-CPU stacks and lock owners.
4. Thermal: check thermal zone logs and trip points in /sys/class/thermal; a critical trip triggers shutdown.
5. Power: voltage droop or PMIC over-current under load (brown-out); correlate with CPU/GPU frequency peaks and battery state.
6. Reproduce with a stress test and bisect recent kernel, DT or firmware changes.

Open in Linux Kernel & BSP →

First decide kernel vs userspace using /proc/meminfo over time. Growing SUnreclaim (slab), KernelStack, VmallocUsed or DMA-BUF totals point to the kernel; growing app PSS (from dumpsys meminfo) points to userspace. For kernel leaks, use slabtop or /proc/slabinfo to find the growing cache, enable kmemleak to list unreferenced allocations with their stacks, and inspect /sys/kernel/debug/dma_buf/bufinfo for leaked buffers (often an fd not closed in userspace). For userspace leaks, use heapprofd in Perfetto, malloc debug, or HWASan, and showmap for mapping growth. Confirm the fix by trending MemAvailable in a long run.

Open in Linux Kernel & BSP →

Determine whether any stage prints. If even the bootloader is silent, check the bootloader's UART configuration, pinmux, clock, baud rate, and whether DDR and clocks come up at all (JTAG can tell you where the CPU is). If the bootloader prints but the kernel does not, add earlycon to the kernel command line with the correct UART type and base address, confirm stdout-path in /chosen and the UART DT node (address, clocks, pinctrl), and check that the serial driver is built in, not a module. If the kernel crashes before the console, early printk or reading the log buffer from memory via JTAG helps. As a last resort, toggle a GPIO or LED at known points.

Open in Linux Kernel & BSP →

1. Measure each stage: bootloader timestamps, kernel dmesg timestamps up to "Freeing unused kernel memory" and init start, init service start times, sys.boot_completed, and a Perfetto boot trace or bootchart.
2. Kernel: boot with initcall_debug to find slow initcalls; move non-critical drivers to modules loaded later; enable asynchronous probe; remove long msleeps and firmware load waits in probe; trim unused config.
3. Userspace: parallelize services, start non-critical HALs lazily, avoid serial wait_for_prop chains, reduce system_server and Zygote preload work, and check dexopt state.
4. Storage: tune read-ahead, use erofs compression, check that dm-verity and fs-verity are not bottlenecks.
5. Always attack the biggest measured contributor and re-measure after each change.

Open in Linux Kernel & BSP →

It is almost certainly in uninterruptible sleep (state D), waiting inside the kernel for something like I/O completion, a mutex, or a driver event that uses wait_event (not the interruptible or killable variant). Signals, including SIGKILL, are handled only when the task returns toward user space, so it cannot die until the wait ends. Check cat /proc/<pid>/stack and /proc/<pid>/wchan to see where it waits, or echo w > /proc/sysrq-trigger to dump all blocked tasks. The root cause is typically a hung storage device, a network filesystem, or a driver that never completes a request. Drivers should use wait_event_killable or timeouts where possible. A zombie (state Z) also cannot be killed, but that is fixed by its parent reaping it.

Open in Linux Kernel & BSP →

Capture a Perfetto trace with sched, freq, idle, irq and binder events along with app atrace markers. For the UI thread and RenderThread in the janky frames, check the thread state: Runnable but not Running means CPU contention or poor placement (look at which CPU and what else ran there); Running on a little core at low frequency means utilization estimation, uclamp or cpuset issues; Uninterruptible sleep means I/O or lock waits; Sleeping on Binder means the slowness is in another process. Also look for long IRQ or softirq bursts on the same CPU and thermal throttling (frequency caps). Fixes include correcting cgroup/cpuset assignment, uclamp boosts for top-app, IRQ affinity changes, or removing priority inversions.

Open in Linux Kernel & BSP →

The module was built against a kernel whose exported symbol CRCs (from CONFIG_MODVERSIONS) differ from the running kernel, meaning a function signature or a data structure used by that symbol changed, or the module was built against different headers or config. With GKI, this indicates either the module was not rebuilt against the new GKI release, or a KMI break (which the ABI tooling should prevent on a frozen branch). Check modinfo for vermagic, compare with uname -r, rebuild the module against the exact GKI kernel source and config, and ensure the symbols it uses are in the vendor symbol list. Never force-load with mismatched CRCs; that risks memory corruption.

Open in Linux Kernel & BSP →

1. Does the node exist? ls -lZ /dev/foo. If not, check that the driver registered the char/misc device and that ueventd processed it.
2. Permissions: owner, group, mode from ueventd.rc; is the HAL's user or group allowed?
3. SELinux: the node's label (from file_contexts) and avc: denied messages in dmesg or logcat for the HAL's domain; add correct type and allow rules in vendor policy (not permissive mode).
4. The driver's open() may itself return an error (e.g. runtime PM resume failing, device busy); check dmesg and the errno the HAL logs.

Open in Linux Kernel & BSP →

Suspend may have powered off the device's regulator or power domain, losing its register state, while the driver's resume callback does not restore it. Check whether the driver implements .suspend/.resume (and runtime PM callbacks) and re-initializes the hardware, restores pinctrl state (sleep vs default), re-enables clocks and regulators in the right order, and re-arms interrupts. Use dmesg with pm_debug_messages or initcall_debug to see resume callback order and errors, and compare register dumps before and after. Dependency ordering matters: the device must resume after its parent bus and supplies (device links help). Also verify the firmware or co-processor state if the peripheral runs its own firmware.

Open in Linux Kernel & BSP →

• Missing cache maintenance: the CPU reads stale cache lines because the buffer was not invalidated (dma_unmap or dma_sync_single_for_cpu not called) on a non-coherent system.
• The buffer shares cache lines with other data (not cache-line aligned), so CPU writes to neighbors write back stale data over what the device wrote.
• Using a stack or vmalloc buffer for DMA.
• The CPU touches the buffer while the device still owns it (ownership rule violated), or the buffer is freed or reused too early.
• Missing dma_wmb() before ringing a doorbell, so the device reads a descriptor before it is fully written.
• IOMMU mapping errors (check for SMMU faults).

Debug with CONFIG_DMA_API_DEBUG, which warns on API misuse, and add checksums at producer and consumer.

Open in Linux Kernel & BSP →

Enable the soft-lockup and hard-lockup detectors and the hung-task detector with panic options so the kernel dumps stacks and panics before the hardware watchdog fires, producing a ramdump. If the hang is a hard lockup (a CPU with interrupts disabled), the arm64 pseudo-NMI (or the SoC's watchdog pre-timeout / FIQ) can capture that CPU's stack. With the ramdump, check all CPU stacks: a CPU spinning in queued_spin_lock_slowpath points to a lock whose owner you then find; a loop in a driver with IRQs off points to a missing timeout while polling hardware. sysrq (l for all CPUs' backtraces) helps if the console is still responsive. Lockdep in a debug build can reveal the ordering problem before it reproduces.

Open in Linux Kernel & BSP →

1. Start from the vendor reference board: its bootloader config, DT and defconfig are ground truth; diff the schematics to list what changed.
2. Power and clocks first: PMIC rails, reset sequencing, crystals. Get a UART console working.
3. DDR configuration and training in the bootloader; then boot the kernel with a new board DT derived from the reference.
4. Storage (UFS/eMMC) so the root filesystem mounts; then USB for adb/fastboot.
5. Peripherals one at a time: display, touch, audio, sensors, cameras, modem, Wi-Fi/BT. For each: DT node, pinctrl, supplies, probe, validation via sysfs or test tools.
6. Power and thermal: suspend/resume, idle and active current, thermal zones; then performance tuning.
7. Keep a working ramdump path early so any crash can be analyzed.

Open in Linux Kernel & BSP →

Treat the vendor reference board, its BSP and defconfig as the source of truth, and read the SoC technical reference manual for the blocks you will touch (clocks, interrupt controller, the peripherals in question). Set up tooling first: a UART console, ramdump collection, symbol files and a fast build-flash loop, so every experiment produces evidence. Learn the code top-down from the DT: follow a node's compatible to its driver, then to the subsystem it registers with. Use dmesg, deferred-probe lists, ftrace function_graph on the driver, and diffs against the reference DT to understand behavior. Approach every bug the same way: which stage, what evidence, smallest reproducer, fix, regression test.

Open in Linux Kernel & BSP →

Trace with Perfetto or ftrace (sched_switch, sched_wakeup, irq, softirq events) around a glitch. Measure wakeup latency: time from wakeup to running. If it is Runnable for long, find what occupies the CPU: a higher-priority RT task, a long IRQ or softirq burst, or an IRQs-off or preemption-off region (use the irqsoff/preemptoff tracers). If it is blocked, look for a lock held by a lower-priority thread (priority inversion; use PI mutexes), a page fault on memory that was not locked (mlock, prefaulting), or a Binder call. Also check CPU frequency ramping and deep idle exit latency on its core, and whether RT throttling kicked in. Fixes include pinning to a quiet core, raising IRQ thread priorities appropriately, avoiding allocations and locks in the audio callback, and PI locking.

Open in Linux Kernel & BSP →

cat /sys/kernel/debug/devices_deferred lists the device and often the reason string (missing clock, regulator, GPIO, PHY). Cross-check the DT: is the provider's node status = "okay", is the phandle correct, is the provider itself a module that never loaded? fw_devlink should order probes from DT phandles; if it does not, look for a missing clocks, *-supply or resets property. Also check that the provider driver is in the vendor module list (GKI) and that it did not fail probe earlier. Fix the provider or the DT; do not paper over it with a long msleep in the consumer.

Open in Linux Kernel & BSP →

1. Check the upstream or vendor kernel for a driver matching the part and its DT binding documentation (Documentation/devicetree/bindings/).
2. Enable the driver in the vendor defconfig as a module (GKI) and add it to the vendor module list so it is packaged in vendor_dlkm or vendor_boot.
3. Add the DT node under the correct I2C/SPI bus with compatible, reg, interrupt, supplies, reset GPIO and pinctrl as the binding specifies.
4. Verify probe in dmesg, the IIO or input device in sysfs, and raw readings.
5. Add ueventd.rc permissions and SELinux labels for any device nodes, then wire up the sensor HAL.
6. Validate suspend/resume, interrupt wake behavior and power consumption.

Open in Linux Kernel & BSP →

1. The PMIC sequences the power rails, starts the 19.2 MHz clock and releases the CPU reset.
2. The PBL (in SoC ROM) sets up SRAM and basic clocks, finds XBL on UFS/eMMC, verifies its signature against the key hash in eFuses, and jumps to it.
3. XBL trains DDR, configures PMIC and clocks, loads and verifies TrustZone/QTEE, the hypervisor and ABL.
4. ABL picks the boot mode and the A/B slot, runs AVB on vbmeta/boot/dtbo, and loads the kernel, ramdisks and device tree into DDR.
5. The kernel sets up the MMU, scheduler and interrupts, parses the device tree, probes drivers, unpacks the ramdisk and runs /init as PID 1.
6. init mounts the partitions with dm-verity, loads SELinux policy, starts the property service, ueventd, servicemanager, HALs and daemons, then Zygote.
7. Zygote starts ART, preloads classes and forks system_server.
8. system_server starts about a hundred services, then SystemUI and the Launcher. The boot animation exits, sys.boot_completed=1 is set and LOCKED_BOOT_COMPLETED is sent to Direct Boot apps. BOOT_COMPLETED waits for the user to unlock CE storage on an FBE device with a lock screen.

Open in Android Boot Process →

Each boot stage cryptographically verifies the signature of the next stage before executing it. The anchor (root of trust) is the immutable PBL in ROM together with a hash of the OEM root public key burned into one-time-programmable eFuses (QFPROM), so the start of the chain cannot be forged or changed by software. The chain continues PBL → XBL → TZ/ABL → vbmeta/boot via AVB → system/vendor via dm-verity at runtime.

Open in Android Boot Process →

The loading path is who copies whom into memory and jumps to it: PBL → XBL → ABL → kernel → init → Zygote → system_server. The trust path is who verifies whom: eFuse key hash → XBL → ABL → AVB → dm-verity. They happen together but are different concepts - for example Zygote and system_server are part of loading but do not verify anything; their integrity comes from dm-verity protecting /system. Interviewers like candidates who separate them.

Open in Android Boot Process →

The Power Management IC applies the SoC's voltage rails in the correct order and at the correct levels, starts the reference clock, waits for stability and then de-asserts the CPU reset. It also records the power-on reason (power key, charger insertion, RTC alarm, watchdog or warm reset), which later becomes part of the boot reason and can make the bootloader choose charger mode. Later stages (XBL, kernel regulator drivers) configure the rest of its rails, charging and battery monitoring.

Open in Android Boot Process →

The Primary Boot Loader is the first code the CPU executes after reset. It is stored in the SoC's Boot ROM (mask ROM), written into the silicon at manufacture. It sets up minimal clocks and on-chip SRAM, reads the security fuses, detects the boot device, loads XBL into SRAM, verifies it and jumps to it. If anything fails it halts or enters EDL.

Open in Android Boot Process →

It is physically part of the chip's mask ROM, so it cannot be flashed, erased or patched. That immutability is what makes it trustworthy as the root: no software attack can modify the first verifier. The downside is that a bug in PBL is permanent for that silicon revision, which is why ROM code is kept as small and simple as possible and all complex logic is pushed into signed, updatable later stages.

Open in Android Boot Process →

At reset the DDR is not usable. LPDDR needs PHY impedance calibration, command/address training, Vref tuning, DQS timing alignment and temperature compensation first, which is complex, board-specific code. On-chip SRAM (IMEM) works immediately without calibration, so PBL uses it for its stack, heap, crypto buffers and as the load buffer for XBL. XBL then trains DDR.

Open in Android Boot Process →

The CPU starts on the external 19.2 MHz crystal oscillator (XO) on Qualcomm platforms. PBL configures a few basic PLLs to raise the core frequency into the low hundreds of MHz so loading and hashing XBL is fast enough. The full clock tree with all PLLs and bus clocks is set up later by XBL and the kernel's clock drivers.

Open in Android Boot Process →

QFPROM (Qualcomm Fuse Programmable ROM) is the block of one-time-programmable eFuses in the SoC. It stores the secure-boot enable bit, the hash of the OEM root public key (the root of trust), anti-rollback version counters, debug/JTAG disable bits and boot configuration. Because fuses can only be blown once, these values cannot be reversed by software.

Open in Android Boot Process →

DDR training and initialization - bringing up the main memory. Before XBL only a few hundred KB of on-chip SRAM exist. XBL also configures the PMIC and clocks, brings up full storage drivers, loads and starts the TrustZone secure world (QTEE), the hypervisor and helper firmware such as AOP, and then loads and verifies ABL.

Open in Android Boot Process →

ABL is the Android-aware stage. It selects the boot mode (normal, recovery, fastboot, charger, ramdump), picks the A/B slot, runs Android Verified Boot on vbmeta/boot/init_boot/vendor_boot/dtbo and shows the boot-state warning, passes the boot state to the TEE, builds the kernel command line and bootconfig, loads the kernel, ramdisks and device tree into DDR and jumps to the kernel. It also implements the fastboot protocol.

Open in Android Boot Process →

• fastboot: a bootloader (ABL) mode for flashing physical partitions, switching slots and locking/unlocking over USB.
• fastbootd: fastboot implemented in user space inside recovery (Android 10+), needed to flash logical partitions in super.
• recovery: a minimal Android environment for applying OTAs, sideloading and factory reset.
• EDL: Qualcomm's ROM-level emergency download mode (QDLoader 9008) for reflashing a bricked device with a signed Firehose programmer.

Open in Android Boot Process →

A header (with the header version, sizes, load addresses and command line) plus the kernel image. Before Android 13 it also contained the generic ramdisk. On devices launching with Android 13+ with GKI, boot contains only the kernel; the generic ramdisk with /init is in init_boot, and the vendor ramdisk, DTB and early modules are in vendor_boot. Device-tree overlays are in dtbo.

Open in Android Boot Process →

A device tree is a data structure (.dts compiled to .dtb) that describes the hardware - CPUs, memory, buses, interrupts, clocks, regulators, GPIOs and peripherals - so the kernel does not hard-code board details. One kernel binary can run on many boards, and drivers bind to nodes by their compatible string. DTBO overlays adjust the base tree for board variants and are selected and applied by the bootloader.

Open in Android Boot Process →

PID 1 is /init, the first user-space process and the ancestor of all others. First stage mounts /dev, /proc, /sys, loads early modules, maps super, sets up dm-verity and mounts system/vendor. The selinux_setup phase loads SELinux policy and switches to enforcing. Second stage starts the property service, parses the .rc files, runs triggers and starts and supervises services including ueventd, servicemanager, HALs and Zygote.

Open in Android Boot Process →

Zygote is a warm ART process started by init via app_process. The init service is always named zygote (the 64-bit binary is app_process64; do not call the service zygote64). On mixed-ABI devices a second service zygote_secondary runs the 32-bit binary. It preloads common framework classes, resources and libraries once. New app processes are created by forking Zygote, so they inherit that state instantly and share its memory pages copy-on-write. This makes app start fast (milliseconds instead of seconds) and saves RAM because the framework is loaded once for all apps. Zygote also forks system_server.

Open in Android Boot Process →

Most Android framework services, running as threads in one process: ActivityManagerService, ActivityTaskManagerService, PackageManagerService, WindowManagerService, PowerManagerService, DisplayManagerService, InputManagerService, ConnectivityService, AudioService, NotificationManagerService and many more. They register with servicemanager and clients reach them over Binder. When they are ready, system_server starts SystemUI and the Launcher.

Open in Android Boot Process →

ACTION_BOOT_COMPLETED is the broadcast telling apps the system has fully booted and they may start background work. On file-based-encryption devices, ACTION_LOCKED_BOOT_COMPLETED is sent first to Direct Boot-aware apps while credential storage is still locked; BOOT_COMPLETED follows after the user unlocks. The property sys.boot_completed=1 is the usual script-level marker that the system user has finished booting.

Open in Android Boot Process →

The device has two copies of each updatable partition, slot _a and _b. An OTA installs to the inactive slot in the background while the user keeps using the active one; on reboot the bootloader boots the updated slot. If the new slot boots fully it is marked successful; if it fails repeatedly its retry counter runs out and the bootloader falls back to the old slot. Benefits: minimal downtime and no brick from a bad update; cost: extra storage.

Open in Android Boot Process →

• GREEN: locked, everything verified with the OEM key.
• YELLOW: locked, verified with a user-installed custom root key; a warning shows the key fingerprint.
• ORANGE: bootloader unlocked; verification results are not enforced; a warning is shown.
• RED: locked and verification failed (or dm-verity corruption); the device refuses to boot or requires user action.

Open in Android Boot Process →

Emergency Download mode is a Qualcomm PBL feature. When the PBL cannot load a valid XBL, or when forced by a test point or command, it enumerates over USB as "Qualcomm HS-USB QDLoader 9008" (ID 05c6:9008). A host tool uploads a Firehose programmer using the Sahara protocol, and the programmer then reads and writes flash. On secure devices the PBL verifies the programmer's signature, so EDL cannot be used to run arbitrary code.

Open in Android Boot Process →