zhangge's stupid and messy life

阿里巴巴终试

03 Jun 2013

今天状态超不好，6点就起来奔市里，以为可以搞定材料库的服务器问题，可是搞了一天还是原地踏步，累啊！赶着回来刚好是阿里终面。晕死，最终面试居然问到很多不知道的，唉，真不爽！

问我冒泡排序的时间复杂度怎么算，我居然忘掉冒泡排序的算法怎么算的，思路很混乱，好吧，我承认我总是记不住冒泡排序，但是时间复杂度的过程也不知道怎么解释了，只知道是O(n^2).我擦，真他妈囧死了，还被反问我什么是时间复杂度和空间复杂度，

今天我真被质疑了，各种质疑我能力，问我简单的两个东西的区别，接口与继承也问。我是实在无语了！
这是平均的复杂度，唉，冒泡还有最好和最坏的情况，这回真吸取教训了，就知道插入排序，总是忘记冒泡：

for(int i = 0, i < n - 1; i++)
    for (int j = 1; j < n - i; j++)
	if (a[j - 1] > a[j])
	    swap(a[j - 1], a[j]);

冒泡排序就是相邻的两个数两两比较，然后交换，所以n个数冒一次泡要比较n-1次，n-1个数冒一次泡要比较n-2此，如此类推。
因此第一轮冒泡是比较是n-1次，第二轮是n-2次，一直到1，就是说，每次都是[0,i]来冒泡，[i+1,n-1]是有序的，
数列求和就是(1+n-1)*(n-1)/2=(n^2-n)/2=O(n^2)。

以为这样就结束了，其实不然，假如[0,i]也是有序的了，那么冒泡的时候就一次也不会交换了，那么就可以停止排序了。 所以还要定义一个boolean变量来判断内部循环是否有交换的。代码就不写了。

那么新的时间复杂度就是：
最好情况比较了n-1次=O(n)
最坏情况是逆序的，假设swap里面是3条语句,交换了3(n^2-n)/2=O(n^2)。

面试官想问我的估计就是这样，我竟然傻逼地简单回答了！～

然后因为我的简单回答他又问我的快速排序，他不想知道快排的思想，就想知道怎么算那个时间复杂度，唉，真钻！我说了时间复杂度是O(nlogn),计算的方法是写出递归方程，然后用递归树来算，他认为不对，还问我那个logn怎么来的，我说就是那棵树的高度啊！

我快无语，他一直说我没算出来，后面我都不知道怎么办了，晕死了，最后我说，这个在上课的时候推导出来的，现在忘了，就被鄙视了一把！

现在回想起来，我竟然忘记了一点，面试官要的是你的思路，而不是结果，我应该在纸上演示这个过程，就算不对也好，让他看到你的操作过程，这就是能力的体现。这些经验我是有的，只不过这么多次的面试以后竟然没有记录下来，有点懒了，就像那个腾讯一面的时候，被鄙视了，然后二面就发挥好那些方法了。都怪我懒，一直想等到真正拿到了一个offer以后再去总结面试经验，我错了，我以后在这个blog上要经常积累经验。

对于快速排序的时间复杂度分析，我的笔记上有详细记录，这里再简单回顾以下：

快排的实现是用数组，按照我的笔记上面所说的。
最坏情况：输入是排好序的，那么递归方程是：T(n)=T(0)+T(n-1)+O(n)
T(0)的意思是第一次遍历以后第一堆的规模是0，另外一堆的规模是n-1,这次遍历花费时间是O(n).
继续化简公式=O(1)+T(n-1)+O(n)=T(n-1)+O(n)=O(n-1)+O(n)+T(n-2)=O(n^2)

最好的情况：输入是逆序，第一次遍历以后分成的两堆大小为一半，所以递归方程是：
T(n)=2T(n/2)+O(n),画递归树的话，没一行的值都是n，树的高度是logn，因此总和就是O(nlogn),树比较简单，这里就不画了。

平均的情况：例如递归公式是T(n)=T(1/10n)+T(9/10n)+O(n),也是用递归树证明，或者用代换法证明，比较复杂，就不写了，结果和最好情况一样。

我发誓，冒泡，快排，堆排是我一生都会记住的。

面试官问完了我这个排序以后，还问我有没有更快的排序，我就举了一些排序方法，像希尔排序，归并排序等一些线性时间的排序，但是他还是说有没有更快的， 我想了一下还是想不到了，然后他就举一个例子，让我用最快的排序来实现，50个1到100的数字，让我用最快的排序方法，TMD，这是故意引导我到错误的方向， 我就使劲想其他的排序方法，想了很久都想不出来，然后放弃了，超级打击我自信心，感觉块要跪掉了。

他没有告诉我结果，后来我回来以后和宋科谈话突然想起了这个问题，瞬间发现好简单，唉，我真TMD在现场为什么总是想不到阿？
用一个1到100的数组，然后遍历50个数字，找到50个数字值对应数组的下表，然后加一，最后遍历数组，如果元素值为n就打印n个数组的下标。

后面还有各种问题什么是hash表，这个真恼火，我解释了面试官总说不对，我擦，我不想背书，我就实实在在地讲hash表，我根据自己的经验，从数组，链表那里入手，说hash表就是为了用key计算得到index要像数组一样来实现快速定位元素，我还举例了java里面的hashmap和hashtable里面，我说我看过里面的实现，就是这样子的，他居然反问是吗！～我X，我又不是背书，记得大概思路，你也不要完全否定我啊！

好吧，今天RP真不好，问到的都是我的软肋，虽然我都学过，也简单复习过一次了，但是，时间一长就记不住，证明我真的没有掌握，那个HR也许是对的，我不能赖我状态不好，

这就是我的正常表现，我必须吸取教训，知道自己哪些地方掌握不好，然后好好去掌握！

最后还问我做项目的感受之类，为什么要那么早做那么多项目，工作要做那个方向，我的一些疑惑解决没有等等问题，最后换来了HR来一起面试，总问一些不相关的问题，越来越感觉不安了，看到那个HR的笑容，让我想起腾讯面试那个HR的脸，真是笑里藏刀啊，我瞬间知道，跪了！

算了，不想回忆了！God bless me!