| LRU Cache Structure |
| |
| +-----------------------------------------------------------+ |
| | Hash Map: Key -> Pointer to Doubly Linked List Node | |
| +-----------------------------------------------------------+ |
| | |
| v |
| +-------+ +-------+ +-------+ +-------+ +-------+ |
| | Head |<-->| Node1 |<-->| Node2 |<-->| Node3 |<-->| Tail | |
| +-------+ +-------+ +-------+ +-------+ +-------+ |
| (Most Recently Used) (Least Recently Used) |
+-------------------------------------------------------------------+
**Be ready to go over:**
- **In-Memory Caching Strategies** – Implementing O(1) read/write caching primitives using combined hash maps and doubly linked lists (e.g., LRU Cache).
- **Streaming Metric Aggregation** – Processing incoming streaming events (such as metric logs or vehicle price updates) using running totals, maps, and stateful structures.
- **Data Structure Implementation** – Building custom Collections, Stacks, or Queue variations from scratch without relying on native container libraries.
- **Advanced concepts (less common)** – Binary bitwise operations, custom thread-safe concurrent data structures, and complex graph traversal algorithms.
**Example scenarios:**
- Write a program that ingests a stream of JSON metric objects and calculates the running average for any specified `metric_name` and `source`.
- Given a list of car listings with pricing attributes, write an efficient algorithm to compute and return the top $k$ listings closest to a buyer
### SQL & Relational Database Design
Database competency is heavily weighted across almost every engineering team at **CarGurus**. You will be asked to compose executable SQL queries and whiteboard relational schemas on live calls.
+-------------------+ +-----------------------+ +-------------------+
| Dealers | | Listings | | Price_History |
+-------------------+ +-----------------------+ +-------------------+
| PK: dealer_id |<----->| PK: listing_id |<----->| PK: history_id |
| name | 1:N | FK: dealer_id | 1:N | FK: listing_id |
| location_zip | | vin | | price |
+-------------------+ | make_model | | updated_at |
| current_price | +-------------------+
+-----------------------+
**Be ready to go over:**
- **Complex Aggregations & Joins** – Using `INNER`, `LEFT`, and `FULL OUTER` joins alongside `GROUP BY`, `HAVING`, and window functions to summarize data sets.
- **Relational Schema Modeling** – Designing normalized SQL tables for domain features (e.g., dealer subscriptions, car reservations, inventory feeds).
- **Query Optimization & Indexing** – Identifying execution bottlenecks, evaluating B-Tree index choices, and optimizing queries against large-scale tables.
- **Advanced concepts (less common)** – Database partitioning, explicit transaction isolation levels, and read-replica sync strategies.
**Example scenarios:**
- Construct a query that joins a `dealers` table and a `listings` table to return the average listing price per dealer, ensuring non-listing dealers are retained with null averages.
- Walk through how you would optimize a slow-running SQL query that performs a multi-join across three tables containing tens of millions of rows.
### System Architecture & Operational Diagnostics
System design rounds test your ability to build fault-tolerant web architectures and diagnose production outages or operational anomalies.
**Be ready to go over:**
- **Microservice Infrastructure** – Designing loosely coupled internal platform services, operational APIs, and scheduled deployment management systems.
- **Debugging & Performance Diagnosis** – Systematic approaches to investigating slow site load times, server errors, and A/B test split anomalies.
- **CI/CD & Deployment Strategies** – Principles of continuous integration, ephemeral environments, blue/green deployments, and Dockerfile optimization.
- **Advanced concepts (less common)** – Distributed consensus protocols, Kafka event-sourcing architectures, and complex cache invalidation patterns.
**Example scenarios:**
- Whiteboard a internal service to manage code freeze schedules between developer platform dashboards and build automation pipelines.
- Trace the systematic root-cause diagnosis steps you would take if production monitoring alerts report an unexpected drop in conversion rates on the main vehicle detail page.