We’re excited to include guest posts on our blog from interesting people and companies in the industry. This post was written by Chaitanya Mattey, a current Pathrise fellow who is working towards his dream job as a software engineer, with help from his mentor, Brian Wong, a former senior software engineer at Zazzle.
Before you even start to receive interview requests for software engineering roles, you should be practicing for the technical interviews. After the phone screen, these are typically the next step, so you need to make sure you give a strong showing so you can move forward to the onsite, which will include more technical questions.
If you are ready to start practicing, you’ll find there are a lot of options for platforms online. We’ve compiled a list of resources to practice software engineer interview questions to help you find the best one for you. You can also practice on your own, though, by working through common interview questions from these 93 software engineering technical interview questions from real tech companies. We wanted to help your preparation by providing you with a step-by-step walkthrough of this Facebook interview question on daily temperatures.
The daily temperatures problem has been a very frequent coding interview problem for the top tech companies like Facebook, Google, LinkedIn, Apple, Amazon, and Uber in the past 6 months, according to our internal sources and LeetCode. Because it has been so popular, we wanted to take a deep dive into this question to see what makes it so interesting!
We are given a list T of daily temperatures for N consecutive days. Our task is to output a new list, which tells us, for each day in T, how many days we need to wait until a warmer day (temperature). If there is no day in the future with a higher temperature, the number of days can be put as 0.
|T = [73, 74, 75, 71, 69, 72, 76, 73]|
Output: [1, 1, 4, 2, 1, 1, 0, 0]
We can observe that for Day 1 with temperature 73 (T), we only need to wait one day for a warmer temperature 74 (T). Therefore Output = 1.
Similarly, on the third day, when the temperature is 75 (T), we need to wait 4 days for a warmer temperature on day 7 (T), so Output = 4.
Output and Output are 0, since there are no days after them with a higher temperature.
Before we start discussing the problem, try solving the problem with a reasonable Time and Space complexity.
Now that you have (hopefully) tried solving the problem, let’s review an optimal way of approaching this problem in a real interview.
One of the more straight-forward approaches to solving this problem would be to traverse the rest of the temperature array and note whenever you encounter a temperature higher than your current temperature. This approach is illustrated in the following diagram.
As we can see, in the worst case, the time-complexity for this algorithm is O(n^2), in the length of the input array, and O(1) space complexity. In a real interview this a good time to seek your interviewer’s opinion, by showcasing your concern that although the space complexity for the above approach is constant, the time complexity is quadratic with respect to the length of the input array.
You can then go on to ask if you should look for a better approach that lowers your time complexity (perhaps at the expense of that constant space complexity). The likely response would be yes, you should look for a better approach.
Score! You’ve not only discarded an approach, but also showcased your understanding of time complexity of your algorithm, without the interviewer having to point it out (something many candidates forget to do). If that wasn’t enough, you can also deduce that your new solution needs to be linear or n*logarithm in time complexity.
Let’s look at our second example again:
I’ll borrow a good framework for improving on a solution from Gayle Mcdowell’s Cracking the Coding Interview, which is a great guide to technical interviews: the BUD framework.
- B: Bottlenecks
- U: Unnecessary Work
- D: Duplicate Work
Let’s apply this to our first approach.
We can identify a lot of duplicate work. In the case of the example above, observe how we iterate over the rest of the array every time. When we are at the first element, we iterate over [74,73,72,71,78], from the second element we iterate over [73,72,71,78] and so on. We should be able to avoid iterating over the same element multiple times.
One way to do this would be to store the elements efficiently. “Efficient” indicates whether or not we can calculate the next higher temperature without multiple iterations through the same data. We’ll use a stack data structure to store our temperatures, along with the index where they occur in our input. We keep removing (pop) the top element from the stack, if the next temperature is higher than our current top.
Let’s see how we can go about doing that.
To formalize, this is our algorithm:
- If stack is empty, insert current temperature and its index.
- If temperature is lower than the temperature at the top of the stack, keep inserting.
- Else while temperature is higher, keep popping elements while this is true, and update output index with the value: current_index – popped_index.
- After going through all the values in the list of temperatures, if there are values left on the stack, these do not have any higher temperatures to their right and the values for their indices in the output would be 0.
Let’s see what that looks like in code now:
|# Time: O(n)|
# Space: O(n)
def dailyTemperatures(self, T: List[int]) -> List[int]:
stack = 
output = *len(T)
for index, temp in enumerate(T):
while stack and stack[-1]<temp:
popped = stack.pop()
output[popped] = index-popped
Now, you would have noticed, the space complexity of the algorithm goes up from being constant to the order of n, O(n) because of our stack. But the time complexity of our algorithm has now come down to linear time: O(n). This is because we only encounter an element twice, once while pushing it on the stack and once while popping it.
This was an interesting problem, with a few different approaches. We looked at a couple of them and ways in which we can improve on a solution using the BUD framework. Congrats if you were able to come up with a linear time and space solution on your own! If not, take a look back and try to see what insights might have kept you from arriving at that solution.
You are now one step closer to acing those technical interviews and landing your dream job! Want to practice more? Check out our step-by-step guide to solving a Google software engineer interview question. If you are looking to learn more about the software engineering hiring processes and interview questions at Facebook and other top tech companies, check out our Interviewing Insider Company Guides.
Pathrise is a career accelerator that works with students and professionals 1-on-1 so they can land their dream job in tech. With these tips and guidance, software engineering fellows in our program have seen their interview performance scores double.
If you want to work with any of our advisors 1-on-1 on your software engineer technical interviews or with any other aspect of the job search, become a Pathrise fellow.