Mock Interview: Real-World System-Design Interview Questions

Mock Interview: Real-World System-Design Interview Questions

By Frank Kane 

This article is an excerpt from our course, Mastering the Systems Design Interview. 

One of the best ways to prepare for an interview is with mock questions. Having thought through potential interview questions will help you to better articulate and position your answers. 

In this article, I will walk through mock interview questions that are often asked in the Systems Design Interview to help you prepare your answers before the interview. 

This set of mock interviews features questions I’ve asked as an interviewer, questions I’ve seen other interviewers ask, and questions I’ve been asked while interviewing at big tech companies myself. For each one, we’ll show you the right questions to ask before you dive into a solution and give you a chance to sketch out your own system design. 

Then, we’ll present a transcript of how a real interview might go and show you what a good interview for this question looks like. Finally, we’ll debrief after each mock interview and talk about what made that interview successful, and what you should learn from it. 

These are also opportunities to gain experience in how the various technologies we’ve discussed earlier in the course fit together. Practice makes perfect, and that applies to interviewing as well!

Mock Interview: Example #1

Question: Design a URL shortening service. 

CANDIDATE: OK, so we’re talking about something like bit.ly, right? A service where anyone can enter a URL, get a shorter URL to use in its place, and we manage to redirect them?

INTERVIEWER: Yup, at a very high level, that’s the idea.

CANDIDATE: What sort of scale are we talking about?

INTERVIEWER: A lot. Say millions of redirects every day. And we don’t want to

make any design decisions that might limit us later, so assume millions of URL’s as well.

CANDIDATE: Any restrictions on the characters we use? Symbols might be a little too hard for people to remember or type…

INTERVIEWER: It’s good that you’re thinking about usability and the customer experience. Yeah, symbols would be a pain, as would be remembering the capitalization of characters and stuff. But, would that limit you too much? Does that give you enough characters to work with?

CANDIDATE: Well, how short is short?

INTERVIEWER: The shorter, the better. How many characters do you figure you’d need?

CANDIDATE: Well, if we use nothing but lowercase letters and numbers to make them easy to remember… that’s 36 characters, right? So we basically have a base-36 system here. Personally, all I can remember would be 6 characters, so how many URLs could that represent? Whatever 36 to the 6th power is… mind if I use the calculator on my phone for that?

INTERVIEWER: Sure, I can’t do that in my head either.

CANDIDATE: Let’s see… oh wow, that’s over 2 billion. So yeah, 6 characters should be plenty for the foreseeable future.

INTERVIEWER: Sure, sounds good. Any more questions?

CANDIDATE: How about vanity URL’s? Can people specify their own URL if it’s available? 

INTERVIEWER: Yeah, that would be nice to have. Might be something only registered users or paid users get. 

CANDIDATE: Do we let them edit and delete short URL’s once created? 

INTERVIEWER: If they have an account, sure. We don’t want people editing or deleting other peoples’ URLs. 

CANDIDATE: How long do shortened URL’s last? 

INTERVIEWER: Well, forever. We don’t want a bunch of dead links out there 5 years from now. Good thing you’ve got room for 2 billion URL’s! 

CANDIDATE: Let’s start by thinking about the API’s to this system.

We’ve asked some clarifying questions here, and you have enough to get started. So, before we go into the actual mock interview and see how that goes down, try it yourself. Get a piece of paper, and sketch out some designs.

Here are some questions to ask: 

1. How would you implement the system? 
2. What API’s do you think will be needed? 
3. How will you work backward from those API’s to develop a system that can work at this massive scale, and handle both the storage of those mappings and the redirects?

Go give it a shot. 

Mock Interview: Example #2

Question: Design a Restaurant Reservation System 

CANDIDATE: Ok, you want me to design a restaurant reservation system. Is this just for one restaurant, or for any number of restaurants like OpenTable or something?

INTERVIEWER: It’s like OpenTable, so it can cover many restaurants.

CANDIDATE: All right, let’s think about the user experience first. A user will want to select a restaurant, enter their party size, find a list of available times near the time they want, lock in their reservation, and get some sort of confirmation via SMS or something. They’ll also need some way to change or cancel reservations.

INTERVIEWER: Yes, that’s good. There are some nuances we could talk about, but you’ve got the main operations we need to support there.

CANDIDATE: So there are probably thousands of restaurants out there that might be a part of this system, and tens or hundreds of thousands of diners. They’ll expect this system to be fast and reliable. Am I right in thinking we should optimize for performance and reliability over cost?

INTERVIEWER: Yes, I want you to design a system that is both scalable and reliable, and with fast load times. Assume some investor gave us millions of dollars, and money isn’t really a problem.

CANDIDATE: I suppose the restaurant is also a customer…what would they need? Reporting, analytics, a way to set up how many tables and their configurations, how many tables to hold aside for walk-ins, a way to contact reservation holders…

INTERVIEWER: Yes, good thinking there. In the interest of time though, let’s just concern ourselves with the diners, and what we need to build in order for them to successfully schedule a reservation at their favorite restaurant.

Again, it’s time to try it yourself before I walk you through the mock interview. 

Here are some questions to ask yourself: 

1. How would you organize the data that’s needed for this system? 
2. How would you structure that data? 
3. How would you store it? 
4. How would you distribute that storage, and how do you design a system, more generally, that would scale to thousands of restaurants and hundreds of thousands of users? 

Take a stab at that yourself on a piece of paper somewhere, or your own whiteboard or virtual whiteboard. And when you’re ready, come back, and we’ll see how our interviewee here actually handled the problem.

CANDIDATE: Let me sketch some thoughts on the data we’ll need while I’m thinking of it…So we’ll need a customer table, and a restaurant table for sure. We’ll need to tie them together so each customer and restaurant will need some unique ID associated with them. What might we need to know about a customer…certainly their name, contact info, and maybe some information to help them find their favorite restaurants or restaurants close to them. So we’ll need their location as well, and maybe a list of their preferences, like their favorite restaurants. We’ll also need to store their login credentials, but this would probably be stored in a more secure system or using some single sign-on system, and not here.

For the restaurant, we also need its name, address, and contact info. We also need to know its layout so we can match up reservation requests to available tables. The application we build will have to have some fairly complex logic for assigning reservations to tables; maybe even taking into account the possibility of moving tables together to accommodate large groups. We also need to make some assumptions about how long it takes for a dining party to finish their meal and clear the table for the next reservation, so that’s something the restaurant will probably want to be able to control – the length of time a reservation lasts. Maybe that ends up being a function of the party size as well or the time of day; we’d have to interview real restaurant owners to understand how to best model that. I assume they’ll also want to keep some tables aside to handle walk-in customers, so we should at least let the restaurant specify how much capacity they want to hold back for walk-ins.

INTERVIEWER: That’s great; you’re really thinking of the customers here and what they will need.

CANDIDATE: So, finally, we’ll need a reservation table that ties it all together. The app will have to use its own logic to assign reservation requests for a given customer, restaurant, and time. So somewhere, we will have a table of reservations, partitioned by restaurant ID so we can quickly look up reservations for a given restaurant. I imagine we’d further partition by date to make it quick to look up existing reservations for a given date at a given restaurant, which the algorithm will need to try and find an opening.

INTERVIEWER: Great that you’re thinking about how the data is stored for optimal performance. So, is there a reason you’re going with a normalized data representation instead of a denormalized one?

CANDIDATE: Well, thinking about the operations we’ll likely need to do…let’s see…you’ll probably already have the customer ID and restaurant ID on the client by the time you navigate to the point where you want to create a new reservation, right? I think it’s simpler to just retrieve information on restaurants and clients as needed via their own hits to the database, or the cache in front of the database. That way we don’t waste space, and we don’t have to deal with the problem of updating everything in some huge denormalized table whenever a customer changes their phone number or something. If, while testing, we find that there is some complex join operation that we’re doing over and over again and it is a performance bottleneck, we could revisit that, but my instinct here is to start simple and only add the complexity of denormalization when needed.

INTERVIEWER: Makes sense to me. Keep going.

CANDIDATE: What information is associated with a reservation…obviously the customer and restaurant it is for, the party size, and the time. We might also want a space for notes to the restaurant, like any special occasions or dietary restrictions they might want to know ahead of time.

INTERVIEWER: OK, that’s all good. Let’s move on to designing the larger system here.

CANDIDATE: So I think the design is pretty straightforward. We have a bunch of clients that represent our diners, running an app or something that needs to issue service requests over HTTP somehow over the internet.

Since we can have a large number of diners, we will need to horizontally scale the servers that process these requests. The act of placing a reservation or retrieving information about a diner or a restaurant seems atomic and stateless, so that shouldn’t really pose a problem. We just have API’s for requesting a reservation and retrieving metadata to display about users and restaurants. There also needs to be some API for securely logging in, creating an account, and stuff like that… but let’s assume we’re using some secure, external system for user management which is outside of what we’re building. Ideally, these servers would be hosted across different racks, data centers, and regions, and geo-routed whenever possible. That would maximize availability, assuming we build in sufficient capacity to handle an outage of an entire region.

And I’m going to draw a hand-wavy, big “NoSQL” database here that stores our customers, restaurants, and reservations tables. The application logic for assigning reservations to time slots will live in the servers that talk to this database. Although I’m drawing it as a single, giant bottleneck, this is really some sort of horizontally scaled database system to ensure it can handle high loads and high availability.

We’ll probably also want to send text messages to people reminding them of their reservations, so we’ll have some application server off on the side querying the same database and firing off SMS messages as appropriate. I’m drawing this as a single server as that probably would be sufficient, but of course, we’d have some sort of failover set up on that as well, maybe with just a cold standby ready to go. This seems like sort of a nice-to-have feature, but if it is deemed critical we could also put it behind a load balancer just to ensure we have redundancy all the time.

INTERVIEWER: I mean, is there really any reason not to do that?

CANDIDATE: No, I suppose not. So, let’s imagine another load balancer and at least a couple of servers in different data centers handling the SMS part.

INTERVIEWER: Tell me more about your big hand-wavy NoSQL database. How would you go about choosing a specific technology for that?

CANDIDATE: Well, part of it would come down to what tools your staff is already familiar with. If you’re an AWS shop, then I would think DynamoDB would fit the bill nicely. But, let’s think about the CAP theorem. You said earlier we care about availability and speed, which implies partition tolerance. So that means we can maybe give up a little on consistency. So, something like Cassandra that has eventual consistency in exchange for not having a single master server might be a reasonable choice. But I think I would push back on those requirements; consistency is probably important for this application, it just isn’t something we talked about yet. We definitely don’t want two customers ending up with the same reservation slot. I mean, in practice, even the databases that trade-off availability are still highly available if you throw enough secondary servers and backup master servers at them. So the usual suspects like MongoDB or DynamoDB, or its equivalent in Google Cloud or Azure, is probably a fine choice.

INTERVIEWER: Yeah, that’s good. Business owners don’t always think about these things, and part of your job is to help them think about these sorts of requirements and the tradeoffs involved. Now, the data you sketched out earlier is relational in nature – we’ve got customers and restaurants referenced in each reservation. Do we need a traditional relational database like Oracle or MySQL to handle that?

CANDIDATE: No, the application servers can query the individual tables and join them internally as needed. We’re not doing anything complicated where that would be a real performance concern. Modern distributed databases can just do the join for us efficiently on their own anyhow. Let’s go with “NoSQL” meaning “Not Only SQL”.

INTERVIEWER: OK, we just have a few minutes left before I have to move on. One last question: What about caching? Do we need it? How can we further improve the performance of this system?

CANDIDATE: Hm, well, we don’t really have a lot of static content in this system, so something like a CDN probably wouldn’t do a whole lot of good. If the client applications are just web pages, though, we’d probably want a CDN for fast hosting of the CSS, Javascript, and images needed on the client side. We talked about hosting the app servers across different regions and geo-routing to them, so at least that will cut down on some latency. We probably would want to have some sort of cache for the database queries, though. The customer and restaurant data isn’t likely to change often, so that can certainly be cached. Let’s assume we have something like Memcached or Redis sitting on top of those queries inside the app servers. Maybe Memcached because it’s simpler and we don’t need anything fancy here. That gives us a little more flexibility in how the database is distributed across regions as well. It doesn’t do much good to geo-route to servers if those servers all have to talk to one region for its data.

INTERVIEWER: Cool. Obviously, there’s a lot more to talk about if we were to build this for real, but you hit on all of the main concerns. Let’s move on.

Mock Interview: Example #3

Question: Design a Web Crawler 

CANDIDATE: We’re designing a web crawler. Like, the entire web – or just a few sites?

INTERVIEWER: Yup, the entire web.

CANDIDATE: I thought you might say that. So we’re talking, like, billions of web pages. Crawled how often?

INTERVIEWER: Let’s say the whole thing should be updated every week.

CANDIDATE: And, we need to check pages we’ve crawled before to see if they have been updated, right?

INTERVIEWER: That’s right.

CANDIDATE: OK, do we need to store a copy of every page as we go? Does that include images?

INTERVIEWER: Yes, we need to store the HTML at least. For now, I don’t care about images, but it would be nice if your design could be extended to handle them later.

CANDIDATE: What about dynamic content? Stuff that’s rendered client-side?

INTERVIEWER: That’s a good thing to ask about. Again let’s set that problem aside for now, but if your design can be extended for it and we have time to talk about it, we can go there later. 

CANDIDATE: What’s the main purpose of this crawler? I should’ve asked that first, really.

INTERVIEWER: We’re building a search engine. That’s why I’m mainly concerned with just storing text for now. Now that we’ve answered some clarifying questions and defined our requirements, it’s time for you to try it yourself once again. How would you distribute this crawler to handle the massive scale required? We’re talking about the entire internet here. That’s crazy. What algorithms will you use to crawl the entire web? We need to bring back what we learned about algorithms and data structures. What problems and failure modes can you anticipate and address in your design? Give it a shot on your own and when you come back, we’ll go through a mock interview showing one approach to the problem.

CANDIDATE: OK, let me start by thinking about it from an algorithmic standpoint. Basically, web pages are vertices on a directed graph, right? And the links between them are the edges of the graph. So fundamentally, this is a graph traversal problem.

INTERVIEWER: Right. So, what kind of traversal would you do here?

CANDIDATE: Well, the choices are breadth-first-search or depth-first-search. Let me think about that for a second. The number of links on one page are pretty finite; that would represent breadth. But the depth of the Internet is pretty much infinite. I think that makes BFS the only real tractable solution here.

INTERVIEWER: Remind me how BFS works.

CANDIDATE: So, starting at some page, you’d go through every link on the page, and kick off the processing of each link to some other process in the name of scalability I’d think. Then each link on the child nodes are processed, working your way across this graph from left to right. As opposed to DFS, where we would follow one path all the way to the end, then back up and follow another path all the way to the end. The problem is that following any path to the end will take pretty much forever. BFS is usually the way to go, and this seems like no exception.

INTERVIEWER: OK, good. Let’s get to the hard part and make this scale to billions of web pages.

CANDIDATE: OK, let me start with something simple and high-level, and then we can start refining it.

INTERVIEWER: Yup, that makes sense.

CANDIDATE: So we need to start with a list of URL’s to crawl. We have to start somewhere. Way back at the beginning of the web, webmasters would submit their domains directly to search engines so they would be crawled, so I would guess that’s what seeded this, along with the sitemaps on those sites. Even today people can submit sites via Google webmaster tools right? So there is some process to directly add new URL’s that have no inbound links at all yet into this list of URL’s to crawl.

INTERVIEWER: That could be a pretty big list.

CANDIDATE: Yeah, it’s not going to fit in memory on a single host or anything like that. We’ll probably need to hash each URL as it comes in, and dispatch it to a list on one of many servers to scale that up.

INTERVIEWER: OK. We’ll dig into that more deeply if we have time. Staying high level for now.

CANDIDATE: So then we’ll have another distributed system of some sort that actually downloads all of those URL’s, and stores their contents into some truly massive distributed storage solution. I guess some sort of simple object store will do where the key is just the URL, and the value is the stuff that was downloaded. So something like Google Cloud storage should fit the bill, or if Amazon were getting into the search engine business Amazon S3 would do for that. Designing a distributed storage system is a whole other design problem, so again, I’ll stick with the high level here.

Next, we need to extract all of the links within that page and crawl them in turn. BFS as we said before. I imagine that’s easier said than done; there needs to be some way of normalizing those URL. There’s the whole http vs. https thing, relative links, trailing slashes, and all sorts of edge cases we’ll need to handle. But in the end, we need some canonical URL that we can resubmit to the crawler.

There are also links we might want to explicitly exclude; known malware sites, people hosting prohibited content, and stuff like that. So some sort of filtering will probably also be needed before we decide to crawl down any given rabbit hole on the Internet.

So, if a URL makes it all the way through this, it goes back into the distributed list of stuff that needs to be crawled. Specifically, that will be a first-in-first-out queue sort of thing; a big distributed linked list would do fine.

INTERVIEWER: Why a linked list and not an array?

CANDIDATE: Well, these URLs are strings, and we don’t really know ahead of time how much memory a certain number of URLs will take. Using arrays means we have to pre-allocate space, but we can’t know how many elements will fit on a given server.

INTERVIEWER: Well, you could have an array of pointers to strings, right?

CANDIDATE: That doesn’t really help; you still have to know how many strings you can fit in memory, and we don’t.

INTERVIEWER: Yeah, you’re right. So, is this list really just in memory? What happens when one of your servers goes up in flames? Do we just lose that part of the Internet?

CANDIDATE: Well, arguably, that might be OK – the next time we run the crawler it would pick it up. The simplicity and lower cost might be a reasonable trade-off there.

INTERVIEWER: Let’s say it isn’t; too many people will freak out if their new web page isn’t crawled quickly. How would you solve that?

CANDIDATE: Hm, we need some sort of distributed, persistent list. I guess you could back it on disk in a distributed database of some sort, but maybe you could just have hot standbys for each server that handles a given bucket in your URL hashing, so if one goes down you have another ready. As long as they are in different data centers, the risk should be low. Or you could do some hybrid thing between the two ideas.

INTERVIEWER: Good thinking. We don’t really have time to get into the details of that, but you’re on the right track. 

One thing we didn’t talk about is the problem of duplicate content. How would you avoid processing copies of the same page that are under different URLs?

CANDIDATE: Hm, well, we could compute some sort of hash or checksum or something on the content after it’s downloaded. Then store every hash value we’ve encountered somewhere. So, before we move from the downloader to the URL extractor, we see if that page’s hash value has been seen before. If not, we add it and move on. If so, we’d have to compare the two pages character by character to ensure it’s not just some random hash collision and they really are identical – so we’d also have to store the URL the hash value came from so we can retrieve it if need be.

We have a similar problem with duplicate URLs, don’t we? If many pages are linked to the same URL, we don’t want to crawl that URL every time it’s linked. Only once will do, right? So let’s also keep a database – distributed, of course – of URLs we’ve already processed in this run. The URL filter will also check against that to ensure we haven’t already submitted that URL to the crawler. Or maybe we could do something clever in the URL queue to ensure we don’t queue the same URL twice. That could include a hash map in addition to the queue to let us check against URLs that have been processed already. But that’s another big distributed system to bolt on there when an off-the-shelf NoSQL database sort of thing would also fit the bill. 

INTERVIEWER: Another thing we didn’t talk about yet is how to avoid bringing sites down by crawling them too fast. A lot of web servers can’t keep up with us if we just hit them with a request for every page on the site all at once. How would you deal with that?

CANDIDATE: Well, some sort of time delay has to be baked in between calls to any given site.

INTERVIEWER: Right, how would you do that?

CANDIDATE: We didn’t really go into detail on the “page downloader” block there, so let’s think that one through. Obviously, that’s going to be running on a huge fleet of servers, each running a bunch of threads to download pages, hash them, and store them. So maybe we hash URL’s to download to individual servers like we did for the queue. And we do this hashed on the domain name, so all the download requests for a given site end up on the same server. That server could then maintain a thread for each site that runs in parallel with the other sites it’s taking care of, with a time delay between each hit on a given site. This is all starting to seem a little overly complex. Maybe this whole thing could be combined with the queue somehow, so we don’t need two different systems. I don’t think we have time to go back and revisit that, though.

INTERVIEWER: No, not really. But you’re right; it is possible to just bake this logic into the queue. Then the page downloader, as you’re calling it, just has some fixed number of download threads, with a time delay between each hit, that the queue feeds requests into. The queue just makes sure requests from the same site end up in the same download thread. I like that you’re aiming for simplicity.

CANDIDATE: Wow, this is all more challenging than it seems at first.

INTERVIEWER: I know! That’s why it’s a good interview question. Let’s go back to your high-level design real quick. So real quick, we did talk about extending this system to store images or do client-side rendering. Where would that fit in potentially?

CANDIDATE: Well, we could extract images at the same time we do URL extraction. But really, we could just treat them like another URL to be crawled, that way, we benefit from all the other pieces of the system. So the “page downloader” just knows how to recognize an image URL, and how to retrieve and store images as well as HTML.

INTERVIEWER: And client-side rendering?

CANDIDATE: I think that would have to go into the URL extraction piece. So instead of just scanning HTML for URLs, we actually render the HTML in a browser and see if any new URLs are created in the process. That means building out a whole other fleet of page renderers and a way to queue them up. Wow, this gets really complicated really fast.

INTERVIEWER: That’s why Google is as big as it is. We didn’t even talk about dynamic content or sites that require you to log in, or malicious sites that try to trap crawlers in an infinite loop. There are all sorts of interesting edge cases. But you’ve done a good job of thinking through this problem in the time we have; let’s move on.

Now that you’ve walked through several mock interview questions, go practice on your own. How would you answer these questions?

Keep in mind the structure here, and the importance of asking clarifying questions, and explaining your thought process out loud so your interviewer can understand how you think and process information. 

If you’re interested in learning more strategies on how to Master your System Design Interview today with our Mastering the Systems Design Interview Course.

Click here to enroll today!