Interview with a Meta engineer.

An Interview with a Meta engineer

Watch someone solve the finding nearby friends problem in an interview with a Meta engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type
Finding Nearby Friends

Interview question
Design the service for finding nearby friends.

Interview Feedback

Feedback about Tasteful Pirate (the interviewee)
Advance this person to the next round?
Yes
How were their technical skills?
4/4
How was their problem-solving ability?
3/4
What about their communication ability?
4/4

TC clarified the definition of nearby.
TC clarified the number of friends to be displayed.
TC talked about the pagination.
TC shared the assumption that making a friend is out of scope for this discussion.
TC clarified how the user would interact with the feature.
TC clarified the abilities to be provided to the user.
TC clarified if the radius is custom input.
TC identified that availability, scalability, and performance are critical.
TC mentioned that there would be a trade-off between consistency and availability.
TC clarified how many users would be there.
TC clarified how many friends a user can have.
TC asked the average number of interactions from a user to this feature.
TC clarified how much delay is acceptable in terms of real-time location of the user.
TC correctly analyzed the storage and QPS.
TC clarified if they should move to the API design.
TC came up with a good set of APIs for the problem.
TC was able to find the observation that the scale for read and write would be different.
TC shared the working naive solution and identified that there is a bottleneck.
TC mentioned that they would use batch requests to get the locations of all the friends for a given user.
TC mentioned that they have heard about geohash to represent the geo-location.

Feedback about Red Maelstrom (the interviewer)
Would you want to work with this person?
Yes
How excited would you be to work with them?
4/4
How good were the questions?
4/4
How helpful was your interviewer in guiding you to the solution(s)?
4/4

All around a very solid interviewing experience. He guided me towards the discussion points he wanted to address while also giving me some freedom to think my design through. Feedback had great points on where I can improve and also resources I could search in order to continue growing my system design skills.
I am very happy with this mock interviewing round.

Interview Transcript

Finding Nearby Friends: System Design Interview with a Facebook Engineer - YouTube

Red Maelstrom: Awesome. So, yeah, this is the problem we'll try to solve. So we want to design a service in which people can find nearby friends. So let's say they have a Facebook or Instagram on such an app. They want an extra feature called Nearby Friends where they can go and search, like, who are nearby friends?

Tasteful Pirate: Okay, so it's an extra feature.

Red Maelstrom: An.

Tasteful Pirate: App like Facebook and Instagram to find nearby friends. Okay. And this is a little broad. I want to define some scope so that we can start coming up with functional requirements. What do we mean by finding nearby friends?

Red Maelstrom: Do we have nearby geographically? Yeah.

Tasteful Pirate: I'm assuming we have our location, which is a center. The location of our device is a center. We're going to have a radius. We're going to have a radius of some sort, and we can configure that radius. Right. And people, our friends that are nearby within that radius are going to be returned on some sort of a list or what's the experience going to be like?

Red Maelstrom: Yeah, so the experience is going to be like, let's say that they open this tab like my nearby friends, and in that tab on the map, they will see smiley faces and the name of those friends, which they fall under the three Ds.

Tasteful Pirate: And do we have a cap on how many friends? Like, let's say we're at a show, right? Taylor Swift concert. Do we care if you want to limit to 20 or maybe we want to paginate?

Red Maelstrom: Oh, that's a really good question. Yeah, maybe 20 to 25. Consider pagination. All right. And our friends are going to be contacts, and I'm going to assume that they're already our friends and that designing the part where we make friends is out of scope.

Red Maelstrom: Righteous.

Tasteful Pirate: We have find nearby friends. Okay. All right, so let's try and start defining the functional requirements here, right? What will trigger this feature? Is it a button in the cell phone? Will I open the app? Is it going to be a widget? How would I, as a user, interact with the feature?

Red Maelstrom: Sorry?

Tasteful Pirate: If I were a user of this feature. How would I interact with it? Is it a button on the app? Is it a tab?

Red Maelstrom: Yeah, there would be some button which yeah, there is a button on app which opens a new screen in which this response would be this screen would be.

Tasteful Pirate: Correct in the newsfeed as some sort of a widget.

Red Maelstrom: New screen. I mean new screen. Yeah, new screen. Widget.

Tasteful Pirate: Okay. It's important to know because if we show this as a widget on the newsfeed, we're going to have a lot larger volume of reads than if it's a button and we have to go on a separate screen. So it's good information to know this. Right. I'm feeling confident about this, and I feel like we may be ready for defining the functional requirements. So let me start with that. Okay. The obvious feature is, as a user, I should be able to see a list of my nearby friends when I access the new feature. Right? As a user, I need to share my location so that my friends can find me if I am within their radius.

Red Maelstrom: Right.

Tasteful Pirate: As a user, I should be able okay. All right, so I need your help with this one. Is this radius configurable?

Red Maelstrom: Sorry?

Tasteful Pirate: Is this radius configurable? Can I say, hey, I want to.

Red Maelstrom: Yeah, we have some fixed radius. Not custom, okay. Like maybe two, five or seven, something like that, but not a custom input.

Tasteful Pirate: Between two to 3 km or like, some fixed radius. Right. Defining that radius will not be a trivial problem, but the fact that the user will not be able to configure that radius will cut one use case, one functional requirements that we would otherwise need to have. All right, so as a user, I should be able to see a list of my nearby friends when I access the new feature. And as a user, I need to share my location so that my friends can find me when they access the feature and I'm within their radius. And I think if we don't configure the radius, I think these functional requirements may satisfy what we want and what we expect for the new feature. Am I forgetting anything? Do you think this is good enough?

Red Maelstrom: I think yeah, these are good enough.

Tasteful Pirate: Okay, awesome. All right, so I'm going to move on, and I'm going to start defining the non-functional requirements. Now, these are important because from my experience, we should be able to use these to guide our decisions when we contemplate multiple design choices on the project. So what are the crucial non-functional requirements here? I think availability, scalability.

Red Maelstrom: Okay.

Tasteful Pirate: Performance. And I need to think about consistency because I don't know what kind of trade there's usually a trade-off between availability and consistency, and it's hard to see what those trade-offs would entail in a system like this until I started defining the components. So I'm going to put consistency here, and this is going to be like a bonus. Right. If this is important, in the end we can reorder, but for now, I'm going to do it like this. So availability, you should have a service that's very available. It should obviously scale to Facebook and Instagram scale. Ideally, performance should be prioritized because it's always a good user experience to have a fast service. And in the end, it may be the case where consistency will bubble up the ranks depending on how the system becomes. But for now, I'm going to put it on four. All right.

Red Maelstrom: Okay.

Tasteful Pirate: Usually here I contemplate a few different options. Right. So we can, one, design the API, or two, try to estimate traffic or data requirements, or three, we can try to come up with data models. Right. So do we care about should I try to design an API?

Red Maelstrom: Yeah.

Tasteful Pirate: All right.

Red Maelstrom: Before that, can we do some estimates? Like how much would be the QPS and how much would be storage?

Tasteful Pirate: We can do those in any order. Right. So I said the three things that I like to do before I jump into the high-level architecture. So we can do estimation, and those are traffic and data storage estimations. Right, okay. Now it I think we need some answers here before we move forwarder. Right. How many users? How many users does this good question.

Red Maelstrom: Yeah, let's say that 10 million daily active users.

Tasteful Pirate: 10 million daily active users?

Red Maelstrom: Yes.

Tasteful Pirate: Okay. And what's the average number of friends each user has? Is that a good metric?

Red Maelstrom: 1000? Yeah, I think that's an important question.

Tasteful Pirate: No?

Red Maelstrom: Yeah, let's say 1000 max. On average. Let's say 500.

Tasteful Pirate: 500 friends. Okay. So the 100 percentile of the number of friends is going to be some person having 1000 friends, and on average, we're going to have 500 friends per user and there are daily active users on the platform. Okay, sounds good. All right, so let me try and define what a record would look like. Right. So I'm assuming that at some point we're going to be sharing our coordinates, latitude and longitude, and we're going to be storing that in some sort of data store. Right. So user location, that's going to be something like latitude, which is going to be a floating point, longitude, also floating point. And this thing is going to be an extra field on the user profile. Right, sorry. Yeah.

Red Maelstrom: I think these would be maybe along with that, maybe some meaningful name, but yeah, I'm not sure we can come back to that. But I think for now, lifelong was enough.

Tasteful Pirate: Yeah, no, this is the draft. Right. We can refine this later if we have the time for it.

Red Maelstrom: Sure.

Tasteful Pirate: Okay. So this is not a lot of space. This is not a lot of extra space. Right. So what if we if we if we put this in terms of bytes of bits right. And we consider that this is ASCII so this is 816, blah, blah, blah. I would say this would be something in the order of maybe 300 bytes. Not 300 bytes, 100 bytes, maybe 800 bits or something like that. And if we're going to be adding this to every user profile right. This is going to be all right, hold on. 200 bytes. Right. So the extra storage that we're going to need is something in the order of 200 bytes times 10 million daily active users. Do we care about non-active users, though? Because if we're going to be adding these.

Red Maelstrom: I think for now, let's say that non-active users are not much, so yeah, we can ignore that.

Tasteful Pirate: Okay.

Red Maelstrom: What I mean by daily active users are at least these are the users who are sharing the location for this feature.

Tasteful Pirate: Oh, I see. Okay. So this would be 2000 megabytes is 2GB, which is not too much, which is great. If we need a lightweight data store for this, there's a chance where we don't have to shard it as much, which is nice. All right. Can I assume that we already have a data store storing all the friends, like, all the friend relationships right?
Red Maelstrom: Yes.

Tasteful Pirate: Okay, awesome. Okay, so this is probably good enough for data storage estimation. What's the frequency of requests that I should expect on a daily basis for an average user?

Red Maelstrom: How many times he will check the nearby users?

Tasteful Pirate: Yes. On average, yeah.

Red Maelstrom: We are expecting, like, at least ten times.

Tasteful Pirate: To feature. Ten times per day. Okay. And what is the expected delay on location? Right? Because if we're going to be doing something like this, I expect users to be sending some kind of a heartbeat request to one of our services in the back end to share their current location. Right. So what is an acceptable delay for us to be able to pull that so we can send?

Red Maelstrom: That's a really good question. Let's say that 32nd is acceptable.

Tasteful Pirate: Acceptable delay for updating location. All right. Okay. So for traffic estimation okay, so each one of our daily active users of our 10 million daily active users is expected to access the app, on average, ten times. Right. And I think this is a realistic estimation because there are people who are going to be accessing less, and obviously, we're going to have some power users. And the average I think it's going to be a good measure of how many total requests we should be expecting in terms of traffic for this new feature. So in terms of the access request, we're expecting ten requests per day times 10 billion users. Right. That's going to be 100 million um, yeah, 100 million requests per day. And we can convert this to seconds so that we can arrive at a neat QPS value. But do you think this is good enough? I'm just about time. This is good enough, yeah. Okay, awesome. In terms of the location heartbeat request.

Red Maelstrom: Can you just convert this into per second? Just a small per day.

Tasteful Pirate: I see. All right, hold on. So times 24 hours per day times 60 minutes. Per hour times 60 seconds/minute. This should give us something.

Red Maelstrom: Right.

Tasteful Pirate: Per second. Now I need to grab my calculator if we really want to convert this.

Red Maelstrom: No, that's okay. You can convert this into 100 for simplicity. You can assume 60 as 160, also as 100 for safer thing. And this 24 ten it will be approximately.

Tasteful Pirate: All right. Yeah. Okay. So if we want to make the math easier, this is going to be ten to the second, ten to the fourth, ten to the fifth times. This is going to be 100 million. Million is ten to the 6th. So this is like ten to the 8th. Right. If we multiply it by it's going to be ten to the 8th times ten to the fifth, which is going to be equal divided.

Red Maelstrom: Right. It would be divided. Right.

Tasteful Pirate: No. Yeah, I got confused. So ten to the third, ten to the power of three. So that's 1000. 1000, yes. For this query.

Red Maelstrom: Right.

Tasteful Pirate: Okay. All right. So for the other request right. The heartbeat request, this will be every user will make one request every 30 seconds. So in terms of QPS, we can consider, as, if one user makes one 30th of the request in a second, right?

Red Maelstrom: If we're trying to good way to look at it. Yeah.

Tasteful Pirate: QPS per user, that's times 10 million users equals 10 million divided by 30. That's 1 million divided by three, which is 3000. No, 300,000, 333,333 or something like that.

Red Maelstrom: Yeah. Let's approximate to $300,000, right?

Tasteful Pirate: Yeah. So I think this is probably enough estimate because I think we're covering all the use cases. Right?

Red Maelstrom: Right.

Tasteful Pirate: All right. Okay. So do we want to design an API for this?

Red Maelstrom: Sure.

Tasteful Pirate: All right. So there's two functional requirements that we want to satisfy here. As a user, I should be able to see a list of nearby friends when I access the feature. That could be something like get nearby.

Red Maelstrom: Friends.

Tasteful Pirate: My User ID. And since the radius is fixed, I'm not going to put it as an argument here. Right. But if it was, we could put radius as a second argument. If we were looking at the Rest contract, this would be get friends nearby user ID equals my user ID. Or if we have authentication, this could be something like in the headers, I have a session token or a user token with which the back end services could parse them and somehow use them to retrieve the user ID associated with my application right. With my session.

Red Maelstrom: Okay.

Tasteful Pirate: So this should be a good start for the first use case. The second use case is update User Location.

Red Maelstrom: So won't you need users correct location with this API, or like you are assuming that it would be stored somewhere on the server.

Tasteful Pirate: Good question, because if I'm sharing my location, in theory, I could get this from a back end data store. But if we really want to, we can share the location here as well.

Red Maelstrom: Here.

Tasteful Pirate: Something like this, right? And update user location, latitude, longitude, and that's it. Right. It doesn't return anything, just returns maybe a 201, no content or like acknowledgment. In terms of if we were to design this as a restful service, this could be a patch, right? Or a post. It really depends. So patch user location and I don't know if we want to be putting it on the query string just for security purposes because this is sensitive information. User location, sensitive information. It's PII, I think. Right. Obviously we're going to have a session token or a user token or something that our back end services can use to identify who's making this request. And then I think I'm going to put it on the body. Right. So that Https, everything's going to be encrypted and it's going to be less easy for a malicious middleman to just take a look at the location of the user at regular intervals. Right. So latitude, longitude, and I think this.

Red Maelstrom: Is.

Tasteful Pirate: What do you think about this API design? Do you think this is good or am I missing something?

Red Maelstrom: I think yeah, this is good. Maybe you already know the header from user token, you know, the user providing that long.

Tasteful Pirate: Sorry, I think you broke up. I'm trying to understand your last message. Is this good? Do you think I'm missing yeah, I'm.

Red Maelstrom: Saying, like, this is enough.

Tasteful Pirate: This is good enough. Right? Okay. All right, so I think we should probably have enough to start drafting a nice high-level architecture for the service. I'm just thinking about what kind of a data store I'm just thinking what kind of a data store would be best suited for us to be able to store these locations or if we should be storing them on the user profile data store along with the rest of their profile. Just because this data is ephemeral and I think it's going to be changing often. So I'm not sure. Maybe a key-value data store would be a good idea. Something that resembles a cache, like a redis data store. If it is something like a cache, we could set how do you call it, a retention policy, right? We could set a TTL so that users that are no longer active or that logged out for more than like 15 minutes, they're just going to be overwritten. The more I speak, the more I'm convinced that this should probably be a good way to do.

Red Maelstrom: It.

Tasteful Pirate: Yeah. So I'm going to go to the whiteboard, I think.

Red Maelstrom: Yeah, I moved to the whiteboard.

Tasteful Pirate: Okay. All right. So, yeah, let's start with the user. Right?

Red Maelstrom: Okay.

Tasteful Pirate: I'm going to do squares because I don't know how to scale draw.

Red Maelstrom: No problem.

Tasteful Pirate: Okay. So I have the user, right? And I'm going to do the diagram for sharing my location. First, I'm going to define something of an API gateway. It's a very common component. It's a very common front-facing component for backend applications today. And the API gateway is great because it has some responsibilities which are very neat. We would expect it to be the component that performs the authentication and the authorization, meaning it extracts the tokens out of the headers and maybe parses them if they're JWTs or if they're just opaque strings. It would just try to fetch the user information out of some data store and you get the user information inside the request and then attach it as some header to our internal backend data structure, load, chatting rate limiting, all that good stuff. It's going to be here, right? It's going to be on API gateway. Okay, so how do we do this? So here's my key-value cache, right? And key-value cache is going to be how do I okay, stores. So the key is going to be the user ID.

Red Maelstrom: Okay.

Tasteful Pirate: And the value could be the pair of longitude and latitude.

Red Maelstrom: Righteous.

Tasteful Pirate: Yeah. And we could define the service that will be the logical cache manager as the we could call it the User location service or the user location Manager. And it would be as simple as this. So every 30 seconds or so, we're going to make that request, that batch request, to get my location into the key value data store passing through the API gateway. And this guy will populate the key value data.

Red Maelstrom: This is and how this key value data store would be like, what would key is your user ID. And the value is let long. Okay. How will this be optimized for the querying part? Because the query is let's talk about that part and then come back to this.

Tasteful Pirate: Sorry, can you repeat? It's hard for me to understand you.

Red Maelstrom: So, yeah, I understood the writing part of it the way you are writing data into the key value store. But let's also talk about how you would query the data from this key value store.

Tasteful Pirate: I see. So we're talking about the other flow, right? We're talking about getting the least users. Okay, yes. I'm going to define another diagram and pretend that this is the same user. It's just I'm doing this for, you know, ease of visualization. So here's the same user, right? And so I'm gonna make I'm gonna make that request right. Get list of nearby friends. And we're probably going to go to another service, I think. Does it justify this being a different component? So this service is supposed to, given my user ID, get a list of my friends. And given that list of friends, I should get the key values. Sorry. All right, so given that list of friends. For each friend, I should get the location right, the latitude and the longitude for that friend. And then if it somehow falls under the radius, we put that friend on the list or something like that. So I'm going to do how should we call this service? There's a case to be made for this functionality to be inside the User Location Manager itself, where semantically, it's location management. Right. Like getting a list of the nearby friends is something that User Location Manager could be responsible for. The reason why I don't like this is because if we separate these services, we should be able to scale writes and reads separately. Right. We're obviously going to be doing a lot more writes, and there's probably a lot of need for us to scale reads alongside that. So I'm going to call this nearby friend service. So the user is going to make that Get request. That get request is going to be redirected by the API gateway into Nearby Friend Service. Nearby Friend Service then will make a call to this black box that I'm going to define, and we're going to call it the Friend Services. Right.

Red Maelstrom: Okay. So this service exposes your API, the first API, which you wrote in API design, right? Yes. Nearby Service.

Tasteful Pirate: Yes.

Red Maelstrom: Okay.

Tasteful Pirate: And we're going to call this service. And we have agreed that this functionality is already built, so it's out of the scope for this design exercise. And I'm going to give it my User ID and it’s going to give me a list of free ends for that user ID. All right? Okay. So now I have a list of my friends, right. And I know that those friends are limited to 1000 friends. A naive approach here would be for me to then query the cache. Right. I think I can query directly 1000 times.

Red Maelstrom: Okay.

Tasteful Pirate: This would be naive approach. Get the location for each of my friends and then do some filtering based on location and return the list of friends to my user. Because the number of friends is 1000. Right. It's kept at 1000. I'm not entirely sure whether Redis is capable of doing bulk requests. Right. Because if we could batch this somehow, it would be great because we would offload a lot of network. That's a good point out of this equation. I don't know if Redis supports that.

Red Maelstrom: Let's assume that it's a port.

Tasteful Pirate: Okay.

Red Maelstrom: Or maybe worst case, you can have something on top of Redis which does this for you and return back to you network. You are talking in terms of I.

Tasteful Pirate: Got toggled back to the text editor. I don't know what happened.

Red Maelstrom: Okay. You can click on bottom left toggle whiteboard.

Tasteful Pirate: No. Yeah. Okay. All right. Let's pretend that Redis supports batching, right? So we can batch request for the location of my friends. And then.

Red Maelstrom: Is there any efficient way of representing the data to facilitate the.

Tasteful Pirate: Query part the query part. Well, what data are you are you referring to the user profiles or the location?

Red Maelstrom: The location.

Tasteful Pirate: The location. I have heard about a hashing method called geo hashing, which seems to be very useful for us to represent the location.

Red Maelstrom: Okay.

Tasteful Pirate: I have seen instances do you have.

Red Maelstrom: An idea about sorry. Do you know how it works?

Tasteful Pirate: Yes. It's a hashing method that produces a string based on how do I say this? It produces a string based on the location, and that string gets longer as the location gets more precise. So if we're looking at a huge chunk of Earth, then the number could be nine. And if we're looking at one eight of that huge chunk of space, then it would be like nine e or nine or something like that. And as we get smaller and smaller, that string gets longer and longer. And I think it can go up to 19 characters of length. And that's like pretty impressive. It's like nanometers of precision. So I think there's a case to be made here where we could perhaps use this geohashing to efficiently store the latitude and longitude encoded as the geohash string. Right. So it'd be something like nine EVGF, 38, something like this. Right. And then when these results return from the batch call, it's going to be a lot easier, I think, to compute the users that are closer to me, just because.

Red Maelstrom: You will still need to do the 100 if there are whatever number of users that may require queries. Right.

Tasteful Pirate: Can you repeat that last part? I just want to make sure I understand.

Red Maelstrom: Okay. So this service exposes your API, the first API, which you wrote in API design, right? Yes. Nearby Service.

Tasteful Pirate: Yes.

Red Maelstrom: Okay.

Red Maelstrom: Okay.

Red Maelstrom: Let's assume that it's a port.

Tasteful Pirate: Okay.

Tasteful Pirate: Got toggled back to the text editor. I don't know what happened.

Red Maelstrom: Okay. You can click on bottom left toggle whiteboard.

Red Maelstrom: Is there any efficient way of representing the data to facilitate the.

Tasteful Pirate: Query part the query part. Well, what data are you are you referring to the user profiles or the location?

Red Maelstrom: The location.

Tasteful Pirate: The location. I have heard about a hashing method called geo hashing, which seems to be very useful for us to represent the location.

Red Maelstrom: Okay.

Tasteful Pirate: I have seen instances do you have.

Red Maelstrom: An idea about sorry. Do you know how it works?

Tasteful Pirate: Yes. It's a hashing method that produces a string based on how do I say this? It produces a string based on the location, and that string gets longer as the location gets more precise. So if we're looking at a huge chunk of Earth, then the number could be nine. And if we're looking at one-eighth of that huge chunk of space, then it would be like nine e or nine or something like that. And as we get smaller and smaller, that string gets longer and longer. And I think it can go up to 19 characters of length. And that's like pretty impressive. It's like nanometers of precision. So I think there's a case to be made here where we could perhaps use this geohashing to efficiently store the latitude and longitude encoded as the geohash string. Right. So it'd be something like nine EVGF, 38, something like this. Right. And then when these results return from the batch call, it's going to be a lot easier, I think, to compute the users that are closer to me, just because:

Key Points