h**6
发帖数: 4160 | 1 我觉得最好的是CLRS上介绍的，从左边开始保持一个大于基准数的段，慢慢增长或者向
右移。 |
|
|
h**k
发帖数: 3368 | 3 O(m+n)这个写程序不应该出错，merge two sorted arrays/lists，add two long
integers presented by strings，都是同样类型的题目。
即使是O(log(m+n)）这个算法，也就难在partition那个部分，自己写过quicksort的应
该都能写出来吧
个人感觉，如果这个code题你还觉得没有把握做到一次性写对，建议再多练几个coding
题，直到编译、unit test都通过。 |
|
f**********w
发帖数: 93 | 4 google intrasort.
If I remember it right, it begins with quicksort, but if it could not finish
in O(nlogn), it switch to heapsort. |
|
f*********5
发帖数: 576 | 5 find the combination of items in input[] with the sum of tartget.
static int count=0;
quicksort(input,0,size-1);
void GetCombinationNumber(int input[],int used[],vector&vec,int
size,int target,int *count)
{
if (target==0) { *count++; return; }
for(int i=0;i
{
if (used[i]==1)continue; //we donot want to use them
repeatedly
if ((vec.size()>0)&&(vec.back()>a[i])) continue; //we will use
the items in
order so that we can avoid duplicate
if (t |
|
I**A
发帖数: 2345 | 6 这“只对10个数排序”还是没有说出你为什么favor O(n^2)吧
我说了几个。。
1. If O(nlg(n)) requires space, while O(n^2) doesn’t
2. If O(nlg(n)) is difficult to understand and implement, while O(n^2) is
easier
3. If O(n^2) has a general running time less than O(nlg(n)) instead, like
Quicksort
他后来提了一点 what about if there are multiple machines...
欢迎讨论～～～ |
|
w******g
发帖数: 67 | 7 刚开始看书，理解不够深刻，哪位大侠给科普一下。
1. 这三个算法都平均复杂度都是 (nlgn), 该怎么选择用哪一种算法呢？
2. 看到以前有例子说n非常大的话用merge sort，几台机器分别sort，然后再merge，
这是为什么
呢？merge sort 不是需要而外的空间～n 吗？这时候用quicksort 会不会好一些？
多谢。 |
|
c**********e
发帖数: 48 | 8 我一开始也是focus on algorithm
但interviewer 很快提醒我 这是 design question 不是algorithm question.
可以选择任意语言 主要是问如何实现
for example, 可以用C++ STL的 quicksort 排序
要考虚的是如何设计类，如何传递排序的对象，参数等等 |
|
s*****n
发帖数: 5488 | 9 个人看法：
先定义出book对象，sort algorithm对象（应该是个decorator,就是可以pipeline到另
外一个alg对象上），然后需要定义less than, 定义adapter到STL quicksort。
public void sort()
{
call adaptoer method or obj from i to n.
for (i = k; i< booklist.count; i++)
{
if key[i] = key [j] continue;
else
if (mydecotor is not null)
mydecortor.setvalue(j, k);
mydecortor.sort();
}
大概框架应该是这样。 |
|
|
o*****e
发帖数: 99 | 11 quicksort doesn't work here.
"numbers should be in the same order they appear" |
|
b*****e
发帖数: 474 | 12 there is a textbook classic of "median of medians of 5", which finds the
median in O(n) worst case time but have no practical use;
practical solution is to use quick-selection, based on the quicksort
partition idea and is average O(n), as mentioned upstairs. Worse case can
typically be avoided by some techniques of choosing the partition value,
such as the "median of three"
search trees, sorting, heaps - these are mostly O(n lg n) solutions and very
practical ones too.
For integers, don't forget... 阅读全帖 |
|
g*********s
发帖数: 1782 | 13 来自主题: JobHunting版 - fb 面经 the problem in the phone is dp, just like Fibonacci?
2, 5, 6 are all classical.
4, i know little about web, so no comments. :)
1, i'm not sure about what rule the pattern follows. can u elaborate it?
3, in case of 2-color only, partition() in quicksort()? so for 3-color
case, u treat two colors as the same first, then distinguish them in the
2nd pass. avg time is O(N) while space O(1). is this good enough?
.)
.
running time
太
种,
然后 |
|
g*********s
发帖数: 1782 | 14 来自主题: JobHunting版 - fb 面经 我孤陋寡闻了。不错。不过反过来按quicksort的partition应该也能得个80分吧？ |
|
h***n
发帖数: 276 | 15 算法是先要找最大数，然后利用其中的信息找到第二大数，quicksort中的partition没
有这层含义把
我只是想知道怎么用O(1)的空间实现n+log(n)-2的复杂度，因为好像没有人讨论 |
|
j*****u
发帖数: 1133 | 16 你是对的，worst case是O(n^2)，所有的左节点都是叶节点，这时候BFS时间会好些
但是tree是balanced情况下还是DFS略好
这个很像quicksort在worst case下fallback to mergesort :)
current_ |
|
d********w
发帖数: 363 | 17 简单型：sort 0， 1数组， O(n)时间，可以使用头尾两个pointer，
i = 0;
j = n-1;
while( i < j){
while( array[i] == 0 && i < j )
i++;
while( array[j] == 1 && j > i )
j--;
if ( i < j )
swap( a[i], a[j] );
}
如果是排序0，1，2数组，就是dutch flag问题， http://en.wikipedia.org/wiki/Dutch_national_flag_problem，跟quicksort中的partition类似
void threeWayPartition(int data[], int size, int low, int high) {
int p = -1;
int q = size;
for (int i = 0; i < q;) {
if (data[i] < low) {
swap(data[i], data[++p]);
++i;... 阅读全帖 |
|
v*******7
发帖数: 187 | 18
solution #1:
using hashtable/hashmap that keeps track of (key, value) pairs where key is
the
element in array while value is the frequency.
scan each element e in the array, if e does not exist as a key in hashtable,
insert
(e, 1) into hashtable. If e exists in hashtable, move to the next one until
the end
of the array.
iterate the key in hashtable and store them in the old array.
Time Complexity: O(N), Space complexity: O(N).
solution #2:
sort the array first (quicksort, O(NlogN) in time on av... 阅读全帖 |
|
g*********s
发帖数: 1782 | 19 this has been discussed before here.
if there does exist such an algorithm, we will have a stable quicksort()
algorithm.
worked it |
|
m****v
发帖数: 84 | 20 很可能会有一个在Palo Alto的实习机会，公司愿意给房子住两人间，或者给点钱自己
找。如果自己
找的话，可能会有交通不便、租金贵等问题，但是会自由很多。请问大家觉得哪个选择
比较合适呢。
谢谢。
同时在此汇报碰到过的面试题若干（来自不同公司的面试环节），抱歉之前没有整理过
，如果有时间
会把它们整理好再发一下。
算法、数据结构：
Prefix Tree
Kth element
BST serialization
quicksort
heap, heapsort
M links, find the Kth element
判断二叉树合法
按层打印二叉树
矩阵找最大和子矩阵
设计：
任务管理
交通系统
语言：
dynamic_cast, static_cast, ...
virtual function
exception in destructor
malloc, dealloc
polymorphism
regex in perl/python/etc.
数学、概率：
Monte Carlo: give an example and explain
Fibonacci series... 阅读全帖 |
|
c**s
发帖数: 43 | 21 十年经验码农。
今天专门过来on site，面的还是码农。
第一个人一上来就问了sorting, 可惜我一时脑筋短路，想起飞机上看的hacking
google interview说quicksort worst case是n^2, 就说mergesort。
结果让我实现的时候，在merge的那块钻了牛角尖，非要写个in-place的merge。
回来搜索一下才发现in place merge不简单。。
最后剩下七分钟的时候，他说再问一个，看够不够时间。
这时在这里混的好处终于体现出来，题目还没写完，就发现是找最大sum的sub-array。
沉吟（回忆）一下，就把想起来的算法写一下。希望能过关。
后面几个面得都很普通，有几个答不出来，人直接给了答案。
不过人基本都是面带微笑，和蔼可亲。还一起玩了一会乒乓球。
最后面ceo，问search engine怎么判断misspelled words, recommend correct words
，好像也答得不好。
机票钱报销是当场就给了张cheque。面的人都挺客气的。说不定有戏。
大家有知道LA码农工资水平的，介绍一下吧？
是一个刚拿到... 阅读全帖 |
|
a****s
发帖数: 9 | 22 用quicksort 的idea, 找一个pivot, 然后partition, 扔掉有3n个elements 的
partition, 如果两个partition都有3n个elements, 那么pivot就是要找的element. |
|
r**d
发帖数: 316 | 23 答的不太好
1：过去项目
2：一些java概念，this, super, synchronized
3:排序，QuickSort方法，binary tree方法，
4：OOD 家具店的问题。（这题没答好，觉得没抓住想问的点，现在事后考虑可能应该
用design patterns的套路）
5: 一个巨大的文件，找出电话号码（regular expression, grep)
6：考虑一个StringToInt函数，估计用户会有什么样的输入，期待什么样的输出。
7:Coding, 写一个函数返回不大于输入的所有素数，email交回。 |
|
S*********r
发帖数: 5693 | 24 你看现在考的这些算法什么的，面还这么广，有哪个PhD都能用到的，不准备你能马上就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能马上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort什么的，也不一定能保证一遍就写对吧。
所以我觉得PhD问这些题真是不能体现出来能力。问本科生的确不错，面很广，看你学的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多年不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得很make sense，但是问什么三连击，最大正方形之类的就不make sense了。很多面试题如果没有提前准备过，很难在短短的时间内想出来，结果就跟我前面说的一样，招进去很多人都是不务正业，整天做题的。
up |
|
f*****n
发帖数: 646 | 25 严重同意, 不过话说回来, 真有能力, 也愿意为google面试准备几个月, 那些题基本也
能搞定.
上就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能
马上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort
什么的，也不一定能保证一遍就写对吧。
学的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多
年不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得很
make sense，但是问什么三连击，最大正方形之类的就不make sense了。很多面试题如
果没有提前准备过，很难在短短的时间内想出来，结果就跟我前面说的一样，招进去很
多人都是不务正业，整天做题的。 |
|
f****4
发帖数: 1359 | 26 那个idea只是在连续整数差一个，两个的情况下才比较合适
这里套的话不合适：题目没说char[]放的东西连续
并且要求in-place，那么用bitmap应该也是不合要求的（？？）
如果能放进内存，可以用变形的quicksort来做
Partition好之后
a[0]x a[i+2]>x ..
. a[j]>x
交换 a[j]<=>a[i]; a[j-1]<=>a[i-1]...a[j-k+2]<=>a[i-k+2]
设置j=j-k+1 (重复的元素被交换到了数组尾部，并且不再参与下一次的递归)
继续
最后得到的数组即为无重复数组+尾部所有的重复元素
将重复元素清空即可 |
|
S*********r
发帖数: 5693 | 27 我看我身边PhD拿到好offer的不少都是不干正事，整天做题准备面试的，那些被老板压
榨天天熬夜干活的有的反而很惨，毕业后要花几个月甚至半年来准备这些狗屁东西然后
才能找到工作。
你看现在考的这些算法什么的，面还这么广，有哪个PhD都能用到的，不准备你能马上
就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能马
上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort什
么的，也不一定能保证一遍就写对吧。
所以我觉得PhD问这些题真是不能体现出来能力。问本科生的确不错，面很广，看你学
的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多年
不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得可以
算是make sense，但是问什么三连击，最大正方形之类的就不make sense了。很多面试
题如果没有提前准备过，很难在短短的时间内想出来，结果就跟我前面说的一样，招进
去的题目答得好的很多人都是不务正业，整天做题的。 |
|
c****n
发帖数: 21367 | 28 取决于你面试的职位
如果你是去面试lead scientist，那么公司不会考你什么quicksort, BST啥的
如果你是去面试software engineer，公司当然考这些，毕竟是招收熟练工么
ph.d.读完本来就应该去做研究，做发考题，面试基层工种有劣势是必然的 |
|
J******t
发帖数: 1945 | 29 同感。不过既然改变不了现实，还是多做面试题吧。
压榨天天熬夜干活的有的反而很惨，毕业后要花几个月甚至半年来准备这些狗屁东西然
后才能找到工作。
上就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能
马上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort
什么的，也不一定能保证一遍就写对吧。
学的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多
年不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得可
以算是make sense，但是问什么三连击，最大正方形之类的就不make sense了。很多面
试题如果没有提前准备过，很难在短短的时间内想出来，结果就跟我前面说的一样，招
进去的题目答得好的很多人都是不务正业，整天做题的。
一个多线程的题，这样有什么意义呢？从公司的角度来说，找个本科生不是更经济么，
如果PhD的方向跟公司project的方向不一样的话，很可能还不如本科生好用呢。那为啥
这些公司还要招个PhD多付那么多钱呢？如果说是看中了PhD的研究能力和长远的潜力，
... 阅读全帖 |
|
s*******t
发帖数: 224 | 30 这都不满，那hedge fund 和 IB
不是更离谱？
压榨天天熬夜干活的有的反而很惨，毕业后要花几个月甚至半年来准备这些狗屁东西然
后才能找到工作。
上就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能
马上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort
什么的，也不一定能保证一遍就写对吧。
学的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多
年不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得可
以算是make sense，但是问什么三连击，最大正方形之类的就不make sense了。很多面
试题如果没有提前准备过，很难在短短的时间内想出来，结果就跟我前面说的一样，招
进去的题目答得好的很多人都是不务正业，整天做题的。
一个多线程的题，这样有什么意义呢？从公司的角度来说，找个本科生不是更经济么，
如果PhD的方向跟公司project的方向不一样的话，很可能还不如本科生好用呢。那为啥
这些公司还要招个PhD多付那么多钱呢？如果说是看中了PhD的研究能力和长远... 阅读全帖 |
|
r********3
发帖数: 2998 | 31 反问一句，一个做search的公司，找一个图像处理的Phd，如果基本多线程都不会，那
招进去有啥意义？连自己公司的平台都无法融入，招进去有意义吗？有木有？？？
一般招PhD的公司，各个方面都要问的。基本专业技能，研究能力都要问。如果基本的
算法，网络协议，cache, 数据库技术都不了解，那只能说明这个人PhD连现代计算系统
都不了解，那大家还上本科干啥？
公司招人，都是要干活的。如果基本功不扎实的话，估计够呛。这不是招PhD。不是随
便一个搞数学，搞物理的，就能随便混进去来，transfer一点数学公式就可以混的地方。
压榨天天熬夜干活的有的反而很惨，毕业后要花几个月甚至半年来准备这些狗屁东西然
后才能找到工作。
上就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能
马上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort
什么的，也不一定能保证一遍就写对吧。
学的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多
年不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得可... 阅读全帖 |
|
l**b
发帖数: 457 | 32 你可以试试thoughtworks，我觉得面试这么多家公司，就这个公司的面试最好玩，而且
我个人的观点也最全面。而且是到现在为止我觉得真的学到了东西的一次面试。
压榨天天熬夜干活的有的反而很惨，毕业后要花几个月甚至半年来准备这些狗屁东西然
后才能找到工作。
上就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能
马上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort
什么的，也不一定能保证一遍就写对吧。
学的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多
年不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得可
以算是make sense，但是问什么三连击，最大正方形之类的就不make sense了。很多面
试题如果没有提前准备过，很难在短短的时间内想出来，结果就跟我前面说的一样，招
进去的题目答得好的很多人都是不务正业，整天做题的。
一个多线程的题，这样有什么意义呢？从公司的角度来说，找个本科生不是更经济么，
如果PhD的方向跟公司project的方向不一样的话，很可... 阅读全帖 |
|
g******7
发帖数: 1532 | 33 dejavu
同样现象你没见过?
考T.G出国和埋头苦干实验的人?
压榨天天熬夜干活的有的反而很惨，毕业后要花几个月甚至半年来准备这些狗屁东西然
后才能找到工作。
上就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能
马上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort
什么的，也不一定能保证一遍就写对吧。
学的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多
年不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得可
以算是make sense，但是问什么三连击，最大正方形之类的就不make sense了。很多面
试题如果没有提前准备过，很难在短短的时间内想出来，结果就跟我前面说的一样，招
进去的题目答得好的很多人都是不务正业，整天做题的。
一个多线程的题，这样有什么意义呢？从公司的角度来说，找个本科生不是更经济么，
如果PhD的方向跟公司project的方向不一样的话，很可能还不如本科生好用呢。那为啥
这些公司还要招个PhD多付那么多钱呢？如果说是看中了PhD的研究... 阅读全帖 |
|
y*******d
发帖数: 1674 | 34 那你说的phd找的是coding工作吧，类似engineer？
很多phd平时很努力发paper，增加research背景的 毕业找research方面的工作(做research是不会问coding问题的。)，不是
靠几个月准备面试就可以的
其实phd毕业如果找不到research相关的而找coding的工作真的还不如读了ms就出来工作
努力是有回报的 真的不用埋怨太多 你在这里发贴抱怨的同时 人家说不定在用功做实
验呢
压榨天天熬夜干活的有的反而很惨，毕业后要花几个月甚至半年来准备这些狗屁东西然
后才能找到工作。
上就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能
马上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort
什么的，也不一定能保证一遍就写对吧。
学的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多
年不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得可
以算是make sense，但是问什么三连击，最大正方形之类的就不make sense了。很多面
... 阅读全帖 |
|
J**********y
发帖数: 1831 | 35 MSFT, GOOG本来job description就是要MS，你有phD非要找MS job还怪别人把你当MS对
待？
如果真想搞research，就去面试faculty，或者MS research，保准不会问你任何coding
问题。
压榨天天熬夜干活的有的反而很惨，毕业后要花几个月甚至半年来准备这些狗屁东西然
后才能找到工作。
上就做出来么。比如说一个做系统的人，你问他字符串的什么操作，不花点时间准备能
马上写出来么，就是那些做纯算法的，如果不准备叫他马上写个quicksort, mergesort
什么的，也不一定能保证一遍就写对吧。
学的扎不扎实，基本都是本科课程里面的东西。PhD很多就是本领域的专家，课都很多
年不上早就忘记了。你如果问做系统的人cache怎么设计，多线程什么机制，我觉得可
以算是make sense，但是问什么三连击，最大正方形之类的就不make sense了。很多面
试题如果没有提前准备过，很难在短短的时间内想出来，结果就跟我前面说的一样，招
进去的题目答得好的很多人都是不务正业，整天做题的。
一个多线程的题，这样有什么意义呢？从公司的角度来说，找个本... 阅读全帖 |
|
n********5
发帖数: 323 | 36 来自主题: JobHunting版 - 一道算法题 三个quicksort，一起merge
就三个array，，不要搞那么复杂。。。 |
|
j***r
发帖数: 69 | 37 1. write a comparator function for character comparison according to the
reference string. This comparator will be used in partition function of sort.
2. quicksort |
|
g***s
发帖数: 3811 | 38 quicksort is not a stable sort.
sort. |
|
|
|
|
|
h***o
发帖数: 30 | 43 Expected complexity是O(nlogn), partition很精简常数小， in-place, 每次逐个扫
数据
(cache miss少) |
|
s********x
发帖数: 914 | 44 // MaxHeap: heapArray starts from index 0
public static void heapSort(int[] a){
// Trickling Down in Place: start at node n/2-1, the rightmost node
with children
// O(n/2*log(n))
for (int i=(a.length/2-1) ; i>=0 ; i--)
trickleDown(a,i, a.length);
// remove max from heap and insert it at the end
// O(n*log(n))
for (int i= a.length - 1; i> 0; i--){
int max = a[0];
a[0] = a[i];
trickleDown(a,0, i... 阅读全帖 |
|
b*******h
发帖数: 53 | 45 QuickSort will sort it： 342,34,34. read reversely, result is 3434342 |
|
a**********2
发帖数: 340 | 46 来自主题: JobHunting版 - 问道排序题 可能average是O(nlogn)就可以了吧
我当时给的解法就是O(n^2)
对i<- n to 1
找到1到i里面最大的值arr[j]然后reverse(j),reverse(i)
明显他不满意，后来说quicksort，选第一个或者最后一个做pivot好像不行，如果题目
改成reverse(i,j)就好了 |
|
q****x
发帖数: 7404 | 47 is it possible?
if yes, how?
if not, why? |
|
g***s
发帖数: 3811 | 48 yes. since getting the median is O(n) and you can you the median to do
partition. |
|
q****x
发帖数: 7404 | 49 you mean use that worst case O(n) get_median() algorithm? cool. |
|
l***i
发帖数: 1309 | 50 Although in practice O(n)-median algorithm carries a large constant so will
likely defeat the small constant advantage of quick-sort compared to other O
(nlogn) sorting algorithms. |
|
