System design interview questions & answers

Model answer

Part 1 - Define the Objective

Objective: Optimize for "Delivery Time Reliability" while ensuring safety and earnings for couriers.

Outcome to Optimize:

• Delivery Time Consistency: Aim to reduce the variance in delivery times across different conditions (e.g., weather, time of day, and urban geography).

Alignment with Marketplace:

• Enhancing delivery time reliability improves customer satisfaction, leading to repeat orders.
• Consistent delivery times can help merchants manage inventory and staffing better.
• Couriers benefit from predictable earnings through optimized routes and reduced idle time.

---

Part 2 - Build the Metrics Framework

Primary Metrics:

1. Average Delivery Time (ADT): - Formula: \( \text{ADT} = \frac{\sum \text{Delivery Times}}{\text{Number of Deliveries}} \)
2. Delivery Time Variance (DTV): - Formula: \( \text{DTV} = \frac{\sum (\text{Delivery Time} - \text{ADT})^2}{\text{Number of Deliveries}} \)

Diagnostic Metrics:

• On-Time Delivery Rate (OTDR): Percentage of deliveries completed within the promised time.
• Courier Earnings per Hour (CEPH): Measures the financial health of couriers.

Guardrails:

• Safety Incidents Rate: Track any increase in accidents or near-misses.
• Merchant Satisfaction Score: Ensure merchants are not negatively impacted by delivery changes.

---

Part 3 - Identify Data, Features, and Risks

Data Needed:

• Courier Data: Location, route choice, delivery times, and earnings.
• Merchant Data: Order preparation times, order volume, and customer ratings.
• Customer Data: Order history, delivery expectations, and satisfaction ratings.
• Environmental Data: Weather conditions, traffic patterns, and urban geography.

Features to Extract:

• Route Complexity: Number of intersections, hills, and pedestrian zones.
• Weather Conditions: Rain, snow, temperature, and wind speed.
• Time of Day: Peak vs. off-peak hours.

Data Quality Risks:

• Incomplete or inaccurate location data from couriers.
• Delays in weather data updates impacting real-time decision-making.
• Potential biases in customer ratings based on external factors.

---

Part 4 - Propose Levers and Validation Plan

Actionable Ideas:

1. Dynamic Routing Adjustments: Use real-time weather and traffic data to adjust routes for couriers.
2. Incentive Programs: Implement bonuses for couriers during peak demand times or adverse weather conditions.
3. Merchant Training: Provide best practices for faster order preparation based on historical data.

Experimentation Plan:

• A/B Testing: Randomly assign couriers to either the new routing algorithm or the existing one to measure differences in delivery time and customer satisfaction.
• Causal Inference: Use regression analysis to control for confounding variables like weather and time of day, isolating the impact of changes made.
• Longitudinal Studies: Track performance over time to assess the sustainability of improvements and ensure no negative impacts on safety or earnings.

By implementing this structured approach, we can effectively optimize bike delivery performance while balancing the needs of customers, couriers, and merchants.

Model answer

1. Requirements & scale

Functional Requirements:

• Users can create, read, update, and delete tasks.
• Tasks have attributes such as title, description, due date, and status.
• Users can list all tasks or filter tasks by status or due date.

Non-Functional Requirements:

• The API should be highly available and responsive.
• It should support a moderate number of concurrent users.
• Ensure data consistency for task operations.

Scale Estimates:

• Assume 10,000 active users, each making 10 requests/day.
• Total Requests per Day = 100,000.
• QPS (Queries Per Second) = 100,000 / 86,400 ≈ 1.16 QPS.
• Storage: Assuming each task is 1 KB and each user has 100 tasks, total storage = 10,000 users 100 tasks 1 KB = 1 GB.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Device]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Task API Service]
    end

    subgraph Datastores
        E["SQL Database"]
    end

    subgraph Cache
        F[Redis Cache]
    end

    A -->|HTTP Request| B
    B -->|Forward Request| C
    C -->|Route Request| D
    D -->|Read/Write| F
    D -->|Read/Write| E
    F -->|Cache Miss| E

3. API design

• POST /tasks: Create a new task.
• GET /tasks: Retrieve a list of tasks, with optional filters for status and due date.
• GET /tasks/{id}: Retrieve a specific task by ID.
• PUT /tasks/{id}: Update a task by ID.
• DELETE /tasks/{id}: Delete a task by ID.

4. Data model & storage

Chosen Datastore:

• SQL Database: A relational database is suitable here due to the need for ACID transactions and structured queries.

Key Tables:

• Tasks Table:
• task_id (Primary Key)
• user_id (Foreign Key)
• title
• description
• due_date
• status

Partitioning Strategy:

• Partition by user_id to distribute load evenly and improve query performance.

5. Deep dive

The core functionality of the task management system is CRUD operations on tasks. Let's focus on the flow for creating a task.

sequenceDiagram
    participant U as User
    participant A as API Gateway
    participant S as Task API Service
    participant C as Redis Cache
    participant D as SQL Database

    U->>A: POST /tasks
    A->>S: Forward request
    S->>D: Insert task into DB
    D-->>S: Task ID
    S->>C: Update cache with new task
    S-->>A: Return success response
    A-->>U: Task created

6. Scale, bottlenecks & trade-offs

Scaling:

• Horizontal Scaling: Add more instances of the Task API Service and SQL Database replicas to handle increased load.
• Caching: Use Redis to cache frequently accessed tasks to reduce database load and improve response times.

Bottlenecks:

• Database: As the number of tasks grows, database read/write operations could become a bottleneck. Use indexing and partitioning to optimize performance.
• Cache Consistency: Ensure cache invalidation strategies are in place to maintain consistency between the cache and the database.

Trade-offs:

• Consistency vs. Availability: Opt for strong consistency for task operations to ensure users always see the most up-to-date task information.
• SQL vs. NoSQL: SQL is chosen for its ACID properties, which are crucial for maintaining data integrity in task management.

By designing the system with these considerations, we ensure a robust, scalable, and user-friendly task management API.

Model answer

1. Requirements & scale

Functional Requirements:

• Store key-value pairs.
• Retrieve values by key.
• Delete key-value pairs.
• Update values for existing keys.

Non-Functional Requirements:

• High availability and reliability.
• Low latency for read and write operations.
• Scalability to handle increasing data volume.

Estimates:

• Assume 1 million keys, each with an average size of 1 KB.
• Total storage: 1 million * 1 KB = ~1 GB.
• Assume 1000 read/write requests per second (QPS).
• Bandwidth: 1000 QPS * 1 KB = ~1 MB/s.

2. High-level architecture

flowchart TD
    subgraph Client
        A[Client]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[API Gateway]
        E[Key-Value Service]
    end

    subgraph Cache
        F[In-Memory Cache]
    end

    subgraph Datastores
        G["MongoDB Cluster"]
    end

    A --> B
    B --> C
    C --> D
    D --> E
    E --> F
    F --> G
    G --> F

3. API design

• POST /store: Store a new key-value pair.
• GET /retrieve/{key}: Retrieve the value for a given key.
• PUT /update/{key}: Update the value for an existing key.
• DELETE /delete/{key}: Delete a key-value pair.

4. Data model & storage

Datastore Choice:

• MongoDB: Chosen for its flexible schema, scalability, and built-in replication features.

Data Model:

• Collection: KeyValueStore
• Document structure:
• _id: ObjectId (MongoDB's unique identifier)
• key: String (unique key)
• value: Binary or String (depending on the use case)
• timestamp: Date (for versioning or TTL)

Partitioning Strategy:

• Shard key: key (ensures even distribution across shards).

5. Deep dive

The core operation of this key-value store is the efficient retrieval and storage of key-value pairs. MongoDB's indexing capabilities allow for fast lookups by key.

sequenceDiagram
    participant C as Client
    participant D as API Gateway
    participant E as Key-Value Service
    participant F as In-Memory Cache
    participant G as MongoDB Cluster

    C->>D: GET /retrieve/{key}
    D->>E: Forward request
    E->>F: Check cache for key
    alt Key in cache
        F-->>E: Return value
        E-->>D: Return value
        D-->>C: Return value
    else Key not in cache
        E->>G: Query MongoDB for key
        G-->>E: Return value
        E->>F: Update cache with value
        E-->>D: Return value
        D-->>C: Return value
    end

6. Scale, bottlenecks & trade-offs

Scalability:

• Sharding: MongoDB's sharding allows horizontal scaling by distributing data across multiple servers.
• Replication: Ensures high availability and reliability by replicating data across multiple nodes.

Bottlenecks:

• Cache Misses: Frequent cache misses can increase latency. Mitigated by optimizing cache hit ratio.
• Network Latency: Can be reduced by deploying MongoDB clusters close to the application servers.

Trade-offs:

• Consistency vs. Availability: MongoDB can be configured for eventual consistency, which improves availability but may result in stale reads.
• Read vs. Write Optimization: The system can be tuned for read-heavy or write-heavy workloads by adjusting cache strategies and MongoDB configurations.

By leveraging MongoDB's robust features and a well-designed architecture, this key-value store can efficiently handle the specified requirements while remaining scalable and reliable.

Model answer

1. Prediction Target and Time

• Prediction Target (Label):
• The target label will be whether a lead converted within a defined conversion window (e.g., 30 days).
• Optionally, we can include time_to_convert_days to provide additional insights.
• Prediction Time:
• Scores will be computed at the time of lead generation.
• For leads that are too recent to have observed the outcome window, we will assign a default score (e.g., average score of historical leads) until sufficient data is available.

2. Feature Sets and Data Sources

• Feature Sets:
• Acquisition Channel: Channel through which the lead arrived (e.g., ads, email).
• Firmographics: Company size, industry, etc.
• Behavioral Signals: Pages viewed, demo requests, email engagement.
• Handling Feature Availability and Leakage:
• Ensure features are only derived from data available at the time of scoring to prevent leakage.
• Use historical data to train models but avoid using future information (e.g., conversion status) during scoring.

3. Statistical and Machine Learning Models

• Statistical Model:
• Logistic Regression as a baseline model.
• Interpretability: Easy to understand and explain coefficients.
• Advanced Machine Learning Model:
• Random Forest or Gradient Boosting Machines (GBM).
• Performance Trade-offs: Higher accuracy but less interpretability compared to logistic regression.

4. Deliverables Based on Stakeholder Needs

• Predictive Performance Focus:
• Deliver the model with performance metrics (AUC, accuracy) and predictions.
• Understanding Feature Importance:
• Provide feature importance scores (e.g., SHAP values) alongside the model to explain which features drive predictions.

5. Multicollinearity

• Definition:
• Multicollinearity occurs when two or more features are highly correlated, leading to unreliable coefficient estimates.
• Importance:
• Matters for linear models (e.g., logistic regression) but less critical for tree-based models (e.g., Random Forest).
• Detection:
• Use Variance Inflation Factor (VIF) to identify multicollinearity.
• Mitigation:
• Remove or combine correlated features to reduce redundancy.

6. Model Evaluation

• Primary Metric:
• AUC-ROC for overall performance, as it balances sensitivity and specificity.
• Diagnostic Metrics/Plots:
• Confusion matrix, precision-recall curve, and feature importance plots.
• Guardrails:
• Monitor fairness (e.g., equal opportunity), stability (e.g., model drift), and operational constraints (e.g., top-K capacity).

7. Operating Threshold / Routing Policy

• Threshold Selection:
• Use ROC curve analysis to select a threshold that balances precision and recall based on business needs.
• Consider business implications of false positives vs. false negatives.

8. Key Risks

• Class Imbalance:
• Address using techniques like SMOTE or adjusting class weights.
• Selection Bias:
• Ensure that the dataset represents the entire lead population, not just those touched by sales.
• Fairness:
• Regularly audit model predictions across different demographic groups.
• Drift:
• Monitor model performance over time and retrain as necessary.

9. Deployment and Monitoring

• Deployment:
• Use a CI/CD pipeline to automate model deployment and updates.
• Monitoring:
• Implement logging to track model performance and lead conversion rates.
• Set up alerts for performance degradation and retrain models periodically based on new data.

Model answer

1. Requirements & scale

Functional Requirements:

• Distribute incoming requests evenly across multiple GPU instances.
• Automatically detect and redirect traffic from failed GPU instances.
• Support dynamic scaling of GPU instances.

Non-Functional Requirements:

• High availability and reliability.
• Low latency in request distribution.
• Scalability to handle increasing loads.

Estimates:

• Assume an average of 1000 requests per second (QPS) initially, with potential scaling up to 10,000 QPS.
• Each request might involve a payload of approximately 1 KB, leading to a bandwidth requirement of 10 MB/s initially, scaling up to 100 MB/s.
• Storage for logs and monitoring data is estimated at 10 GB/month.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Devices]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[GPU Service API]
    end

    subgraph Datastores
        E[Monitoring DB]
    end

    A -->|Requests| B
    B -->|Forwarded Requests| C
    C -->|Distributed Requests| D
    D -->|Metrics| E
    C -->|Health Checks| D

3. API design

• POST /process: Accepts a request to process data using GPU resources.
• GET /status: Returns the current status of a request.
• GET /health: Provides health status of the GPU instances.

4. Data model & storage

Datastores:

• Monitoring DB: A NoSQL database like MongoDB for storing logs and monitoring data due to its scalability and flexibility.

Key Tables:

• Requests: Stores request metadata, status, and timestamps.
• Instances: Tracks GPU instance statuses and health metrics.

Partition Key:

• Use the request ID as the partition key for the Requests table to ensure even distribution and quick access.

5. Deep dive

The core of this system is the load balancer, which efficiently distributes requests across GPU instances. We'll use a round-robin algorithm for simplicity and fairness, ensuring that each GPU instance receives an equal number of requests. The load balancer will also perform health checks to detect any failed instances and redirect traffic accordingly.

sequenceDiagram
    participant User
    participant CDN
    participant LoadBalancer
    participant GPUInstance
    participant MonitoringDB

    User->>CDN: Send Request
    CDN->>LoadBalancer: Forward Request
    LoadBalancer->>GPUInstance: Distribute Request
    GPUInstance->>MonitoringDB: Log Metrics
    GPUInstance-->>LoadBalancer: Return Response
    LoadBalancer-->>CDN: Forward Response
    CDN-->>User: Deliver Response

6. Scale, bottlenecks & trade-offs

Scaling:

• The load balancer can be scaled horizontally by adding more instances to handle increased load.
• GPU instances can be dynamically added or removed based on demand.

Bottlenecks:

• The load balancer itself can become a bottleneck if not scaled appropriately.
• Network latency between the load balancer and GPU instances can affect performance.

Trade-offs:

• Consistency vs. Availability: Prioritize availability by using a stateless load balancer that can quickly redirect traffic in case of instance failure.
• Push vs. Pull: Use a push model for distributing requests to minimize latency.
• SQL vs. NoSQL: Choose NoSQL for monitoring data to handle high write loads and provide flexibility in data schema.

By implementing these strategies, the system ensures efficient load distribution, high availability, and scalability to meet the demands of a GPU cloud service.

Model answer

1. Requirements & scale

Functional Requirements:

• Shorten a given URL.
• Redirect to the original URL when a shortened URL is accessed.
• Track the number of times a shortened URL is accessed.
• Optionally, allow users to customize the shortened URL.

Non-Functional Requirements:

• High availability and reliability.
• Low latency for URL redirection.
• Scalability to handle a large number of requests.

Estimates:

• Assume a service that handles 100 million new URLs per month.
• Average URL length: 100 characters.
• Shortened URL length: 7 characters.
• Estimated QPS (Queries Per Second): 1000 QPS (considering peak load).
• Storage: 100 million URLs * 100 bytes = ~10 GB per month.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[URL Shortening Service]
        E[Redirection Service]
    end

    subgraph Cache
        F[Cache (Redis)]
    end

    subgraph Datastores
        G[SQL Database]
    end

    subgraph Message Queue
        H[Queue]
    end

    subgraph Workers
        I[Analytics Worker]
    end

    A --> B --> C --> D
    D --> F
    D --> G
    E --> F
    E --> G
    G --> H
    H --> I

3. API design

• POST /shorten: Accepts a long URL and returns a shortened URL.
• GET /{shortUrl}: Redirects to the original URL.
• GET /stats/{shortUrl}: Returns access statistics for a shortened URL.

4. Data model & storage

Datastore Choice:

• SQL Database: Chosen for its ACID properties, ensuring consistency and integrity of URL mappings.
• Cache (Redis): Used for quick access to frequently accessed URLs.

Key Tables:

• URLs Table:
• id (Primary Key)
• original_url (VARCHAR)
• short_url (VARCHAR, Unique)
• access_count (INT)

Partitioning Strategy:

• Partition URLs based on the id to distribute load evenly across database shards.

5. Deep dive

The core of the URL shortening service is the generation of a unique short URL. A common approach is to use a base62 encoding of an auto-incrementing ID from the database. This ensures that each short URL is unique and can be easily decoded to retrieve the original ID.

sequenceDiagram
    participant U as User
    participant S as URL Shortening Service
    participant D as SQL Database
    participant C as Cache (Redis)

    U->>S: POST /shorten
    S->>D: Insert new URL
    D-->>S: Return ID
    S->>S: Encode ID to base62
    S->>D: Store short URL
    S->>C: Cache short URL
    S-->>U: Return short URL

6. Scale, bottlenecks & trade-offs

Scalability:

• Sharding: The database is sharded based on the id to handle large volumes of data and distribute load.
• Caching: Frequently accessed URLs are cached in Redis to reduce database load and improve latency.

Bottlenecks:

• Database: Can become a bottleneck if not properly sharded. Using a distributed SQL database can alleviate this.
• Cache: Ensure cache consistency and handle cache misses gracefully.

Trade-offs:

• Consistency vs. Availability: By using a SQL database, we prioritize consistency. However, during network partitions, availability might be affected.
• Push vs. Pull for Analytics: Using a message queue and workers for analytics allows asynchronous processing, reducing the load on the main service.

By addressing these considerations, the URL shortening service can be designed to handle high traffic efficiently while maintaining reliability and low latency.

Model answer

1. Requirements & scale

Functional Requirements:

• Provide an API to retrieve vehicle data.
• Support querying vehicle data by vehicle ID.
• Return vehicle data in JSON format.

Non-Functional Requirements:

• Ensure low-latency responses.
• Handle a moderate number of requests per second (QPS).
• Ensure high availability and reliability.

Estimates:

• Assume 10,000 vehicles, with each vehicle queried approximately once per minute.
• QPS = 10,000 vehicles / 60 seconds = ~167 QPS.
• Average JSON response size = 1 KB.
• Bandwidth = 167 QPS * 1 KB = ~167 KB/s.
• Storage: If each vehicle's data is 1 KB, total storage = 10,000 vehicles * 1 KB = ~10 MB.

2. High-level architecture

flowchart TD
    subgraph Client
        A[Mobile App]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Vehicle API Service]
    end

    subgraph Cache
        E[In-memory Cache]
    end

    subgraph Datastores
        F[SQL Database]
    end

    A -->|HTTP Request| B
    B -->|HTTP Request| C
    C -->|HTTP Request| D
    D -->|Query| E
    E -->|Cache Hit| D
    E -->|Cache Miss| F
    F -->|Data| D
    D -->|JSON Response| C
    C -->|JSON Response| B
    B -->|JSON Response| A

3. API design

• GET /vehicles/{vehicleId}: Retrieve data for a specific vehicle by its ID.

4. Data model & storage

Datastore Choice:

• SQL Database: Chosen for its ACID properties and the structured nature of vehicle data.

Key Tables:

• Vehicles Table:
• vehicle_id (Primary Key)
• make
• model
• year
• status
• location

Partition Key:

• vehicle_id: Ensures efficient lookups and distribution of data across partitions.

5. Deep dive

The core of this design is the efficient retrieval of vehicle data using caching to reduce database load and improve response times.

sequenceDiagram
    participant A as Mobile App
    participant B as CDN
    participant C as Load Balancer
    participant D as Vehicle API Service
    participant E as In-memory Cache
    participant F as SQL Database

    A->>B: HTTP GET /vehicles/{vehicleId}
    B->>C: Forward Request
    C->>D: Forward Request
    D->>E: Check Cache for vehicleId
    alt Cache Hit
        E-->>D: Return Cached Data
    else Cache Miss
        D->>F: Query Database for vehicleId
        F-->>D: Return Data
        D->>E: Update Cache with Data
    end
    D-->>C: Return JSON Response
    C-->>B: Forward Response
    B-->>A: Return JSON Response

6. Scale, bottlenecks & trade-offs

Scaling:

• Horizontal Scaling: API services can be scaled horizontally to handle increased load.
• Caching: Use in-memory caching (e.g., Redis) to store frequently accessed vehicle data, reducing database load and improving response times.

Bottlenecks:

• Database Load: Mitigated by caching and efficient indexing on vehicle_id.
• Network Latency: Minimized by using a CDN to cache static responses closer to users.

Trade-offs:

• Consistency vs. Availability: With caching, there might be a slight delay in data consistency. However, this trade-off is acceptable given the improved response times.
• SQL vs. NoSQL: SQL is chosen for its strong consistency and structured data requirements, despite potentially higher latency compared to NoSQL solutions.

Failure Modes:

• Cache Failure: If the cache fails, the system falls back to querying the database directly, which may increase latency but ensures data availability.
• Database Failure: Implement database replication and failover strategies to maintain availability.

Model answer

1. Requirements & scale

Functional Requirements:

• Users can add items to their shopping cart.
• Users can view items in their cart.
• Users can update item quantities or remove items from the cart.
• Users can proceed to checkout.

Non-Functional Requirements:

• Low latency for cart operations (add, update, remove).
• High availability and fault tolerance.
• Scalability to handle peak loads.

Estimates:

• Assume 1 million active users, with 10% interacting with the cart simultaneously.
• Average of 2 cart operations per user per minute.
• Estimated QPS (Queries Per Second): 100,000 users * 2 operations/minute / 60 = ~3,333 QPS.
• Storage: Assume each cart entry is 1 KB. For 1 million users with an average of 10 items per cart, total storage = 1 million 10 1 KB = 10 GB.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Device]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Cart Service]
    end

    subgraph Cache
        E[Redis Cache]
    end

    subgraph Datastores
        F[SQL Database]
    end

    A -->|HTTP Request| B
    B -->|Forward Request| C
    C -->|API Call| D
    D -->|Read/Write| E
    D -->|Read/Write| F
    E -->|Cache Miss| F

3. API design

• POST /cart/add: Add an item to the cart.
• GET /cart/view: Retrieve current items in the cart.
• PUT /cart/update: Update quantity of an item in the cart.
• DELETE /cart/remove: Remove an item from the cart.
• POST /cart/checkout: Proceed to checkout.

4. Data model & storage

Datastore Choice:

• Use a SQL database for transactional integrity and complex queries.
• Redis for caching to reduce database load and improve response times.

Key Tables:

• Cart: cart_id (PK), user_id, created_at.
• CartItem: item_id (PK), cart_id (FK), product_id, quantity.

Partitioning:

• Partition Cart and CartItem tables by user_id to distribute load evenly.

5. Deep dive

The core operation in a shopping cart system is the management of cart items. Let's focus on the "Add to Cart" operation:

sequenceDiagram
    participant U as User
    participant S as Cart Service
    participant C as Redis Cache
    participant D as SQL Database

    U->>S: POST /cart/add
    S->>C: Check if cart exists in cache
    alt Cache Hit
        C-->>S: Return cart data
    else Cache Miss
        S->>D: Query cart from database
        D-->>S: Return cart data
        S->>C: Store cart in cache
    end
    S->>D: Add item to cart in database
    S->>C: Update cart in cache
    S-->>U: Return success response

6. Scale, bottlenecks & trade-offs

Replication and Sharding:

• Use database replication for high availability.
• Shard the database by user_id to handle large datasets and distribute load.

Caching:

• Use Redis to cache cart data, reducing database load and improving response times.
• Implement cache invalidation strategies to ensure data consistency.

Single Points of Failure:

• Use a load balancer to distribute traffic and avoid single points of failure.
• Ensure redundancy in Redis and SQL databases.

Trade-offs:

• Consistency vs. Availability: Prioritize consistency for cart operations to ensure users see the correct cart state. Use strong consistency in the database and eventual consistency in the cache.
• Push vs. Pull: Use a pull model for cart updates where the client requests the latest cart state, ensuring users always see up-to-date information.
• SQL vs. NoSQL: SQL is chosen for its strong transactional support, which is crucial for maintaining cart integrity during concurrent operations.

Model answer

1. Requirements & scale

Functional Requirements:

• Shorten a given URL.
• Redirect to the original URL when a shortened URL is accessed.
• Track the number of times a shortened URL is accessed.
• Support custom aliases for URLs.

Non-Functional Requirements:

• High availability and low latency.
• Scalable to handle millions of URLs and requests.
• Reliable redirection with minimal downtime.

Estimates:

• Assume 100 million URLs are shortened over the system's lifetime.
• Average URL length: 100 characters; shortened URL length: 7 characters.
• Daily active users: 1 million, each generating 10 requests per day.
• QPS (Queries Per Second): 1 million users * 10 requests / 86,400 seconds ≈ 115 QPS.
• Storage: 100 million URLs * (100 + 7) characters ≈ 10.7 GB.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[URL Shortening Service]
    end

    subgraph Cache
        E[Redis Cache]
    end

    subgraph Datastores
        F[SQL Database]
    end

    subgraph Workers
        G[Analytics Worker]
    end

    A -->|HTTP Request| B
    B -->|Forward Request| C
    C -->|API Call| D
    D -->|Read/Write| E
    E -->|Cache Miss| F
    D -->|Log Access| G

3. API design

• POST /shorten: Accepts a URL and returns a shortened URL.
• GET /{shortUrl}: Redirects to the original URL.
• POST /custom: Accepts a URL and a custom alias, returns a shortened URL.
• GET /stats/{shortUrl}: Returns access statistics for a shortened URL.

4. Data model & storage

Datastore Choice:

• Use a SQL database for ACID transactions and consistency, which is crucial for URL mappings.
• Redis for caching frequently accessed URLs to reduce database load.

Key Tables:

• urls:
• id (Primary Key)
• original_url (VARCHAR)
• short_url (VARCHAR, Unique)
• custom_alias (VARCHAR, Nullable)
• access_count (INT)

Partitioning:

• Partition the urls table by id for scalability.

5. Deep dive

The core functionality of a URL shortening service is to generate a unique short URL for each original URL. This can be achieved using a base conversion algorithm.

1. Generate a Unique ID: Use an auto-incrementing ID from the SQL database.
2. Convert ID to Short URL: Convert the ID to a base-62 number (using characters 0-9, a-z, A-Z) to create a short URL.

sequenceDiagram
    participant User
    participant Service
    participant DB as SQL Database
    participant Cache as Redis Cache

    User->>Service: POST /shorten {original_url}
    Service->>DB: Insert original_url, get ID
    DB-->>Service: Return ID
    Service->>Service: Convert ID to base-62
    Service->>Cache: Cache short_url -> original_url
    Service-->>User: Return short_url

6. Scale, bottlenecks & trade-offs

Scaling:

• Use horizontal scaling for the database and caching layers.
• Implement read replicas for the SQL database to handle read-heavy traffic.

Bottlenecks:

• Cache misses can lead to increased database load; ensure high cache hit rates.
• Network latency can affect redirection speed; use CDNs to minimize latency.

Trade-offs:

• Consistency vs. Availability: Prioritize consistency to ensure accurate URL redirection.
• Caching Strategy: Use a write-through cache to ensure data consistency between cache and database.
• URL Collision: Use a retry mechanism for handling collisions in custom aliases.

By focusing on these aspects, the system can efficiently handle high traffic, provide reliable URL redirection, and support additional features like custom aliases and analytics.

Model answer

1. Requirements & scale

Functional Requirements:

• Users can add new tasks.
• Users can update existing tasks.
• Users can delete tasks.
• Users can view a list of all tasks.

Non-Functional Requirements:

• The system should be highly available.
• The system should have low latency for task operations.
• The system should be scalable to handle an increasing number of users.

Estimates:

• Assume 10,000 users with each user creating an average of 10 tasks per day.
• Total tasks per day = 10,000 users * 10 tasks = 100,000 tasks.
• Assume peak load is 10 times the average load: 1,000 tasks per second (QPS).
• Each task entry is approximately 1 KB. Thus, daily storage requirement = 100,000 KB = 100 MB.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Interface]
    end
    
    subgraph Edge/CDN
        B[CDN]
    end
    
    subgraph Load Balancer
        C[Load Balancer]
    end
    
    subgraph API / Services
        D[Task Service]
    end
    
    subgraph Cache
        E[Redis Cache]
    end
    
    subgraph Datastores
        F[SQL Database]
    end
    
    A --> B["HTTP Requests"]
    B --> C["HTTP Requests"]
    C --> D["API Calls"]
    D --> E["Cache Lookup"]
    E -->|Cache Miss| F["DB Queries"]
    D -->|Cache Hit| A["Response"]
    F --> D["DB Response"]
    D --> E["Cache Update"]
    D --> C["Response"]
    C --> B["Response"]
    B --> A["Response"]

3. API design

• POST /tasks: Create a new task.
• GET /tasks: Retrieve all tasks.
• PUT /tasks/{id}: Update a task by ID.
• DELETE /tasks/{id}: Delete a task by ID.

4. Data model & storage

Datastore Choice:

• Use a SQL database for ACID transactions and structured data storage.

Key Tables:

• Tasks Table:
• id (Primary Key, UUID)
• title (VARCHAR)
• description (TEXT)
• status (ENUM: 'pending', 'completed')
• created_at (TIMESTAMP)
• updated_at (TIMESTAMP)

Partition/Sharding Key:

• Use id as the primary key. For sharding, consider user ID if tasks are user-specific.

5. Deep dive

The core functionality of the task management application revolves around CRUD operations. Let's focus on the "Add Task" operation:

sequenceDiagram
    participant UI as User Interface
    participant API as Task Service
    participant Cache as Redis Cache
    participant DB as SQL Database

    UI->>API: POST /tasks
    API->>Cache: Check if task list is cached
    alt Cache Miss
        API->>DB: Insert new task
        DB-->>API: Task ID
        API->>Cache: Update cache with new task list
    end
    API-->>UI: Task Created (Task ID)

In this flow, when a user adds a task, the service checks the cache for the task list. If not found, it writes the task to the database and updates the cache. This ensures that subsequent reads are faster.

6. Scale, bottlenecks & trade-offs

Replication and Sharding:

• Use database replication to ensure high availability and read scalability.
• Implement sharding based on user ID to distribute load evenly across database shards.

Caching:

• Use Redis to cache frequently accessed data like task lists to reduce database load and improve response times.

Single Points of Failure:

• Ensure redundancy in the load balancer and cache layers to prevent single points of failure.

Trade-offs:

• Consistency vs Availability: Opt for eventual consistency in the cache layer to improve availability and performance.
• SQL vs NoSQL: SQL is chosen for its strong consistency and support for complex queries, which is suitable for task management.

By following this design, the task management application can efficiently handle user requests while maintaining scalability and performance.

Model answer

1. Requirements & scale

Functional Requirements:

• Ingest data from multiple sources in real-time.
• Process and transform the data for analytics.
• Store processed data for querying and analysis.
• Ensure data integrity and fault tolerance.

Non-Functional Requirements:

• Low latency for real-time data processing.
• High availability and scalability.
• Fault tolerance and data durability.

Estimates:

• Assume the system needs to handle 10,000 events per second (QPS).
• Each event is approximately 1 KB, resulting in a data ingestion rate of 10 MB/s.
• Long-term storage requirement: If storing data for one year, approximately 315 TB (10 MB/s 60 60 24 365).

2. High-level architecture

flowchart TD
    subgraph Client
        A[Data Sources]
    end

    subgraph Edge/CDN
        B[Data Ingestion API]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Data Processing Service]
    end

    subgraph Cache
        E[In-memory Cache]
    end

    subgraph Datastores
        F["Real-time DB (NoSQL)"]
        G["Data Warehouse (SQL)"]
    end

    subgraph Message Queue
        H[Message Queue]
    end

    subgraph Workers
        I[Processing Workers]
    end

    A -->|Real-time Data| B
    B -->|Ingested Data| C
    C -->|Load Balanced Data| H
    H -->|Queued Data| I
    I -->|Processed Data| D
    D -->|Transformed Data| E
    E -->|Cached Data| F
    D -->|Batch Data| G

3. API design

• POST /ingest: Accepts data from various sources for ingestion.
• Request: JSON payload containing event data.
• Response: Acknowledgment of data receipt.
• GET /status: Provides the status of the ingestion pipeline.
• Response: JSON with current processing metrics.

4. Data model & storage

Datastores:

• Real-time DB (NoSQL): Chosen for its ability to handle high write throughput and low latency reads. Suitable for real-time analytics.
• Key Tables: Events table with partition key based on event type and timestamp.
• Data Warehouse (SQL): Used for batch processing and complex queries.
• Key Tables: Analytics table with columns for aggregated metrics.

5. Deep dive

The core of this system is the data ingestion and processing pipeline. The data ingestion API receives data from various sources and forwards it to a message queue. This decouples data producers from consumers, allowing for scalable and fault-tolerant processing.

sequenceDiagram
    participant A as Data Source
    participant B as Ingestion API
    participant C as Message Queue
    participant D as Processing Worker
    participant E as Real-time DB

    A->>B: Send Data
    B->>C: Enqueue Data
    C->>D: Dequeue Data
    D->>E: Store Processed Data
    D->>F: Store in Data Warehouse

6. Scale, bottlenecks & trade-offs

Scaling:

• Use horizontal scaling for the ingestion API and processing workers to handle increased load.
• Implement sharding in the NoSQL database based on event type and timestamp to distribute load evenly.

Bottlenecks:

• The message queue could become a bottleneck if not scaled properly. Use a distributed queue system like Kafka to handle high throughput.

Trade-offs:

• Consistency vs. Availability: Opt for eventual consistency in the NoSQL database to ensure high availability.
• Push vs. Pull: Use a pull model for processing workers to control the rate of data processing and avoid overloading the system.
• Sync vs. Async: Asynchronous processing is used to decouple ingestion from processing, improving system resilience and scalability.

This design provides a robust and scalable solution for real-time data ingestion and processing, balancing between performance, scalability, and fault tolerance.

Model answer

1. Requirements & scale

Functional Requirements:

• Track login events using user_id.
• Compute Monthly Active Users (MAU) as the number of distinct user_id with at least one login in the last 30 days.
• Handle a one-time rehash of user_id on a specific date T.

Non-Functional Requirements:

• Ensure accuracy in MAU computation despite user_id rehashing.
• Maintain system scalability to handle large volumes of login data.

Estimates:

• Assume 1 million users with an average of 1 login per day.
• Daily login events: 1 million.
• Storage: If each event requires 100 bytes (including metadata), daily storage is approximately 100 MB.
• Over a 30-day window, this results in 3 GB of storage.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Device]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Login Service]
        E[MAU Calculation Service]
    end

    subgraph Datastores
        F["Event Store (NoSQL)"]
        G["User Mapping Store (SQL)"]
    end

    subgraph Cache
        H[Redis Cache]
    end

    subgraph Workers
        I[Batch Processor]
    end

    A -->|Login Event| B
    B --> C
    C --> D
    D -->|Store Event| F
    E -->|Fetch Events| F
    E -->|Fetch Mapping| G
    E -->|Cache Results| H
    I -->|Process Events| E

3. API design

• POST /login: Record a login event with user_id.
• GET /mau: Retrieve the MAU for a specified date range.

4. Data model & storage

Datastores:

• Event Store (NoSQL): Used for storing login events. Chosen for its scalability and ability to handle high write throughput.
• User Mapping Store (SQL): Stores the mapping between old and new user_id. Chosen for its strong consistency guarantees.

Key Tables:

• LoginEvents: {user_id, timestamp}
• UserMapping: {user_id_old, user_id_new}

Partition Key:

• LoginEvents partitioned by user_id to distribute load evenly.

5. Deep dive

The core challenge is ensuring accurate MAU computation across the user_id rehash. Without the mapping, distinct counts will be inflated for windows overlapping date T.

sequenceDiagram
    participant MAUService as MAU Calculation Service
    participant EventStore as Event Store
    participant MappingStore as User Mapping Store
    participant Cache as Redis Cache

    MAUService->>EventStore: Fetch login events for [d-29, d]
    MAUService->>MappingStore: Fetch user_id mapping for date range
    MAUService->>Cache: Check cached MAU
    alt Cache Hit
        Cache-->>MAUService: Return cached MAU
    else Cache Miss
        MAUService->>MAUService: Compute distinct user_id
        MAUService->>Cache: Cache computed MAU
    end

6. Scale, bottlenecks & trade-offs

Replication and Sharding:

• The Event Store should be sharded by user_id to handle large volumes of data efficiently.
• The User Mapping Store should be replicated across multiple nodes to ensure availability and fault tolerance.

Caching:

• Use Redis to cache computed MAU results to reduce computation overhead for frequently queried date ranges.

Single Points of Failure:

• Ensure load balancers and key services are redundant to prevent single points of failure.

Trade-offs:

• Consistency vs. Availability: Opt for eventual consistency in the Event Store to improve availability and write throughput.
• Push vs. Pull: Use a pull-based approach for MAU computation to allow flexibility in handling data rehash scenarios.

By implementing a robust user mapping mechanism and leveraging caching, the system can accurately compute MAU even in the presence of user_id rehashing, ensuring minimal bias and operational resilience.

Model answer

1. Requirements & scale

Functional Requirements:

• Support video conferencing for 2-5 users per call.
• Real-time audio and video streaming.
• Basic user authentication and call management (join/leave).

Non-Functional Requirements:

• Low latency to ensure smooth video and audio.
• High availability and reliability.
• Scalability to support multiple concurrent calls.

Estimates:

• Users: Assume 1,000 concurrent calls at peak.
• Video Bandwidth: Assume 1 Mbps per user for video. For 5 users, each call requires 5 Mbps.
• Total Bandwidth: 1,000 calls * 5 Mbps = 5,000 Mbps or 5 Gbps.
• Storage: Primarily for logs and metadata, minimal storage needed per call.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Devices]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Auth Service]
        E[Call Management Service]
    end

    subgraph Cache
        F[Redis Cache]
    end

    subgraph Datastores
        G[User DB (SQL)]
        H[Call Metadata DB (NoSQL)]
    end

    subgraph Message Queue
        I[Message Queue]
    end

    subgraph Workers
        J[Media Server]
    end

    A -- "Video/Audio Stream" --> B
    B -- "Stream" --> C
    C -- "Auth Request" --> D
    D -- "User Data" --> G
    C -- "Call Request" --> E
    E -- "Call Data" --> H
    E -- "Notify" --> I
    I -- "Stream Control" --> J
    J -- "Stream" --> B

3. API design

• POST /api/auth/login: Authenticate a user.
• POST /api/call/start: Start a new call session.
• POST /api/call/join: Join an existing call.
• POST /api/call/leave: Leave a call.
• GET /api/call/status: Get the status of a call.

4. Data model & storage

Datastores:

• User DB (SQL): Stores user credentials and profiles.
• Table: Users
• user_id (Primary Key)
• username
• password_hash
• email
• Call Metadata DB (NoSQL): Stores call session data.
• Collection: Calls
• call_id (Partition Key)
• participants (List of user_ids)
• start_time
• end_time

Cache:

• Redis: Used for session management and quick access to frequently accessed data.

5. Deep dive

The core of the video conferencing application is the real-time media streaming, which is handled by the Media Server. The Media Server is responsible for mixing and distributing audio/video streams to participants.

sequenceDiagram
    participant User1
    participant User2
    participant MediaServer
    participant CDN

    User1->>MediaServer: Send Video/Audio Stream
    MediaServer->>CDN: Distribute Stream
    User2->>CDN: Request Stream
    CDN->>User2: Deliver Stream
    User2->>MediaServer: Send Video/Audio Stream
    MediaServer->>CDN: Distribute Stream
    User1->>CDN: Request Stream
    CDN->>User1: Deliver Stream

6. Scale, bottlenecks & trade-offs

Scaling:

• Horizontal Scaling: Add more Media Servers to handle increased load. Use a load balancer to distribute calls evenly.
• CDN Usage: Offload static content and video streams to a CDN to reduce latency and server load.

Bottlenecks:

• Media Server: Can become a bottleneck if not scaled properly. Ensure it can handle multiple streams efficiently.
• Network Bandwidth: Ensure sufficient bandwidth to handle peak loads.

Trade-offs:

• Consistency vs. Availability: Prioritize availability and low latency over strict consistency in call metadata.
• Push vs. Pull CDN: Use a push CDN for static assets, but real-time streams should be directly managed by Media Servers for minimal latency.
• SQL vs. NoSQL: Use SQL for user data requiring ACID properties; use NoSQL for flexible and scalable call metadata storage.

Model answer

1. Requirements & scale

Functional Requirements:

• Users can create, update, and delete tasks.
• Users can view a list of tasks.
• Tasks should have attributes like title, description, due date, and status.

Non-Functional Requirements:

• High availability and reliability.
• Low latency for task operations.
• Scalability to support a growing number of users.

Estimates:

• Assume 100,000 users, each making an average of 10 task operations per day.
• This results in approximately 1,000,000 operations per day.
• QPS (Queries Per Second) = 1,000,000 / (24 60 60) ≈ 11.6.
• Storage: Assume each task is about 1 KB. With 1,000,000 tasks, storage needed is approximately 1 GB.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Interface]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Task Service]
    end

    subgraph Cache
        E[Redis Cache]
    end

    subgraph Datastores
        F[SQL Database]
    end

    A -->|HTTP Requests| B
    B -->|Forward Requests| C
    C -->|API Calls| D
    D -->|Read/Write| E
    D -->|Read/Write| F
    E -->|Cache Miss| F

3. API design

• POST /tasks: Create a new task.
• GET /tasks: Retrieve a list of tasks.
• GET /tasks/{id}: Retrieve a specific task by ID.
• PUT /tasks/{id}: Update a task by ID.
• DELETE /tasks/{id}: Delete a task by ID.

4. Data model & storage

Datastore Choice:

• Use a SQL database (e.g., PostgreSQL) for ACID compliance and structured data storage.

Key Tables:

• Tasks Table:
• id (Primary Key)
• title (VARCHAR)
• description (TEXT)
• due_date (DATE)
• status (ENUM: 'pending', 'completed')
• created_at (TIMESTAMP)
• updated_at (TIMESTAMP)

Partitioning:

• Use id as the primary key for partitioning and indexing to ensure quick lookups and updates.

5. Deep dive

The core functionality of the task management system revolves around CRUD operations. To ensure efficient data retrieval and updates, caching can be employed. Here's a sequence diagram illustrating the flow for retrieving a task:

sequenceDiagram
    participant User
    participant CDN
    participant LoadBalancer
    participant TaskService
    participant Cache
    participant Database

    User->>CDN: GET /tasks/{id}
    CDN->>LoadBalancer: Forward Request
    LoadBalancer->>TaskService: API Call
    TaskService->>Cache: Check Cache for Task
    alt Cache Hit
        Cache-->>TaskService: Return Task
    else Cache Miss
        TaskService->>Database: Query Task
        Database-->>TaskService: Return Task
        TaskService->>Cache: Update Cache
    end
    TaskService->>User: Return Task

6. Scale, bottlenecks & trade-offs

Scalability:

• Replication: Use database replication to ensure high availability and distribute read loads.
• Sharding: Implement sharding if the dataset grows significantly, using the id field for shard keys.

Caching:

• Use Redis to cache frequently accessed tasks to reduce database load and improve response times.

Bottlenecks:

• The database could become a bottleneck under heavy load. Mitigate this by optimizing queries and using read replicas.
• The cache layer could become a single point of failure. Ensure redundancy and failover mechanisms are in place.

Trade-offs:

• Consistency vs. Availability: Opt for eventual consistency in caching to improve availability.
• SQL vs. NoSQL: SQL is chosen for its ACID properties, but NoSQL could be considered if flexibility and horizontal scaling become priorities.

By focusing on these components and considerations, the task management system can efficiently handle user operations while being scalable and reliable.

Model answer

1. Requirements & scale

Functional Requirements:

• Users should be able to create tasks with a title and description.
• Users should be able to update task details.
• Users should be able to delete tasks.
• Users should be able to list all tasks.

Non-Functional Requirements:

• The system should be highly available and responsive.
• It should handle a moderate number of concurrent users.
• Data consistency is important, especially for task updates.

Estimates:

• Assume 10,000 active users with an average of 5 tasks per user.
• Total tasks: 50,000.
• Average task size: 1 KB (title + description).
• Total storage: 50 MB.
• Assume 100 requests per second (QPS) for task operations.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Interface]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Task Service]
    end

    subgraph Datastores
        E["SQL Database"]
        F[Cache]
    end

    A -->|HTTP Requests| B --> C --> D
    D -->|Read/Write| F
    D -->|Read/Write| E
    F -->|Cache Miss| E

3. API design

• POST /tasks: Create a new task.
• GET /tasks: Retrieve a list of tasks.
• PUT /tasks/{taskId}: Update an existing task.
• DELETE /tasks/{taskId}: Delete a task.

4. Data model & storage

Datastore Choice:

• Use a SQL database for ACID compliance, ensuring data consistency for task operations.

Key Tables:

• Tasks Table:
• task_id (Primary Key)
• user_id (Foreign Key)
• title (VARCHAR)
• description (TEXT)
• created_at (TIMESTAMP)
• updated_at (TIMESTAMP)

Partitioning Strategy:

• Partition by user_id to distribute load and improve query performance.

5. Deep dive

The core functionality of this task management system revolves around CRUD operations. Let's focus on the task creation and update flows, ensuring data consistency and responsiveness.

sequenceDiagram
    participant User
    participant UI
    participant TaskService
    participant Cache
    participant SQLDB

    User->>UI: Create/Update Task
    UI->>TaskService: POST/PUT /tasks
    TaskService->>Cache: Invalidate Cache
    TaskService->>SQLDB: Insert/Update Task
    SQLDB-->>TaskService: Acknowledge
    TaskService-->>UI: Success Response
    UI-->>User: Task Created/Updated

In this sequence, when a task is created or updated, the cache is invalidated to ensure that subsequent reads fetch the latest data from the database.

6. Scale, bottlenecks & trade-offs

Scaling:

• Replication: Use master-slave replication for the SQL database to improve read scalability and availability.
• Sharding: Partition the database by user_id to distribute the load across multiple database instances.
• Caching: Implement a caching layer (e.g., Redis) to store frequently accessed tasks and reduce database load.

Bottlenecks:

• Database Write Load: High write operations can become a bottleneck. Consider using write-ahead logging and optimizing indexes.
• Cache Invalidation: Ensuring cache consistency can be challenging. Use a cache with a short TTL or implement a write-through strategy.

Trade-offs:

• Consistency vs. Availability: Prioritize consistency for task operations to ensure users always see the correct task state.
• Push vs. Pull: Use a pull-based approach for task listing to ensure users get the most recent data.
• SQL vs. NoSQL: SQL is chosen for its strong consistency guarantees, which are crucial for task management operations. However, this may come at the cost of horizontal scalability compared to NoSQL solutions.

By focusing on these aspects, the task management system can efficiently handle user requests while maintaining data integrity and performance.

Model answer

1. Requirements & scale

Functional Requirements:

• Measure the impact of a membership feature on rides-per-user (RPU).
• Analyze three scenarios: switchback experiment, observational launch, and randomized experiment with non-compliance.

Non-Functional Requirements:

• Ensure statistical validity and reliability of results.
• Maintain user privacy and data security.

Back-of-the-envelope estimates:

• QPS (Queries Per Second): Assume 100 cities, each with 1000 users, generating 10 rides/day.
• Total rides = 100 cities 1000 users 10 rides = 1,000,000 rides/day.
• Storage: Assuming each ride record is 1KB, total storage = 1,000,000 rides * 1KB = ~1TB/day.
• Bandwidth: Each ride generates ~100KB of data (including metadata), leading to ~100GB/day.

2. High-level architecture

flowchart TD
    subgraph Client
        A["Mobile App"]
    end

    subgraph Edge/CDN
        B["Content Delivery Network"]
    end

    subgraph LoadBalancer
        C["Load Balancer"]
    end

    subgraph API_Services
        D["API Gateway"]
        E["Membership Service"]
        F["Analytics Service"]
    end

    subgraph Cache
        G["In-Memory Cache"]
    end

    subgraph Datastores
        H["SQL Database"]
        I["NoSQL Database"]
    end

    subgraph MessageQueue
        J["Message Queue"]
    end

    subgraph Workers
        K["Data Processing Worker"]
    end

    A --> B
    B --> C
    C --> D
    D --> E
    D --> F
    E --> G
    F --> G
    G --> H
    G --> I
    F --> J
    J --> K

3. API design

• GET /membership/status: Check membership eligibility and status.
• POST /membership/activate: Activate membership for a user.
• GET /analytics/rpu: Retrieve RPU metrics for analysis.

4. Data model & storage

• Chosen Datastores:
• SQL for structured data (user profiles, membership status).
• NoSQL for unstructured data (ride history, operational signals).
• Key Tables:
• Users: user_id, membership_status, rides_taken.
• Rides: ride_id, user_id, timestamp, cost.
• Partition/Shard Key:
• Partition by user_id for user-related data, and by city_id for ride data.

5. Deep dive

Part A — Switchback experimentation:

1. Design: - Randomize at the city-day level. - Alternate between treatment (membership active) and control (membership inactive) every week for 4 weeks.
2. Why not vanilla t-test: - Raw aggregated results ignore time trends, seasonality, and city-level differences, leading to biased estimates.
3. Analysis Approach: - Use a mixed-effects model to account for: - Time trends (fixed effects). - City-level heterogeneity (random effects). - Autocorrelation (ARIMA model). - Covariate adjustment (include user history as covariates).

sequenceDiagram
    participant User
    participant MembershipService
    participant AnalyticsService

    User->>MembershipService: Request membership status
    MembershipService-->>User: Return status
    User->>MembershipService: Activate membership
    MembershipService-->>AnalyticsService: Log membership activation
    AnalyticsService-->>MembershipService: Update RPU metrics

6. Scale, bottlenecks & trade-offs

• Replication: Use multiple cities to replicate results.
• Sharding: Shard data by user_id and city_id to improve query performance.
• Caching: Implement caching for frequently accessed data (e.g., RPU metrics).
• Single Points of Failure: Ensure redundancy in critical services (e.g., Membership Service).
• Trade-offs:
• CAP Theorem: Prioritize availability over consistency during peak times.
• Push vs Pull: Use push notifications for membership updates to users.
• SQL vs NoSQL: Use SQL for transactional data and NoSQL for analytics to balance performance and flexibility.

Model answer

1. Requirements & scale

Functional Requirements:

• Users can send and receive messages in real-time.
• Support for one-on-one and group chats.
• Messages should be stored for future retrieval.
• Messages need to be encrypted for security.

Non-Functional Requirements:

• Low latency to ensure real-time communication.
• High availability and reliability.
• Scalability to handle a growing number of users.

Estimates:

• Assume 1 million active users, each sending an average of 10 messages per day.
• Peak load: 100 messages per second (QPS).
• Average message size: 1 KB.
• Daily storage requirement: 10 million messages * 1 KB = 10 GB.
• Monthly storage: 300 GB.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Device]
    end

    subgraph "Edge/CDN"
        B[WebSocket Gateway]
    end

    subgraph "Load Balancer"
        C[Load Balancer]
    end

    subgraph "API / Services"
        D[Chat Service]
        E[Notification Service]
    end

    subgraph "Cache"
        F[Redis]
    end

    subgraph "Datastores"
        G["SQL DB (Users, Chats)"]
        H["NoSQL DB (Messages)"]
    end

    subgraph "Message Queue"
        I[Message Queue]
    end

    subgraph "Workers"
        J[Message Processor]
    end

    A -->|WebSocket| B
    B -->|Forward| C
    C -->|Distribute| D
    D -->|Store Message| H
    D -->|Update Cache| F
    D -->|Queue Notification| I
    I -->|Process| J
    J -->|Send Notification| E
    E -->|Push Notification| A
    G -->|User Data| D
    F -->|Cached Messages| D

3. API design

• POST /messages: Send a message.
• GET /messages/{chat_id}: Retrieve messages for a chat.
• GET /users/{user_id}/chats: Retrieve chat list for a user.
• POST /notifications: Send a notification to a user.

4. Data model & storage

Datastores:

• SQL Database: For structured data like user profiles and chat metadata.
• Users Table: user_id (PK), username, email.
• Chats Table: chat_id (PK), user_id, type (one-on-one/group).
• NoSQL Database: For unstructured message data to handle high write throughput.
• Messages Collection: message_id, chat_id, sender_id, content, timestamp.

Partitioning:

• Messages: Partition by chat_id to distribute load across multiple nodes.

5. Deep dive

The core of a real-time chat application is the use of WebSockets for bi-directional communication, allowing messages to be sent and received instantly.

sequenceDiagram
    participant User1
    participant WebSocketGateway
    participant ChatService
    participant NoSQLDB
    participant User2

    User1->>WebSocketGateway: Send Message
    WebSocketGateway->>ChatService: Forward Message
    ChatService->>NoSQLDB: Store Message
    ChatService->>WebSocketGateway: Acknowledge
    WebSocketGateway->>User1: Delivery Confirmation
    WebSocketGateway->>User2: Deliver Message

6. Scale, bottlenecks & trade-offs

Scaling:

• WebSocket Gateway: Horizontally scale to handle more concurrent connections.
• Databases: Use sharding for the NoSQL database to distribute message storage and retrieval load.

Bottlenecks:

• WebSocket Connections: Can become a bottleneck if not properly load-balanced.
• Message Queue: Ensure it can handle peak loads without delay.

Trade-offs:

• Consistency vs. Availability: Prioritize availability (AP in CAP theorem) to ensure messages are delivered even during partial failures.
• Latency vs. Security: Encrypting messages may introduce latency, but it's essential for security.
• Push vs. Pull: Use push notifications to ensure users receive messages promptly, even when not actively using the app.

This design ensures a scalable, reliable, and secure chat application capable of handling real-time communication efficiently.

Model answer

1. Requirements & scale

Functional Requirements:

• Store frequently accessed data to reduce access time.
• Support efficient data retrieval and updates.
• Implement cache eviction policies to manage limited storage.

Non-Functional Requirements:

• High availability and reliability.
• Low latency for data retrieval.
• Scalability to handle increased load.

Estimates:

• Assume a CPU architecture with 4 cores, each capable of 2 GHz.
• Cache hit rate target: 95%.
• Cache size: 32 KB per core, totaling 128 KB.
• Access latency target: < 1 ns for cache hits.

2. High-level architecture

flowchart TD
    subgraph Client
        A[CPU Core]
    end

    subgraph "Cache"
        B[L1 Cache]
        C[L2 Cache]
        D[L3 Cache]
    end

    subgraph "Main Memory"
        E[RAM]
    end

    A -->|Request Data| B
    B -->|Miss| C
    C -->|Miss| D
    D -->|Miss| E
    E -->|Fetch Data| D
    D -->|Update| C
    C -->|Update| B
    B -->|Return Data| A

3. API design

In a CPU cache system, APIs are not typical. However, conceptual operations include:

• Read: Fetch data from the cache or memory.
• Write: Update data in the cache and propagate changes to memory.
• Evict: Remove least-used data when cache is full.

4. Data model & storage

Datastores:

• L1 Cache: Smallest, fastest, located on the CPU core. Stores most frequently accessed data.
• L2 Cache: Larger than L1, shared across cores, slower but still fast.
• L3 Cache: Largest, shared across all cores, slower than L1 and L2.

Data Model:

• Cache lines: Fixed-size blocks of data (e.g., 64 bytes).
• Tag, index, and offset used for cache lookup.

5. Deep dive

The core algorithm involves cache lookup and eviction:

1. Cache Lookup: When a core requests data, it first checks the L1 cache using the address's tag and index. If not found (cache miss), it checks L2, then L3, and finally fetches from RAM.
2. Cache Eviction: When a cache is full, an eviction policy like Least Recently Used (LRU) is applied. The cache line that hasn't been accessed for the longest time is replaced.

sequenceDiagram
    participant CPU as CPU Core
    participant L1 as L1 Cache
    participant L2 as L2 Cache
    participant L3 as L3 Cache
    participant RAM as Main Memory

    CPU->>L1: Request Data
    alt Cache Hit
        L1-->>CPU: Return Data
    else Cache Miss
        L1->>L2: Request Data
        alt Cache Hit
            L2-->>CPU: Return Data
        else Cache Miss
            L2->>L3: Request Data
            alt Cache Hit
                L3-->>CPU: Return Data
            else Cache Miss
                L3->>RAM: Request Data
                RAM-->>L3: Return Data
                L3-->>L2: Update Cache
                L2-->>L1: Update Cache
                L1-->>CPU: Return Data
            end
        end
    end

6. Scale, bottlenecks & trade-offs

Scaling:

• Multi-level caches (L1, L2, L3) provide scalability by distributing data storage and access across different levels, balancing speed and size.

Bottlenecks:

• Cache misses lead to higher latency as data retrieval falls back to slower memory levels.
• L1 cache is a potential bottleneck due to its limited size and high demand.

Trade-offs:

• Consistency vs. Availability: Ensuring data consistency across caches can introduce latency, but is crucial for correctness.
• Eviction Policy: LRU is simple and effective but may not always be optimal for all workloads. LFU or FIFO might be considered based on specific access patterns.
• Overprovisioning: Allocating more cache than initially required can handle future load increases but at the cost of higher resource usage.

By carefully designing the cache hierarchy and choosing appropriate eviction policies, the system can achieve high performance and reliability, crucial for CPU operations.

Model answer

1. Requirements & scale

Functional Requirements:

• Users can upload CSV files through a web interface.
• The system processes and ingests CSV data into a database.
• Provide feedback to users on the success or failure of the upload.

Non-Functional Requirements:

• High availability and reliability.
• Scalability to handle varying file sizes and upload frequencies.
• Low latency for feedback on file processing.

Back-of-the-Envelope Estimates:

• Assume 1000 users, each uploading a 5MB CSV file daily.
• Daily data ingestion: 1000 files * 5MB = 5GB.
• Peak QPS (queries per second) during uploads: Assume peak of 10 uploads per second.
• Storage: If retaining data for a year, 5GB/day * 365 = ~1.8TB/year.

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Browser]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Upload Service]
        E[Processing Service]
    end

    subgraph Cache
        F[Redis Cache]
    end

    subgraph Datastores
        G["Blob Storage (S3)"]
        H["SQL Database"]
    end

    subgraph Workers
        I[CSV Processor]
    end

    A -->|Upload CSV| B
    B --> C
    C --> D
    D -->|Store File| G
    D -->|Notify| E
    E -->|Queue Processing| I
    I -->|Process CSV| H
    I -->|Cache Results| F
    F -->|Feedback| A

3. API design

• POST /upload
• Purpose: Upload a CSV file.
• Request: Multipart/form-data with CSV file.
• Response: Upload status and file ID.
• GET /status/{fileId}
• Purpose: Check the processing status of an uploaded file.
• Response: Status of the file processing (e.g., pending, processing, completed, failed).

4. Data model & storage

Blob Storage (S3):

• Used for storing raw CSV files.
• Key: userId/timestamp/filename.csv

SQL Database:

• Chosen for structured data and complex queries.
• Tables:
• Users: userId, name, email
• Files: fileId, userId, uploadTime, status, location
• Data: dataId, fileId, column1, column2, ..., columnN
• Partition Key: userId for Files and fileId for Data.

5. Deep dive

The core of this system is the CSV processing pipeline. Once a file is uploaded, it is stored in blob storage, and a message is sent to the processing service to queue the file for processing. The processing service reads the file, parses the CSV data, and inserts it into the SQL database.

sequenceDiagram
    participant U as User
    participant S as Upload Service
    participant P as Processing Service
    participant B as Blob Storage
    participant D as Database

    U->>S: POST /upload (CSV File)
    S->>B: Store CSV File
    S->>P: Notify File Upload
    P->>B: Retrieve CSV File
    P->>D: Insert Parsed Data
    P->>S: Update File Status
    S->>U: Return Upload Status

6. Scale, bottlenecks & trade-offs

Scalability:

• Use a load balancer to distribute incoming requests across multiple instances of the upload service.
• Blob storage can scale to handle large volumes of data.

Bottlenecks:

• CSV processing can be CPU-intensive; use a distributed processing system to parallelize the workload.
• Database writes can become a bottleneck; consider batching writes or using a queue to manage load.

Trade-offs:

• Consistency vs. Availability: Opt for eventual consistency in processing status updates to ensure high availability.
• SQL vs. NoSQL: SQL is chosen for its ability to handle complex queries and relationships, which is crucial for data integrity and analytics.
• Push vs. Pull: Use a push model for notifying the processing service to reduce latency.

Fault Tolerance:

• Use retries and idempotent operations to handle transient failures.
• Implement monitoring and alerting to quickly detect and resolve issues.

Model answer

1. Requirements & scale

Functional Requirements:

• Users can create, edit, and delete notes.
• Users can view a list of their notes.
• Notes should be stored persistently.

Non-Functional Requirements:

• High availability and reliability.
• Quick response time for note operations.
• Secure storage of notes.

Scale Estimates:

• Assume 1 million users, with each user creating an average of 10 notes.
• Average note size: 1 KB.
• Total storage: \(1,000,000 \times 10 \times 1 \text{ KB} = 10 \text{ GB}\).
• Assume 10% of users are active at any time, performing an average of 1 request per minute.
• QPS (Queries Per Second): \(0.1 \times 1,000,000 / 60 = 1,667\).

2. High-level architecture

flowchart TD
    subgraph Client
        A[User Device]
    end

    subgraph Edge/CDN
        B[CDN]
    end

    subgraph Load Balancer
        C[Load Balancer]
    end

    subgraph API / Services
        D[Notes Service]
    end

    subgraph Cache
        E[Redis Cache]
    end

    subgraph Datastores
        F[SQL Database]
    end

    A -->|HTTP Requests| B
    B -->|Forward Requests| C
    C -->|Distribute Load| D
    D -->|Read/Write| E
    E -->|Cache Miss| F
    D -->|Write-through| F

3. API design

• POST /notes: Create a new note.
• GET /notes: Retrieve all notes for a user.
• GET /notes/{id}: Retrieve a specific note.
• PUT /notes/{id}: Update a specific note.
• DELETE /notes/{id}: Delete a specific note.

4. Data model & storage

Datastore Choice:

• Use a SQL database for structured data and ACID transactions, ensuring consistency and integrity of note data.

Key Tables:

• Users Table: user_id (Primary Key), username, email.
• Notes Table: note_id (Primary Key), user_id (Foreign Key), title, content, created_at, updated_at.

Partitioning:

• Partition Notes Table by user_id to distribute load evenly across database shards.

5. Deep dive

The core functionality of this note-taking application revolves around CRUD operations on notes. The system should efficiently handle these operations while ensuring data consistency and quick access.

sequenceDiagram
    participant U as User
    participant N as Notes Service
    participant C as Cache
    participant DB as SQL Database

    U->>N: POST /notes (Create Note)
    N->>C: Check Cache for User's Notes
    alt Cache Miss
        N->>DB: Insert Note into Database
        DB-->>N: Note Inserted
        N->>C: Update Cache with New Note
    else Cache Hit
        N->>C: Update Cache with New Note
    end
    N-->>U: Note Created

    U->>N: GET /notes (Retrieve Notes)
    N->>C: Check Cache for User's Notes
    alt Cache Hit
        C-->>N: Return Cached Notes
    else Cache Miss
        N->>DB: Query Notes from Database
        DB-->>N: Return Notes
        N->>C: Update Cache with Notes
    end
    N-->>U: Return Notes

6. Scale, bottlenecks & trade-offs

Replication and Sharding:

• Use database replication to ensure high availability and fault tolerance.
• Shard the Notes Table by user_id to distribute load and improve performance.

Caching:

• Implement a Redis cache to store frequently accessed notes, reducing database load and improving response times.

Single Points of Failure:

• Use a load balancer to distribute traffic and prevent any single server from becoming a bottleneck.
• Ensure redundancy in the caching layer to prevent data loss in case of failure.

Trade-offs:

• Consistency vs. Availability: Opt for strong consistency in the SQL database to ensure users always see the most recent version of their notes.
• Push vs. Pull: Use a pull-based model for retrieving notes, as users typically request notes on demand.
• SQL vs. NoSQL: SQL is chosen for its strong consistency guarantees and support for complex queries, which are beneficial for managing structured note data.