狗家店面+Onsite

等待消息中，发面经攒人品～～看我码了字这么多，赏点大米最好

12月初店面：

第一题是Count Complete Tree Nodes， LZ秒掉以后，国人小哥问我做过没。老老实实说Leetcode刷过。换题，Leetcode Gas Station。不用写code，只用讲算法，要求优化到O（n），dp再次秒掉

上周五Onsite五轮：

第一轮白人大叔，口音有点怪，不知道哪儿的人：

1. 定义二叉树的Local minimum为value小于等于parent和两个children的节点。找出local minimum。
    Brute Force是O（n）的算法。接着要求证明Local minimum一定存在。进而优化成O（log（n））

2. Merge k sorted list。 LZ说做过，简单说了算法后换下一题

3. Implement 一个Table 的interface。 实现两个function：set（int i， int j，int value）改变坐标为（i，j）的元素的值；sum（int i， int  j），返回Table中从坐标（0，0）到坐标（i，j）的方块中所有元素的总和。Follow up是如果sum被频繁调用怎么办。答案是在类里面加一个sum_table，记录已经计算好的和。缺点是会牺牲set的performance，，每次set需要更新这个sum_table

4. 给一个int数组，比如[2,3,8,11,37]。 返回[3*8*11*37, 2*8*11*37, 2*3*11*37, 2*3*8*37, 2*3*8*11]。 就是所有元

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

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

都是原始文件的位置。结果就是“hi diegogoodmorningworld”。

LZ东海岸飞过去面试，时差还没倒过来，早上5点就醒了。到这轮的时候，脑子都不太转，这题答得很差，总觉得每次替换之后，再做下一次替换，index发生了改变，会产生各种conflict。最后小哥说，忘记告诉你了，那个array中的offset你可以当成是sorted的。在他的提示下搞出来一个他说works的算法。后来想想还是有问题，到现在也没想出一个特别好的算法。。。感觉要挂了的话，就是这轮了

总体感觉并没有版上好多面经那么难，并没有很牛叉的DP啊，记忆化搜索这类的问题，不知道G家HC最后标准是什么～ 求人品啊～



补充内容 (2017-2-1 10:37):
update一下，刚接到通知HC approve，接着是team match

第五轮代码：

1. public class Replacement {
   
2. 
   
3.     static class Replace {
   
4.         int pos;
   
5.         String origin;
   
6.         String now;
   
7.         public Replace(int p, String o, String n) {
   
8.             pos = p;
   
9.             origin = o;
   
10.             now = n;
    
11.         }
    
12.     }
    
13.     public String replaceString(String s, Replace[] replaces) {
    
14.         if (replaces == null || replaces.length == 0) {
    
15.             return s;
    
16.         }
    
17. 
    
18.         StringBuilder sb = new StringBuilder();
    
19.         int start = 0;
    
20.         for (Replace r : replaces) {
    
21.             sb.append(s.substring(start, r.pos));
    
22.             start = r.pos + r.origin.length();
    
23.             sb.append(r.now);
    
24.         }
    
25.         return sb.toString();
    
26.     }
    
27. 
    
28.     public static void main(String[] args) {
    
29.         Replacement r = new Replacement();
    
30.         Replace[] rps = { new Replace(0, "hello", "hi diego"), new Replace(5, "", "goodmorning")};
    
31.         System.out.println(r.replaceString("Hello world", rps));
    
32.     }
    
33. }
    

复制代码

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

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

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

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

祝LZ人品大爆拿offer！顺便问一下LZ你onsite前都经过了哪些轮啊？

看楼主各种秒，肯定是没问题的了，谢谢分享&好运！

与天共醉 发表于 2017-1-24 12:38
祝LZ人品大爆拿offer！顺便问一下LZ你onsite前都经过了哪些轮啊？

我onsite前就一轮店面

非常感谢楼主分享啊~

楼主面得蛮好，肯定过了

LZ再问个问题，我在地里别的帖子里看到在说google的match问题，这个是怎么回事儿啊，是拿到offer以后还是不能入职，要等到有match了才行吗？

其实lexicographically smallest subsequence of length k弄个k size的queue就行，然后扫一遍array，复杂度O(N)

最后一道题就是从已知的offset，同时根据新旧string的长度差，调整offset，然后一次一次更新string即可，这题不太难。
我也在等google的结果，希望一切ok吧。。。

与天共醉 发表于 2017-1-25 01:38
祝LZ人品大爆拿offer！顺便问一下LZ你onsite前都经过了哪些轮啊？

我只有一轮店面~