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]
     }

LeetCode 1246 - Palindrome Removal

https://algorithm-notes-allinone.blogspot.com/2019/11/leetcode-1246-palindrome-removal.html

Given an integer array arr, in one move you can select a palindromic subarray arr[i], arr[i+1], ..., arr[j] where i <= j, and remove that subarray from the given array. Note that after removing a subarray, the elements on the left and on the right of that subarray move to fill the gap left by the removal.

Return the minimum number of moves needed to remove all numbers from the array.

Example 1:

Input: arr = [1,2]
Output: 2

Example 2:

Input: arr = [1,3,4,1,5]
Output: 3
Explanation: Remove [4] then remove [1,3,1] then remove [5].

Constraints:

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 20

This question can be solved by dp. So the key is find the key logic, or state transfer equation.

Let use dp[i][j] represents the minimum number of moves needed to remove all the numbers from the array from i to j inclusive. Then,

(1) dp[i][j] = 1 + dp[i+1][j] //since it can ways be done by removing one by one;

(2) if(dp[i] == dp[i+1]), dp[i][j] = min(dp[i][j], 1 + dp[i+2][j]);

(3) if(dp[i] == dp[j]),  dp[i][j] = min(dp[i][j], dp[i+1][j-1])//both ends can be removed along with previous palindromes;

(4) if(dp[i] == dp[k]) dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j])  for k = i + 2, to j - 1;

Pay attention to the boundary conditions. The above (2) and (3) actually are the left and right boundaries of case (4).

Also pay attention to the for loops. The time complexity is O(N^3), and the dp is in a bottom-up building fashion. So we need to calculate each subarr with a smaller size or len. Then gradually build up the final dp[0][len-1].

1.     int minimumMoves(vector<int>& arr) {
2.         int n = arr.size();
3.         vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
4.         for(int len = 1; len <= n; ++len) {
5.             for(int i=0, j = len-1; j<n; ++i, ++j) {
6.                 if(len == 1) {dp[i][j] = 1; continue;}
7.                 dp[i][j] = 1 + dp[i+1][j];//can always remove the first one;
8.                 if(arr[i] == arr[i+1]) dp[i][j] = min(dp[i][j], 1 + dp[i+2][j]);
9.                 if(arr[i] == arr[j] && j>i+1) dp[i][j] = min(dp[i][j], dp[i+1][j-1]);
10.                 for(int k=i+2; k<j; ++k) {
11.                     if(arr[i] == arr[k]) dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k+1][j]);
12.                 }
13.             }
14.         }
15.         return dp[0][n-1];
16.     }

https://leetcode.jp/leetcode-1246-palindrome-removal-%E8%A7%A3%E9%A2%98%E6%80%9D%E8%B7%AF%E5%88%86%E6%9E%90/

这是一道动态规划的题目，难度级别为Hard。我在之前的文章说过，所有动态规划（DP）题目都可以转化为递归加记忆数组来实现，本人更青睐于递归，因此本题仍然使用递归来解题。

我们先定义一个递归方法help，help(from, to)的返回值代表，删除区间[from, to]内所有数字所需要的次数。我们从from+1开始循环到to，用每一个数i与from作比较，如果两数(当前数i和from)相同，分两种情况考虑，若当前数i与from相邻，说明这两个数可以组成回文，因此，可以使用一次操作删掉这两个数字，即：

公式1：help(from, to) = 1 + help(i+1, to)。

若当前数i与from不相邻，那么当前数与from是可以融合到区间[from+1, i-1]之内，也就是说， help(from, i) == help(from+1, to-1)。这里解释一下原因，举个例子，比如区间[from, i]为：

Code

1	[1,2,3,1] // 等于[2,3]

将1，2，3，1全部删除需要2步：

1. 删除2，变为1，3，1
2. 此时1，3，1为回文，可一次删除

也就是说，除去区间首尾相同的元素之外，中间部分经过一系列删除之后，一定能剩下1个单独的数字或者一个单独的回文，不论是哪种情况，中间最后剩余的部分都能与区间首尾共同组成一个回文，因此首尾部分可以与中间剩余部分一次性删除掉。结论： 如果两数(当前数i和from)相同，并且当前数i与from不相邻时，

公式2： help(from, to) = help(from+1, i-1) + help(i+1, to)

当循环完区间内所有元素（从from+1循环到to）之后，我们还有另一种选择，即将首元素单独删除，剩下的部分交给递归子问题去解决。即：

公式3： help(from, to) = 1 + help(from+1, to)

有了上述3个公式，本题即可完美解决。另外别忘记添加记忆数组，以防止重复计算（相当于动态规划使用到的dp数组）。我们定义一个二维数组memo[][]，memo[i][j]代表区间[i，j]。

int[][] memo; // 记忆数组

public int minimumMoves(int[] arr) {

    // 初始化记忆数组

    memo = new int[arr.length][arr.length];

    return help(arr, 0, arr.length - 1);

}

 

int help(int[] arr, int from, int to) {

    // 区间范围不合理，返回0

    if (to < from) return 0;

    // 区间长度为1，返回1

    if (to == from) return 1;

    // 如果该区间曾经计算过，返回之前的计算结果

    if (memo[from][to] != 0) return memo[from][to];

    // 返回值

    int res = Integer.MAX_VALUE;

    // 区间首元素的值

    int fromValue=arr[from];

    // 从区间第二个元素循环到区间尾部

    for (int i = from + 1; i <= to; i++) {

        // 如果当前元素等于区间首元素

        if (fromValue == arr[i]) {

            int result = 0;

            if(i-from==1){ // 当前元素与首元素相邻

                result = 1 + help(arr, i + 1, to);

            }else{ // 当前元素与首元素不相邻

                result = help(arr, from + 1, i - 1)

                       + help(arr, i + 1, to);

            }

            // 将最小值更新到返回结果

            res = Math.min(res, result);

        }

    }

    // 我们还可以选择将首字母单独删去后的情况

    res = Math.min(res, 1 + help(arr, from + 1, to));

    // 将本区间的计算结果保存至记忆数组，防止今后重复计算

    memo[from][to] = res;

    return res;

}

https://nagato1208.github.io/2019/11/02/leetcode-1246-Palindrome-Removal/

性质题, 对于每一个数字都有两种选择: 1) 选一个和它一样的数字消去, 如果这两个数字的位置之间有其他数字, 当前消去的过程不增加remove的次数 2) 直接消去它自己, remove的次数+1.
区间DP或者DFS+记忆

DP pattern:

1	dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j]), where arr[k]==arr[i]

def minimumMoves(self, arr): """ :type arr: List[int] :rtype: int """ memo = {} d = collections.defaultdict(list) for i,c in enumerate(arr): d[c].append(i) def dp(i,j): if i == j: return 1 if i > j: return 0 if (i,j) not in memo: res = 1 + dp(i+1, j) for k in d[arr[i]]: if k == i + 1: res = min(res, 1 + dp(k+1, j)) elif i + 1 < k <= j: res = min(res, dp(i+1, k-1) + dp(k+1, j)) memo[i,j] = res return memo[i,j] return dp(0, len(arr)-1)

def minimumMoves(self, arr): """ :type arr: List[int] :rtype: int """ n = len(arr) dp = [[100] * n for _ in range(n)] for i in range(n-1, -1, -1): dp[i][i] = 1 for j in range(i+1, n): if j == n: break dp[i][j] = 1 + (dp[i+1][j] if i+1<n else 0) for k in range(i+1, j+1): if arr[i] == arr[k]: if k == i + 1: dp[i][j] = min(dp[i][j], 1 + (dp[k+1][j] if k+1<=j else 0)) else: dp[i][j] = min(dp[i][j], dp[i+1][k-1] + (dp[k+1][j] if k+1<=j else 0)) return dp[0][n-1]

https://blog.csdn.net/yaoct/article/details/102881840
https://www.acwing.com/solution/LeetCode/content/5795/

(动态规划，区间模型) $O(n^3)$

1. 设 $f(i,j)$ 表示删除区间 $[i,j]$ 所需要的最少操作次数。
2. 初始时，$f(i,i)=1$，$f(i,i-1)=0$。其余为正无穷。
3. 转移时，可以将 $arr[i]$ 单独考虑删除，则转移 $f(i,j)=min(f(i,j),1+f(i+1,j))$。如果 $arr[i]==arr[i+1]$，则这两个可以一起删除，转移 $f(i,j)=min(f(i,j),1+f(i+2,j))$。如果 $arr[i]==arr[k],(i+2<=k<=j)$，则 $arr[i]$ 和 $arr[k]$ 可以随着区间 $[i+1,k-1]$ 一起删除，转移 $f(i,j)=min(f(i,j),f(i+1,k-1)+f(k+1,j))$。
4. 最终答案为 $f(0,n-1)$。

时间复杂度

• 状态数为 $O(n^2)$ 个，转移需要 $O(n)$ 的时间，故时间复杂度为 $O(n^3)$。

空间复杂度

• 需要额外 $O(n^2)$ 的空间存储状态。

    int minimumMoves(vector<int>& arr) {
        int n = arr.size();
        vector<vector<int>> f(n + 1, vector<int>(n + 1));

        for (int i = 0; i <= n; i++)
            f[i][i] = 1;

        for (int i = 1; i <= n; i++)
            f[i][i - 1] = 0;

        for (int len = 2; len <= n; len++)
            for (int i = 0; i < n - len + 1; i++) {
                int j = i + len - 1;
                f[i][j] = 1 + f[i + 1][j];
                if (arr[i] == arr[i + 1])
                    f[i][j] = min(f[i][j], 1 + f[i + 2][j]);

                for (int k = i + 2; k <= j; k++)
                    if (arr[i] == arr[k])
                        f[i][j] = min(f[i][j], f[i + 1][k - 1] + f[k + 1][j]);
            }

        return f[0][n - 1];
    }