You passed the filter.
Now win the room.

Insight: build a max-heap in O(n), then repeatedly swap the root (max) to the end and sift down over the shrinking prefix.

Unlike quicksort, heap sort has no O(n²) worst case and needs no extra memory — but it isn't adaptive and isn't stable.

Insight: at each index, either extend the running subarray or restart at the current element.

To also return indices, track a start that resets whenever cur restarts.

Insight: repeatedly remove nodes with in-degree 0. If you can't remove all n, the graph has a cycle.

Insight: greedily settle the closest unsettled node using a min-heap; skip stale heap entries. No negative edges allowed.

Insight: an in-order traversal of a BST visits values in sorted order — stop at the k-th.

If the tree is modified often, augment each node with its subtree size for O(log n) queries.

Insight (Floyd): slow/fast pointers meet inside the loop. The distance from head to the loop start equals the distance from the meeting point to the loop start — so advance one pointer from head and one from the meeting point until they align.

Insight: HashMap for O(1) lookup + a doubly linked list for O(1) recency reordering. Most-recent at the front, evict from the back.

Insight: keep a min-heap of the k largest seen so far — the heap's top is the answer. Simple and works even without the sorted-row property.

If both rows and columns are sorted, upgrade to binary search on the value plus a monotone count: O(N log(max−min)).

Insight: a fixed array with a head index and a count; wrap with modulo. Tracking count (instead of a tail) avoids the "full vs empty" ambiguity.

Insight: Sieve of Eratosthenes marks composites; a prime's multiples start at p².

Insight: index = power, value = coefficient. Powers add, coefficients multiply, results accumulate.

The linked-list version stores (coeff, power) nodes; multiply pairwise into a map keyed by power, then rebuild a sorted list.

1 · Sort: sort descending, take the first two distinct — O(n log n). Wasteful but trivial.

2 · Two passes: find the max, then scan again for the max that isn't it — O(n), 2 passes.

3 · Single pass: track first and second; on each element, if it beats first, push first down to second — O(n), 1 pass. This is the answer they want.

4 · Tournament method: pair up and compare like a knockout bracket; the runner-up must have lost only to the champion, so it's among ~log n candidates — n + ⌈log n⌉ − 2 comparisons, the comparison-optimal approach.

A tree — the directory hierarchy is an N-ary tree (each folder is a node with child files/folders). On disk, the filesystem indexes directory entries with a B-tree / B+ tree (e.g., ext4's HTree, NTFS) because they keep lookups shallow and are disk-block friendly. Path resolution walks the tree like a trie.

Memory that was allocated but never released and is no longer reachable, so it can't be reused — usage grows over time. In C/C++ it's a malloc/new with no matching free/delete.

Avoid: RAII and smart pointers (unique_ptr/shared_ptr), pair every allocation with a deallocation on all paths (including exceptions), and check with Valgrind/ASan. In Java, "leaks" are unintended live references — static collections, un-removed listeners, unclosed resources — that keep the GC from collecting.

Both split a problem into subproblems. In divide & conquer the subproblems are independent and solved once (merge sort, binary search). In DP the subproblems overlap, so you memoize/tabulate to avoid recomputation (Fibonacci, edit distance). DP additionally requires optimal substructure.

Disadvantages: only LIFO access (no random access or search), fixed capacity in an array implementation, and no efficient traversal of the middle.

Stack overflow with recursion: every call pushes an activation frame (params, locals, return address). A missing or wrong base case — or legitimately very deep recursion like factorial(1_000_000) — exhausts the call-stack region and throws StackOverflowError. Fix with a correct base case, tail-recursion → iteration, or an explicit stack.

A trap raised when a process accesses a page that isn't currently in physical memory. The MMU can't translate it, so the OS's fault handler fetches the page from disk (or allocates it). It occurs on first touch under demand paging, after the page was swapped out, or on an invalid access (which becomes a segfault).

An abstraction giving each process its own large, contiguous address space that can exceed physical RAM, backed by disk. It enables isolation between processes, and lets more processes run than would fit in RAM by paging inactive pages out.

Loading a page into memory only when it's actually referenced, rather than loading the whole program upfront. It cuts startup time and memory footprint; the cost is a page fault on the first access to each page.

An integer synchronization primitive with two atomic operations: wait/P (decrement; block if it would go negative) and signal/V (increment; wake a waiter). A counting semaphore guards N identical resources; a binary semaphore (value 0/1) acts like a lock.

Mutex: a lock with ownership — only the locker unlocks; a blocked thread sleeps.

Semaphore: a counter for N resources, no ownership; used for signalling between threads too.

Spinlock: busy-waits in a tight loop instead of sleeping — great for very short critical sections on multicore (no context-switch cost), terrible if held long or on a single core.

The kernel saves the outgoing process's CPU register context — program counter, stack pointer, general registers — into its PCB (in kernel memory), then loads the next process's context. The process's own stack and heap stay in RAM untouched; only the pointers/registers are swapped, which is why the resumed process finds its frames exactly as it left them.

Insight: three semaphores — empty counts free slots, full counts filled slots, and mutex protects the buffer indices.

Order matters: acquire the counting semaphore before the mutex, never the reverse — the opposite order deadlocks.

Swap-out: the OS moves a page/process from RAM to the swap area on disk to free memory. Swap-in: it brings that data back into RAM when needed again. This is how the system runs more than physical memory can hold.

Starvation: a process waits indefinitely because higher-priority (or shorter) jobs keep jumping ahead. Aging: the remedy — gradually raise the priority of long-waiting processes so they eventually run.

On a page fault with memory full, evict the page that has gone unused for the longest time — the assumption being recently used pages will be used again (locality). Exact LRU needs timestamps/a stack; real systems approximate it with reference bits (the clock/second-chance algorithm).

Pipes/FIFOs, message queues, shared memory, sockets, and signals. Shared memory is the fastest: once the region is mapped, processes read/write it directly with no kernel copying per message — the kernel is only involved in setup. The trade-off is you must add your own synchronization (semaphores) since the OS doesn't mediate access.

Fragmentation is wasted memory from imperfect allocation. External: enough total free memory exists but it's split into small non-contiguous holes, so a large request can't be satisfied — fixed by compaction or paging. Internal: a fixed block is larger than the request, wasting the remainder inside it.

2^N processes total (i.e. 2^N − 1 new children), since each existing process splits into two at every fork(). With three forks: 8 processes, 7 children.

Starvation of low-priority processes — if high-priority jobs keep arriving, the low-priority ones never get the CPU. The standard fix is aging.

An OS that guarantees tasks complete within strict time bounds (deadlines), where correctness depends on timing. Hard RTOS allows no deadline miss (avionics, pacemakers); soft RTOS tolerates occasional misses with degraded quality (media streaming).

Preemptive: the scheduler can forcibly take the CPU from a running process (Round Robin, preemptive priority, SRTF) — better responsiveness. Non-preemptive: a process holds the CPU until it finishes or blocks (FCFS, non-preemptive SJF) — simpler but a long job can hog the CPU.

FCFS. No process is ever preempted (each finishes within its quantum), so it degenerates to first-come-first-served.

Use two counting semaphores: a write semaphore initialized to 2 (each writer does P before writing, V after) and a read semaphore initialized to 1 (each reader does P/V around reading). The semaphore value caps the number of concurrent holders at exactly 2 and 1 respectively.

The stack pointer (SP) always points to the current top of the stack and moves on every push/pop. The frame pointer (FP / base pointer) is fixed for the duration of a function call and anchors access to that frame's parameters and locals at constant offsets — even as SP keeps moving during the call.

A virtual table defined by a stored query — it holds no data of its own; the query runs when the view is accessed. Views simplify complex joins, enforce security (expose only some columns/rows), and provide logical data independence. A materialized view physically stores the result and must be refreshed.

An auxiliary structure (usually a B+ tree, sometimes a hash) that maps a search key to the location of matching rows, turning full-table scans into logarithmic lookups. The cost is extra storage and slower inserts/updates/deletes, since indexes must be maintained.

Insight: group by subject, take MAX(marks), then order.

If they also want which student scored it, use a window function:

Primary index: built on the ordering key of a sorted file — one entry per block (sparse), fastest and smallest.

Clustering index: on a non-key ordering field, so records with the same value are stored together.

Secondary index: on a non-ordering field; must be dense (an entry per record/bucket) because the file isn't sorted on it.

Multilevel index: an index over the index (the levels of a B+ tree), keeping the top level small enough to sit in memory.

Dense: one index entry for every record — supports existence checks without touching the data, but larger. Sparse: one entry per block/group — smaller, but only works when the file is ordered on the key (you land near the record and scan). Sparse trades a little search time for much less space.

Splitting relation R into R1 and R2 is lossless if their natural join reconstructs exactly R — guaranteed when the common attributes form a superkey of at least one of R1 or R2. It's lossy if the join yields spurious extra tuples (information is effectively lost because you can't tell the originals apart). Good normalization always uses lossless decomposition.

Every class with virtual functions has one shared vtable — an array of pointers to that class's virtual function implementations. Every object of such a class carries a hidden vptr that points to its class's vtable. A virtual call is resolved at runtime: dereference the object's vptr → index into the vtable → jump to the correct override. That indirection is exactly what makes runtime polymorphism work.

Best answer (C++11+): the Meyers singleton — a function-local static whose initialization is guaranteed thread-safe by the standard.

Pre-C++11 / if asked to show locking: double-checked locking with an atomic pointer and a mutex — check the pointer, lock only if null, check again inside the lock. Mention that a naive DCL without atomics is broken due to instruction reordering.

Read it inside-out: (*fp) is a pointer, (int) its parameters, char its return type. Useful for callbacks and dispatch tables.

Caller must ensure dest has room for both strings plus the terminator.

Big-endian stores the most-significant byte at the lowest address; little-endian stores the least-significant byte first (x86, most ARM).

Insight: keep a free list of unused cells and a next[] array of links; each stack is a linked chain through the same array, so all space is shared with no fixed partitions.

Virtual function: a member marked virtual so calls dispatch on the object's runtime type via the vtable — the basis of polymorphism.

Virtual destructor: make the base destructor virtual so that delete basePtr; on a derived object runs the derived destructor first. Omitting it → the derived part isn't cleaned up → undefined behaviour / leaks.

A pure virtual function — virtual void f() = 0; — has no body and must be overridden. A class with at least one pure virtual is an abstract class: it can't be instantiated and serves as an interface. "Abstract function" is just the pure virtual.

Early (static) binding resolves the call at compile time — normal functions, overloads, non-virtual calls. Late (dynamic) binding resolves at runtime through the vtable — virtual functions. Late binding costs one indirection but enables polymorphism.

Shallow copy duplicates member values including pointers, so both objects share the same underlying buffer — leading to aliasing and double-free. Deep copy also duplicates the pointed-to data, giving fully independent objects. In C++ this is the Rule of Three/Five (define copy ctor, copy assign, destructor — and move versions).

void* — typeless pointer; must be cast before dereferencing. Smart pointer — RAII wrapper that owns and auto-frees memory (unique_ptr, shared_ptr, weak_ptr). Wild pointer — uninitialized, points somewhere unknown. Null pointer — points to nothing (nullptr). Dangling pointer — points to memory that has been freed or gone out of scope.

With multiple inheritance, if D inherits from both B and C which each inherit from A, D gets two copies of A's subobject and calls to A's members become ambiguous. Fix with virtual inheritance — class B : virtual public A — so a single shared A subobject exists.

A friend is a non-member function or another class granted access to a class's private/protected members. It deliberately relaxes encapsulation for tightly coupled code — e.g. an overloaded operator<< that needs internal access. Friendship isn't inherited or transitive.

An l-value has an identifiable address (can sit on the left of =); an r-value is a temporary. T& binds l-values; T&& (an r-value reference, C++11) binds temporaries and powers move semantics — stealing resources from a soon-to-die object instead of copying.

Encapsulation (bundle data + behaviour, hide internals), Abstraction (expose intent, not implementation), Inheritance (derive and reuse), Polymorphism (one interface, many runtime forms). The four pillars.

A chain of inheritance: C derives from B, and B derives from A — grandparent → parent → child, each level extending or overriding the previous. Distinct from multiple inheritance (one class, several direct bases).

A request to the compiler to expand the function body at each call site, eliminating call overhead — best for tiny, hot functions. It's only a hint (the compiler may decline), and over-inlining causes code bloat.

They control different things. static affects storage and linkage — a single instance that lives for the whole program (and, at file scope, internal linkage). const affects mutability — the value can't change after initialization. A variable can be both.

Local/auto → stack. Global & static → data segment (initialized in .data, zero-initialized in .bss). Dynamic (new/malloc) → heap. register → a CPU register if honoured (a hint). extern → just a declaration; the definition lives in the data segment elsewhere. const → often read-only data (.rodata). volatile → wherever it normally lives; the keyword only tells the compiler not to cache/optimize its accesses.

From low to high addresses: text/code (instructions, read-only) → initialized data (.data) → uninitialized data (.bss) → heap (grows upward) → … free gap … → stack (grows downward) → command-line args & environment at the top.

The compiler inserts unused bytes so each member starts on its natural alignment boundary and the whole struct's size is a multiple of its largest member's alignment — trading a little space for faster aligned access. Reorder members largest → smallest to shrink padding; #pragma pack forces tighter packing.

The compiler encodes a function's name together with its parameter types (and class/namespace) into a unique linker symbol, so overloaded and namespaced names don't collide. extern "C" turns it off so C code can link to the symbol by its plain name.

A memory-access violation the hardware/OS flags as SIGSEGV — dereferencing a null/wild/dangling pointer, writing to read-only memory, or overflowing the stack. The program is trying to touch memory it isn't allowed to.

Yes, but only when you opt in. Via using declarations/directives, argument-dependent lookup (ADL/Koenig — the compiler also searches the namespaces of a call's arguments), and nesting. Namespaces are also open — you can add names to the same namespace across multiple files. They don't silently merge otherwise.

sizeof(void) is ill-formed in standard C++ because void is an incomplete type (GCC returns 1 as an extension). sizeof(void*) is the pointer size — 8 bytes on a 64-bit build, 4 on 32-bit.

Implementation-defined: either NULL, or a unique non-null pointer that you may legally pass to free() but must not dereference. Don't rely on either behaviour.

NULL is C/C++'s null-pointer constant (traditionally 0; prefer nullptr in modern C++). NIL is the "no value / empty" notion from other languages (Lisp, Pascal, Objective-C's nil) — not standard C++. Also distinguish both from the null character '\0'.

The JVM automatically reclaims objects no longer reachable from GC roots (stack refs, statics). It's generational: most objects die young, so a fast minor GC sweeps the young generation (Eden/survivor) and survivors get promoted to the old generation, collected less often by a major/full GC. Modern collectors (G1, ZGC, Shenandoah) mark → sweep → compact with low pauses.

Templates are compile-time generics — the compiler generates a concrete version per type used (function and class templates). STL is the Standard Template Library built on them: containers (vector, map, unordered_map), iterators, and algorithms. Know the internals: vector doubles its capacity on growth; map is a red-black tree (O(log n), ordered); unordered_map is a hash table (O(1) average).

MFC — Microsoft Foundation Classes, a C++ library wrapping the Win32 API for building Windows GUIs. COM — Component Object Model, a binary interface standard letting components interoperate regardless of language. DCOM — Distributed COM, COM extended so components can communicate across networked machines.

Pointer to an array of 10 ints: int (*p)[10]; — mind the parentheses; int* p[10] is instead an array of 10 pointers.

Your own typedef: typedef unsigned long ulong; (modern: using ulong = unsigned long;). A complex one names a function-pointer type: typedef char (*Fp)(int);.

conio = Console Input/Output (conio.h) — a non-standard DOS/Turbo-C header.

Scheduling decides which ready process gets the CPU next. The ready queue is the structure: a plain FIFO queue for Round Robin, a priority queue / heap for priority scheduling, and a red-black tree in Linux's CFS (keyed by virtual runtime).

Some failures aren't C++ exceptions: OS faults like a segfault (SIGSEGV) or divide-by-zero, and exceptions thrown during stack unwinding (which call std::terminate). You can intercept OS-level faults with platform mechanisms — SEH (__try/__except) on Windows, signal handlers on POSIX — and install a std::set_terminate handler, so you can log and shut down gracefully, but you generally can't safely resume. In Java the analogue is Error (e.g. StackOverflowError): technically catchable, but not something to rely on.

Application: HTTP(S), FTP, SMTP, DNS, DHCP. Transport: TCP, UDP. Internet: IP, ICMP, ARP, routing. Network Access / Link: Ethernet, Wi-Fi (802.11), MAC.

A model where clients request services and a central server provides them (data, compute, files). Resources are centralized — easier to manage and secure, but the server is a single point of failure and a scaling bottleneck. Contrast with peer-to-peer, where every node is both client and server.