Introduction

During my senior year at California State University Channel Islands, I was recruited by Infratab to work part time. Upon graduation, Infratab offered me a full time job and I enthusiastically accepted. Those past three years, needless to say, were an amazing experience. I got to meet brilliant people and worked for a company that was passionate about minimizing food waste. Unfortunately, by year three I was experiencing something that many software engineers in our industry eventually feel: boredom. I was no longer learning and my growth as a software developer was stagnated. Although I loved Infratab and my coworkers, it was time to move on.

Since most of my industry experience has been interacting with RFID embedded devices, I wanted to go in the opposite direction into the realm of scalable computing. In order to accomplish this, I needed to join a larger company that successfully utilizes cloud based services to serve millions of customers. During my final months at Infratab I practiced coding challenges on my off-time. Once I felt ready to seriously ramp up my job search, I left Infratab and dedicated myself full-time to practicing coding challenges, learning system design, and applying to various companies. My hard work finally paid off when I landed interviews at Amazon, Dropbox, Google, and Zillow and ultimately got offers from both Google and Zillow!

Now that I have some downtime and my experiences are fresh in my head, I wrote this blog post with the goal of helping anyone who's looking to pass a virtual technical interview.

Disclaimer

This article contains anecdotal experience interviewing with these companies. I am not a recruiter nor do I represent any of the companies mentioned. All observations and opinions are my own.

Before reading this article, I strongly recommend reading at least chapters I to VIII of Cracking the Coding Interview by Gayle Laakmann McDowell. This article intentionally leaves out a lot of information that exists in the book.

My primary background comes from interviewing for experienced roles. A reader applying to a new grad position may have a difference experience. Please consult McDowell's book to see the differences between new grad and experienced roles.

I would also like to point out that there are many great companies that do not require a technical interview. Some companies have take-home assignments and others will straight up hire based on ambition and/or expertise. With that being said, the purpose of this blog post is to help the reader prepare for the companies that do require a technical interview.

Coding Challenges

In order to pass a technical interview, you will need to practice coding challenges on LeetCode, HackerRank, and/or Firecode. Yes, I know it's tedious. Personally, it leaves me brain-dead by the end of the day. Rather than mindlessly grinding random questions, focus on topics that you're weak in. You want the ability to recognize which data structure and/or algorithm to use when presented with a new coding challenge.

Being able to solve coding challenges is not enough. Your interviewer will also be evaluating your creativity, thought process, and code cleanliness.

Learn to comfortably write code without an IDE or compiler

Due to COVID-19, interviews are being conducted remotely rather than on-site. You don't need to worry about whiteboard coding (for now) and instead you will be interviewing via a shared document. This shared doc probably won't have a compiler and even if it does, you won't be allowed to build until you're certain that the solution is complete. You will need to be comfortable writing code without the conveniences of an IDE. Practice this by writing your code on a Notepad application and copy/pasting your solution when ready.

Write documentation and descriptive names

When I look at LeetCode solutions, I notice people tend to solely focus on code performance. In the pursuit to be faster than other solutions submitted, they sacrifice readability. Usually these solutions have no comments, non-descriptive variables (a, b, c), code jammed together with no white-space breathing room, and the irony is the added label "easy-understanding". As a software engineer, you are responsible for writing well documented code that your current and future team members can understand. Practice this by writing comments and descriptive names on every coding challenge (and personal projects).

Come up with your own test cases

One thing that coding challenge websites don't prepare you for is coming up with your own test cases. In every virtual on-site I was expected to come up with my own function input/outputs. This is very closely tied with generating edge cases. Practice this by writing your own test case that are different from the coding challenge examples. I'll go more in-depth in my sample phone interview.

Vocalize

I honestly can't stress this enough. Your interviewer must be on the same page as you at all times. You can also get instant feedback if your idea is incorrect. This is magnitudes better than wasting precious time coding an erroneous solution. One way you accomplish this is by exhibiting your thought process out-loud throughout the entire coding assessment. Practice this by talking to yourself during coding challenges. I certainly do not like hearing my own voice either, however, if you do it enough times you should feel more comfortable talking out-loud to an interviewer.

<3 Python

I'm going to take a quick moment to shill Python 3. Although I used C# professionally for the past 3 years, Python was my language of choice for technical interviews. It has a built-in hashmap, set, list, and queue/stack data structures. It is also one of the few languages that natively supports heaps which, in my opinion, is one of the more annoying data structures to implement. It also supports powerful and versatile sorting methods. Finally, I don't get hindered by minuscule syntax errors such as missed semi-colons and brackets and can instead focus on solving the challenge. With all that being said, every company I interviewed with doesn't care what language you use, choose the one you're most comfortable with.

Embrace Failure

Unfortunately your journey to passing a coding interview may be paved with rejections. Maybe you couldn't come up with a solution better than brute force or you were too slow to generate a solution. If you do get the dreaded "unfortunately we decided to move with other candidates" email, just know that you didn't waste your time. The worst possible way of handling a rejection is to have an ego and admit no faults. The second worst possible way is to get a case of imposter syndrome and think you aren't worthy of trying again. Thank your recruiter for their time and ask if they can provide feedback. (Some companies have a no feedback policy, so it'll be up to you to figure out how you could've done better). Your dream company will allow you to apply again after a cool down period so it's really not the end of the world. There's no such thing as failure, just learning experiences.

Recruitment Format

Since interviews are being conducted remotely rather than on-site, you can expect the experience to be a bit different from traditional interviews. The following is the standard recruitment format I encountered.

1. 30 minute call with a recruiter where you talk about yourself and learning about the role.
2. Coding Assessment, either this will be an automated interview or a phone interview.
3. Virtual on-site, consisting of 4-5 phone interviews.
4. Negotiations and Offer.

The day of the your interview

My first experience performing a coding assessment was 9 months ago with Amazon. I didn't know what to expect so I crammed as much as I could up to the night that I finally took the assessment. Needless to say I nuked it and the following day the my recruiter told me to piss off for 6 months. I vented to a close friend of mine and she gave me excellent advice:

Don't study the day of the interview. Give your brain a day of rest.

There's absolutely no way of knowing which questions the company is going to ask, have faith in yourself and relax until your appointment. You don't want to burn yourself out before you even interview with the company!

Automated interview

You can think of an automated interview as a Firecode/HackerRank/LeetCode style test. You are given instructions, sample test cases, and you write your solution in the premade function. When you click "Run Code", your solution is tested against various test/edge cases. If a test case fails or the time limit was exceeded, the conflicting input will not be provided to you, so you will need to figure out why. For every question you typically have to explain how you came up with the solution and the Big-O. If you run out of time, the interview automatically ends and moves on to the next section.

In my opinion, automated interviews are more difficult than phone interviews because the questions are generally harder, you can't receive valuable feedback from an interviewer, and it's difficult to demonstrate your problem solving skills. Thankfully, you will not encounter automated interviews during a virtual on-site.

Phone interview

Most of your interviews will be phone interviews, which consist of a audio/video call with an interviewer and coding in a shared document. Your interviewer begins with an ambiguous question, your job is to ask clarifying questions to understand the scope of the problem. After understanding the constraints you then write your own test cases. After vocally explaining your solution, you then begin coding your solution, keeping mind of edge cases and Big-O runtime/space. I will go in-depth with a sample phone interview here.

Virtual On-site Preparation

If your recruiter calls you and informs you that you passed the coding assessment, great job! You're on your way to a virtual on-site.

Preparing for Leadership Questions

** Experienced Developers **

You will be expected to talk about your leadership skills in your previous jobs. Your recruiter will give you a list of values that are very important to the company. For example, Zillow has Core Values, Amazon has Leadership Principles, and Google has Googleyness. Leadership questions are just as important as the coding portion of your interview so don't blow it off. I recommend creating a word document with one or two examples of each list item.

Research

Do research into the role and company. A great way to do this is to read their tech blog, listen to podcasts, and watch their conference presentations on Youtube. Doing this will give you some insight into what challenges they faced in the past. If something confuses you during your research, then you found a perfect question to ask your interviewer. What tech stack does the company use? How did the company handle it's employees well-being during the COVID-19 pandemic? Questions like these are a good starting point.

Virtual On-site

COVID-19 dramatically shifted the way companies perform technical interviews. For now, you no longer need to fly out to the company's office and write code on a whiteboard. Instead you will be on a video conference call while coding on a shared document. A virtual on-site consists of 4-5 phone interviews in a row with each interview running at around 45-50 minutes. Some companies will be nice enough to give you a 1 hour break in-between. Others will poorly manage their time and have you almost pissing your pants.

System Design

** Experienced Developers **

System design may be one of your interviews even if you've never worked with scalable technologies before. Jackson Gabbard states on his blog that system design questions are used to determine your level which consequently affects your potential total compensation, therefore you should take it very seriously. In lieu of designing a system on a whiteboard, you will be expected to use a drawing app such as Google Docs. A few free resources you can use to study are Hired In Tech, System Design Interview, and System Design Primer. The book Designing Data-Intensive Applications, by Martin Kleppmann, goes into system components and trade-offs in great detail. Kleppmann's book is very information dense so I suggest you begin with the free resources first.

Leadership Interview

** Experienced Developers **

In each phone interview, your interviewer will begin with leadership questions. It usually starts with "Tell me about yourself" then one or two question related to their leadership values. Only one company questioned my leadership values in a dedicated one hour interview. Your interviewers will be reading off a script, don't get offended. Zillow has a great reply on Glassdoor about why their questions are scripted, I can suspect that other companies have the same reasoning.

... Harvard Business Review wrote a great article on conversational interviews titled “How to Take the Bias Out of Interviews” that really addresses the reason why our interview questions are so structured and conducted in the manner you referenced. We realize this may not come across as the most personal at times but we strive to remove unconscious biases from the interview process so they are as fair and equitable as possible ...

Coding Interview

The coding portion of the interview consists of a typical phone interview. I go over a sample interview here.

Questions about the company

Near the end of the interview your interviewer will ask you if you have any questions. Now's a good time to show your research into the company. Ask meaningful questions about their stack, team specific questions, company culture, and growth opportunities.

While reading tech blog, I noticed that your there isn't much mention of your tech stack, do you mind telling me more about it?

Questions like this show that you're a serious candidate that invested time into learning about the role/company. The more specific the better!

Negotiations

If your recruiter gives you the good news then you'll move on to determining your total compensation and salary. In lieu of talking about this, I will instead link a Business Insider article on Haseeb Qureshi, an engineer who negotiated his way into a $250,000 starting-pay package. Qureshi's blog posts go into fine detail on how to successfully negotiate your offer.

Sample Phone Interview

Now I will go into further detail on how a phone interview is conducted using a sample problem I found online. Be sure to read the tips, it's very important!

A recruiter will begin by pasting a challenge to solve on the shared document. The problem will always be ambiguous, period. It's your responsibility to come up with edge cases and to ask questions to clarify the problem.

Before we write a single line of code we need to clarify the function input/output constraints.

Test Cases

I begin by typing a bunch of random test cases on the shared document and ask the recruiter if I need clarification. As I'm typing these test cases I am always talking outloud (which I will demonstrate with quotes).

Okay... this is the simplest test case; arr is null or empty.

... and in this test case, I'm assuming that there's an astronomically large array where each element is unique and k is the length of the array.

Another thing to note is that each element will have a frequency of 1. This is definitely an edge case and the worst case scenario for this problem.

In this test case we have an enormous amount of 1's, which is the only unique element and k is equal to... five.

This is an edge case since k is greater than the number of unique elements.

.. and finally in this test case, we have two 2 elements, two 4 elements, two 5 elements, and one 3 element and k is equal to two.

In this test case we have three elements with the same frequency.

Function Signature

The recruiter may or may not have given you a function signature. Now that we know some of the constraints we can proceed to creating a function signature.

def get_most_frequent(arr, k):

Clarification Questions

Ideally you want to be asking questions while creating your test cases. Here are a few questions we can ask based on the previous test cases.

Can we assume the array will not be empty or null?

Some interviewers told me I could assume a valid input, others told me to assume it was a Public API, meaning there is a possibility of a null value being passed in. Lets assume it's a Public API.

What we should do if the array is null?

The interviewer should tell you what is expected on an error. In my scenario the interviewer told me it was a library, so I should raise an error (a.k.a. an exception in other languages).

def get_most_frequent(arr, k):
    if not arr:
        # arr is null or empty, throw an error.
        raise ValueError

What is the maximum size of the array?

Most of the time the size of an array will be a finite size of n, where n can potentially be a massive number. State your assumptions out-loud to your interviewer.

What should the algorithm do when k is greater than or equal to the number of unique elements in the array?

In this sample we'll return all the unique elements in frequency order.

What should the algorithm do if two elements have the same frequency?

In this sample use the smallest element value as a tie breaker.

Now that the interviewer told us how to handle edge cases, we can add outputs to our existing test cases.

Coding a solution

At this point of the interview we should be thinking about the data structure we need to solve this problem. One obvious data structure we need is a dictionary (a.k.a. hashtable) to count the frequency of each array element. If you use Python you can use either the Counter or defaultdict built-in type. If you use another language you should be familiar on how to make a dictionary.

from collections import defaultdict

def get_most_frequent(arr, k):
    if not arr:
        # arr is null or empty, throw an error.
        raise ValueError
    
    counter = defaultdict(int)

    for element in arr:
        # Increment the frequency of the element by 1.
        counter[element] += 1

We now have an unordered map from array element to frequencies. For example if the array is [1, 1, 2, 3] the counter should be.

counter = {1: 2, 2: 1, 3: 1}

Since we can't guarantee order with a dictionary, we'll need to convert it into an ordered data structure. Since we need to extract only k elements, we can use a heap. Another option would be to use a bucket sort since we're only dealing with integers. Recognizing when to use a certain data structure like this requires practice. This is why you want to practice coding challenges first and foremost.

Remember our edge case: The answer must be sorted by frequency and smallest element value as a tie-breaker, which means the heap key must reflect this.

Python tips:

Heaps (heapq) are min-heaps, if you want to simulate a max-heap in Python, make the frequency negative.

We can add tie breakers by making the heap key a tuple. In our case we want our heap key to be (-frequency, element). The frequency will be the primary key and the element value will be the secondary key. Since the frequency is negative, the min-heap will be constructed using the highest frequency value and the lowest element value.

from collections import defaultdict
from heapq import heapify, heappop

def get_most_frequent(arr, k):
    if not arr:
        # arr is null or empty, throw an error.
        raise ValueError
    
    counter = defaultdict(int)

    for element in arr:
        # Increment the frequency of the element by 1.
        counter[element] += 1
    
    # In Python, heaps are represented as lists.
    freq_heap = []
    
    for element in counter:
        # Get the number of times the element has been encountered in the array.
        frequency = counter[element]
        # Append it to the (not yet constructed) heap.
        freq_heap.append((-frequency, element))

    # Convert the list of elements into a min-heap
    heapify(freq_heap)

Now that we have a populated heap, we simply need to pop out the most frequent elements!

Remember, we also have an edge case: when k > len(freq_heap) a.k.a k is greater than the number of unique elements in the array.

from collections import defaultdict
from heapq import heapify, heappop

def get_most_frequent(arr, k):
    if not arr:
        # arr is null or empty, throw an error.
        raise ValueError
    
    counter = defaultdict(int)

    for element in arr:
        # Increment the frequency of the element by 1.
        counter[element] += 1
    
    # In Python, heaps are represented as lists.
    freq_heap = []
    
    for element in counter:
        # Get the number of times the element has been encountered in the array.
        frequency = counter[element]
        # Append it to the (not yet constructed) heap.
        freq_heap.append((-frequency, element))

    # Convert the list of elements into a min-heap
    heapify(freq_heap)
    
    # Get the number of unique elements
    n = len(freq_heap)
    result = []
    for _ in range(min(n,k)):
        # Pop the most frequent element from the heap.
        _, key = heappop(freq_heap)
        result.append(key)
    
    return result

We're done coding! The solution looks clean and has plenty of comments that anyone can follow. At this point you may be asked to run your code on your test cases.

Big-O

We confirmed the solution works, now the interviewer asks us...

What is the time complexity of your solution?

Lets begin by thinking about our runtime variables, the size of the input array is n.

The number of unique elements in the array is m. Since you can't have more unique elements than total array elements then m ≤ n.

The most frequent elements we want to return is k and likewise, k ≤ m since we can't return more than a heap of size m.

While you're coding you want to always be mindful of time complexity, most of the time brute force isn't going to cut it. Since I chose to use a heap, the worst case will always be O(n * log(n)) when k == m == n. Lets review the runtime of every block.

from collections import defaultdict
from heapq import heapify, heappop

def get_most_frequent(arr, k):
    if not arr:
        # arr is null or empty, throw an error.
        raise ValueError
    
    counter = defaultdict(int)

    for element in arr:
        # Increment the frequency of the element by 1.
        counter[element] += 1

In this block the runtime will always be O(n).

    # In Python, heaps are represented as lists.
    freq_heap = []
    
    for element in counter:
        # Get the number of times the element has been encountered in the array.
        frequency = counter[element]
        # Append it to the (not yet constructed) heap.
        freq_heap.append((-frequency, element))

    # Convert the list of elements into a min-heap
    heapify(freq_heap)

In this block we're appending each unique element to a list, then calling heapq.heapify, which interestingly enough, runs in linear time. So this block of code runs at O(m) with a worst case O(n) if m == n.

    # Get the number of unique elements
    n = len(freq_heap)
    result = []
    for _ in range(min(n,k)):
        # Pop the most frequent element from the heap.
        _, key = heappop(freq_heap)
        result.append(key)
    
    return result

In the final block of code, we're perform a heap pop min(k, m) number of times. Best case scenario k < m is O(k * log(m)). Worst case scenario is O(n * log(n)) when k == m == n

When you add up all the worst cases you get O(n + n + n * log(n)), removing the non-dominant terms we end up with O(n * log(n). Interviewers should be happy with this answer. Just be sure to know thy complexities!

Conclusion

Passing a technical interview is a skill in itself. I'm hoping this article gave you some insights into what to expect when interviewing with these companies. If you have experience interviewing and see any incorrect information or would like to append anything please let me know and I'll happily amend this article. Good luck!

Image by Mohamed Hassan from Pixabay