一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1295|回复: 16
收起左侧

G家面试好多新题啊

[复制链接] |试试Instant~ |关注本帖
hijkstra 发表于 2016-11-17 05:48:33 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
首先感慨一下G家现在bar越来越高,除了第三轮就没遇过原体。他家现在的“标准化”面试感觉比较适合本科或者硕士毕业生,博士感觉处在比较尴尬的阶段,好多课学过不长用的话忘差不多了,又没有industrial experience。。。三姐recruiter没有提供面试人名单,当天稀里糊涂就去了。总共上午2轮+午饭+下午3轮,越到了2个国人,2个烙印,2个美国。.鏈枃鍘熷垱鑷1point3acres璁哄潧
.鐣欏璁哄潧-涓浜-涓夊垎鍦
第一轮,资深白女,说是校友,开始聊的满开心,然后直接扔了炸弹。第一题设计一个统计投票的系统,统计谁赢。当时有点懵拿算法题写了Hashmap什么的。面试过后回想觉得应该是让设计data structure 然后可以输出任何一个时间点得票领先的人。第二题设计google map 以优化搜索功能,比如搜附近的cafe什么的。瞬间慌乱。
二轮,三姐,进来直接做题。两道lc原体,h-index 和 paint fence。
午饭,三哥。啊啊啊,居然不给个国人陪吃饭,压力微大。
四轮,国男,具体题目忘了,用binary search做的,最后test的时候有个bug,调了一下。大家注意一下validate input的时候,不要受lc影响太深,如果MAX_VALUE什么的都是possible output怎么check,应该写个try-catch block。
五轮,白男聊research。本来最有把握的一轮,以为会是相关专业的人来讨论一下,因为之前还要了thesis abstract 和导师推荐信,没想到来的人完全不懂我做的东西。最后跟他大概讲明白了,他似乎觉得我做的东西对他们产品不太相关。我跟他解说这种统计模型很常见,可以有很多其他application,感觉他还是坚持他的第一印象。
六轮,国男,跟着一个superviser白男。这位哥哥刚进公司不久,好像第一次面试,拼了命的表现给旁边人看,题目是给一2D-matrix,找从左上travel到左下的最短路径,每次只能move到下一个row的正下以及旁边,比如从(i, j) 到 (i + 1, j - 1) 或 (i + 1, j) 或 (i + 1, j + 1)。用dp写的,然后follow-up说只能用O(n) extra space 最后没写玩。. more info on 1point3acres.com

总体感觉还是题型比较多变,准备不够充分,接下来要面的同学加油了。听说内部员工培训时直接让大家别出lc上的原题。。。点名lc。。。
另一方面,感觉现场还是会紧张,脑子一瞬间放空之类的,也没表现出自己的最好水平,请教一下前辈怎么克服。
第一轮问题还请map达人指点
. 1point 3acres 璁哄潧

评分

1

查看全部评分

本帖被以下淘专辑推荐:

gjxwin 发表于 2016-11-17 06:27:36 | 显示全部楼层
很多新题过段时间就会被收录到lc里面去了。。。
回复 支持 2 反对 0

使用道具 举报

Owenli20 发表于 2016-11-17 06:14:29 | 显示全部楼层
我觉得面新题看思路挺好的。像FB那种原题倒是原题,要求严格bug free的感觉不make sense
回复 支持 1 反对 0

使用道具 举报

LynKang 发表于 2016-11-17 06:06:35 | 显示全部楼层
同意,在职跳槽的,过去几乎全是新题。五轮里有三轮是国人,刚送hc,目测希望不大。

补充内容 (2016-11-17 06:09):
内部要求不准出LC的题。除非面试官偷懒,不然不可能遇到原题。
回复 支持 反对

使用道具 举报

yangluphil 发表于 2016-11-17 06:23:48 | 显示全部楼层
第一题已知candidates的数量吗,如果数量小是不是可以用boyer-moore voting algorithm: https://discuss.leetcode.com/topic/17564/boyer-moore-majority-vote-algorithm-and-my-elaboration
回复 支持 反对

使用道具 举报

 楼主| hijkstra 发表于 2016-11-17 07:09:05 | 显示全部楼层
yangluphil 发表于 2016-11-17 06:23
第一题已知candidates的数量吗,如果数量小是不是可以用boyer-moore voting algorithm: https://discuss.le ...

不已知。input stream 是candidates名字,相当于要做一个实时投票系统。
回复 支持 反对

使用道具 举报

yangluphil 发表于 2016-11-17 07:23:51 | 显示全部楼层
hijkstra 发表于 2016-11-17 07:09 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
不已知。input stream 是candidates名字,相当于要做一个实时投票系统。
. 1point 3acres 璁哄潧
嗯,我明白是要一个实时系统,input不是一个static的vector<string>,但是如果candidate pool的大小已知({"Hilary Clinton", "Donald Trump", "Gary Johnson"})就可以用voting algorithm做。要是不已知,投任何名字都可以的话,感觉hashmap已经是代表投票状态的最优的data structure了啊,面试官说了哪里不好吗?
回复 支持 反对

使用道具 举报

123呆板彻底 发表于 2016-11-17 07:44:35 | 显示全部楼层
gjxwin 发表于 2016-11-17 06:27
很多新题过段时间就会被收录到lc里面去了。。。

我估计google把lc杀了的心都有了。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦
辛辛苦苦出题目,不到一个月全进lc了
回复 支持 反对

使用道具 举报

 楼主| hijkstra 发表于 2016-11-17 09:34:26 | 显示全部楼层
yangluphil 发表于 2016-11-17 07:23. more info on 1point3acres.com
嗯,我明白是要一个实时系统,input不是一个static的vector,但是如果candidate pool的大小已知({"Hilary ...

可以投任何人。面试官没说啥就下一题了。但是我觉得她应该是想问怎么存这些信息,然后方便search,注意输出“任何一个时间点领先的人”,如果是搜过去的时间(1小时前)呢?
我当时和你想的差不多,当做algorithm题做了
回复 支持 反对

使用道具 举报

yangluphil 发表于 2016-11-17 10:02:52 | 显示全部楼层
hijkstra 发表于 2016-11-17 09:34. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可以投任何人。面试官没说啥就下一题了。但是我觉得她应该是想问怎么存这些信息,然后方便search,注意输 ...

看来光是一个map<string, int>还不行。可以每次投票后用hashmap算出winner,假如winner跟前一次投票后的winner不一致,就把(timestamp, newWinner)这个tuple存到一个vector尾部。getWinner(timestamp t)在这个vector上做binary search找到winner。但是这样做如果获胜者切换的频率太快的话空间复杂度就很高。

求其他想法
回复 支持 反对

使用道具 举报

sunfish 发表于 2016-11-17 10:06:38 | 显示全部楼层
严重同意楼主,我也刚挂,也是博士,除了一题外都是新题。
回复 支持 反对

使用道具 举报

 楼主| hijkstra 发表于 2016-11-17 11:47:56 | 显示全部楼层
Owenli20 发表于 2016-11-17 06:14. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我觉得面新题看思路挺好的。像FB那种原题倒是原题,要求严格bug free的感觉不make sense

对,感觉面试下来也学到不少东西,不过坏处是还没找到工作诶。。。
回复 支持 反对

使用道具 举报

 楼主| hijkstra 发表于 2016-11-17 11:48:24 | 显示全部楼层
sunfish 发表于 2016-11-17 10:06
严重同意楼主,我也刚挂,也是博士,除了一题外都是新题。

握爪握爪握爪  
回复 支持 反对

使用道具 举报

2008 发表于 7 天前 | 显示全部楼层
输出任何一个时间点得票领先的人

这题用LRU CACHE可以吗?
区别是,实时增加某人选票的时候,不是把这人放在链表头,而是在链表里往前移直到不能动为止。
但是LRU这种蛋疼的题半个小时是写不完的,在Amazon onsite被国女问到过,只来得及写一半。
回复 支持 反对

使用道具 举报

jade86 发表于 7 天前 | 显示全部楼层
统计投票其实是lc432, https://leetcode.com/problems/all-oone-data-structure/。
回复 支持 反对

使用道具 举报

2008 发表于 6 天前 | 显示全部楼层
2008 发表于 2016-12-1 01:30
输出任何一个时间点得票领先的人

这题用LRU CACHE可以吗?
. more info on 1point3acres.com
LC432 by LRU cache, replace moving to head by swap one by one.
  1. class AllOne {
  2.     struct node {
  3.         string key;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.         int val;
  5.         node(string key, int val):key(key), val(val) {};
  6.     };
  7.     list<node> l;. 1point 3acres 璁哄潧
  8.     map<string, list<node>::iterator> m;
  9.     typedef list<node>::iterator IT;
  10.    
  11. public:
  12.     AllOne() { }
  13.    
  14.     void swap(IT it1, IT it2) {. 1point3acres.com/bbs
  15.         node n = *it2;
  16.         *it2=*it1;
  17.         *it1=n;
  18.         m[(*it2).key]=it2;-google 1point3acres
  19.         m[(*it1).key]=it1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.     }
  21.    
  22.     void inc(string key) {
  23.         if(m.count(key)) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.             IT it=m[key];
  25.             (*it).val++;
  26.             while(it!=l.begin()) {
  27.                 IT it1=it, it2=--it;
  28.                 if((*it2).val<=(*it1).val) {
  29.                     swap(it1, it2);
  30.                 } else break;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.             }
  32.         }else {
  33.             node n(key, 1);
  34.             l.push_back(n);
  35.             m[key]=--l.end();
    . 1point 3acres 璁哄潧
  36.         }  
  37.     }. Waral 鍗氬鏈夋洿澶氭枃绔,
  38.    
  39.     void dec(string key) {
  40.         if(m.count(key)) {
  41.             IT it=m[key];
  42.             (*it).val--;
  43.             while(it!=--l.end()) {
  44.                 IT it1=it, it2=++it;
  45.                 if((*it2).val>=(*it1).val) {
  46.                     swap(it1, it2);. 1point 3acres 璁哄潧
  47.                 } else break;
  48.             }
  49.             if(it->val==0) {
  50.                 l.pop_back();
  51.                 m.erase(key);
  52.             }
  53.         }      
  54.     }
  55.    
  56.     string getMaxKey() {. From 1point 3acres bbs
  57.         if(l.size()==0) return "";
  58.         return (*(l.begin())).key;
  59.     }
  60.     . 1point 3acres 璁哄潧
  61.     string getMinKey() {. 1point3acres.com/bbs
  62.         if(l.size()==0) return "";
  63.         return (*(--l.end())).key;        
  64.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 03:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表