s*********n
发帖数: 191 | 1 牛逼牛逼.......按照你的神逻辑，随便什么东西只要不是你原创的，都能套得上。
quicksort搞不清楚+神逻辑.... |
|
T*******e
发帖数: 4928 | 2 我是说，没有准备，现场想quicksort的难度，和你记个
简洁的回乡豆的难度是不一样的。
至于你想怎么理解，那确实不是我能控制的。 |
|
s*********n
发帖数: 191 | 3 quicksort这么基本和特别的in-space sorting， 你工作几年都能把原理忘记？
你在哪高就啊。退一步讲，工作几年的人，找工作，连这种算法书上极其经典的排序都
不看一下？
再退一万步讲：
何况说了很清楚，降低要求了，提示了要用partition，再提示把大小元素分两边，继
续提示给你额外空间，都不要求in-space了。剩下的就是写code而已。
工作几年了，这个都不会？这个恐怕不是不会算法吧，这是压根coding就是一坨屎吧。
你不会“工作”几年coding这个样子吧。 |
|
T*******e
发帖数: 4928 | 4 有意思，人家熟的回乡豆，你说人家是刷题刷的， “coding就是一坨屎”。
你自己熟的回乡豆，那就是永世难忘的原理. 当然了，没准你就是那种提示
一下就能创造出quicksort甜菜。这么简单的原理，你没先创造出来，那只是因为Hoare
他们没提示你。 |
|
T*******e
发帖数: 4928 | 5 "但是恰恰是那些算法一知半解只会背题刷题的人就偏偏不会写。
以前面shadow过个candidate，leetcode， epi里面再难的题目轮轮都能秒，一路高歌
猛进，到了最后一轮我朋友面，就让他写个quicksort就给过，结果写不出来。"
Read your own words. |
|
x****7
发帖数: 86 | 6 去年onsite ASE interview给了我一叠打印好的纸做题，目前只记得
C, data storage type,
nested try catch
然后让写了个quicksort,
一道design
ONSITE之后还追加了一轮电话。 |
|
r******l
发帖数: 10760 | 7 复杂度跟实际速度是两码事。quick sort平均来说是最快的。
? |
|
|
|
j****y
发帖数: 684 | 10 heapsort 很多修改index，在内存里跳来跳去
一堆cache miss，能快就鬼了。
? |
|
L***s
发帖数: 1148 | 11 “实践中”要考虑的情况可就多了，比如locality of reference、输入数据已经部分
有序、排序稳定性、内存不够要外排序、多机并行排序 等等，工程中的默认实用排序
一般都是mergesort的变种，也就是两轮或两轮以上的混合排序：最后一轮mergesort，
前面几轮找sorted runs to be merged的方法八仙过海各显神通（比如简单地插入排序
、双pivot快排等等）。
楼主明显是说面试的情况，不必考虑这么多工程上的因素。 |
|
C*7
发帖数: 234 | 12 iq350推荐的，感谢一下！面试的是个国人大哥，sort linked list，正好是我刷
leetcode时几个觉得特别烦的题之一，临时想的，用的quicksort，递归时估计有问题
，还没test到递归就到时间了，应该是挂了。。顺便问下，这题算是啥难度？是不是我
太菜了 |
|
C*7
发帖数: 234 | 13 迟到3,4分钟，扯了10分钟简历，然后我在merge sort和quicksort中间思考徘徊了10分
钟，写了15分钟，然后让我找个test case跟他一起过一遍，然后他又给个test case，
过到中间有问题我就改一改，然后正要进入递归时就到时间了，总共1小时 |
|
P*A
发帖数: 189 | 14 mergesort instead of quicksort |
|
h*d
发帖数: 19309 | 15 quicksort很麻烦，用merge sort应该会好很多 |
|
r*******k
发帖数: 1423 | 16 从头便利word
两两从头开始比较
abandon
abase
可以确认n在s前面, n-->s
这样遍历所有词之后，可以得到很多对关系
综合起来就是所有词序了
综合可以用类似quicksort
每次选一个pivot，就分成了2份
当然，划分会漏下很多
这时再选pivot，就会添加进一些新的
算法直到每个点都选作pivot之后，
应该就能得到一个确定的顺序
当然，还有要考虑的是
字典里 A和a的排序
空在前在后
比如
abandon
abandoned
可能还有数字
如果abandon和abandoned之间，有一个
abandonal，
我不知道这个词该排哪里。。。 |
|
m********t
发帖数: 13072 | 17 改完了，回来了，有功夫折腾这心理扭曲的丑女了， 尼玛，看看这两个贴，这厮居然
和这么多男人吵过架啊， 是不是现实里男人没有一个想上她的，她痒痒的难受啊，只
好到网上对着美女，再对着男性公民，来发泄A罩杯的郁闷了？
=====================================
发信人: TimeValue (逆水行舟), 信区: JobHunting
标 题: Re: 到底怎么了？很多面试来的居然连reverse一个链表都写不来
发信站: BBS 未名空间站 (Mon Mar 17 19:26:22 2014, 美东)
"但是恰恰是那些算法一知半解只会背题刷题的人就偏偏不会写。
以前面shadow过个candidate，leetcode， epi里面再难的题目轮轮都能秒，一路高歌
猛进，到了最后一轮我朋友面，就让他写个quicksort就给过，结果写不出来。"
Read your own words.
发信人: scorpionlin (女神杀手||女神のキラー), 信区: JobHunting
标 题: Re: 到底怎么了？很多面试来的居然连reverse一个链... 阅读全帖 |
|
m********t
发帖数: 13072 | 18 改完了，回来了，有功夫折腾这心理扭曲的丑女了， 尼玛，看看这两个贴，这厮居然
和这么多男人吵过架啊， 是不是现实里男人没有一个想上她的，她痒痒的难受啊，只
好到网上对着美女，再对着男性公民，来发泄A罩杯的郁闷了？
=====================================
发信人: TimeValue (逆水行舟), 信区: JobHunting
标 题: Re: 到底怎么了？很多面试来的居然连reverse一个链表都写不来
发信站: BBS 未名空间站 (Mon Mar 17 19:26:22 2014, 美东)
"但是恰恰是那些算法一知半解只会背题刷题的人就偏偏不会写。
以前面shadow过个candidate，leetcode， epi里面再难的题目轮轮都能秒，一路高歌
猛进，到了最后一轮我朋友面，就让他写个quicksort就给过，结果写不出来。"
Read your own words.
发信人: scorpionlin (女神杀手||女神のキラー), 信区: JobHunting
标 题: Re: 到底怎么了？很多面试来的居然连reverse一个链... 阅读全帖 |
|
s**x
发帖数: 7506 | 19 Google Princeton university algorithms , the first one, Robert Sedgewick etc.
This is really nice written book.
Trie,quicksort some tricky places are well explained.
CLRS authors donot know how to write books, seriously. |
|
o**********e
发帖数: 18403 | 20 【 以下文字转载自 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分钟内... 阅读全帖 |
|
i*********7
发帖数: 348 | 21 楼上的回答的基本差不多，我就归纳一下吧。
个人理解是这样的，这类型题目基本就两个思路
1. minHeap(PriorityQueue) O(nlogk) time o(k) memory
2. Ranking partitioning(Quicksort的一步) O(N) time no memory(递归call stack
算上的话另说)
minHeap的好处是你可以按序获取前k个，Ranking Partitioning则没有这个功能，只能
帮你找到第k个和前面k - 1个的那一块儿。根据题目采取不同得方案呗。 |
|
c*****m
发帖数: 271 | 22 来自主题: JobHunting版 - 求问一个题 难道不就是quicksort里面的partition么？求拍 |
|
p****6
发帖数: 3 | 23 来自主题: JobHunting版 - 求问一个题 my answer of C++ version. This question actually is a partial of the
quicksort method.
void reorder(vector& nums)
{
int len = nums.size();
int start = -1;
for(int i = 0; i < len; i++)
{
if(nums[i] < 0)
swap(nums[i], nums[++start]);
}
} |
|
c*****m
发帖数: 271 | 24 一直在本版看大家的面经，自己也贡献一下，自己在美国找工第一次面试，一血被拿走
了。。。
电面和onsite都是要写代码，同时要写test case，run出来结果。同时会问下复杂度
1. 电面
国人大哥，题目是找路问题，二维数组中0代表路，1代表墙，找从起点到终点的路并且
输出。
2. onsite
一面：中东人，题目：输入为一个文件，每一行格式：下级名字，上司名字。
输出：
>A
>>A的下级B的名字
>>>B的下级C的名字
>>A的下级D的名字
...
我的方法：
先建树，然后用inorder遍历树，将层序输出。代码写了近100行。
二面：国人大哥（英语很正，可能是ABC），人很nice。题目：输入：word字典，一个
string。输出：string是否可以由字典里面的word拼接而成
我的方法：先说的搜索的方法，然后让我先实现。实现之后，我说可以加入剪枝，加入
到代码里。并且说这样的话复杂度是O(N^2)的。后面和朋友聊，此题用DP也能解，也是
O(N^2)
三面：可能是版上有人说的ABC。题目：给一个二维平面上的点集，需要找一个点（不
是点集里面的点），使得其到所有点的曼哈顿... 阅读全帖 |
|
r****7
发帖数: 2282 | 25 小小的打击一下啊。。。我觉得你答的不算好
2. onsite
一面：中东人，题目：输入为一个文件，每一行格式：下级名字，上司名字。
输出：
>A
>>A的下级B的名字
>>>B的下级C的名字
>>A的下级D的名字
...
我的方法：
>> 先建树，然后用inorder遍历树，将层序输出。代码写了近100行。
typo? 这个怎么看也是preorder啊
二面：国人大哥（英语很正，可能是ABC），人很nice。题目：输入：word字典，一个
string。输出：string是否可以由字典里面的word拼接而成
我的方法：先说的搜索的方法，然后让我先实现。实现之后，我说可以加入剪枝，加入
到代码里。并且说这样的话复杂度是O(N^2)的。后面和朋友聊，此题用DP也能解，也是
O(N^2)
这个用trie的话，应该就是O(N + 字典size)的复杂度，所以depends on字典有多大
三面：可能是版上有人说的ABC。题目：给一个二维平面上的点集，需要找一个点（不
是点集里面的点），使得其到所有点的曼哈顿距离之和最小。
我的方法：所有的点的X坐标找中间值，所有的点的Y坐标找中间值（如果点数是... 阅读全帖 |
|
S********0
发帖数: 5749 | 26 从去年11月份开始，一直在本版向各位大牛取经学习。 最近刚刚接了M家的offer，job
hunting终于告一段落，虽然失败了很多，面试拿的也少，但对于一个非cs phd的背景
，已经很知足了。我背景是engineering，主要就是写code，做模拟，能转行主要是因
为学了些并行计算的东西，研究中写了大量的code，读了我们这个领域的一个famous
open source code，从professional programmer里学到了很多实践经验。 虽然有些经
验，但实际找工作工程中大多数公司理都不会理我，Airbnb一个recruiter跟我说过一
些，大概意思就是说每天收到太多简历，对于非CS学生，仅仅从从简历上很难看出什么
， 所以非CS学生争取能多修几门cs的课，把keyword放上去。不然就像我一样，就是内
推也被拒或者石沉大海，这里面包括了很多本版好心的人帮我内推的，有ebay，
linkedin, twitter, oracle 等。 在这里也想对帮助过我的人说声谢谢，以后我也会
帮助国人。
leetcode是从去年11月份yahoo是onsite失败后开始刷的... 阅读全帖 |
|
b**********5
发帖数: 7881 | 27 没有啊， 我一开始以为要输出path， 然后开始弄BFS。。。然后面试官问我有什么更
efficient方法。。 然后搞了半天， 他妈的来了一句， 如果不要path。。。
我想， 他妈的不要path， 不就是median？
然后我开始写quicksort得partition得median
然后面试官说， assume all JDK 1.6 的都有
然后我说， 你是说我可以arrays。sort？ 他说那你就用那个写。。。
我晕倒。。 然后写了， 然后他妈的他就拍照。。。
我想这是完蛋了。。 |
|
s****a
发帖数: 794 | 28 嗯 我错了 quicksort做到距离小于某个值就停下来。 |
|
g******n
发帖数: 10 | 29 你的第二种方法最坏情况下时间复杂度是 O(n^2)，不是 O(n)，因为不是每次都刚好把
数组分成长度相当的两半，最坏情况下两边长度分别是 0 和 n-1，所以 T(n) = T(n-1
) + O(n)，总的时间复杂度是 O(n^2). 另外这种方法也不叫 selection sort，而是
叫做 randomized-select，因为过程跟 randomized-quicksort 的 partition 非常相
似，期望时间复杂度是 O(n)。详细内容可以看 CLRS pp. 215, §9.2
Selection in expected linear time |
|
t*********r
发帖数: 387 | 30 我老今天面国人
叫他写个quicksort
结果这哥们愣是没写出来
我看这不对赶紧说算了我们写个函数看看input是不是2的指数
结果这哥们还是没写出来 |
|
|
s*******1
发帖数: 33 | 32 应该用quicksort + binarySearch |
|
s******x
发帖数: 417 | 33 quicksort 怎么看都是O(nlgn）啊。。。 |
|
h******e
发帖数: 52 | 34 来自主题: JobHunting版 - FB 面经 你的那个店面解答是不是用类似quicksort的方法？ |
|
j**7
发帖数: 143 | 35 来自主题: JobHunting版 - 刚跪的电面 2.) partial quicksort |
|
J*********a
发帖数: 50 | 36 来自主题: JobHunting版 - 刚跪的电面 quicksort返回前K，是不是可以用个pair（freq，num）进行sort，对比freq，最后返
回pair的num。 |
|
b******b
发帖数: 713 | 37 面了google/facebook/linkedin/two sigma/aqr/uber, 被uber/aqr据了。基本所有面
过的题：
hedge fund 1:
1. Write a function that takes as input integers P and Q and returns P to
the power of Q. Note any assumptions you make and the complexity of the
algorithm. We expect you to do better than O(Q).
2. Write a function that takes as input an array of 1 million integers,
such that 1 ≤ x ≤ 10 for every element x in the array, and returns the
sorted array. The sort does not need to occur in-place. Obviously you ... 阅读全帖 |
|
s**x
发帖数: 7506 | 38
Quick sort worst case O(n^2) heap sort worst nlogn.
但实际上sort 都是用Quicksort 做的。 |
|
发帖数: 1 | 39 背景：CS PhD + 1.5 years. 非CS行业的一个小公司骑驴找马。大概准备了七八个月的
时间吧，晚上回来陪娃睡了然后自己刷题。很不幸，还是全挂了。另外很多大公司现在
也不招opt身份的非new grad。FLA都没有给我面试。有时候想想，大概这种水平的CS
PhD就我一个了吧（呵呵）。还是喜欢写程序的，可是越来越觉得自己似乎并没有这方
面的天分。骑的驴也没积累到什么CS的经验，做了很多business相关的东西。感觉在这
里待得时间越久，自己的career荒废的越多。而且有了几年工作经验之后就会被问很多
design相关的东西，可是我的实际工作中也没涉及多少。用的也是那套软轮。从当年的
认为只要自己努力什么都能做到的少年，慢慢变成了如今已经习惯了生活会经常跟我开
玩笑的准大叔。身份也没有。PTO也差不多用光（每次都要从东海岸飞西海岸，然后面
试当晚红眼飞回来上班）。娃们还嗷嗷待哺。总是想不通，到底是哪一步走错了，才与
其他当初一起上学的小伙伴们的差距越来越大。不过我在帮助国人方面，问心无愧。只
要经过我手的国人来面试我们公司，我都给过了。 牢骚发了不老少，下面回归正题吧
。... 阅读全帖 |
|
G*******n
发帖数: 2041 | 40 刚开始自己写，调了半天没搞出来，后来仔细对照书上的code，发现有两个细微区别。
但是不解为什么必须要这么做，请大侠指教。
两个细微差别是在partition里：
int Partition3(int *a, int left, int right)
{
int pivot = a[(left + right) / 2];
while (left < right) //leetcode: while (left <= right)
{
while (a[left] < pivot)
{
left++;
}
while (a[right] > pivot)
{
right--;
}
if (left < right) //leetcode: if (left <= right)
{
int temp = a[left];
a[le... 阅读全帖 |
|
l*****a
发帖数: 14598 | 41 写一个用a[right]做pivot的版本吧...
另外你的问题自己拿几个例子试试... |
|
k***e
发帖数: 1931 | 42 qsort的partition我还是喜欢算法导论上的做法，拿第一个元素当pivot。反正取哪个
当pivot最优没有定论，面试的时候写成这样面试官也没法反驳。
一般来说partition就两个思路，一个是挖坑，左右两个指针，交替移动，不断挖坑填
坑，这个对两分比较形象，但是对于三分区间（小于，等于，大于）就有点难以理解了
，算法导论上面用的那个partition思路，对付两分三分都比较轻松。 |
|
G*******n
发帖数: 2041 | 43 不好意思，是cracking the coding interview里的code，见附件。我的问题是第13行
和第21行的等号 |
|
|
t******i
发帖数: 35 | 45 感觉原因是因为如果不enforce left > right, partition 就有可能left=right
or left>right . 这样后面处理也要分这两张情况
[在 GreenBean (绿豆) 的大作中提到：]
：刚开始自己写，调了半天没搞出来，后来仔细对照书上的code，发现有两个细微区别
。但是不解为什么必须要这么做，请大侠指教。
：
：........... |
|
|
h******k
发帖数: 810 | 47 quicksort不是浪得虚名的。
Comparator |
|
s**********g
发帖数: 14942 | 48 你这个完全得看application啊
time vs space tradeoff
search一般来说当然binary search是不错的
但hashset能搞出O(1)来，如果hash function很好的话
sort也要看要求啊
哪怕是algorithm，一般NlogN，但是mergesort和quicksort都有不同的应用
整数的话，甚至可以radix sort搞出O(N)
扯上结构的话，linkedlist就经常不是很好用，因为没有O(1) random access
那arraylist也许会比较方便
或者直接上heap
我觉得这种问题就是看你的理解深度，我不认为能简单一个回答解决，而应该看实际的
tradeoff |
|
C********s
发帖数: 278 | 49 美国土生土长的印度妹子，2014伯克利计算机系本科毕业，分给我们组，让我带。妹子
很漂亮，不像印度人，像波斯人，170cm。
我对妹子照顾有加，很快就成为无话不谈的朋友。我们公司是个三流公司，我的老板
director是个ICC过来的阿三，比较变态。今年7月我和妹子一起抱怨公司，两个人一拍
即合，准备跳。我给妹子介绍leetcode, 帮她开了扇门。她说怪不得她毕业的时候所有
公司电面都过不了，原来crack code interview远远不够啊。从此，我带她练题，可是
她毕竟起步晚，刷到现在也才100多道。基本是easy to medium level吧。phone
screen碰到LC原题，拿到了一流公司 onsite.
上周五onsite, 回来伤心地给我说过程，第一轮求两个linkedlist first
intersection，LC原题，妹子做过，用很怪异的解法，似乎不断把尾巴加到头上，给面
试官一说，面试官也懵了，给她很多hint, 最后跌跌撞撞用hashset做出。（my god
这题hashset都让用啊。我给妹子解释可以先算两个的长度，这样可以不用extra
sp... 阅读全帖 |
|
发帖数: 1 | 50 本来分享这些经验只想起一个抛砖引玉的作用，没想到真有一些兄弟要我分享这些工具
和所谓的“知识树”工具。没时间一一回信，所以在这里做统一回复。
首先，我说过工具太多了，你会用的工具才是自己的，所以你已经知道这些东西是干嘛
用的，上网搜呗。不是不想共享，而是恐怕那个你根本看不懂，呵呵。看过后你就知道
了，别拿板砖扔我啊。这是其中的一个自动Login和启动程序工具的视频，供参考。
https://www.youtube.com/watch?v=aX6aV7RzqCw
其次，关于知识树，这不是一个工具，就是你自己的个人总结，你可以总结成文档集，
代码集，工具集...... 这个东西没办法共享。我的做法是首先文档类都有自己的模板
，从项目计划，项目预算，风险评估，需求分析，设计到测试等等。比如说规模估算，
分几个模型，LOC经验法的，FP的，Cocomo的不同模板，每次都重新做太麻烦了，有模
板会省很多时间。再比如风险评估，如果没有模板，现分析有哪些因素太容易遗漏了。
说白了就是老板管你要东西，立马就能找到一套成熟的东西供你拷贝粘贴。代码就更是
这样了，我在正文中已经提到过了，成熟的代码总结成自... 阅读全帖 |
|
