Interviews are stressful.
You are not only asked to solve a problem that you’ve just heard of, but to solve it in a way that demonstrates your ability to communicate and your intelligence. All while the interviewer is staring you down (or blankly at their laptop).
Since these situations are so different than what you normally encounter at work or school, you may end up forgetting basic things like clarifying the problem or working out an approach before writing the code. Failing to do these things will make it harder for the interviewer to understand you and leads to messy code, or even solving the wrong problem.
Because of this, practicing how to structure your problem-solving is just as important as solving the problem itself. Although the specific technical interview question you’re asked to solve may change, how you approach the problem does not. By nailing the problem-solving structure, you’ll be able to effectively communicate with the interviewer even under the most stressful situations.
Here are the steps to solve an interview problem:
- Hear/Read the problem
- Ask questions that clarify the problem and its scope
- Think of a general strategy (sorting, divide and conquer, etc.)
- Write the pseudocode
- Write the code
- Test the code and fix any bugs
This can seem kind of abstract, so let’s look at an interview problem and how to practice it using this problem-solving structure.
Problem: Find the Missing Element from the Array
Step 1: Read the problem
The interviewer describes the problem, “Suppose you’re given an array of size n-1 that contains integers from 1 to n. Find the missing integer.”
Step 2: Ask questions that clarify the problem and its scope
Interviewers can give vague problem descriptions and leave the onus on you to clarify the scope. Here are two questions you could ask for this problem.
- Can there be repeated numbers in the array?
- Does the array only contain integers from 1 to n, or can it have other values?
The answers to these questions can drastically change how you solve the problem, so it’s worth asking as early as possible.
When you’re studying a problem, you obviously won’t have someone to answer the questions for you, and the problems are generally more defined than they would be in an interview. When practicing a problem, I just write down the questions or say them out loud, pretend I received some reasonable answer, and then move on to the next step.
For the purposes of this problem, we will assume that the elements in the array are unique and that it only contains values between 1 to n.
Important: You don’t actually have to ask all of these questions in a real interview. The main purpose of this step is to make sure you understand what the interviewer is asking you do solve.
Step 3: Think of a general strategy
With enough practice, you’ll be able to bucket interview problems into certain types (sorting, hashing, recursion, etc.), which then dictate how you solve the problem. Here, you want to think of the associated space and runtime complexity of each approach before deciding how to move forward. For this problem, here are a few different strategies you might think of:
- Brute force: For each integer 1 to n, we could search for the number in the array. This is O(n^2) time because we have to scan the entire array for each integer, but O(1) space because we don’t need to store any variables.
- Hashing. The above approach is inefficient because we have to keep scanning the array. Instead, we can iterate through the array once and store every number we’ve found in a map. Then, checking each element takes O(1) time. Storing all the elements in the map takes O(n) space and O(n) time, and checking each number from 1 to n takes O(n) time. Therefore, the overall time and space complexity are O(n).
- Sorting: We could sort the array and look for non-consecutive numbers. Sorting the array takes O(nlogn) time, and finding non-consecutive numbers takes O(n) time. Assuming we use an in-place sort, we can achieve O(1) space complexity. There is an edge case where the missing number is 1 or n, but checking that case takes O(1) time. The time complexity is O(nlogn) and the space complexity is O(1).
- Math: We could subtract the sum of 1 to n and the sum of elements in the array. Since the array has every number from 1 to n except for one number, the difference will give us that missing number. It takes O(n) time to sum the elements in the array and O(1) space because we use one variable to keep track of the sum.
- Bitwise operations: I will skip this approach for this post (Hint: use XOR).
In an actual interview, you wouldn’t be expected to list all of the different ways you can solve the problem and their complexities. However, learning how to look at a problem through different lenses will help you when you encounter a problem you don’t know how to solve.
Step 4: Write the pseudocode
This step should be pretty straightforward. You want to do this before jumping into coding so you have a roadmap for the code you’re going to write. Otherwise, you might realize you forgot to consider some edge case and have to backtrack.
- Compute the sum of integers 1 to n by using the formula n(n+1)/2 (or sum 1 through n using a loop)
- Take the sum of elements in the array
- Take the difference between the two
Step 5: Write the code
This step should mainly be translating the pseudocode into actual code.
# There's a bug in this code. Can you find it? def find_missing_element(A, n): sum_A = sum(A) sum_n = n * (n + 1) / 2 return sum_A - sum_n
Step 6: Test the code and fix any bugs
It’s OK to have bugs in your code, as long as you find and fix them carefully. Try to think of at least 2-3 test examples, and run your code through those examples.
A = , n = 0 A = , n = 1 A = [1, 2, 3, 5], n = 5
Let’s try running through these three test cases.
The sum of elements in A is 0, and the value of
sum_n is 0. The difference of the two is still 0, which is correct.
The sum of elements in A is 2, and the sum of 1 and 2 is 3. We then take the difference 2 – 3 = -1, which is the wrong answer. What went wrong?
The sum of elements in A is missing one number from the sum of 1 to n. Since it’s always smaller, we should return
sum_n - sum_A instead. Once we make that change, the code will correctly return 1 as the missing element.
The value of
sum_A is 11, and the value of
sum_n is 15. The difference 15 – 11 = 4, which is indeed the missing number.
Whew! That was a lot. These steps are a little more involved than looking at a problem and just writing code, but it mirrors exactly what you would do in an interview. Interviewers care that you clarify the problem, that you communicate your approach before jumping into code, and that you test your code. Following these steps makes demonstrating those qualities automatic.