Google on-site最后一面非常难的一道题目

whuwangyi 发表于 2014-3-17 22:26
elements of programming interview

Thanks!

这题我也是面g家的时候面过（而且是电面，应该不是同一个人问的吧……！）而且应该是面的还不错。
面试官推荐的方法如下：

首先sort一遍，一般情况下这个data structure都自带排序算法，假设速度nlogn。
然后再这么排序：拿第一个，最后一个，第二个，倒数第二个，。。。，最中间那个。这次排序算法O(n)，所以整个程序运行下来就是个O(nlogn) (assume sort(list) takes O(nlogn) time...)

其实后来我面完了发现还可以有更简单的：第二三个数对调，第四五个数对调，。。。这个我还没验证过正确性，应该问题不大。

金妮韦崽 发表于 2014-3-19 22:49
这题我也是面g家的时候面过（而且是电面，应该不是同一个人问的吧……！）而且应该是面的还不错。
面试官推 ...

你说的第二种是对的。我已经在前面给出了代码。
证明也很容易。

比如 1 2 3.第三个数是需要比第二个小的。
这个时候你交换2,3,   ->  1 3 2.  因为 3比2 大你才交换的，所以 3肯定比1大，  A[0]<=A[1]仍然满足。

恭喜楼主! 另问楼主Onsite时都是算法题吗？有设计题吗？能否透露一下？谢谢！

Lisepher 发表于 2014-3-21 01:50
恭喜楼主! 另问楼主Onsite时都是算法题吗？有设计题吗？能否透露一下？谢谢！

我运气比较好，没有遇到设计题。

1. linear time selection找到中位数, O(N)
2. in place partition, 保证第一部分所有元素<=median，第二部所有元素>=median，O(N)
3. merge前后两部分, O(N)

时间复杂度O(N)，空间复杂度O(1)

youliye 发表于 2014-4-1 07:52
一定是我想的太简单了。。。我总是太天真。。。楼主要嘲笑的话放心里哈。。。
def shuffle(arr):
        if arr ...

你这样是完全正确的。其实我写了C++ 的代码了。只是大家都没看。

我的C++代码跟你的是一个意思。

youliye 发表于 2014-4-1 07:52
一定是我想的太简单了。。。我总是太天真。。。楼主要嘲笑的话放心里哈。。。
def shuffle(arr):
        if arr ...

去看第18垅。