Google Interview Questions

https://leetcode.com/discuss/interview-question/364396/

Design a data structure to calculate the moving product of all elements in a sliding window of size k.

class SlidingWindow {

    public SlidingWindow(int k) {
    }
    
    public void add(int val) {
    }

 public int getProduct() {
 }
}

All methods should work in O(1) time.

Example:

SlidingWindow window = new SlidingWindow(3);
window.add(1); // [1]
window.add(2); // [1, 2]
window.getProduct(); // 2
window.add(3); // [1, 2, 3]
window.getProduct(); // 6
window.add(4); // [2, 3, 4]
window.getProduct(); // 24

Follow-up:
What if k is a method argument instead of constructor?

public int getProduct(int k) {
}

You can assume that a product will fit into a single 32-bit integer without overflowing

Follow-up
Solution with additional space complexity of O(N) where N = number of elements added to the SlidingWindow so far

Intuition 1: All elements have to be retained as k can vary dynamically.

Intuition 2: If all elements were > 0, then we could say:

 Product of Last K elements = Product of all elements till N / Product of elements uptil N - K

So, If elements added were [ 1, 4, 7, 2, 5] and K = 2
Then Product of last 2 elements = 2 * 5 = ( 1 * 4 * 7 * 2 * 5 ) / ( 1 * 4 * 7 * 2 * 5)

What happens if 0 is allowed? Product after encountering it becomes 0 and the above formula cannot be used any longer. Allowance for 0 has to be made

Intuition 3: If 0 exists in last k elements, then we can directly return 0.
We need to keep track of the last occurrence of 0. If the index of the last occurrence of 0 is within range N to N - K then return 0

Using the above,
let leftProduct[i] = product of all non-zero elements from 1..i

add(val)

  if(val == 0) {
       lastIndexOfZero = currentIndex
       leftProduct[currentIndex] = leftProduct[currentIndex - 1]
  } else {
      leftProduct[currentIndex] = leftProduct[currentIndex - 1] * val
  }
  currentIndex++

getProduct(k)

     if (lastIndexOfZero >= N - k) {
         return 0
     } else {
          return leftProduct[N-1] / leftProduct[N-K]
     }