Mastering the System Design Interview

The most basic trick for building systems that scale to massive loads is "horizontal scaling." Learn how it works through architecture diagrams, and how it compares to single-server and vertical scaling designs.

The downside of horizonal scaling is you have more servers that can fail at any time, and your system must seamlessly handle that failure. Learn how cold, warm, and hot standbys address this problem.

Scaling databases present their own problems with data replication and distributing lookups and storage of data. Learn how NoSQL databases address this with sharding, and we'll dive into specific examples of the architecture of MongoDB and Cassandra. We'll also discuss denormalization, which is key to efficient use of NoSQL data stores.

Rather than dealing directly with databases, a common architectural choice for data analysis applications is the use of a "data lake" - just throwing raw data into cloud storage such as S3, and later imparting structure to that data.

Common database-related interview questions will involve ACID compliance (Atomicity, Consistency, Isolation, and Durability) and the CAP theorem (Consistency, Availability, Partition-tolerance.) What these terms mean is far from intuitive, and how they apply to modern real-world systems is nuanced at best. Understanding those nuances will help you stand out as a candidate.

Let's study how MongoDB and Cassandra choose their tradeoffs in the CAP theorem, and how understanding those tradeoffs can help you choose the right data store for a given set of requirements.

Learn where to inject a caching layer in your system design, how caches work, and the nuances of configuring your cache's expiration policy. We'll also discuss the problems of hotspots and the cold-start problem, and how they influence your design.

Your cache has finite space, and you must choose a strategy for evicting old data to make room for the new. We'll talk about LRU (least recently used,) LFU (least frequently used,) and FIFO (first in, first out.)

CDN's such as Akamai, CloudFront, and CloudFlare can cache information as close as possible to your end users. Learn how they work, the problems they solve, and some of the more popular CDN providers.

Having backup hosts is one thing, but what if an entire data center goes down? Or an entire region? Something as small as a network failure can lead to such an event. Learn how to distribute your system, and route requests, such that even major disasters won't bring your system down.

Cloud-based storage solutions such as Amazon S3, Google Cloud Storage, and Microsoft Azure can be important parts of your design. Or you can build your own using HDFS and Hadoop.

Learn how to design a distributed storage solution, by studying the architecture of HDFS (the Hadoop Distributed File System)

Test your knowledge on designing distributed systems!

Data structures and algorithms may play a role in your system design, so let's review those computer science basics as well as their computational complexity.

Learn about singly linked lists and doubly linked lists, their properties, and how to use them.

Learn about the computational complexity and applications of binary trees and hash tables, as well as edge cases such as unbalanced trees and hash collisions that can trip you up in practice.

Graph traversal, including depth-first search (DFS) and breadth-first-search (BFS) may play a role in your design, so be ready to discuss how they work and which one to choose for a given problem.

We'll review linear search and binary search algorithms, and their computational complexity.

A quick review of different sorting algorithms that may apply to your interview problems: insertion sort, merge sort, quicksort, and bubble sort.

Learn how full-text search works, including forward and inverted indexes and ranking functions. We'll also cover TF-IDF (Term Frequency * Inverse Document Frequency) and the role it plays in modern information retrieval. Google's PageRank algorithm is explained, which is fairly likely to come up at interviews at Google.

Review the main computer science algorithms and data structures, and their computational complexity.

Message queues, such as Amazon's SQS (Simple Queue Service,) can be important tools in your design for decoupling producers and consumers of data. Understand how this differs from streaming data.

Apache Spark is an important tool for the distributed processing of massive data sets, which is a common requirement in system design problems. Learn how Apache Spark works architecturally, and the components it offers such as Spark Streaming, Spark SQL, MLLib for machine learning, and GraphX.

Sometimes you can cheat a little, and use a cloud-based service instead of designing your own for components of your design. We'll discuss how AWS, Google Cloud, and Microsoft Azure each address the problems of storage, computing, NoSQL data stores, container, data streams, Spark / Hadoop, data warehousing, and caching. Then we'll look at an example of designing a data warehouse for log data using AWS. We'll also talk about "hybrid cloud" solutions that combine your own "on-premises" or private cloud with public clouds.

Review your learnings in big data processing.

Arriving at the right design for a problem requires working backward from the problem itself and the end result you are trying to build. We'll see how to apply this principle to problems like "designing YouTube"

Before designing a system, you must understand its requirements. Learn what questions to ask about the scaling requirements of the system you are designing. How many users? How many transactions per second? How much data? What are the latency requirements? What are the availability requirements? Sometimes you'll be asked to estimate these requirements yourself, and we'll talk about how to do that.

Some general tips for your system design interview: think out loud while designing, sketch it out as you go while interacting with the interviewer, don't make stuff up and be honest when you need some guidance, and know how to defend and refine your design when your interviewer evaluates it.

In this section, we'll look at some real-world system design interview questions. For each problem, we'll see how to ask the right questions to define the requirements, watch a system design emerge from those requirements, and review the results.

We're asked to design a URL shortening service, like bit.ly. Clarifying questions include the scale of the service, restrictions on the characters used, how short the short URL's must be, features such as vanity URL's, how long shortened URL's last, and how URL redirects are edited and deleted.

Now that you have the requirements, try designing the URL shortening service yourself before watching our solution. What API's will you need? How does the redirection work at scale?

We define the API to this service as a RESTful interface, and design a horizontally-scaled system with a distributed NoSQL database and a caching layer.

We'll review what went well in this mock interview, and what you can learn from it.

We're asked to design a restaurant reservation system, such as OpenTable. Clarifying questions include the number of restaurants, the specific use cases, latency and reliability requirements, and reporting requirements.

Try your hand at designing the restaurant reservation system  yourself.  How would you build a data schema for it? How will it scale to thousands of restaurants, and hundreds of thousands of users?

We work out the database tables we need for this system, and a horizontally scaled, geographically distributed system with a NoSQL data store, caching, and SMS notifications.

We review what went well in our mock system design interview for a restaurant reservation system, and what you can learn from it.

Here's a common system design interview question at Google: design a web crawler, for the entire Internet! We'll clarify the use cases involved, the storage requirements, handling dynamically generated content, and what the main purpose of this crawler is.

Try designing the web crawler yourself first. How would you distribute it? What algorithms will you use? What are the problems and failure modes you can anticipate and address?

Designing a massive web crawler is a complex task. It involves graph traversal, and independent systems for queuing URL's to be crawled, downloading those pages, storing their contents, extracting and processing links between pages, and handling filtering and stoplists.

We'll review what went well in this mock interview for designing a web crawler, and what we can learn from it.

We're asked to design a system to track top-sellers on an e-commerce website. We clarify requirements on scale, timeliness, and the user experience.

Try designing the top-sellers system yourself first. Mostly this is a problem in designing an algorithm that meets the customers' needs.

We apply an exponential decay algorithm for top-sellers, and employ Apache Spark for processing sales data and publishing it to a data store fronted by a cache exposed to the front-end web servers.

We review what went well in our system design interview for designing a bestsellers system, and what we can learn from it.

In this mock system design interview, we're essentially asked to design YouTube. We need to scope that down into something manageable within the time we have.

Try designing the video sharing system yourself first. How will you handle the uploading, transcoding, and serving of videos at massive scale around the world? How do you minimize cost in the process?

In our mock interview, we approach the design with scalable repositories of videos and their metadata uploaded by end users, which go into a queue for transcoding. The transcoded video is then hosted using a smart model to minimize hosting and CDN costs.

Let's review what went well in our mock system design interview for designing a service like YouTube, and what we can learn from it.

This is basically "design Google," and a question you're likely to get there. Again, we need to scope this down into something manageable before we begin.

Try designing a search engine yourself first; how do you measure relevance? What algorithms will you use for mapping keywords to pages, and sorting the results? What system architecture will give you the required scale?

We work through a practical search algorithm inspired by PageRank, and a system design to index the web, store backlinks, rank links, score, sort, and rank results, and build an inverted index of keywords to page results.

We review what went well in our mock system design interview to design a search engine such as Google, and what we can learn from it.

In this section, we'll cover some general technical interview tips that aren't specific to system design interviews - but that you'll find very helpful for your interview loop as a whole.

Learn how to tell stories of how your perseverance allowed you to solve challenging problems in the past. Understand behavioral interviewing and how to excel within one.

Be ready to demonstrate technical skills, your experience through real-world stories, and your fit with the company's stated values. Demonstrate your independence, grit, and perseverance to the interviewer.

Prepare stories that demonstrate your initiative and self-motivation ahead of time. And do your homework on the company's values, and think about stories that demonstrate your fit with those values.

Writing code while someone is watching you can be discomforting and difficult at first, so practice it ahead of time.

Tips for ensuring your energy is at its best throughout the interview, presenting yourself well, and having questions ready to ask of your interviewers.

Remember to always think big, and design systems for massive scale. "Thinking big" can also mean thinking about the business requirements, and not just the technology. Also, some tips of making a positive impression on the people who are evaluating if they want to spend 8 hours a day with you.

Preparation is key - such as taking this course! Research can turn up specifically what to expect during interview loops at the company you are interviewing at, which can be very helpful as well.