Meta has a career portal (https://metacareers.com) and inside that portal there is a tab called "coding puzzles". These are public and intended as practice for technical interviews and they have a browser-based IDE that supports a number of languages and comes with a suite of test cases for each puzzle. Most of the test cases are hidden, which is typical for these kinds of challenges. In this post I will break down the first "Level 1" coding puzzle in detail.
The first coding puzzle is called "cafeteria" and the premise is that you are given a few integers as well as a list of integers with constraints on them:
- N: the total number of seats in the cafeteria.
- K: the number of seats required between customers (social distancing).
- M: the number of seats that are occupied.
- S: the list of integers representing occupied seats in the cafeteria.
We are provided with a list of constraints:
# Constraints: # 1 ≤ N ≤ 10^15 # 1 ≤ K ≤ N # 1 ≤ M ≤ 500,000 # M ≤ N # 1 ≤ Si ≤ N # Allowed runtime ≤ 5 seconds
And two examples:
N: 10
K: 1
M: 2
S: [2,6]
- Function should return 3
- Visual diagram of occupied seats:
1 2 3 4 5 6 7 8 9 10
[-|-] [-|-]
N: 15
K: 2
M: 3
S: [11,6,14]
- Function should return 1
- Visual diagram of occupied seats:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[---|----------|--------|---] The goal is to create a function that returns the number of unoccupied seats that are available after social distancing is taken into account. They provide a function scaffold for you (I'll use Python):
from typing import List def getMaxAdditionalDinersCount(N: int, K: int, M: int, S: List[int]) -> int: # Write your code here return 0
My first thought was a simplistic brute force approach: iterate over the entire seat space and add (and remove) potential available seats as you go. My engineering instincts told me this would not be the best approach, because it would lead to considerable logical complexity and maybe nested loops. On the other hand, thinking about the brute force approach got me started with some basic variables:
def getMaxAdditionalDinersCount(N: int, K: int, M: int, S: List[int]) -> int: # The return counter of available seats. num_seats: int = 0 # The K + 1 seats represent the potentially available seats. k_plus: int = K + 1 # Sort the list of seated diners so we can iterate over an ordered list. seated: List[int] = sorted(S) # More logic to come... return num_seats
At this point, it is useful to break down the problem a little further. There are two main approaches I explore:
- Imagine having to do this by hand on very large lists of seats: what's a way to divide the data into meaningful pieces we might be able to act on, but which are larger than the individual seats so that we don't have to iterate over and perform logic on each and every seat?
- Let tests guide us: come up with some additional test cases and manually determine what their expected results should be.
When trying to complete a real technical interview coding challenge you will have a time limit. The interviewer isn't always looking for a working solution, but ideally you won't wait until the last minute to run your code and see if the tests, visible and hidden ones, actually pass. Additionally, even if you run the tests early in the interview, the hidden ones could fail which won't give you any information about their test cases and stack traces. Test driven development (TDD) is hard to do in the dark. So let's consider a few additional test cases first (this is #2 above):
N: 10
K: 1
M: 2
S: [3,5]
- Function should return 3
- Visual diagram of occupied seats:
1 2 3 4 5 6 7 8 9 10
[-|---|-]
N: 15
K: 1
M: 1
S: [5]
- Function should return 7
- Visual diagram of occupied seats:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
[-|-]
N: 5
K: 0
M: 5
S: [1,2,3,4,5]
- Function should return 0
- Visual diagram of occupied seats: unnecessary/obviousThere's another edge case you might consider testing: no occupied seats. However, the constraint 1 ≤ Si ≤ N implies that S can't be empty. Therefore, we don't need to handle this case.
With our own test cases ready to go, we can see an easy solution to our last test case, where all seats are already filled:
def getMaxAdditionalDinersCount(N: int, K: int, M: int, S: List[int]) -> int: # Handle special case where the restaurant is full and no seats are available. if M == N: return 0 ... ...
The rest is the main part of the logic. Let's consider the gaps between each occupied seat. Is there a quick way to find the number of available seats in the gaps? Yes, we can divide the number of seats in the gap by K + 1. We should use the floor division operator so we always get the lower end integer of the operation, thus preventing over-counting. We are provided a list of occupied seats so we'll iterate over that in this snippet:
... for i in range(0, M): if i < M - 1: spaces: int = seated[i + 1] - seated[i] if spaces > k_plus: num_seats += (spaces // k_plus) - 1 ...
The above for loop should leave num_seats equal to 1 for the following test case:
N: 10 K: 1 M: 2 S: [2,6] - Function should return 3 - Visual diagram of occupied seats: 1 2 3 4 5 6 7 8 9 10 [-|-] [-|-]
When we look at the test cases, the obvious things we're missing are the ends of the total seat space (for this puzzle the visual diagram really makes the logic easier to grasp!). We have two options for handling them. One is to extend the for loop we just made to include the beginning and end of the total seat space. At first that seems easy, because ultimately it is just another gap of potential seats that we can divide by K + 1. However, adding the extra logic makes our for loop more complicated and harder to follow. Plus, logically we don't need to check for the initial and end gaps on every loop iteration.
In a real software application we'd probably want to keep this logic separated for two additional reasons:
- It's easier to pull out the logic into helper functions that we can write unit tests for.
- If requirements or constraints change in the future it'll probably be quicker to modify or extend.
Of course, in a coding puzzle in a technical interview our primary concern is keeping the logic straight so we can complete the puzzle and talk intelligently about it. We can always go back and optimize it for additional efficiency... if we get it completed in time!
Let's handle the beginning and the end in turn:
# Beginning. if seated[0] > k_plus: first: int = seated[0] - 1 if first - k_plus == 1: num_seats += 1 else: num_seats += (first // k_plus) # Ending. if seated[-1] < (N - K - 1): num_seats += ((N - seated[-1]) // k_plus)
The cool thing here is that we can skip either of these entirely with just a simple check as to whether there are enough seats in the beginning and ending gaps. Putting it all together we have the following (for clarity I removed any comments):
from typing import List def getMaxAdditionalDinersCount(N: int, K: int, M: int, S: List[int]) -> int: if M == N: return 0 num_seats: int = 0 k_plus: int = K + 1 seated: List[int] = sorted(S) if seated[0] > k_plus: first: int = seated[0] - 1 if first - k_plus == 1: num_seats += 1 else: num_seats += (first // k_plus) if seated[-1] < (N - K - 1): num_seats += ((N - seated[-1]) // k_plus) for i in range(0, M): if i < M - 1: spaces: int = seated[i + 1] - seated[i] if spaces > k_plus: num_seats += (spaces // k_plus) - 1 return num_seats
During some interviews you may be asked to estimate the complexity of your code. The code above has a time complexity of O(M log M). Remember, M is the length of list S. Specifically, the sorting of S has a time complexity of O(M log M), which is larger than the for loop's simple iteration which is O(M). Therefore the sort dominates the estimate and we can reasonably just say O(M log M). In terms of space complexity the only significant thing is the list S, so O(M).
Why coding puzzles?
It is worthwhile practicing many such coding puzzles and getting good at doing them quickly. Despite the fact that being able to complete such puzzles quickly doesn't say much about your ability to build software applications, most employers consider it essential in order to be considered for an open role. It is seen as both a gatekeeping mechanism to weed candidates out early in the hiring process as well as a sign that you'll code more proficiently and effectively than others. It's also a sort of professional cultural test. You must love coding so much that you spend your spare time doing it too. Even Robert Martin suggests doing coding puzzles in your spare time. But don't forget that he also says it's important to have a satisfying personal life and have your personal things in order so you can concentrate at work.
For some, the life of a software engineer is a delicate balancing act between coding at work and coding side projects in your spare time. The industry tends to extol this. While practicing tends to be a good thing, one's ability to do a particular coding puzzle quickly and under pressure doesn't necessarily mean they'll be good at other ones or anything else job-related for that matter. Further highlighting this silliness, many employers today will expect you to use AI assistance on the job, but in their technical interviews won't let you use it. If AI assistance makes you quicker and more productive, then what's the point of testing someone on a timed coding challenge and not allowing them to use it? Are you trying to test a candidate's dedication to the pure art of human software engineering? Or are you trying to test a candidate's speed and knowledge using the day-to-day tools, including AI, of the actual job?
Solving coding puzzles will probably always be important aspect of interviewing for software engineering roles. It can be a quick way to get an idea of the skills and knowledge of the candidate. But let's not forget that the candidate is a person with unique cultural backgrounds, language skills (not just programming languages!), education, work history, cognitive behaviors, health, assumptions, and expectations. Some candidates may have a lot riding on the interview and so experience greater pressure and stress. Other candidates may not do well multitasking in an unfamiliar environment and in a performative way during an interview, which they normally don't have to deal with when coding day-to-day. Still other candidates might not spend much time practicing coding puzzles. Are they a care-giver with little spare time? Do they have other hobbies or jobs or responsibilities? How much should coding puzzles really matter? Again, we arrive back at the question: what exactly are we trying to test? This is why a multi-stage interview process is both common in software engineering and also so very necessary. Everyone wants to hire the best candidates, but for most software engineering jobs it can't all be about solving a coding puzzle quickly!