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

Linzertorte 发表于 2014-3-14 13:28
有个关于四分树(quad-tree)的题

囧，你遇到的题还都挺奇葩的。

ototsuyume 发表于 2014-3-14 13:34
google电面的时候被问了这道题，这题也就看上去吼人而已，nlogn的算法是一下子能想出来的，线性的算法仔细想 ...

赞这个排序O(nlgn)的方法。

线性算法时，是不是需要注意数组第一个元素，比如 7，5， 6 ...， 这样线性算法就不对了，除了额外考虑第一个元素外，这个算法确实好

exuberance 发表于 2014-3-14 23:09
赞这个排序O(nlgn)的方法。

线性算法时，是不是需要注意数组第一个元素，比如 7，5， 6 ...， 这样线性 ...

不用额外考虑第一个元素，直接从第二个开始就行，比如5是偶数位，比7小，跟7交换变成[5，7，6]，然后下一个是6，比前一个小，不用交换

O(n) 算法是正解。

归纳法证明

if i=0,1 ...

if i是偶数：if need swap a[i],a[i-1]，if means a[i] < a[i-1] <= a[i-2]，swap后new a[i-1] and a[i-2]依然保序.

奇数同理。

ototsuyume 发表于 2014-3-15 12:27
不用额外考虑第一个元素，直接从第二个开始就行，比如5是偶数位，比7小，跟7交换变成[5，7，6]，然后下一 ...

哦哦，明白了，多谢指点

ototsuyume 发表于 2014-3-14 13:34
google电面的时候被问了这道题，这题也就看上去吼人而已，nlogn的算法是一下子能想出来的，线性的算法仔细想 ...

赞O(n)想法，轻巧的解决了问题~如果题目是求所有的shuffle会有什么样的思路呢？？

sort那个办法并不需要排序，只要找到正好为median的那个数作为pivot，然后类似快排那样分一次就好。 找median应该O(n)就可以，所以也是O(n)

sjtuzyt 发表于 2014-3-16 09:38
sort那个办法并不需要排序，只要找到正好为median的那个数作为pivot，然后类似快排那样分一次就好。 找medi ...

对，居然没想到这个，怪不得google连续拒我两次了T T

jimmyyao 发表于 2014-3-16 06:20
赞O(n)想法，轻巧的解决了问题~如果题目是求所有的shuffle会有什么样的思路呢？？

求出所有符合要求的序列我只想到枚举全排列，求的时候判断当前位置是否符合要求，不符合就返回，符合就继续排后面的。感觉没有复杂度比O(n!)更优的解，但是可能会有常数级别的优化

这道题我onsite时也碰到了，开始也是给了个排序nlgn的方法，面试小哥问我还能不能再快点，我说要是知道中位数就好办了～～后来实在想不出舔着脸要了个提示，小哥说有个方法可以O(n)时间找到中位数，但并不需要我实现这个。然后就是根据这个条件从左到右遍历数组，小于中位数的放奇数位，大于的放偶数位，然后中位数有重复，注意下这个就好了。