新鲜谷歌电面

magicsets 发表于 2017-12-15 06:09
其实第一题不太像算法题，而是比较典型的OLAP（online transactional processing）应用场景，给一个workloa ...

感谢分享，that is really helpful!

jingjingfly 发表于 2017-12-14 12:27
我是直接扫的，希望有人能给出更优的解法

请问输入是什么形式呢？我有个思路，首先对输入按照timestamp排序，然后建立一个presum数组记录到当前timestamp为止的投票结果，然后就可以用二分搜索找到T时间之前存在的第一个timestamp的结果。时间复杂度O(logn)

charlie.wuhan 发表于 2017-12-15 11:54
请问输入是什么形式呢？我有个思路，首先对输入按照timestamp排序，然后建立一个presum数组记录到当前tim ...

输入是list of tuple，

我觉得没必要这么做哈，面试官并不是想考把时间复杂度优化到最优，而且按timestamp排序应该是O(nlgn)，对不？

可以参考上面magicsets的回答，我觉得挺好的哈

jingjingfly 发表于 2017-12-15 12:02
输入是list of tuple，

我觉得没必要这么做哈，面试官并不是想考把时间复杂度优化到最优，而且按times ...

我的意思是find操作的时间O(logN)

charlie.wuhan 发表于 2017-12-15 12:04
我的意思是find操作的时间O(logN)

如果只是优化某一步，就因小失大了啊

jingjingfly 发表于 2017-12-15 12:06
如果只是优化某一步，就因小失大了啊

如果是我做的这道题，应该会先问most frequently used function是什么，是不是数据只会给一次然后一堆find，还是会一直update数据，find操作很少，对于不同的情况应该有不同的做法吧

charlie.wuhan 发表于 2017-12-15 12:18
如果是我做的这道题，应该会先问most frequently used function是什么，是不是数据只会给一次然后一堆fin ...

太厉害啦，从来没考虑过这种问题，默认就是single function，给的输入非常固定（捂脸

感觉你的思路可以去面社招了👍

楼主可以再解释一下第二题嘛？不是很懂 谢谢你

第一题，follow up 2 怎么做呀。肯定不能把所有T尝试一遍，找最小的match的。应该二分查找吧。但是，发现不match 时该往哪边走呢

是intern还是全职啊lz