CS Fundamentals¶

Interview-grade theory across OS, Networks, and DBMS. Each section covers what interviewers ask, the theory behind it, and how it maps to Java.

Part 1 — Operating Systems¶

1.1 Processes and Threads¶

A process is an independent program in execution with its own memory space. A thread is a lightweight unit of execution within a process that shares the process's memory.

Process Lifecycle (States)¶

Process Control Block (PCB)¶

Every process is represented in the OS by a PCB, which contains:

• Process ID (PID) — unique identifier
• Process State — current lifecycle state
• Program Counter — address of the next instruction
• CPU Registers — contents of all process-centric registers
• Memory Management Info — page tables, segment tables, base/limit registers
• I/O Status — list of open files, allocated I/O devices
• Scheduling Info — priority, scheduling queue pointers

Process vs Thread Comparison¶

User-Level vs Kernel-Level Threads¶

Java integration: Every Java program runs as a process on the JVM. The JVM manages threads internally.

// Creating threads in Java
// Method 1: Extend Thread class
class MyThread extends Thread {
    public void run() {
        System.out.println("Thread: " + Thread.currentThread().getName());
    }
}

// Method 2: Implement Runnable (preferred)
Runnable task = () -> System.out.println("Running in: " + Thread.currentThread().getName());
new Thread(task).start();

// Method 3: ExecutorService (production-grade)
ExecutorService executor = Executors.newFixedThreadPool(4);
executor.submit(() -> {
    System.out.println("Pool thread: " + Thread.currentThread().getName());
});
executor.shutdown();

// Method 4: Virtual Threads (Java 21+ / Project Loom)
Thread.startVirtualThread(() -> {
    System.out.println("Virtual thread: " + Thread.currentThread().getName());
});

// Or with ExecutorService
try (var executor2 = Executors.newVirtualThreadPerTaskExecutor()) {
    executor2.submit(() -> System.out.println("Lightweight!"));
}

1.2 CPU Scheduling¶

The OS scheduler decides which process/thread runs on the CPU and for how long.

Key metrics:

• CPU Utilization — keep the CPU as busy as possible
• Throughput — number of processes completed per unit time
• Turnaround Time — time from submission to completion
• Waiting Time — time spent in the ready queue
• Response Time — time from submission to first response

Linux CFS (Completely Fair Scheduler):
Modern Linux uses CFS, which assigns each process a virtual runtime. The process with the lowest virtual runtime gets the CPU next. Implemented using a red-black tree for O(log n) scheduling decisions.

1.3 Synchronization¶

When multiple threads access shared resources concurrently, synchronization is needed to prevent race conditions.

Critical Section Problem¶

Requirements for a correct solution:

1. Mutual Exclusion — Only one process in the critical section at a time
2. Progress — If no process is in the CS, selection of the next one cannot be postponed indefinitely
3. Bounded Waiting — A bound on the number of times other processes enter CS after a process has requested entry

Synchronization Primitives¶

Classic Problems¶

Producer-Consumer (Bounded Buffer):

class BoundedBuffer<T> {
    private final Queue<T> buffer = new LinkedList<>();
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();

    public BoundedBuffer(int capacity) { this.capacity = capacity; }

    public void produce(T item) throws InterruptedException {
        lock.lock();
        try {
            while (buffer.size() == capacity) notFull.await();
            buffer.add(item);
            notEmpty.signal();
        } finally { lock.unlock(); }
    }

    public T consume() throws InterruptedException {
        lock.lock();
        try {
            while (buffer.isEmpty()) notEmpty.await();
            T item = buffer.poll();
            notFull.signal();
            return item;
        } finally { lock.unlock(); }
    }
}

Java Synchronization Options Comparison:

1.4 Deadlocks¶

A deadlock occurs when two or more processes are waiting for each other to release resources, creating a circular dependency.

Four necessary conditions (all must hold):

1. Mutual Exclusion: Resource held exclusively by one process
2. Hold and Wait: Process holds one resource while waiting for another
3. No Preemption: Resources cannot be forcibly taken away
4. Circular Wait: A circular chain of processes, each waiting for a resource held by the next

Handling strategies:

Banker's Algorithm (Simplified):

Given n processes and m resource types, maintain:

• Available[m] — currently available resources
• Max[n][m] — maximum demand of each process
• Allocation[n][m] — currently allocated to each process
• Need[n][m] = Max - Allocation

A state is safe if there exists a sequence in which every process can finish. Before granting a request, simulate the allocation and check if the resulting state is still safe.

Java deadlock example:

Object lock1 = new Object(), lock2 = new Object();

// Thread 1: locks lock1, then lock2
new Thread(() -> {
    synchronized (lock1) {
        synchronized (lock2) { /* work */ }
    }
}).start();

// Thread 2: locks lock2, then lock1 — DEADLOCK!
new Thread(() -> {
    synchronized (lock2) {
        synchronized (lock1) { /* work */ }
    }
}).start();

// Fix: Always acquire locks in the same order (lock1 → lock2)
// Or use tryLock with timeout:
ReentrantLock lockA = new ReentrantLock();
ReentrantLock lockB = new ReentrantLock();

if (lockA.tryLock(1, TimeUnit.SECONDS)) {
    try {
        if (lockB.tryLock(1, TimeUnit.SECONDS)) {
            try { /* work */ }
            finally { lockB.unlock(); }
        }
    } finally { lockA.unlock(); }
}

1.5 Memory Management¶

Virtual Memory¶

Virtual memory provides each process with its own address space, decoupled from physical memory. The MMU (Memory Management Unit) translates virtual addresses to physical addresses using page tables.

Virtual Address → [Page Number | Offset]
                       ↓
               Page Table Lookup
                       ↓
              [Frame Number | Offset] → Physical Address

TLB (Translation Lookaside Buffer): A hardware cache of recent page table entries. TLB hit = ~1 ns; TLB miss = ~100 ns (page table walk). Context switches flush the TLB (expensive!).

Paging¶

The OS divides physical memory into fixed-size frames and virtual memory into pages (typically 4KB).

Page Fault Handling:

1. Process accesses a page not in physical memory
2. CPU generates a page fault trap
3. OS finds the page on disk (swap space)
4. OS selects a victim frame (page replacement algorithm)
5. Loads the page from disk into the free frame
6. Updates the page table
7. Restarts the instruction

Page Replacement Algorithms¶

Thrashing: When a process spends more time paging than executing. Occurs when the working set (pages actively used) exceeds available frames. Solution: increase memory, reduce multiprogramming degree, or use working set model.

JVM Memory Areas¶

GC Algorithm Comparison:

1.6 Inter-Process Communication (IPC)¶

Java IPC:

// Sockets (most common for Java services)
// Server
ServerSocket server = new ServerSocket(9090);
Socket client = server.accept();
BufferedReader in = new BufferedReader(new InputStreamReader(client.getInputStream()));

// Java NIO Channels (non-blocking I/O)
SocketChannel channel = SocketChannel.open();
channel.configureBlocking(false);
channel.connect(new InetSocketAddress("localhost", 9090));

// Memory-mapped files (shared memory in Java)
try (FileChannel fc = FileChannel.open(Path.of("shared.dat"),
        StandardOpenOption.READ, StandardOpenOption.WRITE)) {
    MappedByteBuffer buffer = fc.map(FileChannel.MapMode.READ_WRITE, 0, 1024);
    buffer.putInt(42); // Write
    buffer.flip();
    int value = buffer.getInt(); // Read
}

1.7 I/O Management¶

Blocking vs Non-Blocking I/O:

Disk I/O Scheduling Algorithms:

Part 2 — Computer Networks¶

Based on Kurose & Ross, Computer Networking: A Top-Down Approach, Edition 6

2.1 Network Layer Models¶

OSI Model (7 Layers)¶

TCP/IP Model (4 Layers)¶

2.2 Application Layer¶

Transport Services Available to Applications¶

TCP vs UDP Services¶

HTTP (HyperText Transfer Protocol)¶

HTTP is an application-level protocol that uses TCP as underlying transport, typically on port 80. HTTP is stateless — the server maintains no information about past client requests.

The server sends requested files to clients without storing any state information. If a client asks for the same object twice, the server resends it — it has completely forgotten what it did earlier.

HTTP Message Format¶

Request Message:

GET /somedir/page.html HTTP/1.1
Host: www.someschool.edu
Connection: close
User-agent: Mozilla/5.0
Accept-language: fr

Response Message:

HTTP/1.1 200 OK
Connection: close
Date: Tue, 09 Aug 2011 15:44:04 GMT
Server: Apache/2.2.3 (CentOS)
Last-Modified: Tue, 09 Aug 2011 15:11:03 GMT
Content-Length: 6821
Content-Type: text/html

(data data data data data ...)

Common HTTP Status Codes¶

HTTP Versions¶

FTP (File Transfer Protocol)¶

FTP is an application layer protocol that runs on top of TCP. It uses two parallel connections for file transfer: a control connection and a data connection.

                   ┌──────────────────────┐
                   │     FTP Client       │
                   │                      │
                   │  User Interface      │
                   └──────┬───────┬───────┘
              Control     │       │    Data
           Connection     │       │  Connection
             (Port 21)    │       │  (Port 20)
                   ┌──────▼───────▼───────┐
                   │     FTP Server       │
                   └──────────────────────┘

FTP Commands:

FTP Reply Codes: 331 Username OK, password required · 125 Data connection open; transfer starting · 425 Can't open data connection · 452 Error writing file

SMTP (Simple Mail Transfer Protocol)¶

SMTP is a push protocol that uses TCP port 25. The client who wants to send mail opens a TCP connection to the SMTP server and then sends the mail across the connection.

Email delivery flow:

Alice's UA → Alice's Mail Server → (SMTP over TCP) → Bob's Mail Server → Bob's UA

1. Alice composes message, sends to her mail server (message queue)
2. Client SMTP on Alice's server opens TCP connection to Bob's mail server
3. After SMTP handshaking, sends the message
4. Bob's mail server places message in Bob's mailbox
5. Bob reads at his convenience

SMTP uses persistent connections and does not generally use intermediate mail servers.

HTTP vs SMTP¶

Mail Access Protocols¶

DNS (Domain Name System)¶

DNS is a host name to IP address translation service. It is a distributed database implemented in a hierarchy of name servers. It is an application layer protocol using UDP on port 53.

DNS Services¶

DNS Hierarchy¶

                        Root DNS Servers (13 clusters)
                       /        |         \
                    .com       .org       .edu        ← TLD Servers
                   /    \       |          |
             google.com  ...  wikipedia.org  mit.edu  ← Authoritative Servers

Resolution process:

1. Client queries local DNS resolver (recursive resolver, e.g., ISP or 8.8.8.8)
2. Resolver queries root server → returns TLD server address
3. Resolver queries TLD server (.com) → returns authoritative server address
4. Resolver queries authoritative server → returns the IP address
5. IP cached at each level with TTL

DNS Record Types:

Peer-to-Peer (P2P) and BitTorrent¶

In P2P file distribution, the minimum distribution time scales as:

D_P2P ≥ max{ F/u_s, F/d_min, NF/(u_s + Σu_i) }

Where F = file size, u_s = server upload, d_min = min client download, N = number of peers.

BitTorrent Decisions:

Other Application Layer Protocols¶

2.3 Transport Layer¶

The transport layer provides logical communication between application processes running on different hosts. From the application's perspective, it appears as if the hosts are directly connected.

Multiplexing and Demultiplexing¶

• Multiplexing (at sender): Gathering data from multiple sockets, adding headers, passing segments to network layer
• Demultiplexing (at receiver): Delivering data to the correct socket based on header info

Port numbers are 16-bit (0–65535). Ports 0–1023 are well-known (reserved: HTTP=80, FTP=21, SSH=22).

Critical difference:

UDP (User Datagram Protocol)¶

UDP is connectionless. No handshaking. Unreliable — no delivery guarantee. No congestion control.

UDP Segment Structure¶

  0               15 16              31
  ┌─────────────────┬─────────────────┐
  │   Source Port    │  Dest Port      │  ← 2 bytes each
  ├─────────────────┼─────────────────┤
  │     Length       │   Checksum      │  ← 2 bytes each
  ├─────────────────┴─────────────────┤
  │          Application Data         │
  │              (payload)            │
  └───────────────────────────────────┘
         Total Header: 8 bytes

Length = header (8 bytes) + payload.

UDP Checksum Calculation¶

1. Sum all 16-bit words (header + pseudo-header from IP + data)
2. Wrap around any overflow
3. Take 1's complement of the sum → checksum
4. At receiver: sum all words + checksum → should be 1111111111111111

Example:

  0110011001100000
+ 0101010101010101
= 1011101110110101

+ 1000111100001100
= 0100101011000010  (overflow wrapped)

Checksum = 1011010100111101  (1's complement)

Protocols using UDP: DNS, NTP, DHCP, BOOTP, TFTP, RTSP, RIP, OSPF, SNMP.

TCP (Transmission Control Protocol)¶

TCP provides reliable, in-order, byte-stream delivery with flow control and congestion control.

• Full-duplex: Both sides send simultaneously
• Point-to-point: Always between exactly two endpoints (no multicast)
• Connection-oriented: 3-way handshake before data transfer

TCP Segment Structure¶

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  ┌───────────────────────┬───────────────────────┐
  │     Source Port (16)  │  Destination Port (16)│
  ├───────────────────────┴───────────────────────┤
  │              Sequence Number (32)             │
  ├───────────────────────────────────────────────┤
  │          Acknowledgment Number (32)           │
  ├────────┬──────┬───────────────────────────────┤
  │ Header │ Resv │U│A│P│R│S│F│  Receive         │
  │ Length │      │R│C│S│S│Y│I│  Window (16)      │
  │  (4)   │ (6)  │G│K│H│T│N│N│                   │
  ├────────┴──────┴───────┬───────────────────────┤
  │    Checksum (16)      │  Urgent Pointer (16)  │
  ├───────────────────────┴───────────────────────┤
  │              Options (variable)               │
  ├───────────────────────────────────────────────┤
  │                    Data                       │
  └───────────────────────────────────────────────┘
        Typical Header: 20 bytes (no options)

Flag bits:

Sequence Numbers and Acknowledgments¶

• Sequence number: The byte-stream number of the first byte in the segment
• Acknowledgment number: The sequence number of the next byte expected from the other side

Example: File = 500,000 bytes, MSS = 1,000 bytes → 500 segments. First segment: seq=0, second: seq=1000, third: seq=2000...

Cumulative acknowledgments: TCP only acknowledges bytes up to the first missing byte. If bytes 0-535 and 900-1000 are received but 536-899 are missing, ACK = 536.

MSS vs MTU:

• MTU (Maximum Transmission Unit): Largest link-layer frame (Ethernet = 1500 bytes)
• MSS (Maximum Segment Size): MTU – TCP/IP header (typically 40 bytes) = 1460 bytes (max application data per segment)

RTT Estimation and Timeout¶

EstimatedRTT = (1 - α) × EstimatedRTT + α × SampleRTT     [α = 0.125]
DevRTT = (1 - β) × DevRTT + β × |SampleRTT - EstimatedRTT| [β = 0.25]
TimeoutInterval = EstimatedRTT + 4 × DevRTT

This is an Exponential Weighted Moving Average (EWMA). Initial TimeoutInterval = 1 second. On timeout, the interval is doubled (exponential backoff). On receiving an ACK, recalculate using the formulas.

TCP Connection Management (3-Way Handshake)¶

Client                              Server
  │                                    │
  │──── SYN (seq=client_isn) ─────────▶│  Step 1: SYN segment
  │                                    │
  │◀── SYN+ACK (seq=server_isn,  ──────│  Step 2: SYNACK segment
  │          ack=client_isn+1)         │
  │                                    │
  │──── ACK (seq=client_isn+1,  ──────▶│  Step 3: ACK (may carry data)
  │          ack=server_isn+1)         │
  │                                    │
  │         Connection Established     │

Step 1: Client sends SYN with random initial sequence number (client_isn).

Step 2: Server allocates buffers/variables, sends SYN-ACK with its own server_isn and ack=client_isn+1.

Step 3: Client allocates buffers/variables, sends ACK with ack=server_isn+1. This segment can carry data.

Connection Teardown (4-Way):

Client                              Server
  │── FIN ──────────────────────────▶│
  │◀─────────────────────── ACK ─────│
  │◀─────────────────────── FIN ─────│
  │── ACK ──────────────────────────▶│
  │     (TIME_WAIT: 2×MSL)          │

Flow Control¶

Flow control prevents the sender from overwhelming the receiver. Each side advertises its receive window (rwnd) — the available buffer space.

Constraint: LastByteSent - LastByteAcked ≤ rwnd

Zero-window problem: If receiver advertises rwnd=0, sender stops. But how does sender know when buffer clears? TCP requires sender to continue sending 1-byte probe segments when rwnd=0. These probes trigger ACKs with updated rwnd.

Congestion Control¶

Congestion window (cwnd): Limits how much unacknowledged data can be in flight.

Effective window: min(cwnd, rwnd)
LastByteSent - LastByteAcked ≤ min(cwnd, rwnd)

Phases:

On timeout: ssthresh = cwnd/2, cwnd = 1 MSS, restart slow start.

On 3 duplicate ACKs (fast retransmit): ssthresh = cwnd/2, cwnd = ssthresh, enter congestion avoidance (TCP Reno) or fast recovery.

AIMD: TCP uses Additive Increase, Multiplicative Decrease — increases linearly, halves on loss. This creates the classic TCP sawtooth pattern.

Congestion Control Algorithms:

2.4 Java Networking Integration¶

// HTTP Client (Java 11+)
HttpClient client = HttpClient.newHttpClient();
HttpRequest request = HttpRequest.newBuilder()
    .uri(URI.create("https://api.example.com/users"))
    .header("Content-Type", "application/json")
    .GET()
    .build();
HttpResponse<String> response = client.send(request, HttpResponse.BodyHandlers.ofString());
System.out.println(response.statusCode()); // 200
System.out.println(response.body());

// TCP Socket programming
// Server side
ServerSocket server = new ServerSocket(8080);
Socket clientSocket = server.accept(); // blocks until client connects
BufferedReader in = new BufferedReader(new InputStreamReader(clientSocket.getInputStream()));
String message = in.readLine();

// UDP Socket programming
DatagramSocket socket = new DatagramSocket(9090);
byte[] buf = new byte[1024];
DatagramPacket packet = new DatagramPacket(buf, buf.length);
socket.receive(packet); // blocks
String received = new String(packet.getData(), 0, packet.getLength());

// Spring Boot handles HTTP via @RestController
@RestController
@RequestMapping("/api/users")
public class UserController {
    @GetMapping("/{id}")
    public ResponseEntity<User> getUser(@PathVariable Long id) {
        return ResponseEntity.ok(userService.findById(id));
    }
}

Part 3 — Database Management Systems (DBMS)¶

3.1 ER Diagrams and Schema Design¶

Key concepts:

• Entity: A real-world object (User, Order, Product)
• Attribute: A property of an entity (name, email, price)
• Primary Key: Unique identifier for each record
• Foreign Key: Reference to a primary key in another table
• Candidate Key: Minimal set of attributes that can uniquely identify a tuple
• Super Key: Any set of attributes that can uniquely identify a tuple (candidate key + more)

Relationships:

3.2 Normalization¶

3.3 ACID Properties¶

Transaction Isolation Levels¶

Anomalies explained:

• Dirty Read: Txn reads data written by another uncommitted txn → if it rolls back, you read garbage
• Non-Repeatable Read: Txn reads same row twice, gets different values (another txn committed between reads)
• Phantom Read: Txn re-executes a query, gets different set of rows (another txn inserted/deleted)

// Spring: set isolation level per transaction
@Transactional(isolation = Isolation.REPEATABLE_READ)
public void transferFunds(Long fromId, Long toId, BigDecimal amount) {
    // ... transfer logic
}

3.4 Indexing — Deep Dive¶

An index is a data structure that speeds up data retrieval at the cost of extra storage and slower writes.

Without index: Full table scan — O(n)
With B-tree index: O(log n)

B-Tree vs B+ Tree¶

Index Types¶

-- Create index on frequently queried column
CREATE INDEX idx_users_email ON users(email);

-- Composite index for multi-column queries
-- Column order matters! (leftmost prefix rule)
CREATE INDEX idx_orders_user_date ON orders(user_id, order_date);

-- When to index:
-- YES: columns in WHERE, JOIN, ORDER BY, high cardinality
-- NO: small tables, low cardinality columns, heavily updated tables

3.5 SQL Joins¶

-- INNER JOIN: only matching rows from both tables
SELECT u.name, o.total
FROM users u INNER JOIN orders o ON u.id = o.user_id;

-- LEFT JOIN: all rows from left table, matching from right (NULL if no match)
SELECT u.name, o.total
FROM users u LEFT JOIN orders o ON u.id = o.user_id;

-- Common interview question: find users with no orders
SELECT u.name FROM users u
LEFT JOIN orders o ON u.id = o.user_id
WHERE o.id IS NULL;

-- SELF JOIN: employees and their managers
SELECT e.name AS employee, m.name AS manager
FROM employees e LEFT JOIN employees m ON e.manager_id = m.id;

3.6 Transactions and Locking¶

// Optimistic locking with @Version
@Entity
public class Product {
    @Id private Long id;
    @Version private Long version; // Auto-incremented on each update
    private int stock;
}

// If two transactions read stock=10 and both try to decrement,
// the second one gets OptimisticLockException → retry or fail

Two-Phase Locking (2PL): A txn must acquire all locks before releasing any.

• Growing phase: Acquire locks, no releases
• Shrinking phase: Release locks, no acquisitions
• Guarantees serializability but can cause deadlocks

3.7 Query Optimization¶

-- Use EXPLAIN to understand query execution
EXPLAIN SELECT * FROM users WHERE email = 'john@example.com';

-- Common optimizations:
-- 1. Add indexes on WHERE/JOIN columns
-- 2. Avoid SELECT * — only fetch needed columns
-- 3. Use LIMIT for pagination
-- 4. Avoid functions on indexed columns: WHERE YEAR(created_at) = 2024
--    Instead: WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01'

N+1 Query Problem (JPA):

// BAD: 1 query for users + N queries for each user's orders
List<User> users = userRepo.findAll(); // 1 query
for (User u : users) {
    u.getOrders().size(); // N queries (lazy loading)
}

// FIX: Fetch join
@Query("SELECT u FROM User u JOIN FETCH u.orders")
List<User> findAllWithOrders(); // 1 query

3.8 CAP Theorem¶

In a distributed system, you can guarantee at most two of three properties:

Since network partitions are unavoidable in distributed systems, the real choice is CP vs AP:

3.9 Java + DBMS Integration (JPA/Hibernate)¶

// Entity mapping
@Entity
@Table(name = "users")
public class User {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    @Column(nullable = false, unique = true)
    private String email;

    @Column(nullable = false)
    private String name;

    @OneToMany(mappedBy = "user", cascade = CascadeType.ALL, fetch = FetchType.LAZY)
    private List<Order> orders;
}

// Transaction management in Spring
@Service
public class TransferService {

    @Transactional(isolation = Isolation.REPEATABLE_READ, timeout = 30)
    public void transfer(Long fromId, Long toId, BigDecimal amount) {
        Account from = accountRepo.findById(fromId)
            .orElseThrow(() -> new AccountNotFoundException(fromId));
        Account to = accountRepo.findById(toId)
            .orElseThrow(() -> new AccountNotFoundException(toId));

        if (from.getBalance().compareTo(amount) < 0) {
            throw new InsufficientFundsException();
        }

        from.setBalance(from.getBalance().subtract(amount));
        to.setBalance(to.getBalance().add(amount));

        accountRepo.save(from);
        accountRepo.save(to);
        // If any step fails, everything rolls back
    }
}

// Connection pooling (application.yml)
// spring.datasource.hikari.maximum-pool-size: 10
// spring.datasource.hikari.minimum-idle: 5
// spring.datasource.hikari.connection-timeout: 30000

Summary — How CS Fundamentals Connect to Java Backend¶