The 3 E’s for Software Engineering Interviews
Disclaimer: There is no one correct way to solve a technical programming question. You will face scenarios (data science, system design, etc.) where other problem-solving systems are more useful. However, this is the system I have used to ace technical interviews with Oracle, Amazon, and Facebook.
With the increasingly competitive landscape for internship and new grad roles in software engineering, every small step counts. Having a structured process for answering questions can not only make you a more confident interviewee and increase your odds of scoring high. In fact, many companies will score your ability to think in a structured manner, so even if you can’t find the best solution to a problem, you may be rewarded for your ability to have a clear, easy-to-follow system for attacking a coding question. Without further ado, here are The 3 E’s of Software Engineering Interviews.
The 3 E’s
While the number of steps can vary depending on the interview, every answer I give goes through these 3 phases:
In the first phase of education, I try to understand the problem being presented to me. Then, I explore potential solutions and if I’m able to, will analyze their big-O time and space usage. In the execution phase, I will write the code for the algorithm. Though it sounds pretty straightforward, this is more important than you’d think because it may be the first piece of your code that a representative of the company will see.
Each of these three phases has a series of sub-steps. Let’s delve further into each step, with the example question Kth Largest Element in an Array from LeetCode.
In order to understand the problem, you’ll need to do a few different things:
- Read the starter code/spec. You’ll likely be coding on some shared screen or whiteboard and are given a problem statement. Read it carefully!
- Ask questions.
- Briefly run through some sample cases. Just brainstorm some generic, easy to understand input/output pairs. Be mindful of your time on this step since it should just be used to quickly confirm that you understand the question.
Applied to Kth Largest Element
Now let’s apply the above steps to Kth Largest Element in an Array.
- Read: focus on understanding what input your algorithm receives and with its outputs. In our case, we receive an unordered array of integers and want to find the $$kth$$ largest element, where k can be any integer.
- Me: “Are there any error cases we should handle? Such as k=-2 or k=0?”
- Interviewer: “That’s completely up to you” (usually means yes but it’s not a high priority)
- Sample cases:
- Me: “So with the array [0,5,2,1] and k=2, we should get 2?”
- Interviewer: “Yes”
Exploration should be the shortest of the three phases. Here, you’ll quickly brainstorm a couple of approaches. You’ll also note their computational complexity.
In summation, these are the steps for exploration:
- Brainstorm multiple approaches
- Estimate Big-O runtime/space usage for each approach. This is the most important step before execution! Make sure you do this right so you score well for the efficiency of your algorithm.
- Select the best choice: If one choice has the best time and space efficiency, choose it, and move on. Sometimes, one choice will be the fastest and the other will be the most space-efficient. The company will usually prefer the fastest solution. Let the interviewer know that you believe the fastest algorithm is the optimal choice for the problem. If they don’t object to this, move onto execution. If they do question why that’s the best choice, think about whether or not your use case requires a solution that’s fast versus a solution that’s space-efficient. Do this out loud by explaining the suitability of both algorithms for the use case of the algorithm. Then, if you feel the space-efficient solution is better, change your answer, get their validation, and move on.
Applied to Kth Largest Element
- Me: “Off the top of my head, I can think of the following approaches to this question: 0) The brute force solution, which is to just remove the min element until we’re left with k items and return the min of that. 1) We sort the array and return the element at index k-1. 2) We put the items into a sorted data structure and return the kth largest element from that in constant time. 3) Actually, thinking about the last solution made me realize we can just use a bounded min-heap where we keep track of the k largest elements so far as we traverse through the array.”
- Me: “Here’s how these algorithms stack up. We’ll use n to denote the size of the array:”
- Brute force: O(n^2) time but O(1) space
- Sort the array: O(n log n) time and O(log n) space with an in-place sort
- Why in-place sort uses > O(1) space
- Ordered Data Structure: O(n log n) time and O(n) space. Not really an improvement, but the next one is!
- Bounded Min Heap: O(n log k) and O(n) space. This is our fastest algorithm! Since the heap is bounded, it takes log k time in the worst case to insert at each step when we iterate through the array.
- Me: “I think the bounded min-heap gives us a good algorithm because the space usage is linear and the time is fastest. However, if we are concerned with storing extra space, the brute force gives us low space usage at the cost of some time. Since I think speed is a good priority, do you object to me proceeding with the bounded min-heap?”
- Interviewer: “We’d like as fast an algorithm as possible, so let’s go with that.”
If this is a whiteboard interview, execution just means writing out the code in your preferred programming language. You may also have to manually step through your code with some test cases. These test cases will usually be provided by the interviewer, or they can ask you to make them up on your own. In the latter case, you’ve already brainstormed a few during the understanding phase, saving you some time here.
If this is a laptop interview, you may have to write the code and test it against your/someone else’s test cases.
These are the general steps:
- Code: Write up the code. Sometimes they just want pseudocode on a whiteboard or google doc. Usually, they want you to write code in your preferred programming language. I’ll use Python for maximum clarity.
- Step through: Start with a basic test case, then explain how your code works through different types of inputs.
- Edge Cases: If there are any special cases that your code doesn’t cover, address this before the interviewer gets a chance to correct you! Otherwise, just be sure to mention how you handle unconventional inputs.
Applied to Kth Largest Element
Interviewer: “Can you code this up?”
Me: “Sure. This code creates a bounded k-heap from the elements of the array. It will store the k largest elements in the array. We return the smallest of these k elements.”
Interviewer: “You imported some dependencies which help maintain the heap invariant in your ordered data structure. Can you show how to implement these functions?”
Me: “Sure, here’s how the heappop function works. It returns the min element, assuming the heap is ordered least to greatest:”
Me: “Now, here’s how heappush works. It’s mainly binary search for the insertion index, and then the insertion:”
Me: “And for heappushpop, you would just call the previous two methods.”
Interviewer: “Cool. Let’s step through some test cases.”
- Me: “Let’s start with a simple case: [5,8,2,4,1,7] and k=3, we would step through and for each step, the heap would be , [5,8], [2,5,8], [4,5,8], [4,5,8], and [5,7,8]. Then, we return the first element of this heap, 5.”
- Edge Cases
- Me: ”Ok, so the logic seems to work. Are there any special cases you’d like for me to try?”
- Interviewer: “Yup, how about [4,3,5,6,21] and k = 10.”
- Me: “Yeah, since k is larger than the size of the array, it would just return the smallest element, 3. I can add in a check statement to ensure k is bounded by the array length.”
- Interviewer: “No need. Just wanted to ensure you understood that part. How about if k is 0 or negative?”
- Me: “In that case, the function currently errors out. We can have an assert statement at the beginning or simply return the largest element to account for this case.”
- Interviewer: “Ok, sounds good. I think we’ve covered this question well, glad to see your thought process.”
Tech companies will have varying bars for expected interviewee performance. Some want you to have an amazing, structured thought process as well as the fastest, most space-efficient solution. Some just want the correct algorithm. Either way, getting the algorithm right will depend a lot on how much time you spend studying your data structures and algorithm curriculum. Though I was taught these concepts well in school, the structured answering process is something I had to conceive on my own. With the right preparation, you can combine these two skillsets to land the internship of your dreams. Best of luck!