Write SQL and merge linked lists
Company: Google
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
The technical interview included two coding-style tasks: a SQL analytics query and merging two sorted linked lists.
### Constraints & Assumptions
- For SQL, return one row per customer, including customers with no orders.
- Report `total_orders`, `total_amount`, `latest_order_date`, and `latest_order_amount`.
- Use a nested query, CTE, or window function to identify each customer's most recent order.
- For linked lists, reuse existing nodes and return the merged head.
### Clarifying Questions to Ask
- If a customer has multiple orders on the same latest date, how should ties be handled?
- Should returned orders affect total order amount?
- Should `total_amount` be `0` or `NULL` for customers with no orders?
- Are linked-list values sorted in non-decreasing order?
### Part 1 - Write The SQL Query
Given `customers`, `orders`, and `returns`, write a query returning customer-level order metrics and latest order amount.
#### What This Part Should Cover
- Aggregate orders by customer.
- Use `ROW_NUMBER()` or similar to find the latest order per customer.
- `LEFT JOIN` from customers so customers without orders remain.
- `COALESCE` for zero counts and amounts if desired.
### Part 2 - Merge Two Sorted Linked Lists
Given heads of two sorted singly linked lists, merge them into one sorted list by reusing nodes.
#### What This Part Should Cover
- Dummy head and tail pointer.
- Compare current node values and append the smaller node.
- Attach the remaining suffix.
- Complexity and edge cases.
### What a Strong Answer Covers
- Preserves customers with no orders.
- Handles latest-order tie assumptions explicitly.
- Avoids double-counting from unnecessary joins to returns.
- Reuses linked-list nodes without allocating new list nodes.
### Follow-up Questions
- How would you exclude returned orders?
- How would you handle ties in latest order date?
- How would you merge `k` sorted linked lists?
- What is the recursive linked-list solution?
Overview: Solve a SQL customer order aggregation task and merge two sorted linked lists. The solution uses CTEs, window functions, LEFT JOINs, COALESCE, latest-order tie handling, optional returned-order filtering, and an O(m+n) dummy-head linked-list merge.
Community answers
Answer by Machupichu
WITH order_totals AS (
SELECT
customer_id,
COUNT(*) AS total_orders,
SUM(amount) AS total_amount
FROM orders
GROUP BY customer_id
),
latest_order AS (
SELECT
customer_id,
order_date AS latest_order_date,
amount AS latest_order_amount
FROM (
SELECT
o.*,
ROW_NUMBER() OVER (
PARTITION BY customer_id
ORDER BY order_date DESC
) AS ranking
FROM orders o
) ranked
WHERE ranking = 1
)
SELECT
c.customer_id,
c.customer_name,
COALESCE(ot.total_orders, 0) AS total_orders,
COALESCE(ot.total_amount, 0) AS total_amount,
lo.latest_order_date, --Populated with NULL if there re no orders
lo.latest_order_amount -- -Populated with NULL if there re no orders
FROM customers c
LEFT JOIN order_totals ot
ON c.customer_id = ot.customer_id
LEFT JOIN latest_order lo
ON c.customer_id = lo.customer_id
ORDER BY c.customer_id;