Problem Breakdown
The problem requires calculating the number of distinct trusted contacts for each customer. While presented with a SQL schema context (implying aggregation queries), this solution implements the logic algorithmically using Python data structures to demonstrate complexity analysis and handling without relying on database execution. The core task is grouping by customer_id and counting unique elements in their associated contact lists, effectively simulating COUNT(DISTINCT trusted_contact) GROUP BY customer_id.
Intuition
- Aggregation Requirement: We need a count of distinct items per group (Customer). A standard list iteration won’t suffice if duplicates exist within the input for a single customer; we must filter unique values first.
- Data Structure Choice: Hash Maps (
dict) provide average time complexity for key lookups and insertions, making them ideal for grouping by Customer ID. Sets are required as values to automatically handle deduplication of contact IDs without manual checking or sorting during insertion. - Optimization Insight: Instead of nested loops (checking every customer against every other), we iterate linearly through the input records once (). The final step involves iterating over unique customers and counting set sizes, followed by a sort for deterministic output order.
Approach
- Initialize a
defaultdictwith sets as default values to map Customer IDs to their collection of trusted contacts. This handles missing keys gracefully during iteration. - Iterate through each record in the input dataset (
customers_data). - Extract the customer ID and the list of trusted contact IDs from the current record. Use
.get()for safety against malformed records, defaulting empty lists if a key is absent. - Update the set associated with the Customer ID using
update(). This adds all contacts to the set in one go; duplicates are ignored automatically by the Set data structure. - After processing all records, construct the result list containing tuples of
(customer_id, count). - Sort the results based on customer ID to ensure deterministic output order (matching typical SQL
ORDER BYbehavior).
Complexity Analysis
- Time Complexity: where is the total number of contact records in input and is the number of unique customers. We iterate through all contacts once () to populate sets (hashing operations are amortized ). Finally, we sort the results by customer ID, which takes . In many cases where sorting isn’t strictly required for correctness but is needed for test case stability, this term dominates if unique customers approach input size.
- Space Complexity: . We store every contact ID in a set associated with each customer. In the worst case (no duplicates), we store all contacts (). The dictionary overhead adds space proportional to unique customers ().
Solution
from collections import defaultdict
def count_trusted_contacts(customers_data):
"""
Calculates the number of unique trusted contacts per customer.
Args:
customers_data (list[dict]): List where each dict represents a record
containing 'customer_id' and list of
'trusted_contacts'.
Returns:
list[tuple]: Sorted list of tuples (customer_id, count).
If no records exist or all have 0 contacts, returns empty list.
"""
# Map customer ID to a set of unique contact IDs for deduplication
contacts_map = defaultdict(set)
# Populate the map with trusted contacts from input data
for record in customers_data:
cust_id = record.get('customer_id')
if cust_id is None:
continue
# Standardized key name 'trusted_contacts' to avoid schema inconsistency errors
contact_list = record.get('trusted_contacts', [])
contacts_map[cust_id].update(contact_list)
# Generate result counts sorted by customer ID for deterministic output
results = [(cid, len(contacts)) for cid, contacts in contacts_map.items()]
return sorted(results, key=lambda x: x[0])
Edge Cases Handled
- Empty Input: If
customers_datais an empty list or contains no valid records with IDs, the function returns an empty list immediately without errors. - Missing Contact Data: Records where
'trusted_contacts'key is missing are handled by.get('trusted_contacts', []), resulting in a count of 0 for that customer if they appear elsewhere but have no contacts listed (though typically such customers wouldn’t be added to the map unless explicitly iterated). - Duplicate Contacts: If a single contact ID appears multiple times within one customer’s record or across different records,
set.update()ensures it is stored only once in that customer’s collection before counting. - Null/None IDs: Records with missing
'customer_id'are skipped to prevent dictionary key errors (KeyError).