Computer Science Fundamentals
Understand the layers beneath your code — how CPUs execute programs, how memory hierarchies work, how processes and threads enable concurrency, and how networks connect everything together.
How Computers Process Programs
The CPU, memory, instruction execution, floating point, Unicode, and data representation.
-
- Explain the fetch-decode-execute cycle
- Describe ALU operations
- Identify CPU registers
-
- Explain IEEE 754 floating point representation
- Describe Unicode and UTF-8 encoding
- Define endianness
-
- Describe the compilation pipeline
- Contrast compiled vs interpreted languages
- Inspect Python bytecode
Caches
LRU cache implementation, CPU cache hierarchy, locality, and performance implications.
- [ ] LRU Cache
- Explain cache eviction policies
- Implement LRU cache with O(1) get and put
-
- Describe L1, L2, and L3 cache levels
- Explain cache lines and locality
- Identify performance implications
Processes & Threads
Process abstraction, threads, concurrency, synchronization, and deadlock.
- [ ] Processes
- Define process and its resources
- Explain process creation (fork/exec)
- Describe context switching
-
- Distinguish thread from process
- Explain the shared memory model
- Identify concurrency hazards
-
- Use locks, mutexes, and semaphores
- Explain deadlock conditions and prevention
Networking
TCP/IP model, TCP vs UDP, HTTP, sockets, DNS, and subnetting.
-
- Describe the TCP/IP model
- Compare TCP vs UDP
- Explain IP addressing
- [ ] HTTP & the Web
- Explain the HTTP request/response cycle
- Describe HTTPS and TLS
- Identify HTTP methods and status codes
- [ ] Sockets & DNS
- Implement a basic socket client and server
- Explain DNS resolution
- Describe subnetting
Tries & String Searching
Trie structure, autocomplete, string search algorithms (brute force, KMP, Rabin-Karp).
- [ ] Tries
- Explain trie structure
- Implement insert, search, and prefix operations
- Analyze time complexity of trie operations
-
- Implement brute-force string search
- Describe KMP and Rabin-Karp algorithms
- Compare string search approaches
Combinatorics, Probability & Information Theory
Factorials, permutations, combinations, probability, entropy, Huffman coding, cryptography basics.
-
- Calculate factorials, permutations, and combinations
- Apply basic probability rules
-
- Define information entropy
- Explain Huffman coding
- Describe basic compression
-
- Explain symmetric vs asymmetric encryption
- Describe hash functions
- Identify common cryptographic algorithms
NP-Completeness & Complexity Classes
P, NP, NP-complete, reductions, classic intractable problems, approximation algorithms.
-
- Define P, NP, and NP-complete
- Explain polynomial-time reductions
- Recognize NP-complete problems
-
- Identify TSP, knapsack, SAT as NP-complete
- Describe approximation algorithms
Advanced Data Structures
Balanced trees (AVL, red-black, B-tree), probabilistic structures (Bloom filter, HyperLogLog), union-find, k-D trees, treaps.
-
- Explain AVL trees and rotations
- Describe red-black tree properties
- Compare balanced tree variants
-
- Explain Bloom filter
- Describe HyperLogLog
- Identify skip list structure
-
- Implement union-find with path compression and rank
- Describe k-D trees
- Describe treaps