Lesson 1, Interview problem-solving basics

Interview problem-solving basics

Theme

Before grinding patterns, rebuild the solving loop.

A lot of rust is not missing knowledge, it is missing rhythm. The first goal is to become calm and systematic again.

The six-step loop

Clarify the input, output, and edge cases.
Make a tiny example.
Say the brute force out loud.
Ask what data structure removes repeated work.
Code the cleanest version you can explain.
Test edge cases before you submit.

What usually goes wrong

Skipping brute force

People jump straight to an optimized answer and get lost. Brute force gives you a foothold.

Not naming the repeated work

Optimization usually comes from spotting repeated scans, repeated comparisons, or missing memory.

Coding too early

If the idea is fuzzy, code just makes the confusion harder to inspect.

Worked example: Contains Duplicate

Problem idea: given an integer array nums, return true if any value appears at least twice.

Step 1, clarify

Input: an array of integers
Output: boolean
Edge cases: empty array, one element, negative values, repeated values far apart

Step 2, tiny example

[1,2,3,1] should return true
[1,2,3,4] should return false

Step 3, brute force

Compare every pair.

for each i, check all j > i
if any pair matches, return true
otherwise return false

Runtime: O(n^2) Space: O(1)

Step 4, optimize

What repeated work are we doing?

We keep re-checking whether we have seen a value before. A set gives us fast lookup.

Step 5, clean solution

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()

        for num in nums:
            if num in seen:
                return True
            seen.add(num)

        return False

Runtime: O(n) Space: O(n)

Step 6, test

[] → false
[7] → false
[3,3] → true
[1,2,3,4] → false

Pattern takeaway

When a problem quietly asks, “have I seen this before?”, think about:

set
dict or hash map
frequency counting

That one reflex unlocks a lot of beginner interview problems.

Exercises

Do these in order:

#217 — Contains Duplicate Goal: practice the six-step loop without pressure.
#242 — Valid Anagram Goal: compare sorting vs frequency counting.
#1 — Two Sum Goal: use a hash map to trade memory for speed.
#347 — Top K Frequent Elements as a stretch Goal: notice when counting is only the first half of the problem.

Study rule for this week

For each problem:

write the brute force first, even if only in notes
say the runtime out loud
after solving, close the tab and explain the idea from memory

That last part matters. Recognition is weaker than recall.

Next: Lesson 2, Arrays and hashing I