Design a data structure that supports adding numbers to a stream and querying the product of the last k numbers.
Problem
Design a data structure that maintains a stream of integers and supports two operations:
add(num): appendnumto the streamgetProduct(k): return the product of the lastknumbers in the stream
You can assume queries are valid for the current stream length. The stream may contain zeros, so your solution should handle them efficiently.
Goal
Implement the structure so that both operations are efficient, especially when there are many queries.
Input Format
You are given a sequence of operations:
add(num)wherenumis an integergetProduct(k)wherekis a positive integer
Operations are performed online in order.
Output Format
For each getProduct(k) operation, return the product of the last k numbers currently in the stream.
Constraints
- Operations are processed sequentially
- Values may include zero
- A query
getProduct(k)is made only when at leastknumbers have been added since the last reset behavior implied by zeros - Aim for near O(1) amortized time per operation
Example 1
Input
add(3) add(0) add(2) add(5) add(4) getProduct(2) getProduct(3) getProduct(4)
Output
20 40 0
Explanation
The last 2 numbers are 5 and 4, so the product is 20. The last 3 numbers are 2, 5, and 4, so the product is 40. The last 4 numbers include 0, so the product is 0.
Example 2
Input
add(1) add(2) add(3) getProduct(2)
Output
6
Explanation
The last 2 numbers are 2 and 3, and their product is 6.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.