What are the top system design interview questions for Facebook?

When preparing for a system design interview at Facebook, candidates should be ready to discuss designing scalable, reliable, and efficient systems. Facebook's interviews often focus on large-scale systems that handle high volumes of data and traffic. Here are some of the top system design interview questions commonly asked at Facebook:

1. Design a URL Shortener

Problem: Design a service like Bit.ly that generates a short URL from a long URL.

Key Considerations:

• Unique ID generation for each URL.
• Mapping short URLs to long URLs.
• Handling high read and write traffic.
• Data storage and retrieval.
• URL expiration and analytics.

2. Design a News Feed System

Problem: Design a system that generates a news feed for users, similar to Facebook's news feed.

Key Considerations:

• Real-time updates.
• Personalized content based on user preferences.
• Scalability to handle millions of users.
• Efficient querying and data retrieval.
• Push notifications for new content.

3. Design a Messenger System

Problem: Design a messaging service like Facebook Messenger.

Key Considerations:

• Real-time message delivery.
• Message storage and retrieval.
• Handling different types of messages (text, images, videos).
• User presence and notifications.
• Scalability and fault tolerance.

4. Design a Photo Sharing Service

Problem: Design a system for sharing and viewing photos, similar to Instagram or Facebook Photos.

Key Considerations:

• Image storage and retrieval.
• Efficient image uploads and downloads.
• Image metadata storage (captions, tags, geolocation).
• Scalability to handle millions of users.
• Content delivery network (CDN) for fast image delivery.

5. Design a Content Delivery Network (CDN)

Problem: Design a CDN that delivers static content (like images, videos) to users efficiently.

Key Considerations:

• Caching strategies.
• Geo-distribution of servers.
• Load balancing.
• Redundancy and fault tolerance.
• Handling dynamic content.

6. Design a Web Crawler

Problem: Design a web crawler that indexes web pages for a search engine.

Key Considerations:

• Scalability to crawl millions of pages.
• Efficient URL storage and deduplication.
• Handling dynamic and static content.
• Politeness policy to avoid overloading websites.
• Data storage and indexing.

7. Design an API Rate Limiter

Problem: Design a system to rate limit API requests.

Key Considerations:

• Algorithms for rate limiting (token bucket, leaky bucket).
• Handling burst traffic.
• User-specific rate limits.
• Distributed rate limiting.
• Monitoring and logging.

8. Design a Video Streaming Service

Problem: Design a video streaming service like YouTube or Facebook Live.

Key Considerations:

• Video storage and retrieval.
• Efficient video encoding and transcoding.
• Real-time streaming capabilities.
• Scalability to handle millions of concurrent viewers.
• Content delivery network (CDN) for fast and reliable delivery.

9. Design a Distributed Cache

Problem: Design a distributed caching system to speed up data retrieval.

Key Considerations:

• Cache eviction policies (LRU, LFU).
• Data consistency across caches.
• Cache invalidation strategies.
• Scalability and fault tolerance.
• Monitoring cache performance.

10. Design a Notification System

Problem: Design a system to send notifications to users in real-time.

Key Considerations:

• Different types of notifications (push, email, SMS).
• Real-time delivery.
• User preferences and settings.
• Scalability to handle millions of notifications.
• Monitoring and logging.

Example Approach: Design a URL Shortener

Requirements:

• Generate a unique short URL for each long URL.
• Redirect short URL to the original long URL.
• Handle high read and write traffic.
• Optionally track usage statistics and expiration dates for URLs.

Key Components:

1. Unique ID Generation:

   • Use a base-62 encoding to generate short URLs.
   • Optionally, use a hash function with collision handling.

2. Data Storage:

   • Store mappings between short and long URLs in a database.
   • Use a NoSQL database like DynamoDB for scalability.

3. Redirection Service:

   • When a short URL is accessed, retrieve the corresponding long URL from the database and redirect.

4. Scalability:

   • Use load balancers to distribute traffic across multiple servers.
   • Implement caching for frequently accessed URLs using Redis or Memcached.

5. Analytics and Monitoring:

   • Track the number of clicks for each short URL.
   • Use logging and monitoring tools to keep track of system performance and errors.

Example Code Snippet:

class URLShortener:
    def __init__(self):
        self.url_map = {}
        self.counter = 1
        self.base62_chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

    def encode(self, long_url):
        short_url = self._encode_base62(self.counter)
        self.url_map[short_url] = long_url
        self.counter += 1
        return short_url

    def decode(self, short_url):
        return self.url_map.get(short_url)

    def _encode_base62(self, num):
        if num == 0:
            return self.base62_chars[0]
        result = []
        while num > 0:
            result.append(self.base62_chars[num % 62])
            num //= 62
        return ''.join(reversed(result))

# Usage
url_shortener = URLShortener()
short_url = url_shortener.encode("https://www.example.com")
print(short_url)  # Outputs: a unique short URL
print(url_shortener.decode(short_url))  # Outputs: "https://www.example.com"

Conclusion

By understanding and practicing these system design problems, you'll be well-prepared for a system design interview at Facebook. Focus on scalability, reliability, and efficiency, and be ready to discuss trade-offs and design choices in detail.