550. Game Play Analysis IV
Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 45.7%
Problem Breakdown
The problem asks us to analyze player activity logs from an Activity table (typically containing columns like player_id, device_id, and event_date). The goal is usually to aggregate data per player, such as counting total games played or identifying players based on specific date criteria.
Inputs: A dataset of game activities where each row represents a single play session for a user at a specific time/device.
Outputs: Aggregated statistics grouped by player_id (e.g., count of sessions).
Constraints & Edge Cases:
- Empty Input: The list might be empty; the solution must return an appropriate structure without crashing.
- Duplicates: Multiple rows for the same player on different dates are valid and should all be counted/processed. Rows with identical
player_idandevent_date(same session) need to be handled correctly based on whether we count unique sessions or total events. - Overflow: Counts can grow large, but Python handles arbitrary integers automatically; no special overflow handling needed compared to fixed-width languages like C++.
- Nulls: Ensure logic doesn’t break if
player_idis null (though schema usually implies non-null).
Intuition
A brute-force approach would be to iterate through every row and compare it against every other row or check conditions for each player individually. This leads to complexity, which will time out on large datasets typical of production systems.
The key insight is that this problem requires aggregation. We don’t need complex nested loops; we just need to group rows by player_id and apply a count or filter operation per group. In SQL terms, this maps directly to GROUP BY. In Python/algorithmic thinking, the equivalent data structure for grouping is a Hash Map (Dictionary). By iterating through the input list once (), we can build up these groups efficiently.
Approach
- Data Structure: Use a standard Python dictionary where keys are unique
player_ids and values store their activity counts or metadata. This provides average time complexity for updates/lookups. - Iteration: Loop through the input list of activities exactly once.
- Aggregation Logic: For each record, increment a counter associated with that
player_id. If we need to filter (e.g., only players who played > X times), check this condition after aggregation or during iteration if using generators/streams. - Result Construction: Convert the dictionary into the required output format (usually a list of dictionaries or tuples).
Complexity Analysis
- Time Complexity: , where is the number of activity records. We traverse the input data once to build our map and then iterate over unique players for result construction. Dictionary operations are amortized .
- Space Complexity: , where is the number of unique players (keys in our dictionary). In the worst case (all records from different players), this approaches .
Solution
from collections import Counter
from typing import List, Dict, Any
def analyze_game_play(activities: List[Dict[str, Any]]) -> List[Dict[str, int]]:
"""
Aggregates game play data by player_id.
Assumes input is a list of dicts with 'player_id' and other metadata.
Returns a list of {player_id: count} dictionaries or similar structure.
"""
# Handle empty input gracefully to avoid unnecessary processing overhead
if not activities:
return []
# Use Counter for efficient O(1) updates per record (Hash Map logic)
player_counts = Counter()
# Single pass through the data - O(N) time complexity
for activity in activities:
pid = activity.get('player_id')
# Guard against null/missing IDs which could break grouping logic
if pid is not None:
player_counts[pid] += 1
# Convert to list of dicts, filtering out players with zero count
# (though Counter usually won't have them unless we explicitly added empty keys)
result = [{"player_id": k, "games_played": v} for k, v in player_counts.items()]
return sorted(result, key=lambda x: x['player_id'])
# Example usage matching typical interview input format
if __name__ == "__main__":
data = [
{"player_id": 1, "device_id": "A", "event_date": "2023-01-01"},
{"player_id": 1, "device_id": "B", "event_date": "2023-01-02"},
{"player_id": 2, "device_id": "C", "event_date": "2023-01-01"}
]
# Output: [{'player_id': 1, 'games_played': 2}, {'player_id': 2, 'games_played': 1}]
print(analyze_game_play(data))
Edge Cases Handled
- Empty Input: The function checks
if not activitiesand returns an empty list immediately. - Null Player IDs: Logic includes a check (
pid is not None) to prevent using null as a dictionary key, which would group all invalid records together incorrectly or crash depending on implementation details. - Single Record Input: The loop handles correctly without special branching logic.
- Unordered Output: Results are sorted by
player_idat the end to ensure deterministic output for testing/verification, as dictionary iteration order is not guaranteed in older Python versions (though stable in 3.7+, sorting ensures consistency).