Geek Culture
Published in

Geek Culture

Top 12 System Design Interview Questions with Answers (2022)

You can increase your chances of success manyfold by practicing these questions!

FAANG System Design Interview Questions

System design interviews (SDIs) have gained a lot of focus in the past few years. Now a standard part of every software engineering interview, these interviews assess a candidate’s ability to handle complex systems. Performance in these interviews determines the position and salary offered by the interviewing company.

Today we will discuss the top 12 system design interview questions asked at top tech companies, including FAANG (Facebook, Apple, Amazon, Netflix, and Google).

1. Design Facebook Messenger

Design an instant messaging service like Facebook Messenger where users can send text messages to each other through web and mobile interfaces.

Functional Requirements:

  1. Messenger should support one-on-one conversations between users.
  2. Messenger should keep track of the online/offline statuses of its users.
  3. Messenger should support the persistent storage of chat history.

Non-functional Requirements:

  1. Users should have a real-time chatting experience with minimum latency.
  2. Our system should be highly consistent; users should see the same chat history on all their devices.
  3. Messenger’s high availability is desirable; we can tolerate lower availability in the interest of consistency.

High-level solution

At a high level, we will need a chat server that will be the central piece orchestrating all the communications between users. For example, when a user wants to send a message to another user, they will connect to the chat server and send the message to the server; the server then passes that message to the other user and also stores it in the database.

The detailed workflow would look like this:

  1. User-A sends a message to User-B through the chat server.
  2. The server receives the message and sends an acknowledgment to User-A.
  3. The server stores the message in its database and sends the message to User-B.
  4. User-B receives the message and sends the acknowledgment to the server.
  5. The server notifies User-A that the message has been delivered successfully to User-B.
Request flow for sending a message

Learn more on Designing Facebook Messenger.

2. Design Youtube

Design a video sharing service like Youtube, where users will be able to upload/view/search videos.

Functional Requirements:

  1. Users should be able to upload videos.
  2. Users should be able to share and view videos.
  3. Users should be able to perform searches based on video titles.
  4. Our services should be able to record stats of videos, e.g., likes/dislikes, total number of views, etc.
  5. Users should be able to add and view comments on videos.

Non-Functional Requirements:

  1. The system should be highly reliable, any video uploaded should not be lost.
  2. The system should be highly available. Consistency can take a hit (in the interest of availability); if a user doesn’t see a video for a while, it should be fine.
  3. Users should have a real-time experience while watching videos and should not feel any lag.

High-level solution

At a high-level we will need the following components:

  1. Processing Queue: Each uploaded video will be pushed to a processing queue to be de-queued later for encoding, thumbnail generation, and storage.
  2. Encoder: To encode each uploaded video into multiple formats.
  3. Thumbnails generator: To generate a few thumbnails for each video.
  4. Video and Thumbnail storage: To store video and thumbnail files in some distributed file storage.
  5. User Database: To store user’s information, e.g., name, email, address, etc.
  6. Video metadata storage: A metadata database to store all the information about videos like title, file path in the system, uploading user, total views, likes, dislikes, etc. It will also be used to store all the video comments.
High-level design of Youtube

Learn more on Designing Youtube.

3. Design Facebook’s Newsfeed

Design Facebook’s Newsfeed, which would contain posts, photos, videos, and status updates from all the people and pages a user follows.

Functional requirements:

  1. Newsfeed will be generated based on the posts from the people, pages, and groups that a user follows.
  2. A user may have many friends and follow a large number of pages/groups.
  3. Feeds may contain images, videos, or just text.
  4. Our service should support appending new posts as they arrive to the newsfeed for all active users.

Non-functional requirements:

  1. Our system should be able to generate any user’s newsfeed in real-time — maximum latency seen by the end user would be 2s.
  2. A post shouldn’t take more than 5s to make it to a user’s feed assuming a new newsfeed request comes in.

High-level solution

At a high level, we will need the following components in our Newsfeed service:

  1. Web servers: To maintain a connection with the user. This connection will be used to transfer data between the user and the server.
  2. Application server: To execute the workflows of storing new posts in the database servers. We will also need some application servers to retrieve and to push the newsfeed to the end user.
  3. Metadata database and cache: To store the metadata about Users, Pages, and Groups.
  4. Posts database and cache: To store metadata about posts and their contents.
  5. Video and photo storage, and cache: Blob storage, to store all the media included in the posts.
  6. Newsfeed generation service: To gather and rank all the relevant posts for a user to generate newsfeed and store in the cache. This service will also receive live updates and will add these newer feed items to any user’s timeline.
  7. Feed notification service: To notify the user that there are newer items available for their newsfeed.

Following is the high-level architecture diagram of our system. User B and C are following User A.

Facebook Newsfeed Architecture

Learn more on Designing Facebook’s Newsfeed.

4. Design an API Rate Limiter

Design an API Rate Limiter which will throttle users based upon the number of requests they are sending.

Functional Requirements:

  1. Limit the number of requests an entity can send to an API within a time window, e.g., 15 requests per second.
  2. The APIs are accessible through a cluster, so the rate limit should be considered across different servers. The user should get an error message whenever the defined threshold is crossed within a single server or across a combination of servers.

Non-Functional Requirements:

  1. The system should be highly available. The rate limiter should always work since it protects our service from external attacks.
  2. Our rate limiter should not introduce substantial latencies affecting the user experience.

Rate Limiter will be responsible for deciding which request will be served by the API servers and which request will be declined. Once a new request arrives, the Web Server first asks the Rate Limiter to decide if it will be served or throttled. If the request is not throttled, then it’ll be passed to the API servers.

High-level solution

Rate Limiter will be responsible for deciding which request will be served by the API servers and which request will be declined. Once a new request arrives, the Web Server first asks the Rate Limiter to decide if it will be served or throttled. If the request is not throttled, then it’ll be passed to the API servers.

High-level design for Rate Limiter

Learn more on Designing an API Rate Limiter.

5. Design Twitter

Design a Twitter-like social networking service. Users of the service will be able to post tweets, follow other people, and favorite tweets.

Functional Requirements

  1. Users should be able to post new tweets.
  2. A user should be able to follow other users.
  3. Users should be able to mark tweets as favorites.
  4. The service should be able to create and display a user’s timeline consisting of top tweets from all the people the user follows.
  5. Tweets can contain photos and videos.

Non-functional Requirements

  1. Our service needs to be highly available.
  2. Acceptable latency of the system is 200ms for timeline generation.
  3. Consistency can take a hit (in the interest of availability); if a user doesn’t see a tweet for a while, it should be fine.

High-level solution

We need a system that can efficiently store all the new tweets, 100M/86400s => 1150 tweets per second, and read 28B/86400s => 325K tweets per second. It is clear from the requirements that this will be a read-heavy system.

At a high level, we need multiple application servers to serve all these requests with load balancers in front of them for traffic distributions. On the backend, we need an efficient database that can store all the new tweets and can support a huge number of reads. We also need some file storage to store photos and videos.

Although our expected daily write load is 100 million and read load is 28 billion tweets. This means on average our system will receive around 1160 new tweets and 325K read requests per second. This traffic will be distributed unevenly throughout the day, though, at peak time we should expect at least a few thousand write requests and around 1M read requests per second. We should keep this in mind while designing the architecture of our system.

Learn more on Designing Twitter.

6. Design Dropbox or Google Drive

Design a file hosting service like Dropbox or Google Drive. Cloud file storage enables users to store their data on remote servers. Usually, these servers are maintained by cloud storage providers and made available to users over a network (typically through the Internet). Users pay for their cloud data storage on a monthly basis.

Requirements

  1. Users should be able to upload and download their files/photos from any device.
  2. Users should be able to share files or folders with other users.
  3. Our service should support automatic synchronization between devices, i.e., after updating a file on one device, it should get synchronized on all devices.
  4. The system should support storing large files up to a GB.
  5. ACID-ity is required. Atomicity, Consistency, Isolation, and Durability of all file operations should be guaranteed.
  6. Our system should support offline editing. Users should be able to add/delete/modify files while offline, and as soon as they come online, all their changes should be synced to the remote servers and other online devices.

Extended Requirements

  • The system should support snapshotting of the data, so that users can go back to any version of the files.

High-level solution

The user will specify a folder as the workspace on their device. Any file/photo/folder placed in this folder will be uploaded to the cloud, and whenever a file is modified or deleted, it will be reflected in the same way in the cloud storage. The user can specify similar workspaces on all their devices and any modification done on one device will be propagated to all other devices to have the same view of the workspace everywhere.

At a high level, we need to store files and their metadata information like File Name, File Size, Directory, etc., and who this file is shared with. So, we need some servers that can help the clients to upload/download files to Cloud Storage and some servers that can facilitate updating metadata about files and users. We also need some mechanism to notify all clients whenever an update happens so they can synchronize their files.

As shown in the diagram below, Block servers will work with the clients to upload/download files from cloud storage and Metadata servers will keep metadata of files updated in a SQL or NoSQL database. Synchronization servers will handle the workflow of notifying all clients about different changes for synchronization.

High-level design for Dropbox

Learn more on Designing Dropbox.

7. Design a Web Crawler

Design a Web Crawler that will systematically browse and download the World Wide Web. Web crawlers are also known as web spiders, robots, worms, walkers, and bots.

Requirements

Let’s assume we need to crawl all of the web.

Scalability: Our service needs to be scalable such that it can crawl the entire Web and can be used to fetch hundreds of millions of Web documents.

Extensibility: Our service should be designed in a modular way with the expectation that new functionality will be added to it. There could be newer document types that need to be downloaded and processed in the future.

High-level solution

A bare minimum crawler needs at least these components:

1. URL frontier: To store the list of URLs to download and also prioritize which URLs should be crawled first.
2. HTML Fetcher: To retrieve a web page from the server.
3. Extractor: To extract links from HTML documents.
4. Duplicate Eliminator: To make sure the same content is not extracted twice unintentionally.
5. Datastore: To store retrieved pages, URLs, and other metadata.

Learn more on Designing a Web Crawler.

8. Design Twitter Search

Twitter is one of the largest social networking service where users can share photos, news, and text-based messages. Let’s design a service that can store and search user tweets.

Requirements

  • Let’s assume Twitter has 1.5 billion total users with 800 million daily active users.
  • On average Twitter gets 400 million tweets every day.
  • The average size of a tweet is 300 bytes.
  • Let’s assume there will be 500M searches every day.
  • The search query will consist of multiple words combined with AND/OR.

At the high level, we need to store all the tweets in a database and also build an index that can keep track of which word appears in which tweet. This index will help us quickly find tweets that the users are trying to search for.

High-level design for Twitter search

Learn more on Designing Twitter Search.

9. Design a URL Shortening service like TinyURL

Design a URL shortening service like TinyURL. This service will provide short aliases redirecting to long URLs.

Functional Requirements:

  1. Given a URL, our service should generate a shorter and unique alias of it. This is called a short link. This link should be short enough to be easily copied and pasted into applications.
  2. When users access a short link, our service should redirect them to the original link.
  3. Users should optionally be able to pick a custom short link for their URL.
  4. Links will expire after a standard default timespan. Users should be able to specify the expiration time.

Non-Functional Requirements:

  1. The system should be highly available. This is required because if our service is down, all the URL redirections will start failing.
  2. URL redirection should happen in real-time with minimal latency.
  3. Shortened links should not be guessable (not predictable).

Extended Requirements:

  1. Analytics; e.g., how many times a redirection happened?
  2. Our service should also be accessible through REST APIs by other services.

High-level solution

The problem we are solving here is how to generate a short and unique key for a given URL.

We can compute a unique hash (e.g., MD5 or SHA256, etc.) of the given URL. The hash can then be encoded for display. This encoding could be base36 ([a-z ,0–9]) or base62 ([A-Z, a-z, 0–9]) and if we add ‘+’ and ‘/’ we can use Base64 encoding. A reasonable question would be, what should be the length of the short key? 6, 8, or 10 characters?

Using base64 encoding, a 6 letters long key would result in 64⁶ = ~68.7 billion possible strings.
Using base64 encoding, an 8 letters long key would result in 64⁸ = ~281 trillion possible strings.

With 68.7B unique strings, let’s assume six letter keys would suffice for our system.

If we use the MD5 algorithm as our hash function, it will produce a 128-bit hash value. After base64 encoding, we’ll get a string having more than 21 characters (since each base64 character encodes 6 bits of the hash value). Now we only have space for 6 (or 8) characters per short key; how will we choose our key then? We can take the first 6 (or 8) letters for the key. This could result in key duplication; to resolve that, we can choose some other characters out of the encoding string or swap some characters.

What are the different issues with our solution? We have the following couple of problems with our encoding scheme:

  1. If multiple users enter the same URL, they can get the same shortened URL, which is not acceptable.
  2. What if parts of the URL are URL-encoded? e.g., http://www.designgurus.org/distributed.php?id=design, and http://www.designgurus.org/distributed.php%3Fid%3Ddesign are identical except for the URL encoding.

Workaround for the issues: We can append an increasing sequence number to each input URL to make it unique and then generate its hash. We don’t need to store this sequence number in the databases, though. Possible problems with this approach could be an ever-increasing sequence number. Can it overflow? Appending an increasing sequence number will also impact the performance of the service.

Another solution could be to append the user id (which should be unique) to the input URL. However, if the user has not signed in, we would have to ask the user to choose a uniqueness key. Even after this, if we have a conflict, we have to keep generating a key until we get a unique one.

Request flow for shortening of a URL

Learn more on Designing a URL Shortening service.

10. Design Instagram

Design a photo-sharing service like Instagram, where users can upload photos to share them with other users.

Functional Requirements

  1. Users should be able to upload/download/view photos.
  2. Users can perform searches based on photo/video titles.
  3. Users can follow other users.
  4. The system should generate and display a user’s News Feed consisting of top photos from all the people the user follows.

Non-functional Requirements

  1. Our service needs to be highly available.
  2. The acceptable latency of the system is 200ms for News Feed generation.
  3. Consistency can take a hit (in the interest of availability) if a user doesn’t see a photo for a while; it should be fine.
  4. The system should be highly reliable; any uploaded photo or video should never be lost.

High-level solution

At a high-level, we need to support two scenarios, one to upload photos and the other to view/search photos. Our service would need some object storage servers to store photos and some database servers to store metadata information about the photos.

Learn more on Designing Instagram.

Designing Yelp or Nearby Friends

Design a Yelp like service, where users can search for nearby places like restaurants, theaters, or shopping malls, etc., and can also add/view reviews of places.

Functional Requirements:

  1. Users should be able to add/delete/update Places.
  2. Given their location (longitude/latitude), users should be able to find all nearby places within a given radius.
  3. Users should be able to add feedback/review about a place. The feedback can have pictures, text, and a rating.

Non-functional Requirements:

  1. Users should have a real-time search experience with minimum latency.
  2. Our service should support a heavy search load. There will be a lot of search requests compared to adding a new place.

High-level solution

At a high level, we need to store and index each dataset described above (places, reviews, etc.). For users to query this massive database, the indexing should be read efficient, since while searching for nearby places, users expect to see the results in real-time.

Given that the location of a place doesn’t change that often, we don’t need to worry about frequent updates of the data. As a contrast, if we intend to build a service where objects do change their location frequently, e.g., people or taxis, then we might come up with a very different design.

Learn more on Designing Yelp or Nearby Friends.

12. Design Ticketmaster

Design an online ticketing system that sells movie tickets like Ticketmaster or BookMyShow

Functional Requirements:

  1. Our ticket booking service should be able to list different cities where its affiliate cinemas are located.
  2. Once the user selects the city, the service should display the movies released in that particular city.
  3. Once the user selects a movie, the service should display the cinemas running that movie and its available showtimes.
  4. The user should be able to choose a show at a particular cinema and book their tickets.
  5. The service should be able to show the user the seating arrangement of the cinema hall. The user should be able to select multiple seats according to their preference.
  6. The user should be able to distinguish available seats from booked ones.
  7. Users should be able to put a hold on the seats for five minutes before they make a payment to finalize the booking.
  8. The user should be able to wait if there is a chance that the seats might become available, e.g., when holds by other users expire.
  9. Waiting customers should be serviced in a fair, first come, first serve manner.

Non-Functional Requirements:

  1. The system would need to be highly concurrent. There will be multiple booking requests for the same seat at any particular point in time. The service should handle this gracefully and fairly.
  2. The core thing of the service is ticket booking, which means financial transactions. This means that the system should be secure and the database ACID compliant.

High-level solution

At a high-level, our web servers will manage users’ sessions, and application servers will handle all the ticket management, storing data in the databases as well as working with the cache servers to process reservations.

Learn more on Designing Ticketmaster.

Where to go from here?

➡ Practice these questions to distinguish yourself from others!

➡ Learn more about these questions in “Grokking the System Design InterviewandGrokking the Advanced System Design Interview.”

➡ Follow me on Linkedin for tips on system design and coding interviews.

Thanks for reading

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Arslan Ahmad

Arslan Ahmad

Founder www.designgurus.org | Formally a software engineer @ Facebook, Microsoft, Hulu, Formulatrix | Entrepreneur, Software Engineer, Writer.