Count Users Per Funnel Step

HardPython

Problem

Faire tracks user activity as an event log while merchants move through an ordered product funnel, such as view_store, add_product, and request_order. Given the chronological events and the funnel steps, return how many unique users reached each step in sequence.

A user advances only when their event matches their next expected step. Duplicate events for a completed step are ignored, and an event for a later step cannot skip an earlier step. Events are already ordered chronologically.

Formal Specification

Implement count_funnel_users(events, steps).

events is a list of dictionaries, each with a string user_id and a string step.
steps is a list of distinct strings defining the funnel order.
Return a list of integers where position i is the number of unique users who reached steps[i] after completing every previous step.
If steps is empty, return an empty list.

Constraints

0 <= len(events) <= 10^5
0 <= len(steps) <= 10^3
Each event contains a non-empty string user_id and step
Event order is chronological
Every step name is unique

Function Signature

def count_funnel_users(events, steps):

Formal Specification

Implement count_funnel_users(events, steps).

events is a list of dictionaries, each with a string user_id and a string step.
steps is a list of distinct strings defining the funnel order.
Return a list of integers where position i is the number of unique users who reached steps[i] after completing every previous step.
If steps is empty, return an empty list.