Bumble Date wants to identify recurring sequences of user actions, such as view_profile -> swipe_right -> send_message, while processing activity events in arrival order. Given a stream of events and multiple action patterns, return the users who complete each pattern at least threshold times.
Events from the same user form that user's action sequence in stream order. Pattern occurrences must be contiguous within that per-user sequence, and overlapping occurrences count separately.
Implement find_activity_patterns(events, patterns, threshold). events is a list of triples [timestamp, user_id, action], where timestamps are nondecreasing. patterns is a list of non-empty action lists. Return a list whose ith element contains the sorted user IDs that matched patterns[i] at least threshold times. User IDs are strings, actions are strings, and matching is case-sensitive.
Process the events as a stream: do not construct a complete action sequence for every user. An event contributes only to its user's automaton state.
def find_activity_patterns(events, patterns, threshold):