1056. Product of the Tail

Medium3.5 points estimatedDesign Data Stream Prefix Sum Array 3 hints

A growth tracker receives a stream of daily multipliers, such as 1.0x or 3x, stored as non-negative integers. Analysts repeatedly ask what the compounded effect of the most recent few days was, so you must answer these questions fast no matter how long the stream has become.

Implement ProductTail. add(num) appends the multiplier num to the stream. getProduct(k) returns the product of the last k multipliers added so far. A multiplier of 0 wipes out every window containing it. Both operations must run in O(1) time. It is guaranteed that the product of any block of consecutive stream values fits in a signed 32-bit integer.

Example 1

Input:: operations = ["ProductTail","add","add","add","getProduct","getProduct","add","getProduct"]arguments = [[],[3],[2],[5],[2],[3],[4],[2]]
Output:: [null,null,null,null,10,30,null,20]
Explanation:: After 3, 2, 5 the last two multiply to 10 and the last three to 30; once 4 arrives the last two are 5 and 4, giving 20.

Example 2

Input:: operations = ["ProductTail","add","add","add","getProduct","getProduct","getProduct"]arguments = [[],[6],[0],[7],[1],[2],[3]]
Output:: [null,null,null,null,7,0,0]
Explanation:: Any window that reaches back to the 0 has product 0, while the window holding only the 7 gives 7.

Example 3

Input:: operations = ["ProductTail","add","getProduct","add","add","getProduct"]arguments = [[],[1],[1],[1],[9],[3]]
Output:: [null,null,1,null,null,9]
Explanation:: Ones leave the product unchanged, so three values 1, 1, 9 multiply to 9.

Constraints

0 ≤ num ≤ 100

1 ≤ k ≤ number of values added so far

At most 4 * 10⁴ calls in total; every contiguous product fits in a signed 32-bit integer.

How this problem is judged

Answers: Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input: Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.
Time per case: Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms

Expected complexity

Time: O(1) per operation
Space: O(n)

What the author was aiming for. Your own solution is not measured against it.

Were you asked this in an interview? Say where, anonymously.

CodeStarter code

Loading the editor…

operations =arguments =

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.