So there you are. Relieved. Exhausted. You’ve finally come up with an approach to solve the tricky coding question your interviewer asks you. Perhaps you even wrote it up on the whiteboard, line by line. And you made good time! You’re only 20 minutes into the meeting. Your interviewer’s gotta be impressed.
Right?
“This’ll work, but any ideas for how to do it more efficiently?”
Your heart sinks. You thought you were done with the tricky algorithm design part! You try to think of more ways to solve the problem, but all you can think of is the one approach you’ve already come up with.
This happens to almost everyone. And it’s not because they’re stupid. It’s because most people don’t have a method for improving the efficiency of their algorithms.
But the truth is, there are plenty. Next time you’re stumped, try applying these three common approaches.
1. Use a Hash Map
That’s right. Hash maps/associative arrays/dictionaries (they go by many names, depending on what programming language you’re using) have a magical ability to bring down the runtime of algorithms.
For example, suppose the question was to find the most-repeated number in an array of numbers.
Your first thought might be to jump into some loops. For each of our numbers, figure out its count and see if it’s the biggest one. How do we get the count for each number? Loop through the array, counting how many times it occurs! So we’re talking about two nested loops. In pseudocode:
def get_mode(nums):
max_count = 0
mode = null
for potential_mode in nums:
count = 0
for number in our_array:
count += 1
if count >= max_count:
mode = potential_mode
max_count = count
return mode
Right now, we’re looping through our whole array once for each item in the array—but we can do better. In big O notation, that’s O(n2) time in total.
If we store our counts in a hash map (mapping numbers to their counts), we can solve the problem in just one walk through the array (O(n) time!):
def get_mode(nums):
max_count = 0
mode = null
counts = new HashMap, starting each value at 0
for potential_mode in nums:
counts[potential_mode] += 1
if counts[potential_mode] > max_count:
mode = potential_mode
max_count = counts[potential_mode]
return mode
Much faster!
2. Use Bit Manipulation
This’ll really set you apart from the pack. It doesn’t apply to every problem, but if you keep this in your back pocket and bust it out at the right time, you’ll look like a rockstar.
Here’s an example: Suppose we had an array of numbers, where every number appears twice, except for one number which only occurs once. We’re writing a function to find the lonely, non-repeated number.
Your first instinct might be to use a hash map, since we just talked about it. That’s a good instinct to have! And it’ll work for this one. We can make a very similar “counts” map, and use that to see which number ends up with a count of 1.
But there’s an even better way. If you’re familiar with bit manipulation, you might be familiar with XOR. One thing that’s special about XOR is that if you XOR a number with itself, the bits “cancel out” to 0. For this problem, if we XOR every number in the array together, we’ll be left with the one number that didn’t cancel out:
def find_unrepeated(nums):
unrepeated = 0
for num in nums:
unrepeated = unrepeated XOR num
return unrepeated
3. Go Bottom-up
Write a function that outputs the “nth” Fibonacci number, given a number n. This one’s a classic, and it lends itself very nicely to recursion:
def fib(n):
if n is 0 or 1:
return 1
return fib(n-1) + fib(n-2)
But the simple recursive answer isn’t the only one! Think carefully about what this function does. Suppose n is 5. To get the answer, it recursively calls fib(4) and fib(3). Now, what does that call to fib(4) do? It calls fib(3) and fib(2). But we just said we already had a call to fib(3)! This cute recursive function does a lot of repeat work. The total time cost turns out to be O(2n). That’s bad—way worse than O(n2).
Instead of going from n recursively down to 1, let’s go “bottom-up,” from 1 to n. This lets us skip the recursion:
def fib(n):
previous = 0
previous_previous = 1
for i in the range 1 to n:
current = previous + previous_previous
previous_previous = previous
previous = current
return current
The code is longer, but it’s much more efficient! Down to O(n) time. As an added bonus with unrolling recursive algorithms, we save space. All those recursive calls build up in the call stack, which sits in memory and counts towards our space cost. Our recursive function had an O(n) space cost, but this iterative one takes O(1) space.
Next time your interviewer asks you to improve the efficiency of your solution, try walking through these strategies and seeing if they help. With enough practice, you’ll probably find yourself jumping straight to the optimized solution, skipping the more naive solution. And that’s a great thing. It doesn’t just mean you’re becoming a better interviewer—it means you’re becoming a better engineer.