Problem Breakdown
Restatement: We need to identify, for every customer who has placed orders, their three most recent transactions based on order_date. If a specific customer has fewer than three orders in total, we return all available records. The final result must be sorted by the order_date descending globally (most recent first across all customers).
Inputs:
- A list of dictionaries representing rows from an implicit
Orderstable containing at leastcustomer_idandorder_date.
Outputs:
- A list of lists, where each inner list represents a record
[customer_id, order_date], sorted globally by date descending.
Implicit Constraints & Edge Cases:
- Fewer than three orders: The logic must handle customers with < 3 orders without error; simply return all available rows in the correct global sort order.
- Global Sorting Requirement: Unlike standard SQL window functions which might output per-group, Python lists require explicit sorting of the final collection to meet the “sorted by
order_datedescending” requirement stated in the problem description. The proposed solution missed this step initially. - Tie-breaking on dates: If multiple orders share the exact same timestamp, standard sort stability preserves relative order; consistent ordering is acceptable unless specified otherwise.
- Empty Input: The code must handle scenarios where no customers or orders exist gracefully (return empty list).
Intuition
Brute Force Approach: A naive approach might iterate through every customer, filter their specific order history from the global dataset for each one individually, sort that subset, and slice it. If implemented inefficiently (e.g., scanning a large list repeatedly), this could degrade to O(N^2). Even if we scan once per customer, sorting dominates complexity.
Key Insight:
The core operation is grouping by customer_id followed by local sorting within each group. Since the requirement is strictly “top 3”, we don’t need to sort globally and then partition; however, unlike SQL where window functions handle this natively, Python requires explicit post-processing for global ordering if specified. Grouping into buckets (using a hash map) followed by sorting each bucket is the most direct translation of “window function” behavior using standard libraries.
Optimal Approach:
- Grouping: Aggregate orders by
customer_id. This takes linear time O(N). - Sorting & Slicing: For each customer’s list, sort descending by date and take the first three elements. Sorting a subset of size is efficient; worst case (one giant group) remains dominated by sorting complexity.
- Global Ordering: Collect all selected records into a single result list and perform one final global sort to satisfy the output ordering requirement, which adds negligible overhead compared to grouping/sorting steps in most distributions but ensures correctness for edge cases where customers are processed out of date order.
Approach
- Initialize a
defaultdictto mapcustomer_id-> List of dictionaries containing{order_date}. - Iterate through the provided orders list, populating this dictionary. This groups all data logically in O(N).
- Create an empty result list.
- For each customer ID found:
- Extract their order history from the map.
- Sort that specific list by
order_datedescending (using a key function and reverse flag). - Slice the first three items (
[:3]).
- Format these sliced records into
[customer_id, date]tuples/lists and append to our result set. - Crucial Step: Sort the entire
resultlist byorder_datedescending before returning to ensure global compliance with problem requirements. - Return the aggregated results.
Complexity Analysis
- Time: O(N log N) in the worst case (where all orders belong to a single customer). The grouping step is O(N), and sorting dominates with complexity proportional to . If data were distributed evenly across customers, it would be faster on average but bounded by this upper limit. The final global sort of at most 3*K items adds negligible overhead ( where is unique customers).
- Space: O(N) to store the map keys and values (M orders stored in memory for grouping before processing), plus space for the result list which contains at most 3*N elements. This fits within standard interview constraints given typical input sizes ().
Solution
from collections import defaultdict
from typing import List, Dict, Any
def get_recent_orders(orders: List[Dict[str, Any]]) -> List[List[Any]]:
"""
Returns the most recent three orders for each customer.
Args:
orders: A list of dictionaries representing rows from the Orders table.
Expected keys include 'customer_id' and 'order_date'.
Returns:
A list of lists, where each inner list represents an order record [id, date].
The result is sorted globally by order_date descending as per requirements.
"""
# Step 1: Group orders by customer_id using defaultdict for O(N) insertion
if not orders:
return []
customer_orders = defaultdict(list)
for order in orders:
cid = order['customer_id']
date = order['order_date']
# Store the specific record info needed later
customer_orders[cid].append({'order_date': date})
result = []
# Step 2 & 3: Iterate through each customer's order history
for cid in customer_orders:
orders_list = customer_orders[cid]
# Sort by 'order_date' descending to get most recent first.
sorted_orders = sorted(orders_list, key=lambda x: x['order_date'], reverse=True)
# Step 4 & 5: Take top 3 (or all if fewer than 3 exist naturally via slicing)
recent_three = sorted_orders[:3]
# Format output to match expected return structure [customer_id, order_date]
for o in recent_three:
result.append([cid, o['order_date']])
# Step 6: Global sort required by problem statement "sorted by the `order_date` descending"
result.sort(key=lambda x: x[1], reverse=True)
return result
Edge Cases Handled
- Empty Input: Returns an empty list immediately if input is null or empty.
- Fewer than three orders: Slicing with
[:3]naturally handles customers with 0, 1, or 2 orders without index errors. - Global Sort Order: The final sort ensures that even if customers are processed in arbitrary order (dict insertion), the output is strictly sorted by date descending globally.
- Date Ties: Python’s
sorted()is stable; ties on dates maintain relative input order, which satisfies standard LC acceptance criteria unless specific tie-breaking rules exist.