t********1
发帖数: 266 | 1 non-CS guy's solution:
Given same length A, B python lists.
Steps:
1, turn A, B lists into associated arrays A1, B1, keys are the uniq numbers,
values are counts of the particular uniq numbers.
2, quicksort A1, B1 arrays' key space lists, so the KA1, KB1 arrays' keys
are in order.
3 compare the sorted keys sequentially (which are lists themselves), stop at:
3.1: the lengths of KA1, KB1 key lists differ.
3.2: At the same list position i, KA1[i], KB1[i] keys differ.
3.3, at the same list pos |
|
f*****r
发帖数: 229 | 2 看了一圈，好像quicksort的方法靠谱一些：拿一个element
来divide two arrays, then first count the numbers of each part. If they are
same, then go ahead.
Hash based methods should be also ok.
如果两个数组不一样的概率很大的话，前面提到的一些方法可以快速检测很多不一样的情况，such as, hash code, bloom filter, fingerprinting, or even moments, etc. 但是这些方法都有false positive. |
|
r****o
发帖数: 1950 | 3 Quicksort的那个题目是不是应该说每次partition的时候随机选择一个元素跟最后一个
互换？对吗？
束了。人家不待见我...... |
|
P*******e
发帖数: 1353 | 4 用quicksort的那个partition函数
是不被favorable的吧。。。 |
|
x******3
发帖数: 245 | 5 如果这个问题有解的话，岂不是说明有space o(1)的stable quicksort？
除非不用comparison也能进行partition |
|
y**i
发帖数: 1112 | 6 那不是结果变成了-5, -12, 1, 9, 7, 15，顺序改变了，不stable了，如果这样的话，
根本不需要第一次扫描，直接用quicksort的一次partition就可以了，pivot选一个额
外的数：0。
[0 |
|
g*******y
发帖数: 1930 | 7 觉得这个题是跟stable quicksort关联的吧
time |
|
P********l
发帖数: 452 | 8 是存在o(n)time o(1)space 解法的。
分区是对的，但是我不知道怎末分区。一般要分成sqrt(n)区，选择排序每个区得到局
部有序。然后拿一个区做临时的交换区。具体的怎么做还没搞定。
这道题的答案是稳定quicksort的基础。
这道题（复杂度要求）不适合面试，没见过的基本上没戏，只有准备过的才能有思路。 |
|
g******e
发帖数: 389 | 9 Binary search is not applicable, at least not as you(above) indicated.
int * find_sum(int *v,int len, int SUM){
quickSort(v,0,len-1);
int low(0), high(len-1);
while(low < high){
if(v[low]+v[high] > SUM) high--; //high = (low+high)/2;
else if(v[low]+v[high] < SUM) low++; //low = (low+high)/2;
else {
int* newV = new int[2];
newV[0] = v[low]; newV[1] = v[high];
return newV;
}
}
return NULL;
} |
|
q*********u
发帖数: 280 | 10 感觉这种办法比较清爽也好懂
用基本相同的代码， 还可以用来做给出一个数组，比如{1, 2, 1, -1, -4, 10, 2, 9,
8, -6, 1}, 然后找出subarray which has a max summation among other subarrays;
Binary search is not applicable, at least not as you(above) indicated.
int * find_sum(int *v,int len, int SUM){
quickSort(v,0,len-1);
int low(0), high(len-1);
while(low < high){
if(v[low]+v[high] > SUM) high--; //high = (low+high)/2;
else if(v[low]+v[high] < SUM) low++; //low = (low+high)/2;
else {
int* newV = |
|
l**********g
发帖数: 426 | 11 int get_two(int *nlist, int sum, int *n1, int *n2)
{
quicksort(nlist);
left = 0;
right = len(nlist) - 1;
while(right > left)
{
while(left < right && nlist[left]+nlist[right]
{
++left;
}
if (nlist[left]+nlist[right]==sum)
{
*n1 = nlist[left];
*n2 = nlist[right];
return 0
}
--right;
}
return 1;
}
change a little then u can find all pairs |
|
c*********7
发帖数: 19373 | 12 总体说，问题都不算难。但第一次电话面试感觉还是准备不好。另外，每次面试电话中
间都断掉了一次，可能是信号不好。
第一个人问得很细，TCP, UDP。然后问TCP如果丢了反馈信号怎么办，另外，package里
边数据大小怎么定义啥的。然后又问quicksort，最坏情况，怎么样做到最好，我说选
median，他说怎么选median?这个没答出来。接下来coding是整数位倒置。又问了一系
列数据流怎么选出k个最大的，我说用堆，然后问堆的具体步骤。可惜堆没仔细看，我
说了用小顶堆，每次比较根，然后再变换堆。感觉对方故意说话不清楚，声音非常低沉
沙哑，让重复的时候还是说的很含糊，跟念经一样。
第二个人就比较nice，上来先问了我简历一边一个research的东西。我讲了有15分钟，
接下来就说写个ring queue，结果听成rain。说不知道，给解释了几句，才发觉是ring
。不过写code的时候又按普通queue写的，提示了后改正，然后写了push的操作，提示
修改了一个pop的定义，问empty和full的情况怎么处理，test case，和multi thread
的时候怎么push |
|
q*********u
发帖数: 280 | 13 好像你这个起码是第二个人说起TCP和UDP的情况了，看来这种概念型的题目考到的很多。
k个大的话，觉得采用类似quick sort的那种分割，判断右边有没有k个是不是好一点。
一直很困惑，能不能用java写你的queue和multi－thread的题目,interviewer会不会因
为是
java, 他那里运行起来比较麻烦，高人指点一下哈。
总体说，问题都不算难。但第一次电话面试感觉还是准备不好。另外，每次面试电话中
间都断掉了一次，可能是信号不好。
第一个人问得很细，TCP, UDP。然后问TCP如果丢了反馈信号怎么办，另外，package里
边数据大小怎么定义啥的。然后又问quicksort，最坏情况，怎么样做到最好，我说选
median，他说怎么选median?这个没答出来。接下来coding是整数位倒置。又问了一系
列数据流怎么选出k个最大的，我说用堆，然后问堆的具体步骤。可惜堆没仔细看，我
说了用小顶堆，每次比较根，然后再变换堆。感觉对方故意说话不清楚，声音非常低沉
沙哑，让重复的时候还是说的很含糊，跟念经一样。
第二个人就比较nice，上来先问了我简历一边一个resea |
|
c*********7
发帖数: 19373 | 14 k个大他说输入是个stream不是array，所以不能用quicksort。heap应该是对的。
多。 |
|
d********t
发帖数: 121 | 15 看到竟然有人把这个东西做为面试题目
还有careerup 上的一些题目,
45分钟的面试, 20分钟让interviewee
写一个复杂算法, 难道都是天才? |
|
g***l
发帖数: 2753 | 16 面试者有病啊。这些SORT方法知道怎么回事，在什么情况下用就行了。 |
|
k*n
发帖数: 150 | 17 qsort的确应该20分钟内写下来吧。。。这么经典的东西，呵呵。。。 |
|
f*******r
发帖数: 1086 | 18 实在地说，如果之前复习准备过，20分钟之内应该是可以写出来的。 |
|
k*n
发帖数: 150 | 19 试了一下，用google doc写完，大概10分钟吧。
感觉已经太慢了，n多地方都想不起来细节 |
|
m**x
发帖数: 790 | 20 俺面试完的时候，傍边的俩老印还在讨论那个算法可不可以再优化，一个老印O(n*logk
),另外一个no，only O(n), only O(n)，让我想起了周星驰的一句话。
“呕，呕，呕，呕你妈个头，你再呕，我一刀捅死你！” |
|
S******a
发帖数: 862 | 21 ...
我面试就写过
感觉很快，10min
比较经典，练过几遍的缘故
而且我属于写code比较慢的类型
练习是王道 |
|
a***c
发帖数: 2443 | 22 if pseudo code is acceptable I think it's very reasonable. |
|
y**i
发帖数: 1112 | 23 没练习过要调试应该会花点时间，练习过的话就几行代码，理解意思外加记忆完全可以
5分钟内写下来，昨晚我练习写LIS的时候其中用到要sort，就尝试又写了一遍quick
sort。我觉得有些代码要写还真的很难，我看CLRS上面的RB-Tree的插入和删除，伪代
码都好长啊，如果要我当场code，那真是要死，就算是把伪代码放在旁边，估计怎么也
得花个2个小时吧 |
|
d********t
发帖数: 121 | 24 我是说不复习的情况下
背书的话, 估计有人
3分钟就搞定了, 不能
证明interviewee任何
东西 |
|
r**********n
发帖数: 97 | 25 I don't think I am a hacker or genius but I believe I can finish quick
sort in 15-20 mins by myself. I believe that you have to be able to do
that to find a good job for now. |
|
z****e
发帖数: 2024 | 26 i believe what you said.
but did you try heap sort?
write from scratch., how long does it take? |
|
|
l******c
发帖数: 2555 | 28 如果你事先背下来，4 分钟 就够了， 如果你从没学过， 45天能写出来就比 MIT
Standford 的CS 教授博士水平高， 45 年能写出来也算 above the average。 |
|
d*****a
发帖数: 38 | 29 如果不写代码只说思路就不难，基本思想是分而治之，每次挑一个数出来，小于它的放
左边，大于它的放右边。 |
|
d****2
发帖数: 6250 | 30 太弱了，就是一个经典的randomized algo，外加divide-and-conquer,还用背吗？最多5分钟搞
定，哈哈. |
|
k***e
发帖数: 556 | 31 写出这个就天才?
你对自己的要求也太低了
编程珠玑给出了code和很细致的讨论
记住loopinvariant就迎刃而解了
如果你明天就要面试 你现在应当能在10分钟内写出来
前五分钟算法分析 大概的idea 后五分钟编码
这还只是一般的速度 |
|
m**x
发帖数: 790 | 32 Really? 除非你除了面试没别的可做，很多在职的很忙吧，而且早就忘了这些东西了 |
|
j**l
发帖数: 2911 | 33 前提是我们站在那些巨人的肩膀上了。原创总是最难的，即使现在看来很简单的东西。
当然准备技术面试，不看书不做题，光靠自己想，估计没戏。要善于利用现有资源和前
人总结 |
|
k***e
发帖数: 556 | 34 现在的关键是恶性竞争
别人行你不行 怎么办?
骂两句然后继续k书吧 |
|
a*****e
发帖数: 1700 | 35 qsort [] = []
qsort (x:xs) = qsort m ++ [x] ++ qsort n
where m = [ a | a <- xs, a < x ]
n = [ b | b <- xs, b >= x]
一分钟不到。 |
|
z*j
发帖数: 42 | 36 老大, 你真牛, 不过如果事先知道算法(最简单的divide and conquer + partition),
确实5
分钟就可以写完了, 如果是要tune 的, 那就麻烦了. 比如要保证worst case nlgn. 我
还真被问
到过.
多5分钟
搞 |
|
|
c******f
发帖数: 2144 | 38 如果一个算法4分钟可以背下来 对于面试来说 平时不背真亏啊 |
|
s******s
发帖数: 3694 | 39 这玩意， 也就是面试新人有用， 实际工作中用到多少还真不好说。
比如说这个， 我从业以来就重来没用过 |
|
|
|
|
|
h**6
发帖数: 4160 | 44 是不是传说中的中值的中值
五个一组，每组取中值，然后找这些中值的中值作为分区的基准值，这样可以避免两边不对称的极端情况。 |
|
|
y**i
发帖数: 1112 | 46 能讲的更详细一些么？这个取中值不是要先排序才能去么（难道是我理解错了）？我只
知道CLRS上是取一个random元素做pivot
边不对称的极端情况。 |
|
a***9
发帖数: 364 | 47 5个分组的找法(recursively)，最后刚好可以做到O(n)时间内找到中位数，
你可以google一下 |
|
N**********e
发帖数: 32 | 48 Is the Erlang qsort implementation the most concise one?
qsort([]) -> [];
qsort([Pivot|T]) ->
qsort([X || X <- T, X =< Pivot])
++ [Pivot] ++
qsort([X || X <- T, X > Pivot]). |
|
c*********7
发帖数: 19373 | 49 不是用heap?k space。这个如果只是数组或stream数据的话应该是用heap。换成矩阵应
该也是吧O(nlogk)。也有人提过用quicksort的方法来做，但不一定能保证每次都能找
到最优piviot。 |
|
j**l
发帖数: 2911 | 50 貌似有好几种，原始作者给的那种在清华老严的教材有讲述，好像有一头一尾指针向中
间靠拢（这个模式也多次在各种解题中用到，比如找数组两个数的和为定值，比如
sweep一个01串使得所有0在前半段，所有1在后半段...)
大家觉得哪种简单好记? |
|
