Google LA onsite

实习return被加面两轮，选择在LA的办公室onsite，两天后通知过hc。

第一题

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

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

第二题

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

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

家里要揭不开锅了，觉得有用的话求加米哈～


补充内容 (2019-11-15 06:53):
看好多同学对题目有些疑问 补两个例子
第一题：input ['bad', 'ad', 'ccc', 'd', 'bacd'] -> output ['d', 'ad', 'bad', 'bacd']
第二题：dropBall(0) = 2; dropBall(1)会卡住
     0 1 2
0 |\|\|/|
1 |/|\|\|

补充内容 (2019-11-28 14:12):
11.26 收到offer

第一题是蠡口邑玲嗣疤

第1题

1. public class LongestChain {
   
2. 
   
3.     public String longestChain(String str) {
   
4.         int ans = 0, num = 0;
   
5.         for (int i = 0; i < str.length(); i++) {
   
6.             int bit = str.charAt(i) - 'a';
   
7.             if ((num & (1 << bit)) > 0) {
   
8.                 return str.substring(0, ans);
   
9.             }
   
10.             num = num | (1 << bit);
    
11.             int target = (1 << (i + 1)) - 1;
    
12.             if (num == target) {
    
13.                 ans = Math.max(ans, i + 1);
    
14.             }
    
15.         }
    
16.         return str.substring(0, ans);
    
17.     }
    
18. 
    
19.     public static void main(String[] args) {
    
20.         LongestChain longestChain = new LongestChain();
    
21.         System.out.println(longestChain.longestChain("acdz"));  // expect a
    
22.         System.out.println(longestChain.longestChain("acdbz"));  // expect acde
    
23.     }
    
24. }
    

复制代码

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

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

第二轮follow up怎么答？

wtcupup 发表于 2019-11-14 12:46
第二轮follow up怎么答？

我的方法是用cache，但在flip的时候要注意这次flip影响了哪些结果然后清除相应的cache

woshi12323 发表于 2019/11/14 14:02:09
我的方法是用cache，但在flip的时候要注意这次flip影响了哪些结果然后清除相应的cache

请教Cache里具体存啥呢

wtcupup 发表于 2019-11-14 14:03
请教Cache里具体存啥呢

如果有n行，dropBall的复杂度就是O(n)，最简单的可以用map或者一维array存dropBall入参和结果的对应，但是这样flip就要清空cache。也可以用matrix存路径，这样cache清理的精度更高

第2题，每个插板的cell都记录哪个column会掉落到这里。当某个cell flip的时候，重新计算此cell掉落的路径，然后更新此cell所对应column的掉落值。
请问如果掉到了-1, n位置如何算？

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

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

allenlipeng47 发表于 2019-11-14 14:53
第2题，每个插板的cell都记录哪个column会掉落到这里。当某个cell flip的时候，重新计算此cell掉落的路径， ...

就算是卡住了

woshi12323 发表于 2019/11/14 15:54:55
input应该是list或者array of strings，比如input ['bad', 'ad', 'ccc', 'd', 'bacd'] -> output ['d', 'ad', 'ba...

第一题是先排序，然后DFS？