新鲜谷歌电面

谢谢楼主！评分加收藏了

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

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

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

msu_HIDDEN 发表于 2017-12-14 11:14
第一题是要用 Boyer–Moore majority vote algorithm 吗？

面试官没有提...........

第一题 follow up 2求大佬指点。。。

为什么设置需要分数才能看呢

june3 发表于 2017-12-14 16:30
为什么设置需要分数才能看呢

发帖要求 http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311

2388260384 发表于 2017-12-14 14:29
第一题 follow up 2求大佬指点。。。

就是面经里面说的哈，遍历时间，调用follow1的函数，看返回的结果是否和输入的list一样

jingjingfly 发表于 2017-12-15 03:56
就是面经里面说的哈，遍历时间，调用follow1的函数，看返回的结果是否和输入的list一样

额。。。我的意思是答案。。。

2388260384 发表于 2017-12-15 03:58
额。。。我的意思是答案。。。

答案？你说code吗？sorry，我没get到你的点

其实第一题不太像算法题，而是比较典型的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