Google Onsite 10/26

昨天收到HR通知说已经通过了HC，正在焦急等待最后的结果，为了攒RP发一个面经希望能够帮助大家。
第一面是个羞涩的印度小哥，题目说了一大堆但是基本上就是从N个数里面随机选出K个。楼主的做法非常Naive就是每次random一个数代表选择的，然后把这个数和最后一个数swap,然后继续做K次这样最后K个树就是选择出来的。Follow Up是给定的数字没有Fix Size,要求在任意时刻调用某Function都能生成随机的K个数字，楼主当时算概率算错了，小哥给我耐心的算了一遍。。做法挺简单的就是保存一个size 为K的数组，里面放着的是当前时刻选择出的数字，对每一个新的数字来的时候，该数字被选中的概率是 k/N,N为当前数字总和，如果选中了，那么要从之前保存的K个数字里面选择一个Drop，所有数字都是等概率的所以数组里任意元素被Drop的概率是1/K,然后用新的数字覆盖该位置就好。这样的话对于Stram我们只需要记一个Size为K的数组和一个count.每次调用该函数可以当成是在常数时间内完成。
第二面有点诡异，来了个白人小哥跟我说他是做图像是所以出一个图形处理的题，我当时就懵逼了因为不会，结果题目和图像没有任何关系 =- -=。题目是给一个Matrix代表一个图像，求每一行和每一列的和。。。。我当时反复确认了半天。。然后写了一个One Pass的方法，Fol

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

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

是额外的你写个Header File说说思路就好了，楼主就简单说了说，感觉不像在面试更像在聊天。面完之后小哥送我到停车场，一天的面试结束。
昨天接到电话HR说结果挺好的HC给的结果都是Recommended To Hire.因为楼主手上有个Offer昨天Deadline头脑一热就把那个Offer Decline了专心等这个，现在想想有点忐忑但愿一切都好吧。想着这半个月打Dota玩斧王从来不转玩PA从来不暴击，根据人品守恒定律人品余额应该还是有的，所以在此怒攒一波RP希望之后都顺顺利利的。
楼主的解法应该不算好还是希望大家如果有更好的想法能够分享。
希望大家都能有个好结果。
在此多问一句，HC过了之后对于New Grad来说后面出问题的几率大么。。。。

写了下LongestCommonPath的代码，欢迎指教

1. public class LongestCommonPath {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 String[] strs = {"/abc/def/g", "/abc/def/h"};
   
5.                 String res = findLongestCommonPath(strs);
   
6.                 System.out.println(res);
   
7.         }
   
8.         public static String findLongestCommonPath(String[] strs) {
   
9.                 if (strs == null || strs.length == 0) {
   
10.                         return "";
    
11.                 }
    
12.                 String commonPath = strs[0];
    
13.                 for (int i = 1; i < strs.length; i++) {
    
14.                         String[] strs1 = commonPath.split("/");
    
15.                         String[] strs2 = strs[i].split("/");
    
16.                         StringBuilder sb = new StringBuilder();
    
17.                         for (int j = 0; j < strs1.length && j < strs2.length; j++) {
    
18.                                 if (strs1[j].equals(strs2[j])) {
    
19.                                         if (strs1[j].length() != 0) {
    
20.                                                 sb.append("/" + strs1[j]);
    
21.                                         }
    
22.                                 } else {
    
23.                                         break;
    
24.                                 }
    
25.                         }
    
26.                         if (sb.length() == 0) {
    
27.                                 return "/";
    
28.                         } else {
    
29.                                 commonPath = sb.toString();
    
30.                         }
    
31.                 }
    
32.                
    
33.                 return commonPath;
    
34.         }
    
35. }
    

复制代码

夜行码农耗子 发表于 2015-11-6 06:01
不对，我是取第一个为common path,扫一遍，可以的话第二个。。一直到最后，你这个如果不匹配的话无法确定 ...

可能我之前叙述的有点不清楚，Path的话总有一个"/"是公共的吧。
比如:
s1 = /abc/def,
s2 = /abc
s3 = /
s4 = /abc/def/ghi
我的想法就是维护一个cp,一开始cp就是s1.
然后cp和s2比， update cp ＝ /abc
cp和s3, update cp ＝ /
cp和s4, cp = /
最后返回值就是"/"了，不知是不是lz naive方法的意思

第三面的naive讲法lz可以详细讲讲么? 我也是第一反应用trie，感觉trie还是好理解的。我还有一种解法，不知对不对(或者就是lz naive解法), 维护一个common path的String, one-pass, 每次都用common path和下一个Path String比较，找新的common path, 接着update common path. 扫完一遍最后的common path即为最长公共Path。

MCwong 发表于 2015-11-6 05:50
第三面的naive讲法lz可以详细讲讲么? 我也是第一反应用trie，感觉trie还是好理解的。我还有一种解法，不知 ...

是这么个意思！

MCwong 发表于 2015-11-6 05:50
第三面的naive讲法lz可以详细讲讲么? 我也是第一反应用trie，感觉trie还是好理解的。我还有一种解法，不知 ...

不对，我是取第一个为common path,扫一遍，可以的话第二个。。一直到最后，你这个如果不匹配的话无法确定最长的啊- -

求问LZ四轮面试官的feedback是咋样的？全部positive嘛？我还在等HC所以想了解一下bar是咋样的，多谢多谢~~~

言过饰非 发表于 2015-11-6 06:11
求问LZ四轮面试官的feedback是咋样的？全部positive嘛？我还在等HC所以想了解一下bar是咋样的，多谢多谢~~~

HR给我打电话说都是Recommended Hire,我不知道是面试官的feedback还是HC的feedback。忐忑- -祝一切都好

MCwong 发表于 2015-11-6 06:14
可能我之前叙述的有点不清楚，Path的话总有一个"/"是公共的吧。
比如:
s1 = /abc/def,

恩恩，我理解错了~是这样

夜行码农耗子 发表于 2015-11-6 06:16
HR给我打电话说都是Recommended Hire,我不知道是面试官的feedback还是HC的feedback。忐忑- -祝一切都好

多谢~~ 一般过了HC都没啥问题，好运~~~