Introduction to Data Structures and Algorithms

Why start here?

This course is not about memorizing 300 interview questions. It is about building the judgment to see the structure underneath a new problem quickly.

Even if you have solved FAANG-style questions before, interviews often fail candidates at the foundation layer:

• Choosing the wrong representation
• Missing an invariant
• Optimizing the wrong operation
• Ignoring constraints hidden in the input size
• Writing code that is asymptotically fine but practically brittle

In this first lesson, we will reset the mental model for data structures and algorithms. Later lessons will go deeper into Dynamic Programming, Graph Algorithms, Tree Algorithms, and Problem Solving Techniques.

Data structures are representations

A data structure is not just a container. It is a set of tradeoffs around operations.

Before choosing one, ask:

Question Why it matters What operation is most frequent? Lookup, insert, delete, min/max, traversal, range query Is order meaningful? Original order, sorted order, priority order, hierarchy Are duplicates allowed? Set vs multiset vs frequency map Do we need random access? Array-like structures shine here Is the input static or dynamic? Preprocessing may be worth it for many queries

Interview problems usually hide the correct data structure inside the verbs: find, count, merge, schedule, rank, connect, group, stream, undo.

Same data, different costs

A strong interview solution often starts by matching the access pattern to the structure.

• Need index-based access? vector is usually the default.
• Need fast front and back operations? deque is useful.
• Need fast membership checks? unordered_set or unordered_map.
• Need sorted traversal? set or map, with logarithmic updates.

The goal is not to know every STL container. The goal is to know what each one makes cheap.

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> scores = {70, 85, 92, 88};
    cout << "Random access scores[2]: " << scores[2] << '\n';

    deque<string> tasks;
    tasks.push_back("compile");
    tasks.push_front("read input");
    cout << "First task: " << tasks.front() << '\n';
    cout << "Last task: " << tasks.back() << '\n';

    unordered_set<int> seen = {10, 20, 30};
    cout << "Has 20? " << (seen.count(20) ? "yes" : "no") << '\n';
    cout << "Has 99? " << (seen.count(99) ? "yes" : "no") << '\n';

    return 0;
}
```

You are processing up to 1,000,000 user IDs. For each incoming ID, you only need to know whether it has appeared before. You do not need sorted order.

Which C++ structure is usually the best first choice?

Big-O is the start, not the finish

In interviews, asymptotic complexity is essential, but senior-level reasoning goes further.

Consider these dimensions:

• Worst-case vs average-case: Hash tables are average-case constant time, but worst-case can degrade.
• Amortized cost: A vector::push_back is usually O(1), even though occasional resizes are O(n).
• Memory pressure: An O(n) extra array may be impossible if n is huge.
• Cache locality: Contiguous arrays often outperform pointer-heavy structures in practice.
• Input constraints: n = 40 suggests exponential with pruning may be viable; n = 10^5 usually demands near-linear or n log n.

A good interviewer wants to hear both the math and the engineering tradeoff.

True or false:

Binary search is a valid way to find an element in any vector as long as the element exists somewhere in the vector.

Every algorithm has a state and an invariant

When you explain a solution, do not only say what the code does. Say what remains true after every step.

Example: first duplicate in a stream-like scan.

State:

• seen: all values encountered before the current index

Invariant:

• Before processing nums[i], seen contains exactly nums[0..i-1]

That invariant makes the correctness argument short: if nums[i] is already in seen, it appeared earlier, so it is the first duplicate discovered by left-to-right order.

```cpp
#include <bits/stdc++.h>
using namespace std;

int firstDuplicate(const vector<int>& nums) {
    unordered_set<int> seen;

    for (int x : nums) {
        if (seen.count(x)) return x;
        seen.insert(x);
    }

    return -1;
}

int main() {
    vector<int> nums = {4, 7, 2, 9, 7, 2};
    cout << "First duplicate: " << firstDuplicate(nums) << '\n';
    return 0;
}
```

A vector sometimes performs an expensive resize, but over a long sequence of push_back operations the average cost per insertion is O(1).

This is called ____ analysis.

Convert problem language into structure

Interview problems often disguise familiar operations. Train yourself to translate from story to structure.

Problem signal Likely structural idea Need to remember what appeared Hash set or hash map Need counts or grouping Frequency map Need most urgent, smallest, or largest repeatedly Heap or ordered structure Need last-in-first-out behavior Stack Need breadth-style processing Queue Need relationships between entities A representation of connections Need parent-child hierarchy A hierarchical representation

We will go deeper on connection-heavy and hierarchy-heavy problems in the Graph Algorithms and Tree Algorithms lessons. For now, focus on recognizing the structural signal before coding.

Know the STL defaults

In C++ interviews, the STL lets you express the right data structure quickly. But defaults matter.

A common example: priority_queue<int> is a max-heap by default. To get a min-heap, you must provide greater<int>.

This matters because many scheduling, ranking, and streaming problems rely on repeatedly extracting the best next candidate.

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;

    for (int x : {5, 1, 9, 3}) {
        maxHeap.push(x);
        minHeap.push(x);
    }

    cout << "Max-heap top: " << maxHeap.top() << '\n';
    cout << "Min-heap top: " << minHeap.top() << '\n';

    map<string, int> orderedCounts;
    orderedCounts["banana"] = 2;
    orderedCounts["apple"] = 3;
    orderedCounts["cherry"] = 1;

    cout << "Ordered keys:";
    for (auto [key, value] : orderedCounts) {
        cout << ' ' << key;
    }
    cout << '\n';

    return 0;
}
```