Step 1: Constraints and use cases

The very first thing - clarify the system's constraints and to identify what use cases the system needs to satisfy.

  • Spend a few minutes questioning your interviewer and agreeing on the scope of the system. Many of the same rules we discussed while talking about algorithm design apply here as well.
  • Usually, part of what the interviewer wants to see is if you can gather the requirements about the problem at hand, and design a solution that covers them well. Never assume things that were not explicitly stated.

For example, the URL-shortening service could be meant to serve just a few thousand users, but each could be sharing millions of URLs. It could be meant to handle millions of clicks on the shortened URLs, or dozens. The service may have to provide extensive statistics about each shortened URL (which will increase your data size), or statistics may not be a requirement at all.

You will also have to think about the use cases that are expected to occur. Your system will be designed based on what it's expected to do. Don't forget to make sure you know all the requirements the interviewer didn't tell you about in the beginning

Use Cases

  • Shortening: take a url => return a much shorter url
  • Redirection: take a short url => redirect to the original url
  • Custom url
  • Analytics
  • Automatic link expiration
  • Manual link removal
  • UI vs API
  • High availability of the system

What are in the scope? What are out of scope?

Constraints

  • How many requests should be handled per second?
    • The interviewer may give you a number directly or test you by asking question like "let's assume it is a top 10 website"
  • e.g. Twitter, 15 Billion new tweets per month
    • All shortened URLs per month: 1.58 Billion
    • The top 20% got much more traffic than the rest 80%
    • Sites below the top 3: shorten 300M per month
    • We: 100M per month
  • How many requests need to be handled?
    • 1 Billion requests per month
    • 10% from shortening and from redirection
    • If not sure about the number, discuss with interviewer
  • Requests per second: 400+ requests (40 shortened, 360 redirects)
  • Total urls: 5yrs * 12months * 100M = 6Billion urls in 5 yrs
  • 500 bytes per URL
  • 6 bytes per hash
  • 3TB for all urls, 36GB for all hashes (over 5 yrs)
  • New data written per second
    • 40 * (500 + 6): 20k
    • data read per second: 360*506 bytes: 180k

The point is that at the interview, if you need to come up with such numbers it's good to have some background knowledge but also to be able to do reasonable conclusions about the numbers and to explain them to the interviewer.

results matching ""

    No results matching ""