Interview Idiom Drills

Your C++ interview toolkit

Everything below is a one-liner combination of things you built in this course.

The drill in this lesson is the most famous interview problem of all, Two Sum, which asks for two numbers in a list that add to a target.

The hash-map insight is to reframe the question. For each value x, instead of searching for a partner, ask whether target minus x has already been seen. That turns a search into a lookup, giving one pass with O(1) average work per element for O(n) total, against the O(n²) of checking every pair.

Two Sum, complete

The input is n, then n numbers, then the target, and the program prints the 0-based positions of the pair.

#include <iostream>
#include <vector>
#include <unordered_map>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; i++) std::cin >> v[i];
    int target;
    std::cin >> target;

    std::unordered_map<int, int> seen;   // value -> index where we saw it
    for (int i = 0; i < n; i++) {
        int need = target - v[i];
        if (seen.count(need)) {
            std::cout << seen[need] << " " << i << "\n";
            return 0;
        }
        seen[v[i]] = i;
    }
    std::cout << "no pair\n";
    return 0;
}

Input

5
2 7 11 15 1
9

Output

0 1

The map stores value to index rather than the other way around, because the lookup is by value. Getting that direction backwards is the most common way this solution goes wrong, and it produces code that compiles and finds nothing.

seen.count(need) is used rather than seen[need], and lesson 9-1 explains why that matters. Indexing would insert need with a value of 0 on every miss, quietly filling the map with junk and, worse, making a later element pair with a phantom index of 0.

The return 0; inside the loop is what makes the trailing no pair line correct, since reaching the bottom of main means every element was checked without a match.

The complexity of the Two Sum solution

The program visits each of the n elements once and does one average-O(1) map lookup plus one insert per element, so its overall time complexity is O(n), linear time.

Each element triggers a constant amount of average-case work, so the total grows in direct proportion to n. Applying lesson 8-4's rules, the loop is O(n) and the constant work inside it contributes no additional factor.

The brute-force alternative tries every pair with two nested loops, giving O(n²). On an input of 100,000 elements that is the difference between about 100,000 operations and about 10,000,000,000, which is the difference between instant and a time-limit failure.

The memory cost moves in the opposite direction, and an interviewer may well ask about it. The brute force uses O(1) extra space while the map version uses O(n), so this is a deliberate trade of memory for time, which is the most common shape of optimization in interview problems.

Worth stating honestly: the O(1) lookup is an average, and a hash table's worst case is O(n) per lookup if every key collides. That makes the true worst case O(n²), which is why a map version with a guaranteed O(n log n) is sometimes the safer answer against adversarial input.

Why the two positions cannot be the same

The pair is guaranteed to come from two different positions because v[i] is inserted into seen only after the check for its complement, so any match must have come from an earlier index.

The order of the two statements inside the loop carries the whole guarantee. Check first, insert second. When the check succeeds, the stored index came from a previous iteration, so it is strictly less than i.

Reversing them would break it in a specific case. With insert-before-check, an element could pair with itself whenever the target is exactly twice that element's value, so an input of 4 with a target of 8 would report position 0 twice.

The current order handles that case correctly. A genuine pair of two 4s at different positions is still found, because the first 4 is in the map by the time the second one is checked, while a lone 4 is not. Details of this kind are exactly what interviewers probe once the main idea is on the board.

Where to go from here

You now hold the working core of C++: the compile model (unit 1), types and control flow (units 2-3), functions, references, and recursion (unit 4), pointers and memory (units 5-6), classes (unit 7), and the STL with its big-O cost model (units 8-9), capped by the contest habits of unit 10.

Next steps:

1. Practice on the DSA platform. Pick easy problems, choose C++ as your language, and reuse this unit's template. Fluency comes from repetition, not rereading.
2. Deepen the memory story when you are ready: copy vs move semantics, the rule of three/five, shared_ptr, and templates are the natural next layer.
3. Read real C++. Standard library documentation and well-written open source will keep stretching you.

The language rewards exactly what interviews reward: knowing what your code costs, down to the byte and the pass.

First non-repeating character

Two passes over the same word. The first counts every character, and the second finds the earliest one with a count of 1.

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::string w;
    std::cin >> w;

    std::unordered_map<char, int> freq;
    for (char c : w) {
        freq[c]++;
    }

    for (char c : w) {
        if (freq[c] == 1) {
            std::cout << c << "\n";
            return 0;
        }
    }

    std::cout << "none\n";
    return 0;
}

Input

swiss

Output

w

Two passes are necessary rather than wasteful. A single pass cannot know whether the s at position 0 repeats later, so the counts have to be complete before any decision is made.

The second pass walks the word rather than the map, and that is what makes the answer the first such character. Iterating the unordered_map would find a character with a count of 1 but in an arbitrary order, and even a map would give the alphabetically smallest rather than the earliest.

In swiss, the counts are s appearing three times, w once, and i once. Both w and i are non-repeating, and w wins because it comes first in the word.

The return 0; inside the loop is what keeps the trailing none line from printing after a successful answer, and the whole thing runs in O(n) with two linear passes, which lesson 8-4's addition rule keeps at O(n).