CS fundamentals every dev should know.
2 topics
Fundamental linear data structures. Arrays: O(1) access by index, O(n) insert/delete. Linked lists: O(1) insert/delete at known position, O(n) access. Stacks (LIFO): push/pop for undo, parsing, DFS. Queues (FIFO): enqueue/dequeue for BFS, scheduling. Choose based on access patterns.
2 resources
Trees: binary trees, BSTs (O(log n) search), AVL/Red-Black (self-balancing), heaps (priority queues), tries (prefix matching). Graphs: adjacency list/matrix, BFS, DFS, shortest path (Dijkstra, Bellman-Ford), topological sort. Hash tables: O(1) average lookup, collision handling (chaining, open addressing).
Sorting: comparison-based (quicksort O(n log n) avg, mergesort O(n log n) stable, heapsort) and non-comparison (counting sort, radix sort O(nk)). Searching: binary search O(log n) on sorted data. Big-O notation for time and space complexity analysis. Amortized analysis for dynamic arrays.
Dynamic programming: solve overlapping subproblems by caching results. Identify: optimal substructure + overlapping subproblems. Approaches: top-down (memoization) vs bottom-up (tabulation). Classic problems: fibonacci, knapsack, LCS, edit distance. Greedy: make locally optimal choices (Huffman coding, activity selection). Divide and conquer: merge sort, quicksort.
OS manages hardware resources for programs. Processes vs threads, context switching, scheduling algorithms (round-robin, priority). Memory: virtual memory, paging, page faults, cache hierarchy (L1/L2/L3). Concurrency: mutexes, semaphores, deadlocks (prevention, detection). File systems: inodes, journaling, permissions.
How the internet works: TCP/IP layers, DNS resolution, HTTP request lifecycle, TLS handshake. Transport layer: TCP (reliable, ordered) vs UDP (fast, unreliable). Application protocols: HTTP/2, WebSockets, gRPC. Network security: firewalls, encryption, certificates. Understand latency, bandwidth, and throughput.