Google LA onsite

去年12月去Google LA面的。很少看到LA的，贡献出来做个参考。


round 1：有一个密码箱，密码是4位数，可以是0-9任何一位。在输入密码时可以连续输入，密码会自动匹配最后4位。假设密码为3456，我输入123456时就可以打开了，但是我总共输入了6位数。要求设计一个算法，使得输入的位数尽量少。
这一轮面得很不好，估计这轮是挂了。


round 2：找 longest in

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

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

recursive的算法，面试官不太满意，一再提示下写了个dp的

最后还是挂了。总结了一下，Google面试很喜欢follow up，不断地发散。所以刷题的时候不能自己写完就行，还得想想有没有更优的。
没大米了，求大家给打赏一点

第一题代码

1. public class DeBruijn {
   
2. 
   
3.     public static void main(String[] args) {
   
4.         String res = getDebruijn();
   
5.         System.out.println(res);
   
6.         System.out.println(res.length());
   
7.     }
   
8. 
   
9.     public static String getDebruijn() {
   
10.         StringBuilder sb = new StringBuilder();
    
11.         sb.append("999");
    
12.         HashSet<String> set = new HashSet();
    
13.         for (int i = 0; i < 1000; i++) {
    
14.             String str = sb.toString().substring(sb.length() - 3);
    
15.             for (int j = 0; j <= 9; j++) {
    
16.                 String newStr = str + j;
    
17.                 if (!set.contains(newStr)) {
    
18.                     str = newStr;
    
19.                     sb.append(j);
    
20.                     break;
    
21.                 }
    
22.             }
    
23.             set.add(str);
    
24.         }
    
25. 
    
26.         System.out.println(set.size());
    
27.         return sb.toString();
    
28.     }
    
29. 
    
30. }
    

复制代码

楼主确定没被黑么。。。 第一题是要求De Bruijn sequence，虽然说其实就是个贪心，但是一般人谁能想到啊。。。

mark 一下看看第一个怎么做。

第一题啥意思？

delcarren 发表于 2017-1-28 16:53
第一题啥意思？

可以想成是一个sliding window，长度为4，但是他只会看最后4位是不是跟密码一样。比如我先输入1234，密码不匹配。接着我再敲个5，最后4位是2345，还是和密码不一样。最后当我敲入6的时候，最后4位是3456，跟密码一样，箱子就可以打开了。要求设计一个算法，使得我输入的位数尽量少。

muyunhai 发表于 2017-1-29 02:50
楼主确定没被黑么。。。 第一题是要求De Bruijn sequence，虽然说其实就是个贪心，但是一般人谁能想到啊。 ...

能不能细说一下思路呀？ 只能想到backtracking暴力啊

总共有10000种情况，所以最次40000个数一定要出解，目标就是要做的比他优。那么如果你非常的倒霉，worstcase情况你无论如何都要看10000个不同的组合，也就是说你输入至少10003位（前三位多余，从第四位开始每一位表示一个不同的四位数的结尾）。那么问题来了，能否在10003个数之内解决问题。

答案是能。你可以直接Google De Bruijn Sequence，上面有算法。算法非常简单，最开始输入000，然后每次加一位的时候找没出现过的最小的。证明比较复杂，但是可以证明在这10000种情况都出现之前，不会有重复的出现，也不会有不能走的情况出现。

请问LZ第五轮DP怎么做啊，是要Iterative吗

muyunhai 发表于 2017-1-29 03:04
总共有10000种情况，所以最次40000个数一定要出解，目标就是要做的比他优。那么如果你非常的倒霉，worstcas ...

给大神跪了

但是这种题，这是黑吧。。。。。。

第一题不就是那个欧拉环嘛，这种题不会也不怪lz，好公司多得是