1) Brute Force
“Enumerate all possible solutions, and check them for correctness.”
This is usually our first thought when we’re breaking down a new problem.
Want to get the highest product of 3 numbers in an array? Grab every set of 3 numbers (“all possible solutions”), multiply them, and keep track of the max (“check them for correctness”).
This idea can be applied to most questions, and it’s a great way to get from “I have no idea how to even get started” to “I have a way to break down this problem.”
The brute force solution is usually not the most efficient, but it can still be a helpful way to start.
By the way, when I say “efficient” I’m talking about “big O time cost.” If you’re rusty on big O notation (or have no freaking idea what that is), definitely read the explainer.
2) Greedy
“Keep track of the best answer ‘so far,’ in one pass through the input.”
This is a common way to go from brute force to something more efficient.
The tricky part is answering the question, “what values will I need to keep updated at each step in order to have the final answer when I reach the end of the input?”
3) Use a Hash Table
“Seriously, just use a hash map or maybe an array”
Throwing a hash map/hash/dictionary at the problem is actually the answer a lot of the time. If you just make it one of your first thoughts, you’ll blow through these kinds of questions.
Hint: it’s often a “counts” hash, mapping items to how many times they appear in the input array.
One caveat: this approach spends space in order to save time. You can impress your interviewer by noting this tradeoff! (Not sure what “spends space” means? Seriously, read the explainer!)