CS fundamentals interview questions: operating systems, networks and data structures

A process is a running program with its own memory space. A thread is a path of execution inside a process. Threads in the same process share its memory — the heap, global data and open files — but each thread has its own stack and registers.

That makes threads cheaper to create and quick to share data, but it also means they need synchronisation to avoid race conditions. A crashed process doesn't directly corrupt another process, while one misbehaving thread can bring down its whole process.

A deadlock is when two or more processes wait for each other forever. For example, P1 holds lock A and waits for lock B, while P2 holds B and waits for A.

It needs four conditions at the same time: mutual exclusion, hold and wait, no preemption and circular wait. Breaking any one prevents it. The most practical fix is to always acquire locks in the same global order, which removes circular wait. Other options are timeouts on lock waits, and avoidance algorithms such as the Banker's algorithm.

Virtual memory gives each process the illusion of a large, private, continuous address space, while the operating system maps it onto physical RAM and disk.

Paging is how most systems do it: memory is divided into fixed-size pages (often 4 KB), and a page table maps each virtual page to a physical frame. If a page isn't in RAM, a page fault occurs and the OS loads it from disk. The benefits are isolation between processes, running programs larger than RAM, and simpler allocation. If page faults happen constantly — thrashing — the system slows to a crawl.

A mutex is a lock with an owner: one thread locks it, runs its critical section and the same thread unlocks it, so only one thread is inside at a time.

A semaphore is a counter that allows up to N threads in at once: wait() decrements it and blocks when it reaches zero, and signal() increments it. A binary semaphore looks like a mutex, but it has no owner — any thread can signal it — so it's typically used for signalling between threads, while a mutex protects shared data.

The OSI model describes networking in seven layers, from the bottom up:

1. Physical — bits on the wire or radio
2. Data link — frames between neighbouring devices, MAC addresses, switches
3. Network — routing packets between networks, IP addresses, routers
4. Transport — end-to-end delivery, TCP and UDP, ports
5. Session — opening and managing connections
6. Presentation — data formats, encoding and encryption
7. Application — the protocols apps use, such as HTTP, DNS and SMTP

Real networks follow the simpler TCP/IP model, which merges the top three layers into one application layer.

TCP is connection-oriented and reliable. It sets up a connection with a three-way handshake, numbers every segment, retransmits anything lost, delivers data in order and controls congestion. UDP is connectionless: it sends independent datagrams with no guarantee of delivery or order, which makes it faster and lighter.

Use TCP when every byte must arrive — web pages, file transfers, email. Use UDP when speed matters more than an occasional lost packet — video calls, online games and DNS lookups.

Roughly, in order:

1. The browser checks its cache, then resolves the domain name to an IP address using DNS.
2. It opens a TCP connection to that address — port 443 for HTTPS — and performs a TLS handshake to set up encryption.
3. It sends an HTTP request. The server, often behind a load balancer, processes it and returns a response containing HTML.
4. The browser parses the HTML, requests the CSS, JavaScript and images it references, builds the page and renders it.

Interviewers like an answer that names each step and can go deeper into any one of them when asked.

DNS is the internet's phone book: it turns a name like example.com into an IP address. Your computer asks a resolver — usually your internet provider's or a public one. If the resolver doesn't have the answer cached, it asks a root server, which points it to the .com top-level-domain servers, which point it to the domain's authoritative name server, which returns the IP address. Answers are cached for a set time (the TTL), so most lookups are fast.

HTTPS is HTTP sent over an encrypted TLS connection. With plain HTTP, anyone on the network path can read or change the traffic. With HTTPS, the server proves its identity with a certificate signed by a trusted authority, and the browser and server agree on keys during the TLS handshake, so the data is encrypted and protected against tampering. HTTPS uses port 443 by default; HTTP uses port 80.

Time complexity describes how an algorithm's running time grows as its input grows. Big-O gives an upper bound for large inputs, ignoring constant factors:

• O(1) — constant, like reading an array element by index
• O(log n) — like binary search
• O(n) — one pass over the input
• O(n log n) — efficient sorting, like merge sort
• O(n²) — nested loops, like bubble sort

For example, checking a list for duplicates with two nested loops is O(n²); adding items to a hash set as you go is O(n) on average.

An array stores elements in one continuous block of memory, so reading by index is O(1). Inserting or deleting in the middle is O(n), because the following elements have to shift, and growing it means copying.

A linked list stores nodes anywhere in memory, each pointing to the next. Inserting or deleting at a node you already have is O(1), but finding the i-th element means walking the list, which is O(n). In practice arrays are also faster to scan, because their elements sit next to each other in the CPU cache.

A stack is last-in, first-out (LIFO): you push and pop at the same end, like a pile of plates. It's used for function calls, undo, checking balanced brackets and depth-first search.

A queue is first-in, first-out (FIFO): you add at the back and remove from the front, like a ticket line. It's used for task scheduling, breadth-first search and print queues. Both support O(1) insertion and removal when implemented well.

A hash table stores key–value pairs in an array, using a hash function to turn each key into an index, so lookups, inserts and deletes take O(1) time on average.

A collision is when two keys map to the same index. The two usual fixes are chaining, where each slot holds a small list of entries, and open addressing, where you probe for the next free slot. When the table gets too full — past its load factor, often 0.75 — it grows and re-hashes everything. If many keys collide, operations degrade towards O(n), which is why a good hash function matters.

Binary search finds a value in a sorted array by repeatedly halving the range: compare the target with the middle element, then continue in the left or right half. It runs in O(log n) time.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Common follow-ups: why the array must be sorted, and how you'd change it to find the first occurrence of a repeated value.

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. The base case is the condition where it stops; without one, the calls continue until the call stack overflows.

Example: factorial(n) = n * factorial(n - 1), with the base case factorial(0) = 1. Every recursive call uses stack space, so very deep recursion is often rewritten as a loop, and repeated work can be avoided with memoisation — as in computing Fibonacci numbers.

A compiler translates the whole program into machine code (or bytecode) before it runs, reporting errors up front, and the result usually runs fast — C and C++ work this way. An interpreter translates and runs the program one statement at a time while it executes, which makes experimenting easier but running slower.

Many languages mix the two: Java compiles to bytecode that the JVM interprets and JIT-compiles to native code while the program runs, and Python compiles source to bytecode that its virtual machine executes.