Problem Solving Techniques

Why this lesson matters

You have already worked through the main interview toolkits:

• Introduction to Data Structures and Algorithms gave you representation-first thinking.
• Dynamic Programming trained you to define states as contracts.
• Graph Algorithms gave you traversal, connectivity, and shortest-path loops.
• Tree Algorithms sharpened recursive return contracts and invariants.

Now we zoom out. The final skill is not memorizing more patterns. It is deciding which lens to use, under pressure, when the problem is disguised.

In interviews, strong candidates do not jump straight to code. They build a path from ambiguity to implementation.

A repeatable loop

When a problem feels new, use this loop:

Clarify → Model → Brute Force → Find Bottleneck → Choose Pattern → Prove → Code → Test

Each step has a job:

• Clarify: inputs, outputs, constraints, edge cases.
• Model: array, graph, tree, interval set, state machine, search space.
• Brute Force: establish correctness before optimization.
• Find Bottleneck: repeated work, expensive lookup, exploding branches.
• Choose Pattern: DP, BFS, DFS, heap, two pointers, binary search, union-find, etc.
• Prove: invariant, monotonicity, state contract, or traversal guarantee.
• Code: small functions, clear names, safe types.
• Test: edge, typical, adversarial.

This loop is the bridge between knowing algorithms and solving interview problems.

You receive a new coding interview problem and immediately recognize that it might involve graphs, DP, or greedy reasoning.

What is usually the best first move?

Brute force is not failure

A brute-force solution is often the cleanest way to reveal the bottleneck.

Example: count pairs whose sum equals a target.

Naive idea:

Try every pair → O(n^2)

Bottleneck:

For each x, repeatedly search for target - x

Pattern upgrade:

Use a frequency map of values already seen

This is the same discipline you used in DP: identify repeated work, then store the right information.

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

int countPairsWithSum(const vector<int>& a, int target) {
    unordered_map<int, int> seen;
    int ans = 0;

    for (int x : a) {
        ans += seen[target - x];
        seen[x]++;
    }
    return ans;
}

int main() {
    vector<int> a = {1, 5, 7, -1, 5};
    cout << countPairsWithSum(a, 6) << "\n"; // 3
    return 0;
}
```

When the answer space is ordered

Some problems are not asking you to find a path, state, or traversal. They are asking for the smallest feasible value or largest valid value.

Look for phrases like:

• minimum speed
• maximum capacity
• smallest distance
• largest minimum value
• can finish within k

The key proof is monotonicity:

If speed s works, then any speed greater than s also works.

Once that is true, binary search on the answer becomes a powerful interview technique.

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

long long hoursNeeded(const vector<int>& piles, int speed) {
    long long hours = 0;
    for (int p : piles) {
        hours += (p + speed - 1) / speed;
    }
    return hours;
}

bool canFinish(const vector<int>& piles, int h, int speed) {
    return hoursNeeded(piles, speed) <= h;
}

int minEatingSpeed(vector<int> piles, int h) {
    int lo = 1;
    int hi = *max_element(piles.begin(), piles.end());

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, h, mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

int main() {
    vector<int> piles = {3, 6, 7, 11};
    cout << minEatingSpeed(piles, 8) << "\n"; // 4
    return 0;
}
```

True or false:

If a feasibility function changes only once from false to true, then binary search on the answer may be appropriate.

Every pattern needs a reason

A solution is interview-ready when you can state why it stays correct.

Use the right proof language:

Technique Proof handle Sliding window Window invariant Binary search Monotonic feasibility DP State contract and transition completeness BFS First time reached is shortest in unweighted levels DFS State colors, postorder, or recursion contract Trees Return value contract per subtree Greedy Exchange argument or local choice invariant

This is how you avoid code that merely passes samples. You connect the implementation to a property that cannot be accidentally true.

Before coding a DP solution, define the meaning of each ____ as a contract.

One problem, multiple lenses

Consider a problem like:

Find the cheapest flight from src to dst with at most k stops.

A weaker approach says: this is a graph problem, so use Dijkstra.

A stronger approach asks:

1. Model: airports are nodes, flights are weighted directed edges.
2. Constraint twist: normal shortest path is not enough because stops matter.
3. State: node plus number of edges used.
4. Pattern blend: graph traversal with DP-like state tracking.
5. Proof: we compare costs only under the same or better stop budget.

That is the final course theme: real interview problems often combine earlier lessons. Your job is to preserve the right contract while adapting the pattern.

Testing is part of problem solving

Before you say done, run a small mental test suite:

• Empty or smallest valid input
• One element or one node
• Duplicates
• Negative values if allowed
• Already sorted or reverse sorted
• Disconnected graph
• Skewed tree
• Large values that may overflow int

In C++, a tiny harness can keep your thinking disciplined. During a real interview, you may not write this exact helper, but you should think this way out loud.

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

int maxSubarray(const vector<int>& nums) {
    int best = nums[0];
    int cur = nums[0];

    for (int i = 1; i < (int)nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);
        best = max(best, cur);
    }
    return best;
}

void check(const string& name, int got, int want) {
    cout << name << ": " << (got == want ? "PASS" : "FAIL")
         << " got=" << got << " want=" << want << "\n";
}

int main() {
    check("mixed", maxSubarray({-2, 1, -3, 4, -1, 2, 1, -5, 4}), 6);
    check("all negative", maxSubarray({-8, -3, -6}), -3);
    check("single", maxSubarray({5}), 5);
    return 0;
}
```

Your final interview checklist

When you face a new problem, walk this path:

1. Restate the task and examples.
2. Ask constraints before choosing complexity.
3. Choose representation before choosing algorithm.
4. Start with brute force to expose the bottleneck.
5. Match the bottleneck to a known pattern.
6. State the correctness handle: invariant, contract, monotonicity, or traversal guarantee.
7. Code in small pieces with safe C++ types.
8. Test edge cases before optimizing further.

You now have the full course arc: data structures for modeling, DP for repeated choices, graphs for relationships, trees for recursive structure, and problem-solving techniques for choosing among them.

That is what interviewers are really measuring: not whether you have seen the exact question, but whether you can turn an unfamiliar problem into a familiar structure.