|
|
K*****k
发帖数: 430 | 3 你开始就直接说堆的方法，不要提Quicksort那个。我记得Quicksort的partition法一
般是用来找第k个元素，而不是找前k个元素。 |
|
S**I
发帖数: 15689 | 4 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Aug 30 00:32:06 2011, 美东) 提到:
Given an array A of positive integers. Convert it to a sorted array with
minimum cost. The only valid operation are:
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element
☆─────────────────────────────────────☆
chenpp (chenpp) 于 (Tue Aug 30 00:37:57 2011, 美东) 提到:
my 2 cents:
允许额外花费O(n)空间么。。。
允许的话就不停地减数组中所有元素的值，减一次计数器加1，遇到减到0的就删掉，把
当前计数器值放入新开的等大... 阅读全帖 |
|
w****o
发帖数: 2260 | 5 sunlight365,
你的回答：
“这是从N个数中找最大的k个数，修改一下quicksort, ”
到底怎么修改quicksort就能解决这个问题？
能不能说说你的想法？
谢谢！ |
|
w****x
发帖数: 2483 | 6
到这种程度快不快只能测试, 不好推测. Insert sort在小于100个数的情况下比
quicksort还快. 后来我改了方法也不用insertsort了, 用10个元素的数组, 每次只需
要遍历10个元素然后如果比最小的大再替换, 实际上替换的概率也很低. Select
algorithm每次会swap很多元素, 开销在这个地方, swap比compare要大. 当然如果k足
够大用select划算, 可以设计成像stl::quicksort那样根据k值调整alg的方法 |
|
d*******e
发帖数: 24 | 7 方法和quicksort差不多。
在quicksort里，选择一个pivot value，完成partition，这时候有大于pivot value和
小于pivot value的两个序列，都需要递归的用quick sort排序。
如果要求第k大的数，只要判断一下该数在哪个序列里，然后对那一个序列再找第k'个
数就可以了。
该方法平均时间成本是O(n)，如果选pivot时增加一些限制，可以保证最坏时间成本是O
(n)。 |
|
x*******6
发帖数: 262 | 8 quicksort空间是O(1)吧，mergesort有最坏情况？一直都是O（nlogn）时间O（n）空间
吧。
磁盘上mergesort有优势。heapsort效率和quicksort相当但是多些额外操作所以一般没
人用吧。 |
|
d**********x
发帖数: 4083 | 9 作为一个补充，stl的sort是introsort，除了这里提到的对quicksort的优化以外，还
可能会在quicksort递归深度过深的时候切换成heapsort
median-
factor |
|
k****r
发帖数: 807 | 10 lz, 关于sort的特点，ls说的都很好了。
对于你的困惑about lgn space of quicksort，我个人认为是quicksort没层递归需要
为stack存下partition point，这样一层一层的，需要lgn space。
我自己的理解，不知道对不对。 |
|
l*******b
发帖数: 2586 | 11 log (n!)本来就和 n log(n)是同阶的呀，有什么问题？
heapsort本来速度就和quicksort差不多， quicksort的hidden factor小一点，
locality好一点吧 |
|
h****e
发帖数: 928 | 12 Quicksort的题目我也出过。如果对方忘记的话，我会大致解释一下，
然后叫写代码。因为是学过的，所以提示以后应该能够回想起来。
当然难点在细节。
其实Quicksort的思想在不少题目中都可以用到，例如找第K大的数。 |
|
p*****9
发帖数: 20 | 13 Intern面试：
电面：
是阿三问的，不过人很好，我不会的一直在提示我，问了C++和Java的区别，C++中
virtual function，java当中的Garbage collection，更喜欢哪种语言，为什么等，又
问了两道题：
1. 两个sorted list，求相同的部分（值相同）
2. n！后面以多少个零结尾。
Onsite：
1面是两个人轮流问问题。第一个人问hashtable的实现，怎么实现hashcode（不会。。
），写个函数判断两个字符串是否是anagram，用了一个大小为256的数组，先遍历++,
后遍历--， 写完后又优化。第二个人让写quicksort，让比较mergesort和quicksort，
哪种情况用哪个最好。然后又问了leetcode的原题，sort colors，要求in place
2面第一个人问哪个数据结构比较熟，然后自己写一个函数，我说了bst，他让我写find
函数，然后又问delete如何delete。问malloc的时候需要size，free不需要size，为什
么。第二个人问travel tree by level。后面又有... 阅读全帖 |
|
d******l
发帖数: 98 | 14 In my opinion, quicksort() is better because the CPU cache thing, has better
locality of reference -- the next thing to be accessed is usually close in
memory to the thing you just looked at. In java, java.util.Arrays.sort()
uses quicksort(), while java.util.Collections.sort() use mergesort().
As for heapsort(), it doesn't build a real heap(tree-heap), it is array/
arraylist in fact, through the index jumping, give us an illusion of a heap.
By the way, bless for myself recent onsite. ^_^ |
|
l********7
发帖数: 40 | 15 我记得Java里的Arrays.sort()同时实现了quicksort和mergesort，如果是primitive
type就用quicksort，如果是对象就用mergesort，所以应该是nlogn |
|
s*********n
发帖数: 191 | 16 Quicksort 还有反转链表这些都太基础了吧，lz面得没错啊。
理解快排算法的话，根本不需要复习什么。就算退一步讲，代码里面有点小bug，边界
条件小于等于还是小于之类的，出现一点bug，面试官也未必一眼看到啊，就算看到了
稍微一提示不就完了。
但是恰恰是那些算法一知半解只会背题刷题的人就偏偏不会写。
以前面shadow过个candidate，leetcode， epi里面再难的题目轮轮都能秒，一路高歌
猛进，到了最后一轮我朋友面，就让他写个quicksort就给过，结果写不出来。
提示降低要求只要写个partition函数，还是写不出来。
再降低，开辟额外数组让他实现partition，还是写不出来。就这么提示了都不会。
其实这种基本功的题目还是可以刷掉很多刷题背题水货的。 |
|
s*********n
发帖数: 191 | 17 你这是精神不太对吧。
叫你写quicksort，你写不出来，可以理解你以前算法没学好，或者后面又没好好复习
，搞不懂partition的原理。
现在说了只要把一个数组按某大小排到两侧，并且可以借助额外空间，完全告诉你了。
这个跟quicksort的要求几乎已经没关系了吧，也不需要什么提示了吧，剩下就是叫你
写。给你一个数组，给你一个值，把小的方前面，大的放后面，再给你借助额外空间。
正常人都能写出来吧。
你这个写不出来，coding不是一坨屎是什么?莫非阁下也是这个水平？拼命辩护？
Hoare |
|
s*********n
发帖数: 191 | 18 别整这些酸不拉几的话，这个根本就不是partition的原理，partition是要求in-space
的，现在是开辟数组，随便你玩，这个应该会manipulate array的都能做。自己水平烂
就低调点，
别胡搅蛮缠地说酸话。
也别整什么天外飞仙的发现原理不原理的，就事论事学习快排是每个cs出身的人
都经历过的，没什么所谓答案不答案的。我没说过什么发现新原理的本领。就事论事：
1） 在校生该不该懂quicksort？ 2）工作上班族不懂quicksort那什么都告诉你了，
coding skill是不是起码得有？
还是有不少基础不错的人在hunting job, 你少在这里误导别人。基本几大公司都面过
这种题，还不少见。 |
|
f******h
发帖数: 45 | 19 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
o*******s
发帖数: 1375 | 20 只能面出这个人有没有准备过. 我参加了很多招人面试,面试时候的表现和进来的表现
没有任何相关性.
我一个同事是清华本,硕,博的CS毕业.有一次我问他会不会白板写quicksort.他说他写
不出.连quicksort到底怎么做的都忘了.我绝对没夸张. |
|
b*****c
发帖数: 1103 | 21 quicksort写不出那quickselect也不会啰？quickselect比较常见，等于quicksort只递
归其中一半。 |
|
k******a
发帖数: 44 | 22 我的思路，靠谱么？
第一轮，是利用binary search的思路。对于中点元素，如果比正常重点元素大，说明
缺少的元素在左边。否则在右边。如此递归。
第二轮，第一题，按照quicksort partition的思路。或者直接双指针也行，head找非
负元素，tail找负元素，然后兑换。直到head==tail。
第五轮，我觉得的可以用java的comparator排序。对于任何两个整数，运行这三个函数
（2-3次调用）就可以找到这两个整数的关系。然后Arrays.sort()就可以。当然，如果
手写，就用quicksort，那么就是nlogn， 空间O（1）
这个题对于时间复杂度要求是什么？ |
|
发帖数: 1 | 23 居然真有面试要现场写quicksort/quickselect，很复杂啊
[在 rubberban (小笨猪) 的大作中提到：]
:两周前去面试碰到类似的题目 （一个搜素系统有N个搜素输入 找出最小SUB SET
:CONTAINING 5%的搜素） 临时想出用quickSORT 的partition， 但写代码还是不太熟练 |
|
h*********n
发帖数: 11319 | 24 “刷的不精”？
刷题就能通过下面这种国女么？
“一轮domain knowledge: 一国女。这个吐一下槽。此interviewer显然早上和人刚吵
完架，进来后面若冰霜，而且面有怒色。在我讲述的过程中，不停地打断我的思路。对
一些明显正确的知识点，问我“is it correct?" or "are you sure?". 我并没有企
望等到什么hint,但我明明on the right tracks的时候，将我打断，想将我扭到别的方
向去。咳，比三哥三姐还狠。”
“要吐槽的是这个女面试官竟然不懂quicksort算法，非得说我中间过程有一个
duplicate的number，是不对的，还说我举的例子是coincident correct, 遇到其他例
子就不行了，我和面试官解释quicksort要找的是pivot的正确位置，中间有一个
duplicate没关系，最后会用pivot replace那个duplicate number，当时还有一个
shadow，这个人在旁边说“我感觉code是对的”，这个女面试官还在纠结，最后我用一
个general case说服了她，结果她竟然... 阅读全帖 |
|
x*j
发帖数: 271 | 25 我当然知道有O(n)的算法去找到k个最大的数，是quicksort的partition部分部分的一
个改版，在最开头我已经说的很清楚了。
这个问题的原因在于大于和小于的关系还在，但等于的关系没了。
举例说明 假设有3个单词a b c
a和b之间的 edit distance是 1 b和c之也是1，但a和c之间可能就是2，如果我们定义
edit distance是1或者0的都是不可分的，但二以上就有一个大小于关系，我们可以说a
这个topk的问题是要求返回一个子集，对于没有返回的任何元素，这个子集里都存在着
k个比它大的，但这个子集可以存在和它约等于的元素。因为对于元素a和b，如果a约等
于b，那么比a大的元素不一定比b大。所以这个返回的集合是可能包含不只k个元素的。
我很欢迎有帮助的讨论。对于问题不理解我也很愿意继续澄清，但是请注意的是这里没
有等于只有约等于，所以那些对于integer的排序的算法比如quicksort mergesort
heapsort，它们的复杂度不适用于这个问题。
我知道mergesort的复杂度是O(n^2logn)在这个 |
|
T**********n
发帖数: 480 | 26 quicksort beat heapsort是因为Cache Locality减少了缓存抖动
要说更深刻的原因可以说机器的结构针对quicksort做了优化 |
|
l******e
发帖数: 470 | 27 X=50我都不用你的算法
人家前几楼的heap就扫一遍
我还没见过quicksort不行，非得要线形算法的应用。 谁作过实验，quicksort比线形
扫一遍慢多少？ |
|
h**o
发帖数: 548 | 28 明白了。
the basic idea of QUICKSORT' 是说 每次循环都 recursively sort the first part
, iterately sort the second part.
QUICKSORT' |
|
t****t
发帖数: 6806 | 29 你这就接近于胡搅蛮缠了
通常的说法, quicksort 平均O(nlogn),最差O(n^2), radix是O(n), hash也是O(n)
如果要谈细节,都可以找出毛病来
quicksort worse case O(nlogn)?可以啊,加一个大常数你干不干
radix, 样本空间很大怎么办
hash, 找不到好的函数怎么办 |
|
X****r
发帖数: 3557 | 30 There is really no point writing Python code like that.
If you like functional style, just use Haskell:
q s = case s of{[]->[];(x:xs)->q [y|y<-xs,y=x]}
Which does almost (except for the case the the pivot element is repeated)
exactly you do here and is more readable.
Note that this 'quicksort' (both the Python and the Haskell version)
is not really a quicksort, i.e. it does not sort in-place, thus has
quadratic space and time cost. |
|
ET
发帖数: 10701 | 31 1, 2有啥区别。 都有quicksort了，1为啥还用bubble？
quickSort). |
|
w*********n
发帖数: 439 | 32 quickSort是对一维数组进行： quickSort(Comparable[] c)
bubbleSort是对二维数组进行：bubbleSort(Comparable[][] c) |
|
k*********g
发帖数: 791 | 33 随便地扔进集合c；
然后用quicksort；
a 世界上没有比quicksort更快的了；
b 任何玩雕虫小技的，都是浪费时间；；； |
|
t********t
发帖数: 5415 | 34 之前去一个公司面试被design manager一个问题恶心坏了...
一块内存，1-port，1k*n bit（大小无所谓），都是整数，设计电路对这些数排序（方
法不限）。
之前从没想到过会有这样的问题...一下把我问晕了。版上的估计很多人让用C写个
quicksort眼睛都
不眨一下就能写出来，但是用verilog写呢？
我当时只想到了bubble sort...才疏学浅啊，当时quicksort原理搞得还不是太懂。画
白板的时候
预计4个n-bit flop加一点counter就能解决。
高手们有什么好的实现方法？google了一下相关文章似乎没看到太好的解决方案... |
|
g****t
发帖数: 31659 | 35 2个数比较大小，然后大的换到前头，这个用点数字电路实现很容易吧。
每次比较两个数，换位,冒泡法。
你是这么做的吧？ 这个我觉得挺好的。
quciksort不查书我也不会......
之前去一个公司面试被design manager一个问题恶心坏了...
一块内存，1-port，1k*n bit（大小无所谓），都是整数，设计电路对这些数排序（方
法不限）。
之前从没想到过会有这样的问题...一下把我问晕了。版上的估计很多人让用C写个
quicksort眼睛都
不眨一下就能写出来，但是用verilog写呢？
我当时只想到了bubble sort...才疏学浅啊，当时quicksort原理搞得还不是太懂。画
白板的时候
预计4个n-bit flop加一点counter就能解决。
高手们有什么好的实现方法？google了一下相关文章似乎没看到太好的解决方案... |
|
o**********e
发帖数: 18403 | 36 【 以下文字转载自 SanFrancisco 讨论区 】
发信人: onetiemyshoe (onetiemyshoe), 信区: SanFrancisco
标 题: 面完fb,结果已经出来了，share下被拒的原因（请转jobhunting版 (转载)
发信站: BBS 未名空间站 (Wed Nov 19 21:05:36 2014, 美东)
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 面完fb,结果已经出来了，share下被拒的原因（请转jobhunting版
发信站: BBS 未名空间站 (Tue Nov 18 20:46:44 2014, 美东)
考了下古，发现这位哥们的转贴，基本可以确认是一个人，基本可以确定这个是我被拒
的原因
同样迟到了大概5分钟，闲扯了十分钟左右，然后read4,确实很简单，但是给的题目非
常不清楚，所以完全没有考虑buffer里面留下的部分，中间我问了除了输出int,需不需
要考虑读出的字符放在哪里，被他含混过去了。自己没做过底层的东西，竟然也没有看
到这个帖子，细节基本一致，因为题目很简单，所以35分钟内... 阅读全帖 |
|
G***i
发帖数: 150 | 37 我用c写过一个 从文件中读取 一百万个数字 用quicksort 排序的 你要要的话 私信我
我可以发给你 你改改就可以用 |
|
s******r
发帖数: 2876 | 38 c不是自带qsort吗？
我用c写过一个 从文件中读取 一百万个数字 用quicksort 排序的 你要要的话 私信我
我可以发给你 你改改就可以用 |
|
S***a
发帖数: 934 | 39 一到这种时候就只能把杨82拉出来
不过客观来说杨82的东西比quicksort牛多了 |
|
w****n
发帖数: 25644 | 40 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 面完fb,结果已经出来了，share下被拒的原因（请转jobhunting版
发信站: BBS 未名空间站 (Tue Nov 18 20:46:44 2014, 美东)
考了下古，发现这位哥们的转贴，基本可以确认是一个人，基本可以确定这个是我被拒
的原因
同样迟到了大概5分钟，闲扯了十分钟左右，然后read4,确实很简单，但是给的题目非
常不清楚，所以完全没有考虑buffer里面留下的部分，中间我问了除了输出int,需不需
要考虑读出的字符放在哪里，被他含混过去了。自己没做过底层的东西，竟然也没有看
到这个帖子，细节基本一致，因为题目很简单，所以35分钟内完成，全程毫无任何提示
，所有问他的问题基本上都回答得非常模糊，非常有误导性。之后让问fb问题，自己回
答了六周的ramp 什么着，我明明没问。。。最后拍照
我比下面这位哥们唯一好点的地方，我记下了这个人的名字的大致发音,自己查了下
linkedin, 应该是R--it---u---raj Kir---... 阅读全帖 |
|
j*********h
发帖数: 21 | 41 1. number all the element in the original array, in growing sequence (O(n)).
e.g. original array is [3,2,1,0,1,2], after numbering, it became [(3,0),
(2,1),(1,2),(0,3),(1,4),(2,5)].
the "number" of each element is the corresponding position it is in the
original array.
2. after numbering, sort the new array according to their original value ,
using quicksort. (O(nlogn))
e.g. after sorting, [3,2,1,0,1,2]->[0,1,1,2,2,3]. ( I didn't list the "
position" of each element here).
3. find the lo |
|
m******9
发帖数: 968 | 42 问题1： 2个超大file，memory容不下，都是unsorted，假设里面全是integer。如何找
出2个文件
中的重复部分？
我看到的一个答案是：
step 1: external merge sort F1 (file 1): 将原文件分成若干个temporary
smaller
files, 对每个temporary small file进行quicksort，然后对所有smaller files 进行
multiple-way merge sort, 重新合并成一个sorted big file.
step 2: traverse F2, binary search F2's each element in F1,
step 3: 能找则是common element，如果找不到则继续读取判断下一个element
问题2： 1个超级大文件，unsorted，里面都是string。如何找出所有的anagram？
这个题没什么思路
求教了，谢谢 |
|
c*********n
发帖数: 1057 | 43 啊，突然想明白了，就是变种的quicksort |
|
s*******a
发帖数: 42 | 44 对的就是，quicksort的变种，时间复杂度nlogn |
|
w*********l
发帖数: 1337 | 45 1. merge sort空间开销大。而且insertion sort对于基本有序的数组排列是很快的，
比如quicksort最后一步就是用insertion sort
2. 应该就是两种overlap。想看实现去爬visual studio或者glibc的代码。
用i
overl |
|
B*****g
发帖数: 34098 | 46 ding
135K + 10-25% Bonus （奖金时好时坏， 大致在10% 到 25% 之间）
linkedList loop. how to do HashMap implementation...
让现场写过QuickSort, binary Search现场写过）
金10
真是比你们在Google, Amazon... 容易多了）
。(我在本版获益良多， 发个个人心得， 给大家分享）
以， 有了经验， 跳槽或者转成EMPLOYEE就容易了。
， 好找纽约的工作。 |
|
s*****i
发帖数: 355 | 47 没错，在街上面java developer，java.collection, concurrent, gc要非常熟。数据
库就是store proc
135K + 10-25% Bonus （奖金时好时坏， 大致在10% 到 25% 之间）
linkedList loop. how to do HashMap implementation...
让现场写过QuickSort, binary Search现场写过） |
|
w******k
发帖数: 917 | 48 楼主就是有offer了
那个叫什么下山如行云流水？
我们这些还在挣扎找工的，整天患得患失的，
135K + 10-25% Bonus （奖金时好时坏， 大致在10% 到 25% 之间）
linkedList loop. how to do HashMap implementation...
让现场写过QuickSort, binary Search现场写过） |
|
w********p
发帖数: 948 | 49 非常感谢。给大家多一个思路。如果在加州这样的机会会不会少一些。
收藏。
135K + 10-25% Bonus （奖金时好
时坏， 大致在10% 到 25% 之间）
linkedList loop. how to do HashMap
implementation...
让现场写过QuickSort, binary Search
现场写过） |
|
r********g
发帖数: 1351 | 50 如果没有重复元素，我的idea：是不是可以用quicksort那样的，比如根据某个random值分两段，
然后比较两边长度是不是相等，然后再分。。。直到剩下一个为止，这样的好处是中间就可以
return了。
为什么我的mit格式这么奇怪，都改两回了。。
45 |
|
