Google面经

gg onsite面经

您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求加米啊，谢谢大家🙏

wozm 发表于 2019-9-20 16:09
用一个arrayList来装prefix product，注意每次遇到0就跳过。 用另一个arrayList来装0的个数。查的时候先查 ...

1. public class LastKElementsProduction {
   
2.     List<Integer> preProduct = new ArrayList<>();
   
3.         List<Integer> num0 = new ArrayList<>();
   
4. 
   
5.     public void add(int i){
   
6.         if(i == 0) {
   
7.                         preProduct.add(preProduct.size() == 0 ? 1 : preProduct.get(preProduct.size() - 1));
   
8.                         num0.add(num0.size() == 0 ? 1 : num0.get(num0.size() - 1) + 1);
   
9.                 } else {
   
10.                         preProduct.add(preProduct.size() == 0 ? i : i * preProduct.get(preProduct.size() - 1));
    
11.                         num0.add(num0.size() == 0 ? 0 : num0.get(num0.size() - 1) + 1);
    
12.                 }
    
13.     }
    
14. 
    
15.     public int get(int k){
    
16.         int size = preProduct.size();
    
17.                 int start = Math.max(size - k, 0);
    
18.                 if(num0.get(size - 1) - num0.get(start) == 0) {
    
19.                         return preProduct.get(size - 1) / preProduct.get(start);
    
20.                 } else {
    
21.                         return 0;
    
22.                 }
    
23.     }
    
24. 
    
25.     public static void main(String[] args){
    
26.         LastKElementsProduction test = new LastKElementsProduction();
    
27.         test.add(3);
    
28.         test.add(-5);
    
29.         test.add(6);
    
30.         test.add(9);
    
31.         test.add(3);
    
32.         System.out.println(test.get(6));
    
33.     }
    
34. }

复制代码

用一个arrayList来装prefix product，注意每次遇到0就跳过。 用另一个arrayList来装0的个数。查的时候先查查0的个数，右端点减左端点>0就返回0，否则就返回prefix product右端点除以左端点。

碰到简单题，现场跟面试官跑了一边，当场觉得没问题，然后开始聊天。回来自己想想好像有bug，跑不过corner case，不知道面试官回头再去看一遍。:(

楼主请问下， 这个k可变是不是不能用sliding window的方法降低复杂度了？

这个solution可以吗，有没有更好的？

1. public class LastKElementsProduction {
   
2.     List<Integer> list = new ArrayList<>();
   
3.     int all = 1;
   
4. 
   
5.     public void add(int i){
   
6.         list.add(i);
   
7.         all *= i;
   
8.     }
   
9. 
   
10.     public int get(int k){
    
11.         int total = 1;
    
12.         int n = list.size();
    
13.         if(n < k) return -1;
    
14.         if(k >= n/2){
    
15.             total = all;
    
16.             for(int i = 0; i < (n-k); i++){
    
17.                 total /= list.get(i);
    
18.             }
    
19.         }else{
    
20.             for(int i = 0, j = n - 1; i < k ; i++, j--){
    
21.                 total *= list.get(j);
    
22.             }
    
23.         }
    
24.         return total;
    
25.     }
    
26. 
    
27.     public static void main(String[] args){
    
28.         LastKElementsProduction test = new LastKElementsProduction();
    
29.         test.add(3);
    
30.         test.add(-5);
    
31.         test.add(6);
    
32.         test.add(9);
    
33.         test.add(3);
    
34.         System.out.println(test.get(6));
    
35.     }
    
36. }

复制代码

想到了个更好的方法，思路来自利口 rangeSumQuery

1. public class LastKElementsProduction {
   
2.     Map<Integer, Integer> map = new HashMap<>();
   
3.     int all = 1;
   
4. 
   
5.     public void add(int i){
   
6.         all *= i;
   
7.         map.put(map.size()+1, all);
   
8.     }
   
9. 
   
10.     public int get(int k){
    
11.         int m = map.size();
    
12.         if(m == k) return all;
    
13.         if(k > m) return -1;
    
14.         return all / map.get(m-k);
    
15.     }
    
16. 
    
17.     public static void main(String[] args){
    
18.         LastKElementsProduction test = new LastKElementsProduction();
    
19.         test.add(3);
    
20.         test.add(-5);
    
21.         test.add(6);
    
22.         test.add(9);
    
23.         test.add(3);
    
24.         System.out.println(test.get(3));
    
25.     }
    
26. }

复制代码

jemi 发表于 2019-9-13 02:39
想到了个更好的方法，思路来自利口 rangeSumQuery[mw_shl_code=java,true]public class LastKElementsProdu ...

你这个没考虑 0 的情况

请问楼楼onsite只面了一道题吗