Introduction
After weeks of preparation, the big day has finally arrived. At 10:28 am PST, Javier (👨) is moments away from his first interview with Jordanna (👩), a senior software engineer at MAANG inc. The zoom call begins.
👩 “Thanks for taking the time to interview with us today. We’ll start off with brief introductions. My name is Jordanna and I earned my M.Sc. from UPenn before joining MAANG six years ago. I lead a small user experience team that improves product performance and load times for people with slow internet connections across the rural United States and remote regions of Latin America. Please tell me about yourself.”
👨 “It’s great to meet you Jordanna! I think that’s really cool, and really meaningful to me. I come from El Salvador, and I have often struggled with waiting for slow internet connections. I taught myself to code using Google Colab and google resources evenings and weekends while I studied economics at the National University.”
👩 “Well that’s great! Let’s dive into the first problems. Let’s review the problem statement.” Jordanna copies the following problem statement into the shared code editor and Javier reviews the problem statement.
Problem Statement
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
After carefully reading the problem statement out loud, Javier begins to talk through a possible first pass solution with Jordanna.
👨 “Ok, we have a list of numbers and we need to find the indices of two unique values that add up to the target number. We could start off with a simple brute force solution with two for loops. We could start at i = 0 in the outer loop and then loop from j=i+1 to N-1 in the inner loop. When we find two values at i and j that sum up to the target value, we can return [i, j] as the result.”
👩 “That’s definitely a starting point. What would the time complexity of that solution be?”
👨 “Since we would be using two nested for loops, it wouldn’t be that great. It would be O(N^2).”
👩 “Do you think you could come up with a O(N) solution?”
👨 “I agree, O(N^2) isn’t that great. Let’s see if we can do better! In order to do better, we are probably going to need to store previous work for future reference. So I suspect that we will probably need to use a hash map.”
👩 “I like where this is going Javier, please continue!”
👨 “Ok, since we need to solve this problem in linear time we will want to solve the problem by performing linear passes. We could loop through the nums list and populate a hash map mp with the indices of each value. Since the problem statement tells us that the input data has been designed to give us unique results, we won’t need to worry about having duplicate values mapping back to different indices, is that correct?”
👩 “Yes, you are correct. We don’t need to worry about that.”
👨 “Ok! Since our hashmap mp stores the value-index pair, we can employ the concept of complements to solve this problem. A complement is a number derived by subtracting another number from a base number, in our case, the target. If we subtract each num in nums from target, we will eventually find the complement of that operation in the hashmap mp. Once we have done that, we can simply use the current i for the given num and the hashed i from the complement.” Javier writes up the solution and walks through some sample data with Jordanna, and confirms that the runtime is linear.
👩 “This looks good Javier, you do have a linear solution. However, I think we can do a bit better. Can you think of a way where we could do this in one pass?”
👨 “Let’s see what we can do! When i=0, we can’t have a solution yet because the problem statement tells us that we can’t use the same number twice. When i=1, we could actually have a solution. Using this observation, we could check if the complement of num exists in the hashmap mp, if it does, we have our result and we return [mp[complement], i]. If it does not, we can add the complement to the hashmap. Using this logic, we can rewrite the code so that we solve the problem in one pass. This would give us a one pass O(N) implementation.” Javier writes the following code.
Solution
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
mp = dict()
for i, num in enumerate(nums):
comp = target - num
if comp in mp:
return [mp[comp], i]
else:
mp[num] = i
👩 “This looks good Javier, can you run through an example input?”
👨 “For sure!” Javier runs through an example set of inputs, finds a syntax error, and promptly corrects it. With time left at the end of the interview, Javier asks Jordanna some questions about her experiences at MAANG and the interview ends with everyone feeling good. At least Javier thinks everything went well!