新鲜谷歌电面

背靠背，每一轮都只有一题，但是follow up两个升级版，让copy之前的代码并改动，所以最后会有三个version的代码
第一面45分钟，第二面1个小时。求问谷歌面试时间是多久？在邮件里面没找到。。。。从第一个面试官那感觉是45分钟，从第二个面试官那感觉是1个小时，尴尬

一面：

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

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

二面：

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

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

补充内容 (2017-12-14 12:32):
感觉谷歌面试并不最求最优解，面试官更多的是考察对数据结构和算法是否了解，这两个题都可以优化，但是面试官没有focus on在优化上，而是更多的变化输入或者定义，看能否给出reasonable的解决方案

补充内容 (2017-12-14 12:32):
感觉谷歌面试并不最求最优解，面试官更多的是考察对数据结构和算法是否了解，这两个题都可以优化，但是面试官没有focus on在优化上，而是更多的变化输入或者定义，看能否给出reasonable的解决方案

补充内容 (2017-12-14 12:32):
感觉谷歌面试并不最求最优解，面试官更多的是考察对数据结构和算法是否了解，这两个题都可以优化，但是面试官没有focus on在优化上，而是更多的变化输入或者定义，看能否给出reasonable的解决方案

补充内容 (2017-12-14 12:32):
感觉谷歌面试并不最求最优解，面试官更多的是考察对数据结构和算法是否了解，这两个题都可以优化，但是面试官没有focus on在优化上，而是更多的变化输入或者定义，看能否给出reasonable的解决方案

biostat转ds 发表于 2017-12-16 10:07
第一题，follow up 2 怎么做呀。肯定不能把所有T尝试一遍，找最小的match的。应该二分查找吧。但是，发现不 ...

没法二分做啊，我只给了扫T的答案

其实第一题不太像算法题，而是比较典型的OLAP（online transactional processing）应用场景，给一个workload（比如10亿量级数据）和时间上的要求（比如10秒以内），一般就是糙快猛，上众核CPU+SSD或是集群，然后并行scan+aggregate就可以达到要求。

如果从算法层面考虑并试图用一些复杂数据结构的话，反而可能会
(1) 空间爆炸
(2) 不能有效并行化
(3) 不scalable


对于第一题的follow2，可以建一些索引来加速计算，但索引怎么建效果比较好，应该是和投票数据的具体性质有关，没有办法一概而论，我随便扯一点想法：

I. 首先把投票数据划分为以X小时（例如1小时）为单位的区间，从最早的时间开始，标记各区间为 S(0), S(1), ...

II. 考虑各区间开始时的candidates序列，定义如下性质（都是胡乱命名的..）：

(a) 我们称一个区间S(i)为 K-absolutely-stable，当且仅当在S(i)中的任意时刻，得票前K的candidates都与其在S(i)开始时得票顺序完全一致
(b) 我们称一个区间S(i)为 K-relatively-stable，当且仅当在S(i)中的任意时刻，得票前K的candidates与S(i)开始时得票前K的是同一个集合（但顺序可以不一样）
(c) 我们称一个区间S(i)为 K-P-variatively-stable，当且仅当S(i)中得票前K的candidates的可能顺序不超过P种

这里(a)是非常好的性质，因为对于满足(a)的区间，我们能立刻判断所期望的candidates序列是否在这个区间里 —— 但是有多少区间能满足(a)，就要看区间大小X的选取和投票数据的性质了（竞争是否非常激烈）

而(b)是相对不错的性质，我们可能可以快速跳过满足此性质的区间 —— 如果需要查询的列表与(b)所定义的前K个人不一样的话

最后对于(c)如果M比较小的话（实际投票中我觉得不可能超过100，即使竞争激烈，在投票后期可能就三、五种），那么空间预算足够的情况下，把所有M种序列在该区间中首先出现的时间都记录下来，会大大加速查找


III. 在follow up里，给出的k是一个变量，这一变量是否有范围？例如k在1000以下（或者是candidates的人数在1000以下），那么我们可以针对每个区间用bitmap存储对于K = 1, ..., 1000的所有(a)/(b)信息，耗用的空间很小；也可以存储(c)的信息，耗用的空间大一些但也算合理

IV. 建立和维护索引需要一些时间（这里可以继续优化建索引的算法），如果查询很多的话，应该是非常值得的


补充内容 (2017-12-15 06:10):
OLAP定义写错了orz.. 是online analytical processing

看题要求好高啊。。求好心人贴一下。。

lz的两轮是连在一起的吗？
第一个面完直接面第二个？

msu_HIDDEN 发表于 2017-12-14 08:07
lz的两轮是连在一起的吗？
第一个面完直接面第二个？

是的是的是的是的

楼主能再说一下第一题follow2是什么意思吗？
第一题的follow2是说，你有一个list A，要找一个T值，然后调用follow1的函数（输入是T还有k，还有list A）， 然后follow 1 接着返回list A？不好意思哈，咩有看懂。。。。sorry

wannagotousa 发表于 2017-12-14 08:51
楼主能再说一下第一题follow2是什么意思吗？
第一题的follow2是说，你有一个list A，要找一个T值，然后调 ...

原意是给一个top k的list，找到一个T值，使得小于这个T值得top k list和输入的top k list相等

请问第一题怎么做呢?

有没有甚么高效的作法? 如果是只查一次, 是不是直接扫过整个array就可以了?

这题有考虑到甚么东西呢?

谢谢

第一题是要用 Boyer–Moore majority vote algorithm 吗？

谢谢楼主！评分加收藏了

reliveinfire 发表于 2017-12-14 11:13
请问第一题怎么做呢?

有没有甚么高效的作法? 如果是只查一次, 是不是直接扫过整个array就可以了?

我是直接扫的，希望有人能给出更优的解法