183. Customers Who Never Order
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 57.5%
Problem Breakdown
The problem asks us to find customers who have never placed an order. We are given two tables: Customers and Orders. The Customers table contains customer IDs and names, while the Orders table contains order IDs and corresponding customer IDs. Our task is to return a list of customer names from the Customers table that do not appear in the Orders table.
Inputs:
- Two tables:
Customers: columnscustomer_id(int),name(string)Orders: columnsorder_id(int),customer_id(int)
Outputs:
- A list of customer names from the
Customerstable that have no corresponding entries in theOrderstable.
Implicit Constraints or Tricky Edge Cases:
- The
Customerstable may be empty. - The
Orderstable may be empty. - There could be duplicate customer IDs in either table, but since they are primary keys, duplicates should not exist.
- Customer names can be any string, including special characters.
Intuition
A brute-force approach would involve iterating over each customer and checking if their ID exists in the Orders table. This would result in a time complexity of O(n * m), where n is the number of customers and m is the number of orders. This is inefficient for large datasets.
The key insight is to use a set operation to find the difference between the set of all customer IDs and the set of customer IDs that have placed orders. This can be done efficiently using SQL’s NOT IN or LEFT JOIN operations, which reduces the time complexity to O(n + m).
Approach
- Identify the Set Difference: We need to find customers whose IDs are not present in the
Orderstable. - Use SQL Set Operations:
- We can use a subquery with
NOT INto filter out customers who have placed orders. - Alternatively, we can use a
LEFT JOINand check for null values in the joined result.
- We can use a subquery with
Algorithm Steps:
- Select all customer names from the
Customerstable. - Use a subquery to exclude those whose IDs are present in the
Orderstable usingNOT IN.
Complexity Analysis
- Time Complexity: O(n + m), where n is the number of customers and m is the number of orders. This is because we need to scan both tables once.
- Space Complexity: O(k), where k is the number of customers who never ordered, as this is the size of the result set.
Solution
# SQL query to find customers who never order
SELECT name FROM Customers WHERE customer_id NOT IN (SELECT customer_id FROM Orders);
Edge Cases Handled
- Empty
CustomersTable: The query will return an empty list since there are no customers. - Empty
OrdersTable: All customers will be returned since none have placed orders. - No Matching Customer IDs: If all customer IDs in
Customersare unique and do not exist inOrders, all customer names will be returned.