Problem Breakdown
The problem involves analyzing an activity dataset to determine engagement metrics. Specifically, we need to count the number of distinct users who participated in activities on each specific date.
Inputs: A list (or table) representing activity logs containing at least a unique participant ID (user_id) and a timestamp/date field (date).
Outputs: An ordered list or map grouping dates against their respective counts of unique participants.
Key Requirements:
- Distinct Counting: Multiple activities by the same user on the same date must count as exactly one participation (use
COUNT(DISTINCT ...)logic). - Null Handling: Rows with null or empty dates are typically filtered out in strict business logic unless specified otherwise to group them separately.
- Ordering: Results should be sorted by date for readability and consistency with SQL expectations (
ORDER BY).
Intuition
A brute-force approach iterating through rows while maintaining a list of participants per date would require complexity due to repeated uniqueness checks (e.g., linear search in lists).
The optimal insight is leveraging hash-based data structures. In Python, set objects automatically handle deduplication ( amortized insertion/check) and SQL aggregation functions (GROUP BY, COUNT) are optimized by database engines using similar internal hashing mechanisms. By mapping dates to sets of user IDs, we can aggregate counts in a single pass over the data followed by sorting distinct keys.
Approach
- Initialize Storage: Create a dictionary (or
defaultdict(set)) where keys represent activity dates and values are sets storing uniqueuser_ids for that date. - Iterate Rows: Loop through each record in the input dataset.
- Filter & Group: Extract
dateanduser_id. Skip rows with null/empty dates to adhere to standard business logic (filtering NULLs). Add the user ID to the set corresponding to that date. Sets ensure duplicates are ignored automatically. - Aggregate Counts: After processing all records, iterate through the storage structure. Convert each set’s size into a count for its respective date.
- Format Output: Construct a list of tuples
(date, count). Sort this list by date to match SQL output expectations before returning.
Complexity Analysis
- Time Complexity: , where is the number of activity rows and is the number of distinct dates (). We iterate through each row once for set operations (amortized ), resulting in . Sorting the unique keys takes . Since sorting dominates only when many distinct dates exist, overall complexity remains linear with respect to input size plus a logarithmic factor for output ordering.
- Space Complexity: , where is the number of unique dates and is the total count of user-date pairs stored across all sets (bounded by ). In the worst case where every row has a distinct date/user combination, space approaches .
Solution
from collections import defaultdict
def get_activity_participants(activity_data):
"""
Calculates distinct participants per date from activity logs.
Args:
activity_data: List of dicts with keys 'date' and 'user_id'.
Returns:
List of tuples (date, count) sorted by date.
"""
# Use a defaultdict to map dates -> set of user_ids for automatic deduplication
participants_per_date = defaultdict(set)
# Iterate through each activity record
for row in activity_data:
# Handle potential missing or null keys gracefully based on schema assumptions
date_str = row.get('date')
# Skip rows with NULL/Empty dates as per standard business logic (filtering out NULLs)
if not date_str:
continue
user_id = row['user_id']
# Add user ID to the set for this specific date.
# Sets handle duplicates automatically (same user, same day).
participants_per_date[date_str].add(user_id)
# Convert sets to counts and prepare result list
results = []
# Sort keys by string representation of date or datetime object if applicable
for date in sorted(participants_per_date.keys()):
count = len(participants_per_date[date])
results.append((date, count))
return results
Edge Cases Handled
- Same User Multiple Times: The use of
setensures that if a user appears multiple times on the same date (e.g., checking in twice), they are only counted once. - Empty Input: If
activity_datais empty, the loop skips and returns an empty list, which matches SQL behavior for no rows selected (SELECT ... GROUP BY). - Missing Dates/Nulls: The code explicitly checks
if not date_str:to skip NULL or empty dates. This aligns with standard business logic where incomplete records are excluded from daily metrics unless specifically requested (e.g., “group by null”). If grouping NULLs were required, the condition would be removed and a specific key like'NULL'could be used. - Missing Keys: Using
.get('date')preventsKeyErrorif ‘date’ is missing from a row, treating it as falsy (skipped).