FastPrep
Problem · Hash Table

Metric Counter with a Fake Clock

Learn this problem
● MediumSnap Inc. logoSnap Inc.FULLTIMEONSITE INTERVIEW

Problem statement

Simulate a metric counter driven by a deterministic fake clock. The clock starts at time 0. A metric’s count is the number of its recorded events in the trailing windowSeconds seconds.

Process the arrays from left to right. At index i, the operation is:

  • increment: record one event for metricNames[i] at the current fake time.
  • count: append the active count for metricNames[i] to the result.
  • advance: advance the fake clock by timeDeltas[i] seconds. Its metric name is empty.

At time now, an event at time eventTime is active exactly when eventTime > now - windowSeconds. Therefore, an event expires when its age becomes exactly windowSeconds. Operations at the same fake time follow input order. Remove metric state after all of that metric’s events expire. Return the results of the count operations in their original order.

Function

metricCounts(operations: String[], metricNames: String[], timeDeltas: int[], windowSeconds: int) → int[]

Examples

Example 1

operations = ["increment","increment","count","advance","count","increment","count","advance","count","count"]metricNames = ["click","click","click","","click","view","view","","view","click"]timeDeltas = [0,0,0,5,0,0,0,1,0,0]windowSeconds = 5return = [2,0,1,1,0]

The two click events are active at time 0. At time 5, both have reached the expiration boundary. The view event recorded at time 5 is still active at time 6.

Example 2

operations = ["increment","advance","increment","increment","count","count","advance","count","count"]metricNames = ["a","","a","b","a","b","","a","b"]timeDeltas = [0,2,0,0,0,0,2,0,0]windowSeconds = 3return = [2,1,1,1]

At time 2, metric a has events from times 0 and 2. At time 4, the event from time 0 is expired, while both events recorded at time 2 remain active.

Constraints

  • 1 <= operations.length <= 100000.
  • The three operation arrays have equal length.
  • Each operation is increment, count, or advance.
  • Metric names used by increment and count are nonempty printable ASCII strings of length at most 50.
  • For increment and count, timeDeltas[i] == 0.
  • For advance, metricNames[i] is empty and 0 <= timeDeltas[i] <= 10^9.
  • 1 <= windowSeconds <= 10^9.
  • The fake clock’s total time fits in a signed 64-bit integer.

More Snap Inc. problems

drafts saved locally
public int[] metricCounts(String[] operations, String[] metricNames, int[] timeDeltas, int windowSeconds) {
    // Write your code here.
}
operations["increment","increment","count","advance","count","increment","count","advance","count","count"]
metricNames["click","click","click","","click","view","view","","view","click"]
timeDeltas[0,0,0,5,0,0,0,1,0,0]
windowSeconds5
expected[2,0,1,1,0]
checking account