Product of the Last K Numbers

Product of the Last K Numbers

What is this problem about?

The Product of the Last K Numbers problem asks you to design a data structure that supports adding numbers to a stream and querying the product of the last k numbers added. This design problem uses prefix products with a reset-on-zero technique. The data stream, array, math, design, and prefix sum interview pattern is the core.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it tests prefix product with the edge case of zeros — which would make all subsequent products zero until the zero leaves the window. The reset trick elegantly handles this.

Algorithmic pattern used

Prefix products with zero-reset. Maintain a prefix product list [1]. For add(num): if num == 0, reset prefix = [1] (all products involving this zero are 0 until zero leaves window). Else: append prefix[-1] * num. For getProduct(k): if k >= len(prefix), return 0 (a zero is within the last k elements). Else: return prefix[-1] / prefix[-k-1].

Example explanation

Stream: [3,2,0,4,5,3].

• add(3): prefix=[1,3].
• add(2): prefix=[1,3,6].
• add(0): reset prefix=[1]. (Products involving 0 are 0.)
• add(4): prefix=[1,4].
• add(5): prefix=[1,4,20].
• getProduct(2): k=2. prefix[-1]/prefix[-3]=20/1=20 (product of [5,4] wait reversed...20/prefix[-3]? len=3, k=2: 20/prefix[0]=20/1=20 for last 2 elements [4,5]. ✓

Common mistakes candidates make

• Not handling zeros (storing zero in prefix makes all future queries give 0 unnecessarily).
• Off-by-one: prefix has a leading 1, so prefix[-k-1] for last k elements.
• Integer overflow (use float or ensure numbers are small).
• Not resetting after zero (the zero resets the window history).

Interview preparation tip

Product of the Last K Numbers combines prefix products with a clever zero handling trick. The zero-reset approach is elegant: when zero is added, start fresh because any window containing that zero has product 0. The out-of-range check (k >= len(prefix)) handles this implicitly. Practice similar "sliding window aggregate" design problems: "moving maximum," "moving average," "product in sliding window."