Computer science exams and interviews both test the same underlying set of concepts repeatedly — data structures, complexity, and object-oriented design. This guide organizes them into a single exam-ready reference, with the reasoning behind each concept, not just the definition.
Programming Fundamentals
Variables and data types: A variable is a named storage location; its data type (integer, float, string, boolean) determines what kind of value it can hold and how much memory it uses. Type mismatches are one of the most common sources of runtime errors in typed languages.
Control structures:
- Conditionals (if/else) execute code based on a boolean condition
- Loops (for, while) repeat a block of code — a
forloop is typically used when the number of iterations is known in advance, awhileloop when it depends on a condition being met
Functions: A function groups reusable code under a name, taking inputs (parameters) and optionally returning an output. Understanding scope (which variables a function can access) and return values (what a function passes back to the caller) is essential before moving to more complex topics.
Data Structures
Arrays: Fixed-size, contiguous memory blocks with O(1) access time by index, but O(n) time to insert or delete in the middle (since remaining elements must shift).
Linked lists: A sequence of nodes, each pointing to the next. Insertion and deletion are O(1) if you already have a reference to the relevant node, but O(n) to search for a specific value since you must traverse from the head.
Stacks: Last-In-First-Out (LIFO) — think of a stack of plates. Core operations: push (add to top), pop (remove from top), peek (view top without removing). Used in function call management, undo features, and expression evaluation.
Queues: First-In-First-Out (FIFO) — think of a line at a checkout counter. Core operations: enqueue (add to back), dequeue (remove from front). Used in task scheduling and breadth-first search.
Trees: A hierarchical structure with a root node and child nodes. A binary search tree keeps left children smaller and right children larger than their parent, giving O(log n) search time on average — but this degrades to O(n) if the tree becomes unbalanced (essentially a linked list).
Hash tables: Store key-value pairs using a hash function to compute an index, giving average O(1) lookup, insertion, and deletion. Collisions (two keys hashing to the same index) are handled via chaining (a list at each index) or open addressing (finding the next free slot).
Graphs: A set of nodes (vertices) connected by edges, either directed or undirected, weighted or unweighted. Represented as an adjacency matrix (a 2D grid, good for dense graphs) or an adjacency list (a list per node, good for sparse graphs).
Algorithm Complexity (Big O Notation)
Big O describes how an algorithm’s runtime or memory use grows as input size increases:
- O(1) — constant time, regardless of input size (e.g., array access by index)
- O(log n) — logarithmic, grows very slowly (e.g., binary search)
- O(n) — linear, grows proportionally with input (e.g., a single loop through an array)
- O(n log n) — typical of efficient sorting algorithms (merge sort, quicksort on average)
- O(n²) — quadratic, common in nested loops (e.g., bubble sort)
Why this matters beyond exams: an O(n²) algorithm that runs fine on 100 items can become unusably slow on 100,000 items — Big O is really about predicting how an algorithm scales, not just describing it in the abstract.
Object-Oriented Programming (OOP)
The four pillars:
- Encapsulation — bundling data and the methods that operate on it within a class, restricting direct access to internal details (using private/protected access modifiers)
- Inheritance — a class (child/subclass) can inherit properties and methods from another class (parent/superclass), promoting code reuse
- Polymorphism — objects of different classes can be treated through a common interface, with each responding to the same method call in its own way (e.g., a
speak()method that behaves differently for aDogclass versus aCatclass) - Abstraction — hiding complex implementation details behind a simple interface, so a user of a class doesn’t need to know how it works internally to use it
Class vs. object: A class is a blueprint (e.g., “Car”); an object is a specific instance created from that blueprint (e.g., “my red Honda Civic”). Confusing these two is one of the most common conceptual errors for students new to OOP.
Common Sorting Algorithms
- Bubble sort: Repeatedly swaps adjacent elements if they’re in the wrong order — simple to understand, O(n²), rarely used in practice due to inefficiency.
- Selection sort: Repeatedly finds the minimum element and moves it to its correct position — also O(n²), slightly fewer swaps than bubble sort.
- Merge sort: Divides the array in half recursively, sorts each half, then merges them — reliably O(n log n), stable, but requires extra memory.
- Quicksort: Picks a pivot element and partitions the array around it — O(n log n) on average, but O(n²) in the worst case (rare with good pivot selection).
Exam and Interview Technique Notes
- Trace through code by hand before assuming what it does — this catches logic errors that are easy to miss just by reading.
- Always consider edge cases: empty input, a single element, duplicate values, and very large inputs — these are where most bugs and incorrect complexity assumptions surface.
- State the Big O of your solution explicitly when asked to solve a problem — interviewers and exams often specifically want this stated, not just implied.
- Draw data structures before coding them — a quick sketch of a linked list or tree operation prevents pointer-logic mistakes that are hard to debug after the fact.
Frequently Asked Questions
Which data structure should I use for fast lookups? A hash table, when you need average O(1) lookup by key and don’t need the data sorted; use a balanced binary search tree instead if you need the data to stay sorted.
What’s the practical difference between a stack and a queue? A stack processes the most recently added item first (useful for undo operations and function call tracking); a queue processes the oldest added item first (useful for task scheduling and order-preserving processing).
Why does my quicksort implementation sometimes run slowly? Likely a poor pivot choice (e.g., always picking the first element) on already-sorted or reverse-sorted data, which triggers quicksort’s O(n²) worst case — randomizing the pivot choice usually fixes this.
Is understanding Big O actually necessary, or just theoretical? It’s practical — it’s how you predict whether a solution will work at scale before you’ve actually run it on large data, and it’s a near-universal expectation in technical interviews.