Product of the Last K Numbers

Problem Design a data structure over a stream of integers supporting add(num) and getProduct(k) — the product of the last k numbers added. Zeros must be handled correctly.

Input / Output

• add(num): append to the stream. getProduct(k): product of the last k added values.

Constraints

• Up to 4*10^4 operations; getProduct must be O(1) — recomputing the window per query is the naive answer.

Example

• add 3, add 0, add 2, add 5, add 4 → getProduct(2) = 20, getProduct(3) = 40, getProduct(4) = 0 (window includes the 0).

Expected approach

• Prefix products: keep a list where p[i] = product of all elements up to i; getProduct(k) = p[n] / p[n−k]. Zeros break division, so on add(0) reset the prefix list — any window reaching past the reset contains a zero → return 0 (check k ≥ current list length). O(1) per operation, O(n) space. Discuss overflow (use long/BigInteger) and why storing raw elements + recomputation is O(k) per query.