Taro's official blog designed for Software Engineer career growth. Onboarding, compensation, promotion and more
Subscribe
Meta

Meta Software Engineer Interview Question Breakdown: Finding Unique Integers

Meta Software Engineer Interview Question Breakdown: Finding Unique Integers

Back when I was at Meta, I interviewed ~100 engineers, specializing with data structures and algorithms (DSA) questions (internally known as the "Ninja Round"). Meta has a pretty rigorous and standardized process for training its interviewers, and I really came to appreciate that as I worked at the company and absorbed its incredible engineering culture.

In this new series, I will go through the interview questions I asked at Meta in-depth, including how I graded them. I'm hoping this helps you understand:

  1. How to properly solve DSA problems and treat them as more than a raw memorization grind
  2. The complexity behind how FAANG companies evaluate software engineer candidates.
  3. How to give interviews yourself, which will help you mock interview others

Meta in particular has a great philosophy behind extracting the maximum signal from candidates, and I'll be going through that in the rest of the article.

The Problem

This question was the warm-up I gave during the phone screen. It was essentially a check to make sure that the candidate could code and had basic problem solving abilities. After they (hopefully) solved this problem, I would give them another DSA problem. This means that the candidate should spend 15-20 minutes on this part max, otherwise there's not enough time for the 2nd problem.

Here's the problem: Given a list of numbers, return a list of all the numbers that are unique within that list (i.e. they aren't duplicated).

Let's clarify this with an example:

Input: [1, 10, -4, 2, 7, 8, -2, 98, 10, 8, 2]

Output: [1, -4, 7, -2, 98]

Simple enough right? Well, you would be surprised at how many candidates failed this. Let's go into how we can add a lot of complexity to it.

The Setup

If you look at the prompt, it's purposely vague. "Number" is a generic term that can refer to many things. "List" is generally a keyword, but it's also a generic term. I did this so the candidate would ask questions to clarify the problem like:

  1. What kind of numbers are we dealing with? Is it just Ints or is it Double or Float?
  2. What is the input data structure? Is it an Array, List, or something else?
  3. How many numbers can be in the list?
  4. Can the list be null or empty? What do we return in these cases?

The "Optimal" Solution

This problem boils down to knowing what a HashMap/Dictionary is. The logic is as follows:

  1. Create a HashMap of numbers to track how many times you have seen each number.
  2. Iterate through every number in the list and keep the HashMap updated.
  3. After your loop is done, go through the keys in the HashMap and extract everything where the value is 1.

Here's the solution in Java (my main programming language during my Meta days):

public static List<Integer> findUniqueIntegers(int[] arr) {
    Map<Integer, Integer> frequencyMap = new HashMap<>();
    List<Integer> uniqueIntegers = new ArrayList<>();

    // Count the frequency of each integer in the array
    for (int num : arr) {
        frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
    }

    // Add unique integers to the result list
    for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
        if (entry.getValue() == 1) {
            uniqueIntegers.add(entry.getKey());
        }
    }

    return uniqueIntegers;
}

Run-time: O(n) - You only need to go through each number once and updating the HashMap is O(1) for each operation. Reading through the keys at the end is also linear.

Space: O(n) - The HashMap is 2n space, which reduces down to O(n).

The Follow-Ups

The first thing I did after the candidate got the 1st solution and explained it was to make them really think through how to make their code robust. I asked something like this: "Let's say this code you wrote is going to production and thousands of engineers in your company will call it. What test cases can you run by it to really show your teammates that the code is truly rock-solid?"

From there, I would expect some collection of these (some of which may have been mentioned in the setup step):

  1. The list is huge (i.e. several billion numbers or more)
  2. The list is tiny (0 or 1 items)
  3. The list is null
  4. Everything is a duplicate
  5. Everything is unique
  6. The list is just the same number repeated many times

After the edge-case discussion is where things got exciting! The main evolution here is asking for an alternative solution. Since coding takes time (especially when you have to both code and explain yourself simultaneously), I didn't ask candidates to code out the 2nd solution. Being able to explain the approach and having some very rough pseudo-code was enough.

So in the "optimal" solution, the run-time is optimized. However, it allocates O(n) amount of space. After candidates coded it up, I would ask them if we could come up with another solution that made trade-offs against the 1st one (hinting that they can sacrifice run-time for better space usage).

The alternative solution with O(1) space is as follows:

  1. Sort the input list and create an output list
  2. Iterate through each number
  3. For each number, linearly scan ahead to see how many instances of it there are. Jump to the end of the "duplicate train"
  4. If there is no duplicate train, add the number to your return list
  5. After you have gone through the entire input list, return the output list from #1

Here's the Java solution:

public static List<Integer> findUniqueIntegers(int[] arr) {
    List<Integer> uniqueIntegers = new ArrayList<>();

    Arrays.sort(arr); // Sort the array in place

    int n = arr.length;
    int i = 0;

    while (i < n) {
        int current = arr[i];
        int count = 0;

        // Count the frequency of the current element
        while (i < n && arr[i] == current) {
            count++;
            i++;
        }

        if (count == 1) {
            uniqueIntegers.add(current);
        }
    }

    return uniqueIntegers;
}

Run-time: O(n log n) - Sort is the dominant operation, and it is n log n. Everything else is linear.

Space: O(1) - The only space we allocate is for the return list which doesn't count.

Grading

At Meta, there are 3 types of "Yes" votes:

  • Strong Yes - The candidate completely crushed it. I would be surprised if they did too poorly on other parts of the interview. Candidates in this bucket always have superb communication skills.
  • Yes - The candidate did quite well.
  • Weak Yes - The candidate barely passed, and I could easily be convinced by another interviewer in the panel to not extend this candidate an offer.

In order to get "Yes" on this round, the requirements are:

  • Get both optimal solutions (one for run-time and the other for space). Be able to write the 1st one and thoroughly explain the 2nd one
  • Have proper run-time and space-analysis for both
  • Ask 1-2 clarifying questions before diving into the problem
  • Be able to come up with at least 3 valid edge-case scenarios to test
  • Explain their code throughout the entire process

In order to get "Strong Yes", the candidate needs to have a mix of:

  • Excellent communication
  • More thorough edge-case analysis and problem clarification
  • Stellar coding speed + quality (be able to code the 2nd solution, get everything right on first try, clean variables, concise code).

50%+ of candidates failed this very basic problem. Here's where they messed up to drop into the "No" vote categories:

  • They weren't able to get the 2nd solution
  • They didn't ask any clarifying questions about the problem
  • They weren't able to do run-time and space analysis properly. Many candidates said that sort is O(n^2) or that the HashMap was O(1) space
  • They weren't able to come up with meaningful edge cases to test for
  • Their code was messy and/or didn't work
  • Their communication was poor in general and it was hard to understand what they were thinking

How You Can Get Better

If you're looking at all this and thinking that you probably can't pass a round that's as rigorous as this one, no worries - We're here to help! Check out these resources to actually improve your interviewing skills instead of just treating LeetCode as a memorization-fest:

Read next

Comments ()