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.
“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!)