Computer Science

Big O describes the upper bound of an algorithm's time or space growth relative to input size n as n → ∞.

• O(1) — Constant: array index access, hash lookup.
• O(log n) — Logarithmic: binary search, balanced BST operations.
• O(n) — Linear: single-pass array scan.
• O(n log n) — Merge sort, heap sort.
• O(n²) — Nested loops, bubble sort.
• O(2ⁿ) — Exponential: brute-force subsets.

Big O ignores constants and lower-order terms. Space complexity follows the same notation.

Use arrays for random access/iteration. Use linked lists for frequent head insertions/deletions (e.g., LRU cache).

• Stack (LIFO — Last In, First Out): push/pop from the same end. Used for: function call stack, undo history, bracket matching, DFS.
• Queue (FIFO — First In, First Out): enqueue at back, dequeue from front. Used for: BFS, task scheduling, print queues.
• Deque (Double-ended queue): push/pop from both ends. Powers sliding-window maximum algorithms.
• Priority Queue / Heap: dequeue the highest-priority element. Used for Dijkstra's, scheduling, k-largest problems.

Both are O(1) for their primary operations when backed by a linked list or circular buffer.

• A hash table maps keys to values using a hash function that computes an index into a backing array.
• Average case: O(1) insert, delete, lookup. Worst case: O(n) if all keys hash to the same bucket.
• Collision resolution:
  • Chaining: Each bucket holds a linked list of colliding entries.
  • Open addressing: Probe for the next empty slot (linear, quadratic, double hashing).
• Load factor: n_entries / n_buckets. Hash tables resize (rehash) when load factor exceeds a threshold (~0.75).

• A tree is a hierarchical data structure of nodes where each node has a value and zero or more children.
• Terminology: root, parent, child, leaf, depth, height, subtree.
• Binary tree: Each node has at most 2 children.
• Traversal orders: In-order (L-Root-R), Pre-order (Root-L-R), Post-order (L-R-Root), Level-order (BFS).
• Balanced vs unbalanced: A balanced tree keeps height O(log n) — crucial for performance guarantees.

• A BST is a binary tree where: left subtree values < node value < right subtree values.
• Operations: search, insert, delete — all O(h) where h is height.
• Balanced BST (AVL tree, Red-Black tree): guarantees h = O(log n).
• Unbalanced BST: Degrades to O(n) in the worst case (sorted input inserts).
• In-order traversal of a BST yields elements in sorted order.

• A heap is a complete binary tree satisfying the heap property:
• Max-heap: Parent ≥ children. Root is the maximum element.
• Min-heap: Parent ≤ children. Root is the minimum element.
• Typically implemented as an array (children of index i are at 2i+1 and 2i+2).
• Operations: insert O(log n), extract-min/max O(log n), peek O(1).
• Use cases: Priority queues, heap sort, k-largest/smallest problems, Dijkstra's algorithm.

• A graph G = (V, E) consists of vertices (nodes) and edges (connections).
• Directed vs undirected. Weighted vs unweighted. Cyclic vs acyclic.
• Representations:
  • Adjacency matrix: V×V boolean matrix. O(1) edge check; O(V²) space.
  • Adjacency list: Map of vertex → list of neighbours. O(V+E) space; more memory-efficient for sparse graphs.
• Special types: DAG (directed acyclic graph), tree (connected, acyclic, undirected).

• BFS (Breadth-First Search): Explores level by level using a queue. Finds shortest path in unweighted graphs. O(V+E) time, O(V) space.
• DFS (Depth-First Search): Explores as deep as possible first using a stack (or recursion). Used for: topological sort, cycle detection, path finding, connected components. O(V+E) time, O(V) space (call stack).
• Use BFS when: shortest path, level order traversal of a tree.
• Use DFS when: exhaustive search, backtracking, topological sort.

The comparison sort lower bound is O(n log n). JavaScript's Array.prototype.sort() uses Timsort (merge + insertion).

• Binary search finds a target in a sorted array by repeatedly halving the search space.
• Time: O(log n). Space: O(1) iterative, O(log n) recursive.

Common extensions: find first/last occurrence, search rotated array, search for boundary condition.

• Recursion is when a function calls itself to solve a smaller sub-problem.
• Every recursive function needs a base case — a condition that stops recursion — to avoid infinite loops.
• Call stack: Each recursive call adds a frame; too many → stack overflow. Depth is O(n) for linear recursion.
• Tail recursion: Recursive call is the last operation — some compilers optimise to iteration (TCO). JavaScript does not reliably perform TCO.
• Most recursive solutions can be rewritten iteratively with an explicit stack.

• DP solves problems by breaking them into overlapping sub-problems and storing results to avoid recomputation (memoisation or tabulation).
• Two conditions: Optimal substructure + overlapping sub-problems.
• Top-down (memoisation): Recursive + cache results in a hashmap/array.
• Bottom-up (tabulation): Iteratively fill a DP table from smallest sub-problems up.
• Classic problems: Fibonacci, coin change, knapsack, longest common subsequence, edit distance, climbing stairs.

• A greedy algorithm makes the locally optimal choice at each step, hoping to arrive at a globally optimal solution.
• Works when: The problem has the greedy-choice property — local optima lead to global optima.
• Classic examples: interval scheduling, activity selection, Huffman encoding, Dijkstra's (with non-negative weights), Kruskal's/Prim's MST.
• When greedy fails: Coin change with arbitrary denominations (use DP instead).

• Split the problem into independent sub-problems, solve each recursively, then combine results.
• Key difference from DP: Sub-problems do not overlap (no shared computation to cache).
• Classic examples: Merge sort, quick sort, binary search, fast Fourier transform.
• Master Theorem gives the time complexity of recursive divide-and-conquer recurrences: T(n) = aT(n/b) + f(n).

• Use two indices (left/right or slow/fast) moving through a data structure to solve problems in O(n) that would naively be O(n²).
• Opposite ends: Two-sum on sorted array, container with most water, palindrome check.
• Same direction (slow/fast): Remove duplicates in-place, detect linked list cycle (Floyd's algorithm), find middle of linked list.
• Requires sorted input or specific structural properties.

• Maintain a window (contiguous sub-array or substring) and slide it across the input, updating the result incrementally — avoiding O(n²) recomputation.
• Fixed-size window: Maximum sum of sub-array of size k.
• Variable-size window: Longest substring without repeating characters, minimum sub-array sum ≥ target.
• Typically O(n) time, O(1) or O(k) space.

• A trie (prefix tree) is a tree where each node represents a character prefix. Words are stored by traversing from root to a marked leaf.
• Insert / Search / StartsWith: All O(m) where m = length of the word.
• Space: Can be large — each node may have up to 26 children (for lowercase English).
• Use cases: Autocomplete, spell check, IP routing, word search in a grid.

• Bit manipulation uses bitwise operators to perform operations directly on binary representations.
• Operators: & (AND), | (OR), ^ (XOR), ~ (NOT), << (left shift), >> (right shift).
• Common tricks:
• n & (n-1) — clears the lowest set bit (count set bits).
• n & 1 — checks if n is odd.
• a ^ a = 0, a ^ 0 = a — XOR a number with itself cancels out (find unique element).
• 1 << k — 2^k (set k-th bit).

• Stack: Stores function call frames (local variables, return addresses). Managed automatically by the CPU. Fast, fixed size, LIFO. Stack overflow = recursion depth exceeded.
• Heap: Dynamically allocated memory (objects, closures). Managed by GC (JS/Python) or manually (C/C++). Larger, slower, flexible size.
• In JavaScript: primitives on stack (by value); objects/arrays allocated on heap (by reference).
• Memory leak: Heap memory that is no longer reachable but not collected (e.g., lingering event listeners, circular references).

• Process: An independent program with its own memory space. Isolated — one process cannot directly access another's memory. Heavyweight to create.
• Thread: A unit of execution within a process. Shares memory with sibling threads. Lightweight. Enables concurrency within an app.
• Context switching: OS switches between processes/threads; threads are cheaper to switch.
• Node.js runs on a single thread (event loop) but uses a thread pool (libuv) for I/O. Workers add true multi-threading.

• A race condition occurs when the outcome of a program depends on the interleaving of concurrent operations on shared state.
• Prevention techniques:
  • Mutex (mutual exclusion): Lock shared resource so only one thread accesses it at a time.
  • Semaphores: Allow N concurrent accesses.
  • Atomic operations: CPU-level indivisible operations (compare-and-swap).
  • Immutable data: No shared mutable state → no race conditions.
  • Single-threaded event loop (Node.js): Avoids shared memory races at the JS level.

• A deadlock occurs when two or more threads are each waiting for the other to release a resource — a circular dependency that causes all to block forever.
• 4 Coffman conditions (all must hold for deadlock):
  1. Mutual Exclusion — resource held exclusively.
  2. Hold and Wait — thread holds one resource while waiting for another.
  3. No Preemption — resources cannot be forcibly taken.
  4. Circular Wait — circular chain of threads each waiting on the next.
• Prevention: Impose a strict ordering on lock acquisition; use timeouts; use lock-free algorithms.

• The OS scheduler decides which process/thread gets CPU time.
• FCFS (First Come First Served): Simple, but long jobs block short ones (convoy effect).
• SJF (Shortest Job First): Minimises average wait time. Requires knowing job length in advance.
• Round Robin: Each process gets a fixed time slice (quantum). Fair, used in most modern OSes.
• Priority Scheduling: Higher priority runs first. Risk of starvation for low-priority processes.
• Multi-level Feedback Queue: Combination — processes can move between queues based on behaviour.

• Virtual memory gives each process the illusion of having its own large, contiguous address space, regardless of physical RAM.
• The OS and MMU (Memory Management Unit) map virtual addresses to physical addresses via a page table.
• Paging: Memory divided into fixed-size pages; pages swapped to disk when RAM is full.
• Page fault: Accessing a page not in RAM triggers the OS to load it from disk — expensive.
• Benefits: Process isolation, memory overcommitment, easier memory management.

• TCP (Transmission Control Protocol): Connection-oriented. Guarantees delivery, order, and error correction. Three-way handshake. Slower. Used for HTTP, FTP, email.
• UDP (User Datagram Protocol): Connectionless. No guarantee of delivery or order. No handshake. Faster, lower overhead. Used for video streaming, gaming, DNS, VoIP.
• Flow control & congestion control: TCP has both; UDP has neither.
• HTTP/3 uses QUIC (built on UDP) to reduce handshake latency while keeping reliability.

• HTTPS = HTTP over TLS (Transport Layer Security).
• TLS Handshake: Client and server negotiate cipher suite → server presents certificate → key exchange (e.g., ECDHE) establishes a shared session key → encrypted communication begins.
• Certificate: Issued by a trusted Certificate Authority (CA). Proves server identity via public-key cryptography.
• Symmetric encryption (e.g., AES) used for bulk data after handshake (fast).
• Asymmetric encryption (e.g., RSA) used only during handshake (slow).
• HTTP/2 and HTTP/3 require HTTPS.

• REST: Resources mapped to URLs; HTTP verbs (GET, POST, PUT, DELETE). Multiple endpoints. Over/under-fetching is a common pain point.
• GraphQL: Single endpoint. Client specifies exactly what data it needs. Strong typing via schema. Avoids over/under-fetching. Better for complex, nested data.
• REST pros: Simple, cacheable (HTTP), well-understood, wide tooling.
• GraphQL pros: Flexible, reduces round trips, self-documenting schema, great for frontend-driven APIs.
• GraphQL cons: Harder caching, N+1 query risk (use DataLoader), complex to secure.

• Caching stores the results of expensive operations so future requests can be served faster.
• Levels: CPU cache (L1/L2/L3) → RAM → disk → network (CDN).
• Strategies: Cache-aside, write-through, write-behind, read-through (covered in depth on the Databases page).
• Eviction policies: LRU (Least Recently Used), LFU (Least Frequently Used), FIFO, TTL-based.
• Cache invalidation is hard: "There are only two hard things in CS: cache invalidation and naming things." — Phil Karlton.
• CDN caching: Static assets cached at edge nodes geographically close to users.

• S — Single Responsibility: A class should have only one reason to change.
• O — Open/Closed: Open for extension, closed for modification. Add behaviour without changing existing code.
• L — Liskov Substitution: Subclasses must be substitutable for their base class without breaking correctness.
• I — Interface Segregation: Prefer many small, specific interfaces over one large general one.
• D — Dependency Inversion: High-level modules should not depend on low-level modules; both should depend on abstractions.