Product of the Last K Numbers
Asked at TikTok
Problem
Product of the Last K Numbers asks you to design a stream that supports add(num) and getProduct(k), which returns the product of the last k numbers. Prefix products make queries O(1) — as long as you handle zeros, which would otherwise break division.
Asked At
| Company | Difficulty | |
|---|---|---|
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Multiplying the last k numbers on each query is O(k) per call.
Key insight: like prefix sums, keep prefix products. The product of the last k numbers is prefix[-1] / prefix[-1 - k].
Zeros break division. Handle them by resetting: when 0 is added, clear the prefix list back to [1]. Any query whose window reaches back past that zero must return 0.
So after a reset, if k is at least the number of values added since the last zero (k >= len(prefix)), the window contains the zero — return 0.
Walkthrough: add 3, 0, 2, 5, 4 -> prefix after the zero is [1, 2, 10, 40]. getProduct(2) = 40 / 2 = 20. getProduct(4) reaches the zero -> 0.
Optimal Approach
State: prefix = [1].
add(num): if num == 0, reset prefix = [1]; else append prefix[-1] * num.getProduct(k): if k >= len(prefix), return 0; else return prefix[-1] // prefix[-1 - k].
The problem guarantees that products of the current list fit in a 32-bit integer, so the prefix values never overflow.
Time: O(1) per operation. Space: O(n).
What Trips People Up in Real Interviews
Dividing by a zero prefix. Resetting on zero avoids it and makes the zero check a simple length comparison.
Storing the raw numbers and multiplying per query — O(k) each time.
Off-by-one in the zero check: the window of the last k numbers includes the zero exactly when k >= len(prefix).
Forgetting the overflow discussion. Here the problem bounds the product, but mention that without that guarantee you would need big integers or logs.
Solution Code
class ProductOfNumbers:
def __init__(self):
self.prefix = [1]
def add(self, num):
if num == 0:
self.prefix = [1]
else:
self.prefix.append(self.prefix[-1] * num)
def getProduct(self, k):
if k >= len(self.prefix):
return 0
return self.prefix[-1] // self.prefix[-1 - k]Frequently Asked Questions
What is the Product of the Last K Numbers problem?
Product of the Last K Numbers asks you to design a stream that supports `add(num)` and `getProduct(k)`, which returns the product of the last `k` numbers. Prefix products make queries `O(1)` — as long as you handle zeros, which would otherwise break division.
How do you solve Product of the Last K Numbers?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Product of the Last K Numbers?
Product of the Last K Numbers is asked at TikTok. It is a medium difficulty problem.
What are common mistakes on Product of the Last K Numbers?
- Dividing by a zero prefix. Resetting on zero avoids it and makes the zero check a simple length comparison.
- Storing the raw numbers and multiplying per query — `O(k)` each time.
- Off-by-one in the zero check: the window of the last `k` numbers includes the zero exactly when `k >= len(prefix)`.
- Forgetting the overflow discussion. Here the problem bounds the product, but mention that without that guarantee you would need big integers or logs.