DSA Study Plan & Complexity

Your GPS before writing a single line of code

Imagine you're lost in a city and need to get somewhere fast. You wouldn't just start running in a random direction — you'd look at a map first, find your location, figure out the fastest route, and then move. DSA interviews are the same. Big-O complexity is your map. The constraint in the problem statement (n ≤ 10⁵) tells you exactly which "road" you're allowed to take before you've solved anything.

🧭 The navigator's reflex: Before writing any code, read n. If n ≤ 10⁵ and time limit is 1 second, an O(n²) solution would need ~10¹⁰ operations — roughly 100 seconds. That's impossible. Your map says: take the O(n log n) road. This single reflex separates strong candidates from everyone else.

What SDE2 DSA actually tests

Not "do you know the trick" — it's: can you recognize the pattern, state the complexity, write clean code, handle edge cases, and communicate while doing it. Talk through the brute force, name the bottleneck, then optimize. A working O(n log n) you can explain beats a buggy O(n) you can't.

Big-O complexity: cheat sheet

The input-size → complexity trick

The constraint tells you the target complexity before you've solved anything:

Pattern recognition — signal → technique

How to communicate while coding

1. Restate the problem + ask about edge cases (empty, duplicates, negatives, overflow).
2. State brute force + its complexity.
3. Name the bottleneck and the pattern that removes it.
4. Code, narrating invariants.
5. Dry-run a small example; then state final time/space.

Complexity examples in code

# O(n) — single pass, two-pointer style
def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

# O(n log n) — sort then linear scan
def contains_duplicate(nums):
    nums.sort()              # O(n log n)
    for i in range(len(nums) - 1):   # O(n)
        if nums[i] == nums[i + 1]:
            return True
    return False

// O(n) — hash map lookup
import java.util.HashMap;

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {
                return new int[]{seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[]{};  // guaranteed to have solution
    }
}

// O(n log n) — sort + binary search
#include <vector>
#include <algorithm>
using namespace std;

bool containsDuplicate(vector<int>& nums) {
    sort(nums.begin(), nums.end());  // O(n log n)
    for (int i = 0; i + 1 < (int)nums.size(); i++) {
        if (nums[i] == nums[i + 1]) return true;
    }
    return false;
}

Think it through

Before solving anything, interviewers expect two instant reflexes: read the complexity of code you're looking at, and read the target complexity off the constraints. Practise both before revealing.

Practice — climb the ladder

Check yourself — pattern recognition speed test

Visualize complexity growth