Problem · Hash Table
Recent Event Stream Queries
Learn this problem● Medium
SnowflakeFULLTIMEPHONE SCREEN
See Snowflake hiring insightsSnowflakeFULLTIMEPHONE SCREENProblem statement
Process a finite ordered batch of string operations while retaining only the most recently recorded m events. Each recorded event has a timestamp and key.
Operations have these forms:
record timestamp key: append an event. Record timestamps are nondecreasing. If the retained window now contains more thanmevents, discard its oldest event.count timestamp: return the number of distinct keys among retained events whose event timestamp is strictly less thantimestamp.top: return the most frequent key in the complete retained window. Break frequency ties by lexicographically smaller key. Return the empty string when the window is empty.
A record operation produces no output. Return each query result in operation order. Represent counts as decimal strings.
Function
processRecentEvents(operations: String[], m: int) → String[]Examples
Example 1
operations = ["record 1 a","record 2 b","record 3 a","count 3","top","record 4 c","count 4","top"]m = 3return = ["2","a","2","a"]The first count sees keys a and b before timestamp 3. Recording c evicts the oldest a; the three remaining keys then have equal frequency, so a wins lexicographically.
Example 2
operations = ["top","count 10","record 10 z","count 10","count 11","top"]m = 2return = ["","0","0","1","z"]The initial window is empty. The event at timestamp 10 is excluded from count 10 and included in count 11.
Constraints
1 <= operations.length <= 10^5.1 <= m <= 10^5.- Every operation exactly matches one of the documented forms.
- Record timestamps are integers from
0through10^18and are nondecreasing. - Each key contains from
1through30letters, digits, or underscores.