Catch Cheaters: Detect Anomalous Score Submissions in an Online Game
Interview Experience
Problem
You are given a list of score submissions. Each submission has a player_id, score, and timestamp. A submission is suspicious if the player's score increased by more than max_delta points compared to their previous submission.
Return a list of suspicious (player_id, score, timestamp) tuples, sorted by timestamp ascending.
python
def find_suspicious(
submissions: list[dict],
max_delta: int
) -> list[tuple]:
# submissions: [{"player_id": str, "score": int, "timestamp": int}]
pass
Example:
submissions = [
{"player_id": "p1", "score": 100, "timestamp": 1},
{"player_id": "p1", "score": 102, "timestamp": 2},
{"player_id": "p1", "score": 200, "timestamp": 3},
{"player_id": "p2", "score": 50, "timestamp": 4}
]
max_delta = 10
p1 goes 100->102 (delta=2, ok) then 102->200 (delta=98, suspicious).
**Output**: [("p1", 200, 3)]
Follow-ups
- How would you handle submissions arriving out of order? How does this affect your per-player last-seen-score tracking?
- What if a player can submit from multiple devices simultaneously? How does your model change?
- Add a second rule: flag any player whose score exceeds the 99th percentile of all scores in a rolling 1-hour window.
- How would you design this as a streaming pipeline (Kafka + Flink) at 500K submissions/second?
Full Details
Problem
You are given a list of score submissions. Each submission has a player_id, score, and timestamp. A submission is suspicious if the player's score increased by more than max_delta points compared to their previous submission.
Return a list of suspicious (player_id, score, timestamp) tuples, sorted by timestamp ascending.
python
def find_suspicious(
submissions: list[dict],
max_delta: int
) -> list[tuple]:
# submissions: [{"player_id": str, "score": int, "timestamp": int}]
pass
Example:
submissions = [
{"player_id": "p1", "score": 100, "timestamp": 1},
{"player_id": "p1", "score": 102, "timestamp": 2},
{"player_id": "p1", "score": 200, "timestamp": 3},
{"player_id": "p2", "score": 50, "timestamp": 4}
]
max_delta = 10
p1 goes 100->102 (delta=2, ok) then 102->200 (delta=98, suspicious).
**Output**: [("p1", 200, 3)]
Follow-ups
- How would you handle submissions arriving out of order? How does this affect your per-player last-seen-score tracking?
- What if a player can submit from multiple devices simultaneously? How does your model change?
- Add a second rule: flag any player whose score exceeds the 99th percentile of all scores in a rolling 1-hour window.
- How would you design this as a streaming pipeline (Kafka + Flink) at 500K submissions/second?
About This Question
This is a candidate experience report from a karat interview.
It covers the following topics: Coding .