Google VO

第一题：一个data stream，每input一个数，output比当前数小的个数，难点是要优化，logN的算法没想到，求地理大牛指点
第二题：
第三题：给定一个string由两种字符组成，给定N个长度为M的a

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

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

第三题例子就是用aaa，aaa去分别替换string里面连续的三个字符，最好情况就是替换aab，abb，最后剩一个b。

第一题可以用Binary Index Tree吧

第三题可以用dp[n][k]: 长度为n的string, 用k个长度为m的string来替换，b的最少数量
第一种情况，刚好替换到最后一个字符 此时上一个状态是dp[n - m][k - 1]
第二种情况，除去第一种情况的其他情况(最后一个字符没有被替换）此时上一个状态是dp[n-1][k] + (str[n-1] == ‘b’)
综合两种情况：
dp[n][k] = min(dp[n - m][k - 1], dp[n - 1][k] + str[n - 1] == ‘b’)

markbs123 发表于 2021-5-28 12:54
大大能不能详细写一下这个方法，我按照您的思路写出来结果不是1, max会保留最大的b count数，烦劳大大指 ...

1. /**
   
2.      * @param str target string contains only 'a' and 'b'
   
3.      * @param n number of mask string contains only 'a'
   
4.      * @param m length of mask string
   
5.      * [url=home.php?mod=space&uid=160137]@return[/url] number of char 'a' after applying mask strings
   
6.      */
   
7.     public int findNumberOfBAfterReplace(String str, int n, int m) {
   
8.         int l = str.length();
   
9.         int[][] dp = new int[l][n];
   
10.         int[] countB = new int[l];
    
11.         for (int i = 0; i < l; i++) {
    
12.             countB[i] = (i == 0 ? 0 : countB[i - 1])
    
13.                     + (str.charAt(i) == 'b' ? 1 : 0);
    
14.         }
    
15. 
    
16.         for (int i = 0; i < l; i++) {
    
17.             for (int j = 0; j < n; j++) {
    
18.                 if (i < m) {
    
19.                     dp[i][j] = countB[i];
    
20.                 } else {
    
21.                     dp[i][j] = Math.max(dp[i - 1][j],
    
22.                             (j == 0 ? 0 : dp[i - m][j - 1]) + countB[i] - countB[i - m]);
    
23.                 }
    
24.             }
    
25.         }
    
26. 
    
27.         return countB[l - 1] - dp[l - 1][n - 1];
    
28.     }

复制代码

第二题是帖子中哪一道啊群主？

第一题是不是可以用红黑二叉树或者其他自适应的搜索二叉树 在插入结点的同时记录其余值比自己小的结点的列表

zhengzaoyu1992 发表于 2021-5-25 07:31
第二题是帖子中哪一道啊群主？

我猜是phone screen那题吧，就那题完整些

第三題可以講清楚點嗎 看不太懂怎麼會剩兩個b

补充内容 (2021-05-25 08:44 +08:00):
1個b才對 謝謝

第一题可以用b+ tree，没有implement 过， 这题是真难啊， 楼主你面的是level几呀

第一题典型的binary tree… worst scenario需要 N平方

aababbbbaaa
00112233210
Total=5
2 length=3
算了第三题是真的想不出来 mark了明天继续想

第三题是是不是dp啊 类似的题目伊尔就溜 算出怎么分这个数组能取得最多的b值 类似disjoint interval

第三题什么意思啊？看不懂想要干什么