Computer Science Fundamentals

# Process example (Python) -- use for CPU-heavy work.
# Each process gets its own Python interpreter and memory space,
# completely bypassing the Global Interpreter Lock (GIL).
from multiprocessing import Process

def cpu_intensive_task(n):
    """Squaring 10M numbers -- pure computation, no I/O waiting."""
    return sum(i * i for i in range(n))

# Creates a separate OS-level process with isolated memory.
# More expensive to create (~10ms) but achieves true parallelism.
p = Process(target=cpu_intensive_task, args=(10000000,))
p.start()
p.join()  # Block until the child process finishes

# Thread example -- use for I/O-heavy work (network calls, disk reads).
# While one thread waits for a network response, other threads can
# execute -- this is called "concurrency" rather than "parallelism."
from threading import Thread

def io_bound_task(url):
    """Network call -- the thread mostly waits for the server to respond."""
    response = requests.get(url)
    return response.text

# Shares memory with the main thread -- cheaper to create (~1ms)
# but be careful: shared memory means potential race conditions.
t = Thread(target=io_bound_task, args=("https://api.example.com",))
t.start()
t.join()

┌─────────────────────────────────────┐
│           Virtual Memory            │
├─────────────────────────────────────┤
│  Stack (grows down)                 │
│    ↓  Local variables, function    │
│       calls, return addresses       │
│  ... (free space) ...               │
│    ↑  Dynamically allocated        │
│       memory (malloc, new)          │
│  Heap (grows up)                    │
├─────────────────────────────────────┤
│  BSS (uninitialized data)           │
│    Global/static vars (zero-init)   │
├─────────────────────────────────────┤
│  Data (initialized data)            │
│    Global/static vars with values   │
├─────────────────────────────────────┤
│  Text (code)                        │
│    Executable instructions          │
└─────────────────────────────────────┘

// Stack allocation - fast, automatic cleanup.
// The compiler knows exactly how much space to reserve at compile time.
void stackExample() {
    int x = 10;           // Stack: 4 bytes, allocated instantly
    int arr[100];         // Stack: 400 bytes, fixed at compile time
}  // ALL memory freed automatically when function returns -- no cleanup needed

// Heap allocation - flexible but you own the lifecycle.
// Use when: size unknown at compile time, data must outlive the function,
// or the allocation is too large for the stack (>1MB).
void heapExample() {
    int* ptr = malloc(sizeof(int) * 1000);  // Heap: ~4KB, allocated at runtime
    if (ptr == NULL) return;                 // Always check -- malloc can fail!
    // ... use ptr ...
    free(ptr);  // MUST manually free! Forgetting = memory leak.
    ptr = NULL; // Good practice: prevent use-after-free bugs
}

# Deadlock example -- this WILL hang indefinitely under the right timing.
# Thread 1 grabs lock_a, Thread 2 grabs lock_b, then both wait forever.
import threading

lock_a = threading.Lock()
lock_b = threading.Lock()

def thread_1():
    lock_a.acquire()        # Thread 1 holds lock_a
    time.sleep(0.1)         # Context switch happens here...
    lock_b.acquire()        # Thread 1 waits for lock_b (held by thread_2) -- STUCK
    # ...
    
def thread_2():
    lock_b.acquire()        # Thread 2 holds lock_b
    time.sleep(0.1)         # Context switch happens here...
    lock_a.acquire()        # Thread 2 waits for lock_a (held by thread_1) -- STUCK
    # ...

# Prevention strategy 1: Lock ordering -- always acquire locks in the SAME
# global order across ALL threads. This breaks the "circular wait" condition.
def thread_safe():
    lock_a.acquire()  # Always acquire A first, everywhere in the codebase
    lock_b.acquire()  # Then B -- no thread can hold B without already holding A
    # ...
    lock_b.release()  # Release in reverse order (good practice, not strictly required)
    lock_a.release()

# Prevention strategy 2: Use context managers with timeouts
# so a thread gives up instead of waiting forever.
def thread_with_timeout():
    if lock_a.acquire(timeout=5):
        if lock_b.acquire(timeout=5):
            try:
                pass  # Do work
            finally:
                lock_b.release()
        lock_a.release()

# Race condition example -- the classic "lost update" problem.
counter = 0

def increment():
    global counter
    for _ in range(100000):
        # counter += 1 looks atomic but is actually THREE operations:
        #   1. READ current value of counter into a register
        #   2. ADD 1 to the register
        #   3. WRITE the new value back to counter
        # If two threads both READ the same value (say, 42), they both
        # write 43 -- and you lose one increment entirely.
        counter += 1  # NOT atomic! Read-modify-write

# Two threads, expected: 200000, actual: some random lower number
# Run it 10 times and you will get a different wrong answer each time.

# Fix with Lock -- guarantees mutual exclusion around the critical section.
lock = threading.Lock()

def safe_increment():
    global counter
    for _ in range(100000):
        with lock:           # Only one thread can execute this block at a time
            counter += 1     # Now the read-modify-write is protected

Layer 7: Application  (HTTP, FTP, DNS, SMTP)
        └── What the user interacts with -- "I want this web page"
        
Layer 4: Transport    (TCP, UDP)
        └── End-to-end communication, port numbers, reliability decisions
        
Layer 3: Network      (IP, ICMP, Routing)
        └── Logical addressing (IP addresses), routing across networks
        
Layer 2: Data Link    (Ethernet, MAC, Switches)
        └── Physical addressing (MAC addresses), local network delivery
        
Layer 1: Physical     (Cables, Signals, Hubs)
        └── Raw bit transmission over copper, fiber, or radio waves

Client                    Server
  │                         │
  │───── SYN (seq=x) ──────►│  1. Client initiates
  │                         │
  │◄── SYN-ACK (seq=y,      │  2. Server acknowledges
  │     ack=x+1) ───────────│     and sends its own SYN
  │                         │
  │───── ACK (ack=y+1) ────►│  3. Client acknowledges
  │                         │
  │◄═══ Connection ════════►│  4. Ready to transfer data

1. Browser Cache      → Check local browser cache (fastest, ~0ms)
2. OS Cache           → Check operating system DNS cache (~1ms)
3. Resolver Cache     → ISP's recursive resolver cache (~5ms)
4. Root Server        → "Who handles .com?" (13 root server clusters worldwide)
5. TLD Server         → "Who handles example.com?" (Verisign for .com)
6. Authoritative NS   → "example.com = 93.184.216.34" (the definitive answer)

# Trace DNS resolution
nslookup example.com
dig example.com +trace

# Common HTTP Methods
GET     # Retrieve resource (idempotent, cacheable)
POST    # Create resource (not idempotent)
PUT     # Update/Replace resource (idempotent)
PATCH   # Partial update (not necessarily idempotent)
DELETE  # Remove resource (idempotent)
HEAD    # GET without body (check if resource exists)
OPTIONS # Supported methods (CORS preflight)

# Status Code Categories
1xx  # Informational (100 Continue)
2xx  # Success (200 OK, 201 Created, 204 No Content)
3xx  # Redirection (301 Moved Permanently, 302 Found, 304 Not Modified)
4xx  # Client Error (400 Bad Request, 401 Unauthorized, 403 Forbidden, 404 Not Found, 429 Too Many Requests)
5xx  # Server Error (500 Internal, 502 Bad Gateway, 503 Service Unavailable, 504 Gateway Timeout)

HTTP: Request-Response (Half-duplex)
Client ───Request──► Server
Client ◄──Response── Server
Client ───Request──► Server
Client ◄──Response── Server

WebSocket: Full-duplex, persistent connection
Client ◄═════════════► Server
       │ Real-time    │
       │ bidirectional│
       │ messages     │

-- Set isolation level
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

BEGIN TRANSACTION;
-- Your queries here
COMMIT;

-- B-Tree Index (default for most DBs)
-- Stores data in a balanced tree structure -- O(log n) lookups.
-- Good for: range queries, sorting, equality, prefix matching.
-- Think of it as a phone book: sorted by name, fast to find "Smith."
CREATE INDEX idx_user_email ON users(email);

-- Hash Index
-- Stores a hash of the key for O(1) lookups -- blazing fast for exact matches.
-- Good for: equality comparisons ONLY (not range queries, not sorting).
-- Think of it as a dictionary: instant lookup, but you cannot browse alphabetically.
CREATE INDEX idx_user_id ON users USING HASH(id);

-- Composite Index (column order matters enormously!)
-- Follows the "leftmost prefix" rule -- the index is usable for queries that
-- filter on the first column, or the first two columns, or all three.
-- Think of it like a phone book sorted by (last_name, first_name, city).
CREATE INDEX idx_orders ON orders(user_id, status, created_at);
-- ✅ Uses index: WHERE user_id = 1                     (leftmost column)
-- ✅ Uses index: WHERE user_id = 1 AND status = 'pending'     (left two)
-- ✅ Uses index: WHERE user_id = 1 AND status = 'pending' AND created_at > '2024-01-01'
-- ❌ Skips index: WHERE status = 'pending'              (missing leftmost column!)
-- ❌ Skips index: WHERE user_id = 1 AND created_at > '2024-01-01' (gap in middle!)

-- Covering Index (includes all needed columns)
CREATE INDEX idx_users_covering ON users(email) INCLUDE (name, created_at);
-- Query can be answered entirely from index, no table lookup needed

-- Partial Index (index subset of rows)
CREATE INDEX idx_active_users ON users(email) WHERE status = 'active';

-- Denormalized (violation of 1NF)
CREATE TABLE orders (
    id INT,
    products VARCHAR(255)  -- "laptop,mouse,keyboard"
);

-- Normalized
CREATE TABLE orders (id INT PRIMARY KEY);
CREATE TABLE order_items (
    order_id INT REFERENCES orders(id),
    product_id INT REFERENCES products(id),
    quantity INT
);

┌─────────────────────────────────────────────┐
│                   CPU                       │
│  ┌─────────────────────────────────────┐   │
│  │           Core                      │   │
│  │  ┌─────────────────────────────┐   │   │
│  │  │   L1 Cache (32-64KB)       │   │   │  ~1ns
│  │  │   Fastest, per-core        │   │   │
│  │  └─────────────────────────────┘   │   │
│  │  ┌─────────────────────────────┐   │   │
│  │  │   L2 Cache (256KB-1MB)     │   │   │  ~3-10ns
│  │  │   Per-core                 │   │   │
│  │  └─────────────────────────────┘   │   │
│  └─────────────────────────────────────┘   │
│  ┌─────────────────────────────────────┐   │
│  │   L3 Cache (8-64MB)                │   │  ~10-40ns
│  │   Shared across cores              │   │
│  └─────────────────────────────────────┘   │
└─────────────────────────────────────────────┘
┌─────────────────────────────────────────────┐
│   RAM (8-128GB+)                           │  ~100ns
└─────────────────────────────────────────────┘
┌─────────────────────────────────────────────┐
│   SSD (~1TB)                               │  ~100μs
└─────────────────────────────────────────────┘
┌─────────────────────────────────────────────┐
│   HDD (~10TB)                              │  ~10ms
└─────────────────────────────────────────────┘

         Consistency
            /\
           /  \
          /    \
         /  CA  \
        /________\
       /\        /\
      /  \  CP  /  \
     / AP \    /    \
    /______\  /______\
Availability  Partition
              Tolerance