狗家 Onsite 跪经 + 狗家Google Onsite 96题面经大礼包 (2017 -2018 Feb) 求人品唉...

一次性回答你们的问题哈.... 是的在MTV 面的 我会被考是Web Design 是因为我主要是做web开发的，工作经验也就一年吧  第一轮 是要随时返回当前最多票的人，build time Time O(n) space (n), lookup time O(lgn) space O(lgn/2) 先自己建一个class Vote{ String candidate, int timestamp} Build: 开一个暂时的Map<String, Integer> 和两个辅助变量去maintain 当前的最大值，再建一个List<Vote>,  每当当前最大值改变的时候就把一个新的Vote 加进list 里面，lookup 的时候就用Binary Search 找上一个最近的值就好了  第二轮 忘记说了不好意思，输入的string 一定会给相同的长度 所以 s1: ab, s2: cd -> 第一位输出a -> c inclusive 第二位输出 b -> d inclusive Output: aa, ab, ba, bb  ex2: s1: za, s2: ab -> 第一位输出a -> z inclusive 第二位输出 a -> b inclusive a~z + a~b  ex3: ex: s1: ab, s2: cd return:    ab, ac, ad,             bb, bc, bd            cb, cc, cd  第三轮 1. 数学归纳法 O(n) space O(k) 思路跟sliding window 基本一致 正常用sliding window 做记录所有的出现过的字母的index Space是O(n) 但我们只需要记录k个就足够了  2. KMP Google 一下这个就好了，我也没有implement 只是说这也是一个解法  第五轮 第一题用Map 过一遍List 里面的单词，转换好的莫斯密码存到一个Map<String, Integer>里面， 如果新生成的莫斯密码已经在Map 且莫斯密码的频率为1 就count++， return count 第二题在上一题的基础上，建一个Map<String, List<Stirng>> 把相同莫斯密码的原单词存进去，同时用两个辅助变量去maintain 当前的最大值，return 最大值在map里面所对应的list

一次性回答你们的问题哈....
是的在MTV 面的
我会被考是Web Design 是因为我主要是做web开发的，工作经验也就一年吧

第一轮 是要随时返回当前最多票的人，build time Time O(n) space (n), lookup time O(lgn) space O(lgn/2)
先自己建一个class Vote{ String candidate, int timestamp}
Build: 开一个暂时的Map<String, Integer> 和两个辅助变量去maintain 当前的最大值，再建一个List<Vote>,
每当当前最大值改变的时候就把一个新的Vote 加进list 里面，lookup 的时候就用Binary Search 找上一个最近的值就好了

第二轮 忘记说了不好意思，输入的string 一定会给相同的长度
所以 s1: ab, s2: cd -> 第一位输出a -> c inclusive 第二位输出 b -> d inclusive
Output: aa, ab, ba, bb

ex2: s1: za, s2: ab -> 第一位输出a -> z inclusive 第二位输出 a -> b inclusive
a~z + a~b

ex3: ex: s1: ab, s2: cd
return:    ab, ac, ad,
           bb, bc, bd
           cb, cc, cd

第三轮
1. 数学归纳法 O(n) space O(k) 思路跟sliding window 基本一致
正常用sliding window 做记录所有的出现过的字母的index Space是O(n) 但我们只需要记录k个就足够了

2. KMP Google 一下这个就好了，我也没有implement 只是说这也是一个解法

第五轮
第一题用Map 过一遍List 里面的单词，转换好的莫斯密码存到一个Map<String, Integer>里面， 如果新生成的莫斯密码已经在Map 且莫斯密码的频率为1 就count++， return count
第二题在上一题的基础上，建一个Map<String, List<Stirng>> 把相同莫斯密码的原单词存进去，同时用两个辅助变量去maintain 当前的最大值，return 最大值在map里面所对应的list

fantasysukun 发表于 2018-3-15 07:26
一次性回答你们的问题哈....
是的在MTV 面的
我会被考是Web Design 是因为我主要是做web开发的，工作经验 ...

楼主，有点没明白你第一题的意思，能举个例子吗？ 还有list是如何binary search的？

第五题解法你这个完全错的啊。。不懂为啥你觉得你都秒了。。

paopaojeffrey 发表于 2018-3-18 06:11
第五题解法你这个完全错的啊。。不懂为啥你觉得你都秒了。。

那你给出你认为正确的解法？

fantasysukun 发表于 2018-3-15 07:26
一次性回答你们的问题哈....
是的在MTV 面的
我会被考是Web Design 是因为我主要是做web开发的，工作经验 ...

第一题好像就是 LFU吧  应该可以 O（1） time的
hashmap<string candidate, ListNode* node>
node {
string candidate;
int votes;
node* prev, *next;
}
每次update linkedList O（1），直接读取末尾票数最多 O（1）

辛苦楼主了，楼主加油， 祝好运

谢谢楼主分享，这个整理太牛啦

WOW, 发现楼主昂赛一轮竟然和我一轮电面的题目一样诶~~

感谢分享