Problem Solving Techniques

Why this lesson matters

In Data Structure and Algorithm Fundamentals, we treated arrays, maps, sets, stacks, queues, heaps, trees, and graphs as tools with cost contracts.

Now we shift into the actual interview skill: choosing the right move under pressure.

For a senior software engineer interview, solving is not just about reaching accepted code. Interviewers watch how you:

• Clarify ambiguous requirements
• Start with a correct baseline
• Identify the bottleneck
• Improve using constraints and patterns
• Explain correctness and tradeoffs

Think of this lesson as your reusable problem-solving operating system.

A repeatable loop

When you see a new problem, avoid jumping directly into code. Use this loop:

1. Restate the problem
2. Ask constraints and edge cases
3. Build a brute-force solution
4. Find the repeated work
5. Choose a technique
6. Prove correctness with an invariant
7. Code cleanly
8. Test with edge cases

The key is step 4: find the repeated work.

Most optimizations are not magic. They remove repeated scanning, repeated sorting, repeated recomputation, or repeated exploration.

As someone with years of LeetCode and HackerRank practice, your next jump is consistency: recognizing why a pattern applies, not merely remembering that it exists.

You are given an array and must find whether any two numbers sum to a target.

Which observation most directly suggests using a hash-based approach?

Baseline, then optimize

A strong interview answer often starts with:

“The brute-force solution checks every pair. That is correct but costs O(n²). The bottleneck is repeated complement search. I can store previous values in a map and reduce lookup to expected O(1).”

That sentence shows maturity: correctness first, optimization second.

Below, the code intentionally prints both approaches so you can compare the thinking.

```java
import java.util.*;

public class Main {
    static int[] twoSumBrute(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }

    static int[] twoSumOptimized(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) {
                return new int[]{seen.get(need), i};
            }
            seen.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;

        System.out.println("Brute: " + Arrays.toString(twoSumBrute(nums, target)));
        System.out.println("Optimized: " + Arrays.toString(twoSumOptimized(nums, target)));
    }
}
```

A brute-force algorithm checks every pair of elements in an array of size n exactly once.

Its time complexity is ____.

When a range moves continuously

Use sliding window when the problem asks about a contiguous subarray or substring and you can maintain useful state while moving two boundaries.

Common signals:

• “Longest substring...”
• “Smallest subarray...”
• “At most K...”
• “No repeated characters...”
• “Sum/product within condition...”

The mental model:

left              right
 ↓                 ↓
[ a, b, c, d, e, f ]

You expand right to include more data, and move left when the window becomes invalid.

The important part is not the syntax. It is the invariant: what condition is always true about the current window?

Example: longest substring without repeats

Invariant:

The current window from left to right contains no duplicate characters.

When adding s.charAt(right) would violate the invariant, move left until the duplicate is removed.

This is stronger than memorizing the problem. You can reuse the same idea for many “longest valid contiguous region” questions.

```java
import java.util.*;

public class Main {
    static int longestUniqueSubstring(String s) {
        Set<Character> window = new HashSet<>();
        int left = 0;
        int best = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);

            while (window.contains(c)) {
                window.remove(s.charAt(left));
                left++;
            }

            window.add(c);
            best = Math.max(best, right - left + 1);
        }

        return best;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("Input: " + s);
        System.out.println("Longest unique substring length: " + longestUniqueSubstring(s));
    }
}
```

True or false:

A sliding window approach is safest when you can clearly define when the current window is valid and update that validity as left and right move.

Binary search beyond sorted arrays

Binary search is not only for finding an element in a sorted array.

You can binary search an answer space when:

1. There is a minimum possible answer
2. There is a maximum possible answer
3. You can test whether a candidate answer is feasible
4. Feasibility is monotonic

Monotonic means:

false false false true true true

Once a capacity works, any larger capacity also works.

Example: minimum ship capacity to deliver packages within D days.

```java
public class Main {
    static boolean canShip(int[] weights, int days, int capacity) {
        int usedDays = 1;
        int current = 0;

        for (int w : weights) {
            if (current + w > capacity) {
                usedDays++;
                current = 0;
            }
            current += w;
        }

        return usedDays <= days;
    }

    static int minCapacity(int[] weights, int days) {
        int low = 0;
        int high = 0;

        for (int w : weights) {
            low = Math.max(low, w);
            high += w;
        }

        while (low < high) {
            int mid = low + (high - low) / 2;

            if (canShip(weights, days, mid)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }

    public static void main(String[] args) {
        int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int days = 5;
        System.out.println("Minimum capacity: " + minCapacity(weights, days));
    }
}
```

Your problem-solving checklist

Before coding:

• Restate the problem in your own words
• Ask about constraints, duplicates, ordering, nulls, and overflow
• Name a brute-force solution
• Identify the bottleneck
• Choose a technique based on the bottleneck

While coding:

• Keep variables meaningful
• Preserve the invariant
• Handle edge cases early if it simplifies the main logic
• Talk through complexity as you go

After coding:

• Test a normal case
• Test a boundary case
• Test a case that breaks naive logic
• State time and space complexity clearly

This lesson turns your DSA fundamentals into interview execution. Next, we will zoom out from algorithmic problem solving into System Design and Scalability, where tradeoffs move from code-level efficiency to architecture-level decisions.