Google电面，面经

祝楼主好运啊！onsite回来记得写面经～

monolake 发表于 2015-10-1 00:45
第一题求测试，sorted array, O(logn)

int totalPass(int * num, int size) {

你的算法在dup的情况下难道不是O(n)?

补充内容 (2015-10-10 08:51):
看错了。。

monolake 发表于 2015-10-1 00:45
第一题求测试，sorted array, O(logn)

int totalPass(int * num, int size) {

你的算法在dup的情况下难道不是O(n)?

第一问，先找min，O(N), 然后再遍历一遍找比min大的数的个数，O(N)，对不？

第二题可以用两个priority_queue(就是堆)，第一个大根堆存储比当前数小的数字，第二个小根堆存比当前数大的数字
然后每次move next 就看数变大还是变小了，然后从一个堆pop()到另一个堆

M_Jason 发表于 2015-9-30 08:53
感觉这道题的第二问好像可以用Stack来解决啊，还是需要先排序，从大到小排，然后还要用hash表存储好所有重 ...

我又想了几遍 不可行

zxy_snow 发表于 2015-10-9 15:53
第二问是不是可以用C++的STL中的multiset，每插入一个，可以算出来前面的个数，是nlogn的。当然也可以用线 ...

stl set里怎么算出前面的个数啊？  lower_bound() 可以返回大于等于的第一个元素的iterator,然后怎么算出前面的个数呢

补充内容 (2015-10-10 20:27):
找到了std::distance(InputIterator p1, InputIterator p2)这个函数 可以计算两个iterator距离 不过时间复杂度是o(n)的 这样总的就成了o(n^2)了

monolake 发表于 2015-10-1 00:45
第一题求测试，sorted array, O(logn)

int totalPass(int * num, int size) {

不太懂这个思路。。
看上去是二分查找的模板，但是二分查找的前提条件是sorted array。
能否稍微讲一下思路？～

第二题应该是算法导论第14章,数据结构的扩张-动态顺序统计.使用rbt,每个节点附加size属性吧. 有duplicate也可以

八月槎 发表于 2015-10-10 15:16
第二题可以用两个priority_queue(就是堆)，第一个大根堆存储比当前数小的数字，第二个小根堆存比当前数大的 ...

怎么没人支持这楼，这个方法很好啊!