Stan Runge

Big O & Complexity theory
Arrays & hashmaps
2-pointers / sliding window
Strings
Stacks/queues, linked lists
Trees + BFS/DFS
Talk out loud

A hashmap is a data structure that shows up a LOT, especially in beginner questions. If you learn nothing else, just know that you can use one to get and set elements in a speed of O(1). (This relies on a good hash function (https://en.wikipedia.org/wiki/Hash_function))

In JS, you can build a hashmap with the built in Map() object.

With a hashmap, we can perform a few nice patterns that get asked in a lot of problems. Sometimes these patterns are literally the answer already, and sometimes you need to use them as only a part of your solution.

Pattern 1: Counting frequency

const counts = new Map()
for (const x of arr) {
    counts.set(x, (counts.get(x) ?? 0)) + 1)
}

Pattern 2: Complement lookup

const seen = new Map()
for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need), i]
    seen.set(nums[i], i)
}

Pattern 3: Group by computed key

const groups = new Map()
for (const s of words) {
    const key = s.split("").sort().join("") // for example: check for anagrams
    if (!groups.has(key)) groups.set(key, [])
    groups.get(key).push(s)
}

Let's see this in action in a few Leetcode problems:

242. Valid Anagram (https://leetcode.com/problems/valid-anagram/description/) You get given 2 strings s and t. You need to decide if they are anagrams of each other. String s is an anagram of string t if you can rearrange the letters from s so that you get t. You are not allowed to remove or add any letters.

For some words like "bat" and "tab", you can just see that this is the case. But what about more complex words, or just huge random strings? Written as an algorithm, you'd naively do something like:

Take the first letter in s
Check if that letter is somewhere in t
Keep track of the seen letters from t
Do this for all letters in s. If it's an anagram, you'd cleanly go through all letters with none left over from t. If somewhere along the process you can't find a matching letter from t, or if there are letters left over in t afterwards, it's not an anagram. In JS:

function isAnagram(s, t) {

}

How fast is this algorithm? If string s has X letters, and string t has Y letters, you need to check X * Y times. In complexity theory, that equates to O(n^2). That's pretty bad.

Let's see if we can do better, maybe with our hashmap.

Preparing for a junior software engineer tech interview