a technical interview cheat sheet: REACTO!

solving Leetcode’s (first problem) Two Sum using the best strategy for technical interviews.

Now that I’ve completed Data Structures and Algorithms courses, I find the Two Sum problem to be a simple and trivial exercise. However, I vividly recall how much it impacted my self-esteem when I struggled to solve it during my early days of learning how to code. Using REACTO, the technical interview version of STAR (a highly recommended method for tackling behavioural interview questions), here is how I would answer and explain a solution for Two Sum in an interview.

A lot of the time, students find themselves in situations where they can solve technical problems but are unsure of how to explain their strategy and properly communicate with their interviewers. The first step is to:

Repeat (first part of REACTO)

This may sound tedious but repeating the question back to your interviewers or even yourself helps provide clarity. This ensures you fully understand what you are being asked before diving into coding a solution.

Now, suppose you received the Two Sum question in a technical interview: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

By repeating the question, you may be prompted to ask clarifying questions like: “what would we do in a situation where there are no two numbers that add up to the target” or “what would we return if there are more than one pair of numbers that add up to the target”. You do not want to make any assumptions without sharing them with your interviewers. By asking these questions, we will be able to think of clear input and output examples, leading to the next part of the strategy:

Examples (second part of REACTO)

Walk through some examples with your interviewers and create various inputs and outputs (aka test cases). This helps further clarify the question in the case where you are still stuck. Leetcode specifies that “each input would have exactly one solution, and you may not use the same element twice”, we will pretend this was also the response from our imaginary interviewers to answer our questions above.

Test case 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] (which is 2) + nums[1] (which is 7) == 9, we will return [0,1] as the answer.

Test case 2:

Input: nums = [2,3,4], target = 7
Output: [1,2]
Explanation: Because nums[1] (which is 3) + nums[2] (which is 4) == 7, we return [1,2] as the answer.

Test case 3:

Input: nums = [2,5,12,7,15,1], target = 6
Output: [1,5]
Because nums[1] (which is 5) + nums[5] (which is 1) == 6, we return [1,5] as the answer.

By verbally running through some examples, we now know the expected output for our code given different inputs. This leads to the next part of the strategy, explaining our:

Approach (third part of REACTO)

This is where you want to share with your interviewers your plan/approach to solving the specified question. Do you have a data structure in mind, or would a simple for loop get you the desired output? Do not rush into coding as you are not only being tested on your technical abilities but also your ability to communicate your ideas.

Rather than thinking of possible ways to approach a solution in your head, you want to share them all with your interviewers. Find out what their thoughts are on your plans. Do they like it? Do they have better suggestions? You could receive helpful tips during this stage, and it will show them how well you respond to critique/advice.

Now to actually think of an approach for Two Sum: “my first step would be to access the first integer in the array nums and then the second integer and check if they add up to the target. If they do not, I do not want to stop there, but instead still hold onto the first integer and then access the third integer and check if this new combination adds up to the target, if they still do not, I still want to keep the first integer and then access the fourth integer and check if this newer combination adds up to the target, and so on…”

gif from davidseek.com/two-sum

The pattern is shown in the gif above and it essentially takes the first integer and checks if all the other integers in the array (after it) can add up to equal the target, if not you move on to the second integer and check if all the other integers in the array (after it) can add up to the target. To do all of this we would need for-loops to access each integer in the nums array and eventually, you will find a pair that adds up. We will now actually implement our approach in the next part:

Code (fourth part of REACTO)

The solution using our specified approach would look like this:

def twoSum(nums, target):
    #the first loop which starts at index 0 in array nums
    for i in range(len(nums)):
        #second for loop which points to the next index after i
        for j in range(i+1, len(nums)):
            #check if the integers at these indexes equal target
            if nums[i] + nums[j] == target:
                return i,j

This brute force solution has the Time Complexity of O(n²) because we will be looping through the entire array once which takes O(n) time, and we also have a second loop to find the complement which also takes O(n) time and that results in O(n²). This leads to the next part:

Test (fifth part of REACTO)

You may not always have the opportunity to code in an IDE during an interview, so this step is optional. I have coded solutions in Google Docs for interviews but, if you are working in an IDE, the next step will be to run your code. You have curated example inputs in the previous steps, now you should use them and confirm your code gives the correct output.

There are times when you may come up with a better approach to solving your question while already coding a solution or even after. It is great to share all other ideas you have which lead us to the last part:

Optimize (last part of REACTO)

Suppose the array nums had 1000s of integers in it, you can agree that it would take a pretty long time to loop over nums and find integers that sum up to the target. To reduce our Time Complexity, we will have to think of another approach or update our current approach. In this case with Two Sum, a better approach would be to use a Hash Table/Map as shown:

def twoSum(nums, target):
    #initialize an hash table
    hashtable = {}
        #loop through nums
        for i in range(len(nums)):
            #each integer will have a complement which will == j
            j = target - nums[i]
            #check if j is in our hash table
            if j in hashtable:
                # if so, return index of j and i
                return [hashtable[j], i]
            #if it's not in hash table, store index and value
            else:
                hashtable[nums[i]] = i

Keep in mind that this step is also optional, you may not have enough time to share or think of an optimal approach or your interviewers may be satisfied with what you have. You may also not code your optimal solution but rather walk through how you would approach implementing it, but the key point is that you are able to improve and formulate better and optimal code.

If you get anything out of my cheat sheet, it should be that REACTO is a great guide for approaching technical questions in an interview. This technique enables constant communication during interviews which can only work in your favour. Do not forget that practice makes perfect!