Twitter 面试

刚刚面完第二轮电面，上来发个面经。

第一轮，7-29面的，面试官是个阿三（为什么又是阿三！），听的无比吃力，好歹问题是敲在online text editor 上的。
问：一个横纵都排好序的数组，判断一个数是否在数组里。
CTCI上排序那一章的题，很快就敲出来了，然后问我test case，我说了几个，然后问我还有吗，我说我想不出来了，他表示是差不多了。然后他解释了好久他所在的组是具体干

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

被quicksort惯性思维了），这个错犯的真是无比傻逼啊。下回还是得把题完全完全弄明白，再开始敲。之后问了问他的组主要做什么的问题。

明天电面google，压力山大。。。还望面过google的同学指点一二，谢了。

排序那题明明刚做完的 又敲了遍还是有问题 唉 智商是硬伤啊 ~

请教LZ下quicksort那个题“k不一定是a里的数”是什么意思那？

浅浅 发表于 2013-8-13 01:42
请教LZ下quicksort那个题“k不一定是a里的数”是什么意思那？

In quicksort, generally we choose k = a[(start+end)/2], but here k can be any integer, so perhaps k is greater than or less than any element in a, in that case you should return n or -1.

xiaoma318 发表于 2013-8-13 22:30
In quicksort, generally we choose k = a[(start+end)/2], but here k can be any integer, so perhaps  ...

如果返回n或者-1，那么partition之后的quicksort(a, 0, pivot - 1)和quicksort(a, pivot+1, n)是否会死循环啊

浅浅 发表于 2013-8-13 09:52
如果返回n或者-1，那么partition之后的quicksort(a, 0, pivot - 1)和quicksort(a, pivot+1, n)是否会死循 ...

sorry, my bad, this problem i don't need to do quciksort, just partition. so it's simpler.

补充内容 (2013-8-13 10:47):
Actually, i've said you just need to implement the int partition() function in my post

看上去边界条件什么的看得很严啊～
虽然题都不难，但是想一听到就迅速反应上来并且稳稳写出程序也不容易啊～

希望lz面g家顺利！
谢谢分享面经！

xiaoma318 发表于 2013-8-14 00:45
sorry, my bad, this problem i don't need to do quciksort, just partition. so it's simpler.

补充内 ...

啊多谢指教哈，再请教下哈，那么如果说这个partition不是为了quicksort；是不是这个partition实现的目的可以用作求第k大的数字？

浅浅 发表于 2013-8-14 17:36
啊多谢指教哈，再请教下哈，那么如果说这个partition不是为了quicksort；是不是这个partition实现的目的可 ...

是可以，第K大的数字简单点就用冒泡好了。。。

xiaoma318 发表于 2013-8-15 07:59
是可以，第K大的数字简单点就用冒泡好了。。。

恩多谢前辈哈，祝你多拿offer