Stanford CS106B - Programming Abstractions & Data Structures in C++ Flashcards

Question 1

Pass-by-Value vs. Pass-by-Reference in C++

Accepted Answer

**Pass-by-Value** (`void fn(int x)`) creates a full copy of the variable, leaving the original caller variable unchanged.

**Pass-by-Reference** (`void fn(int& x)`) passes an alias to the original memory location, allowing direct modification.

**Const Reference** (`void fn(const Vector<int>& v)`) avoids copying large data structures while preventing modifications.

Question 2

Base Case vs. Recursive Step

Accepted Answer

Every valid recursive function requires:
1. **Base Case**: The simplest terminal condition that solves the problem directly without recursive calls.
2. **Recursive Step**: Breaks the problem into smaller self-similar subproblems and advances toward the base case.

Question 3

Recursive Backtracking Core Template

Accepted Answer

The canonical pattern for exploring all choices (e.g., N-Queens, Sudoku, Subsets):
```cpp
void solve(State& state) {
    if (isSolution(state)) {
        process(state);
        return;
    }
    for (Choice choice : choices) {
        if (isValid(choice)) {
            makeChoice(state, choice);   // Choose
            solve(state);               // Explore
            undoChoice(state, choice);   // Unchoose
        }
    }
}
```

Question 4

Raw Pointer vs. Reference Syntax & Behavior

Accepted Answer

- **Reference** (`int& ref = x;`): Must be initialized upon declaration, cannot be reassigned to point elsewhere, and cannot be `nullptr`.
- **Pointer** (`int* ptr = &x;`): Variables storing memory addresses. Can be reassigned, set to `nullptr`, and manipulated using pointer arithmetic.

Question 5

Dynamic Memory Allocation: `new` and `delete`

Accepted Answer

Allocates and frees memory manually on the **Heap** (Free Store):
- Single element: `int* p = new int(10);` -> freed via `delete p;`
- Dynamically sized array: `int* arr = new int[size];` -> freed via `delete[] arr;`

*Rule*: Every call to `new`/`new[]` must have a corresponding call to `delete`/`delete[]` to prevent memory leaks.

Question 6

Dangling Pointer vs. Memory Leak

Accepted Answer

- **Memory Leak**: Heap memory is allocated with `new`, but all pointers referencing it are lost before calling `delete`. The memory remains inaccessible until program exit.
- **Dangling Pointer**: A pointer that points to a memory address that has already been deallocated using `delete`.

Question 7

Big-O Formal Definition

Accepted Answer

A function $f(n)$ is $O(g(n))$ if there exist positive constants $c$ and $n_0$ such that:
$$f(n) \le c \cdot g(n) \quad 	ext{for all } n \ge n_0$$

It establishes an upper bound on time or space complexity in the worst-case scenario as input size $n$ grows toward infinity.

Question 8

Amortized $O(1)$ Time Complexity (Dynamic Array Expansion)

Accepted Answer

When a custom `Vector` fills its underlying array, it allocates a new array of double the size and copies elements ($O(n)$ cost).

Because doubling occurs infrequently (after $1, 2, 4, 8, \dots$ insertions), the total cost of $n$ pushes is $O(n)$, making the **amortized cost per push** $O(1)$.

Question 9

Stack Abstract Data Type (ADT)

Accepted Answer

A **Last-In, First-Out (LIFO)** data structure.

- Key operations: `push(val)` ($O(1)$), `pop()` ($O(1)$), `peek()`/`top()` ($O(1)$).
- Common use cases: Managing function call stacks, recursive evaluation, expression parsing, and undo stacks.

Question 10

Queue Abstract Data Type (ADT)

Accepted Answer

A **First-In, First-Out (FIFO)** data structure.

- Key operations: `enqueue(val)` ($O(1)$), `dequeue()` ($O(1)$), `peek()`/`front()` ($O(1)$).
- Efficient array implementation requires a **circular array** strategy using modulo arithmetic (`(rear + 1) % capacity`) to prevent shifting elements.

Question 11

Singly Linked List Node Structure & Prepending

Accepted Answer

Basic C++ node struct:
```cpp
struct ListNode {
    int data;
    ListNode* next;
};
```

To prepend value `v` in $O(1)$ time:
```cpp
ListNode* newNode = new ListNode{v, head};
head = newNode;
```

Question 12

Map ADT: `std::map` vs `std::unordered_map`

Accepted Answer

- `std::map` (or Stanford `Map`): Implemented as a self-balancing **Red-Black Binary Search Tree**. Keeps keys sorted. Search, insert, and delete take $O(\log n)$ time.
- `std::unordered_map` (or Stanford `HashMap`): Implemented using a **Hash Table**. Unordered key storage. Search, insert, and delete average $O(1)$ time.

Question 13

Set ADT: Trees vs. Hash Tables

Accepted Answer

Stores unique elements only.
- **`Set` (Tree-based)**: Maintains ordered elements via BST. Operations take $O(\log n)$ time.
- **`HashSet` (Hash-based)**: Unordered storage via Hash Table. Operations take $O(1)$ average time.

Question 14

Rule of Three (C++ Resource Management)

Accepted Answer

If a class manages dynamic memory (raw pointers), it must explicitly define all three of the following to prevent shallow copy bugs:
1. **Destructor** (`~ClassName()`) - frees heap memory.
2. **Copy Constructor** (`ClassName(const ClassName& other)`) - deep copy.
3. **Copy Assignment Operator** (`ClassName& operator=(const ClassName& other)`) - deep copy.

Question 15

Deep Copy vs. Shallow Copy

Accepted Answer

- **Shallow Copy**: Copies field values directly. If a member is a pointer, both objects end up pointing to the exact same heap memory, leading to double-free errors.
- **Deep Copy**: Allocates new heap memory for the destination object and copies the actual underlying values.

Question 16

Binary Search Tree (BST) Invariant

Accepted Answer

For every node $N$ in a valid BST:
- All values in $N$'s **left subtree** are strictly less than $N$'s value ($< N$).
- All values in $N$'s **right subtree** are strictly greater than $N$'s value ($> N$).

An **in-order traversal** of a BST visits nodes in sorted ascending order.

Question 17

Hash Table Collisions: Separate Chaining

Accepted Answer

A collision occurs when two distinct keys produce the same hash index (`hash(key) % buckets`).

**Separate Chaining** resolves collisions by storing a singly linked list at each array bucket index. Average lookup is $O(1)$ when the **Load Factor** $\alpha = \frac{N}{	ext{buckets}}$ is kept small (typically $\alpha < 0.7$).

Question 18

Destructor Mechanics in C++

Accepted Answer

A class destructor runs automatically when an object goes out of scope or is explicitly deleted via `delete`.

```cpp
class VectorList {
private:
    int* elements;
public:
    ~VectorList() {
        delete[] elements; // Prevents memory leak
    }
};
```

Question 19

Time Complexity Hierarchy Ranking

Accepted Answer

From fastest to slowest growth rates:

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$$

- Algorithms with $O(2^n)$ or $O(n!)$ are intractable for large input sizes $n$.

Question 20

Stack Frame & Call Stack Execution

Accepted Answer

When a function is called, a **stack frame** containing local variables, arguments, and return addresses is pushed onto the system call stack.

In recursion, each recursive step pushes a new frame. Unbounded recursion causes a **Stack Overflow** by exhausting allocated call stack memory.

Stanford CS106B - Programming Abstractions & Data Structures in C++

Cards in this deck

Related Flashcard Sets

STANFORD CS106B - Programming Abstractions & Recursive Problem Solving

TypeScript - Advanced Type Systems, Generics & Design Patterns

Harvard ECON1011 - Intermediate Microeconomics: Game Theory & Market Structures

MIT 18.03 - Differential Equations: Ordinary Differential Equations, Laplace & Fourier