Bird
Raised Fist0

ETA and Time Series Prediction System - Maps, Delivery Forecasting

SYSTEM-DESIGNhardInterview freq: high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
ETA and Time Series Prediction System - Maps, Delivery Forecasting
Design a robust system for accurate ETA predictions in delivery services.
system-designhardFreq: highPrediction Systems
Prerequisites:Feature EngineeringGradient Boosting
🎯
Problem Framing
Business Objective

Minimize delivery time deviations to improve customer satisfaction and operational efficiency.

ML Objective

Predict accurate ETA for deliveries based on historical and real-time data.

Constraints
  • P99 latency < 100ms for ETA predictions
  • High throughput: 10,000 QPS
  • Real-time data ingestion from GPS and traffic sources
  • Cold start for new delivery routes
  • Regulatory compliance with data privacy laws
Clarifying Questions
  • What is the acceptable error margin for ETA predictions?
  • How frequently does the traffic data update?
  • What are the peak usage times for the system?
  • Are there any specific regions with higher prediction errors?
  • What fallback mechanisms are currently in place?
Out of Scope
✗ User interface design
✗ Backend logistics management
✗ Non-delivery related predictions
📊
Offline Metrics
MAE (Mean Absolute Error) because it provides a direct measure of prediction accuracy in time units.
RMSE (Root Mean Square Error) to penalize larger errors more heavily, which is critical for ETA predictions.
📈
Online Metrics
On-time delivery rate to measure the percentage of deliveries meeting the predicted ETA.
Customer satisfaction score as a proxy for the accuracy and reliability of ETA predictions.
⚖️
Trade-offs

Offline metrics like MAE may show improvement, but if on-time delivery rate doesn't increase, the model may not be capturing real-world dynamics effectively.

💼
Business Metric

On-time delivery rate

🗄️
Data Sources
  • Historical delivery logs (structured, daily updates)
  • Real-time GPS data (streaming, real-time)
  • Traffic data from third-party APIs (structured, every 5 minutes)
  • Weather data (structured, hourly updates)
🏷️
Data Properties
Labeling Strategy

Explicit labels from historical delivery logs indicating actual delivery times.

Data Volume

Approximately 10 million rows per day, 1 TB per month.

Freshness

Real-time for GPS and traffic data, T-1 day for historical logs.

⚠️
Data Challenges
  • Sparse labels for new routes
  • Position bias due to varying traffic conditions
  • Survivorship bias in historical data
  • Cold start for new delivery areas
🔧
Key Features
numerical
current_traffic_speed
Directly impacts travel time.
numerical
historical_route_time
Baseline for expected travel time.
categorical
weather_conditions
Affects driving conditions.
categorical
time_of_day
Traffic patterns vary by time.
categorical
day_of_week
Different traffic patterns on weekends.
categorical
special_events
Can cause unexpected delays.
⚡
Feature Engineering Notes
Real-time vs Batch

Real-time computation for current_traffic_speed and weather_conditions; batch for historical_route_time.

Feature Store

Required

🐍
Feature Snippet
Python
def compute_traffic_speed_feature(gps_data):
    return gps_data['speed'].mean()
🤖
Model Selection
Baseline

Linear regression using historical averages.

Proposed Model

Gradient Boosting Machine (GBM)

GBM handles non-linear relationships well and can incorporate a variety of feature types, which is crucial given the diverse data sources.
✗
Alternatives Rejected
LSTM: Rejected due to high latency and complexity in handling real-time data.
Random Forest: Rejected due to higher computational cost and less interpretability compared to GBM.
🏋️
Training Strategy

Offline training with periodic updates to incorporate new data.

🚀
Serving Infrastructure
LatencyP99 < 100ms end-to-end
Throughput10,000 QPS
ArchitectureSingle-stage for simplicity and speed, given the latency constraints.
CachingCache recent predictions with a TTL of 5 minutes to handle repeated requests for the same route.
FallbackUse historical averages for ETA if the model is unavailable.
📡
Data Drift Signals
Change in traffic speed distribution
Shift in weather condition frequencies
New route patterns emerging
📉
Model Drift Signals
Increase in MAE over a rolling window
Decrease in on-time delivery rate
Shift in prediction score distribution
🔔
Alerting & Retraining
Retraining Trigger

MAE increases by 10% over a month.

Alerting Strategy

Page on-call engineer if MAE exceeds threshold; log all prediction errors; auto-recover by switching to fallback.

📌
Key Decisions
  • Choosing GBM for its balance of accuracy and interpretability.
  • Implementing a single-stage serving architecture to meet latency requirements.
  • Designing a robust monitoring system to detect and respond to data and model drift.

Practice

(1/5)
1. For an ad auction system aiming to maximize revenue, which metric should be optimized?
easy
A. Click-through Rate (CTR)
B. Conversion Rate
C. Ad Impressions
D. Expected Revenue

Solution

  1. Step 1: Align metric with objective

    To maximize revenue, the system should optimize for Expected Revenue, which considers both CTR and bid amounts.

  2. Step 2: Eliminate wrong options

    • Click-through Rate (CTR): Measures engagement, not directly linked to revenue.
    • Conversion Rate: Focuses on post-click actions, not directly on revenue.
    • Ad Impressions: Measures visibility, not revenue.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Optimize Expected Revenue for revenue goals. [OK]
Hint: Optimize Expected Revenue for revenue goals. [OK]
Common Mistakes:
2. For a spam detection system, which metric is most appropriate to optimize for?
easy
A. F1 Score
B. Precision
C. Recall
D. Accuracy

Solution

  1. Step 1: Understand the importance of balancing precision and recall

    F1 Score balances precision and recall, which is crucial in spam detection.

  2. Step 2: Eliminate less balanced metrics

    Accuracy (A) can be misleading with imbalanced data. Precision (B) and Recall (C) alone don't balance false positives and negatives.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    F1 balances precision and recall. [OK]
Hint: F1 balances precision and recall. [OK]
Common Mistakes:
3. When implementing a 'People You May Know' feature, should you use a simple Jaccard similarity or a more complex graph embedding approach? Assume the graph is sparse and dynamic.
medium
A. Use Jaccard similarity because it's computationally efficient for sparse graphs.
B. Use graph embeddings because they are always better than simple metrics.
C. Use Jaccard similarity because it adapts well to dynamic graphs.
D. Use graph embeddings because they capture more complex relationships.

Solution

  1. Step 1: Analyze graph characteristics.

    The graph is sparse and dynamic, requiring methods that capture complex relationships.

  2. Step 2: Evaluate options.

    Jaccard similarity (A) is efficient but too simplistic for capturing complex relationships. Graph embeddings (B) are suitable as they capture more nuanced relationships. Jaccard similarity (C) does not inherently adapt to dynamic graphs. Graph embeddings (D) are not always better, but in this case, they are due to the complexity of relationships.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Embeddings capture complex relationships. [OK]
Hint: Embeddings capture complex relationships. [OK]
Common Mistakes:
4. What is a likely failure mode if a spam detection system is not robust to adversarial attacks?
medium
A. Model underfitting
B. Increased false positives
C. Model overfitting
D. Increased false negatives

Solution

  1. Step 1: Understand adversarial attack impacts

    Adversarial attacks often aim to bypass detection, leading to false negatives.

  2. Step 2: Eliminate unrelated failure modes

    False positives (B) are less likely from adversarial attacks. Overfitting (C) and underfitting (D) are unrelated to adversarial robustness.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Adversarial attacks increase false negatives. [OK]
Hint: Adversarial attacks increase false negatives. [OK]
Common Mistakes:
5. As the number of queries increases tenfold, which component of a search ranking system is most likely to become a bottleneck first?
hard
A. Ranking computation
B. Document retrieval
C. Query parsing
D. Index updating

Solution

  1. Step 1: Consider the impact of scaling queries

    Ranking computation is resource-intensive and scales with query volume.

  2. Step 2: Evaluate other components

    Query parsing and document retrieval are less computationally intensive, and index updating is not query-dependent.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Ranking computation scales with query volume. [OK]
Hint: Ranking computation scales with query volume. [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard