y*********r
发帖数: 94 | 1 把quicksort的partition算法变形一下就可以了 |
|
l******c
发帖数: 2555 | 2 should be no solution, otherwise, quicksort become stable, big improvement |
|
s***h
发帖数: 662 | 3
就是你quicksort不是选一个pivot吗, 然后partition,
这个pivot的最后位置比如说是某个k, 那么它就是第k大(小)的元素.
这个partition就是O(n)啊. 当然这个位置未必是你找的,那么你再
继续在这个pivot的一边partition下去,最后总能找到你要的那个位置.
假定总是平分, n + n/2 + n/4 + ... = 2n. 所以线性时间.
不过我早上犯糊涂了. 那根本不是n*k, 那就是n, 因为你找到第k大的,
它右边的partition里面就是1-(k-1)大的, 所以那个k可以去掉. 但是
奇怪的是他也没有反应过来, 可能他猛一看,也觉得每个都n, 那么k个
就乘k也对. :-) |
|
u***q
发帖数: 21 | 4 昨天电话一面自我感觉很差，今天意外被通知获得电话二面机会。
本人非CS专业，全凭自学，前阵子在网上投了简历。Amazon联系我一面。我在同意之后
上本站看各位的面经，感觉自己根本不可能通过面试。不管怎样，从未有过任何CS面试
的我打算体验一把。
电话接通后，打完招呼让我就自己的简历介绍一下当前做的project。顺便了解了我并
非CS专业。接下来是CS方面的问题。
问：OOD的几个概念。
答（略）
问：喜欢什么排序算法，为什么。
答：quicksort，因为很多语言有现成的library，不用自己实现
问：复杂度是多少
答（略）
问：什么情况下是这个复杂度
答：average
问：worst情况下是什么复杂度
答（略）
问：什么样是worst情况
答（略）
问：什么其他算法可以避免这个
答：binary search（我脑子里搞起来了）
问：那个不是排序呀
答：哦，是呀，对了，可以用merge sort
然后出了一道编程题。我一上来张口就说，大家沟通不清。让我登陆collabedit。他
spell快了点，我没听清这个网址。不得已他给我email了那个地址。
题目是给一个数组的成员进行... 阅读全帖 |
|
j********x
发帖数: 2330 | 5 很多办法都可以
最简单的hashing
另一种是用quicksort的partition，每次看两边sub array的长度n，找到n满足n%3==1
，然后这个数一定在这一边，O(n) |
|
t****n
发帖数: 263 | 6 Well, what is the relationship between quicksort and bucket sort? what is
the complexity of quick sort. Bro? |
|
z****u
发帖数: 104 | 7 C version，求指正
int NextNumber(int i)
{
int max_length = 1;
int* digits = (int*) malloc(sizeof(int) * max_length);
/* break number down to digits */
int idx = 0;
while(i)
{
if (idx > max_length - 1)
{
max_length *= 2;
digits = (int*) realloc(digits, sizeof(int) * max_length);
}
digits[idx++] = i % 10;
i /= 10;
}
int length = idx;
/* find the break digit */
for (idx = 1; idx < length; idx++)
... 阅读全帖 |
|
K*****k
发帖数: 430 | 8 都是取第一个元素为支点, 哪个写得更好？
void quickSort1(int arr[], int left, int right)
{
if (left >= right)
return;
int pivot = arr[left];
int i = left;
int j = right + 1;
while (i < j)
{
do { i++; } while (i <= right && arr[i] < pivot);
do { j--; } while (arr[j] > pivot);
if (i < j)
swap(arr, i, j);
}
swap(arr, left, j);
quickSort1(arr, left, j - 1);
quickSort1(arr, j + 1, right);
}
===============================================... 阅读全帖 |
|
|
v*****k
发帖数: 7798 | 10 做两次quicksort？估计做一次也行不过得分别track word和数字的下标
in |
|
b*******y
发帖数: 232 | 11 quicksort找到第k个元素的同时，byproduct就是前k个元素了 |
|
f*******t
发帖数: 7549 | 12 bubblesort,quicksort,mergesort,countsort,heapsort
至少得知道这5种的空间、时间复杂度吧 |
|
w*******s
发帖数: 96 | 13 If the string is not the same length, my code will crash because of array
index out of boundary. Can you help find the bug?
//Refer Algorithm 4th, page 722
void exch(string &a, string &b)
{
string c = a;
a = b;
b = c;
}
int compare(int a, int b)
{
if (a
if (a==b) return 0;
if (a>b) return 1;
}
void ThreeWayQsort(vector &v, int low, int high, int d)
{
if (high<=low) return;
//3 way partition to handle duplicate
int lt = low;
int gt = h... 阅读全帖 |
|
w*******s
发帖数: 96 | 14 貌似与编译器有关。在G++下面运行没有问题，在VC下报异常。 |
|
v***a
发帖数: 365 | 15
Maybe here:
int pivot = 0;
if (d < v[low].length())
pivot = v[low][d]; |
|
i******t
发帖数: 798 | 16 没准备
算法很烂
你现在让我写个 quicksort 我要看半天书 才能回忆起来
哎 |
|
w**z
发帖数: 8232 | 17 要都能练出来，还要QA干吗？
一个QuickSort， James Gosling，不也写错了，好久才被别人发现嘛 |
|
H***e
发帖数: 476 | 18 这跟quicksort有啥关系？
从前往后一遍就行了吧，两个指针，一个指向有用的数据最后一个，一个current,如果
current不是target,就把此数据考向前面的指针 |
|
l***i
发帖数: 1309 | 19 Use 0 to partition your array, the same idea as partition for quicksort |
|
d********w
发帖数: 363 | 20 我记得linkedin有道题问
给个tree，让你把每个结点的值更新为自己子树的sum，
写个多线程版本，改怎么做么？
是不是还有并行的quicksort, mergesort |
|
r**********g
发帖数: 22734 | 21 merge sort并行性能很好，quicksort 不是那么好并行滴 |
|
d********w
发帖数: 363 | 22 我记得linkedin有道题问
给个tree，让你把每个结点的值更新为自己子树的sum，
写个多线程版本，改怎么做么？
是不是还有并行的quicksort, mergesort |
|
r**********g
发帖数: 22734 | 23 merge sort并行性能很好，quicksort 不是那么好并行滴 |
|
b******i
发帖数: 914 | 24 弱弱问一下，这个你在切分的时候，是不是按照quicksort里面的partition那样？
如果是的话，岂不是会打乱原来的顺序（因为partition是不稳定的）？ |
|
w****o
发帖数: 2260 | 25 我觉得 你说的不对。
你去研究一下，DNF不是stable,因为它跟quicksort如出一辙，都不是stable的。 |
|
s*********5
发帖数: 514 | 26 一百万个amazon product id，问过去一小时销售量top 10的(map-
reduce)
这个还要用到map-reduce, 答错方向了吧。
这是从N个数中找最大的k个数，修改一下quicksort, 或者用heapsort, with a heap
of size of k.
heap build time: Nlog(k)
sort time: klog(k)
here N=1,000,000, k = 10,
total operation less than 4 million, 2G clock, 也就几个微秒的事情。
数据量不上T，单次map计算时间少于1分钟，都没必要map-reduce |
|
s*********5
发帖数: 514 | 27 注意是O(Nlog(K)), here log(K) = 4.
比InsertSort还是要快一点。
用QuickSort的修改版，就是只排最大的10个。推而广之就是找第K个大的数，一个应用
是找median, 每次都扔掉一半数据，因此平均复杂度是O(2N)。
为了提高worst case performance, 用median of medians算法。 自己搜吧。 |
|
S******t
发帖数: 151 | 28 刚写错了...
selection algorithm复杂度是expected O(N)...
当然这里K=10, O(NK)也是O(N)罢了....
median of medians那个就算了，constant factor巨大无比
in practice randomized quicksort never degenerates |
|
i*********7
发帖数: 348 | 29 用quicksort的思路的话，就会有不stable的结果。。。 |
|
w****x
发帖数: 2483 | 30
不知道面试官什么意思， 没太大必要用，比如quicksort当样本很小的时候用
insertsort是为了避免产生很多递归小节点， 这里就直接下来了没多大必要， 不知道
interviewer要什么结果， 可能interviewer随便说说的吧 |
|
G**********s
发帖数: 70 | 31 简而言之，推荐两本都买都看。两本侧重点真的不一样，如果有时间还是读CLRS吧，那
本才是圣经，木有时间就看后者，很快就能看完，相比CLRS，这本太短了而且易读，一
天可以看1章。我半个月看完的 =）
CLRS总的来讲，可以负责的告诉你，里面木有ERROR，代码放心的看，绝对不会错，因
为后面一般都跟着详细的证明； 2版伪代码，3版C代码，我都看过，课后题做的不多，
以前上课的HW、QUIZ、EXAM后就木有继续做过其他的。
ALGORITHM IN XX系列的书很有趣。看Robert的书，你会感觉这个老师，仿佛在和你一
对一的聊天，用平凡的话语解释如何”实现“这些数据结构以及算法，注意，他主要告
诉你如何实现，如何继续优化，那些方面可以入手优化。还会每章开头结尾解释上下章
之间的关系，告诉你这一章之所以出现，是因为上一章不能解决XX，要解决XX我们可以
OO，BOTTOM UP实现了这个MERGESORT之后，告诉你如何继续优化，比如可以SKIP小范围
内的迭代，回头再用QUICKSORT来理一遍，。容易理解，但是，他介绍的优化的方法就
那么几种，看了几章后，有点感觉啰嗦。
推荐PRO... 阅读全帖 |
|
w***y
发帖数: 6251 | 32 bst找k-th元素是什么题？ 怎么做？ 我战战兢兢去搜了半天， 找到的都是unsorted
array怎么找k-th, 答案基本都是说用quicksort里面partition的方法 |
|
b***e
发帖数: 1419 | 33 我认为有O(n^2)的做法：
先把s1和s2转化成index表示：
tiger -> 12345
itreg -> 21543
第一个string总是正序的，第二个是乱序的。
那么问题转化成在s2里面找pivot index(在quicksort意义上的)。具体的说，一个
pivot index前面的数都<=这个index，它后面的数都>这个index。在上述例子中，
pivot index是1(counting from 0)。
找一个pivot index需要的时间是O(n)。找出所有的需要O(n^2)。 |
|
l****r
发帖数: 689 | 34 一个月前面的, 还算新鲜.感觉板上的V的面经不多. 虚拟机的
虽然最后拿到了offer, 但是很曲折. 猎头先把名字弄错了, 把我拒了, 后来HM发现后,
联系我的时候, 我已经签了其他的公司了, 错过了.
pp1:
1. print tree nodes by level (not bet)
2. given two sorted array, find kth smallest. (o(k) is not good enough)
pp2:
1. knowledge about lock, mutex, linux, kernel
2. threading related
3. write consumer and producer
4. some tasks like this:
a -> b (to do a, need to do b first)
b -> c,d,e
c - >
d -> a
e -> f
f -> e,a
Design a st... 阅读全帖 |
|
K*****k
发帖数: 430 | 35 典型的Hoare双向扫描Partition法一般都会在左右设置sentinel, 或者对左右边界检测
下标越界，这个非典型的代码却不用。
int Partition(int arr[], int left, int right)
{
int pivot = arr[left + (right - left) / 2];
while (left <= right)
{
while (arr[left] < pivot]
left++;
while (arr[right] > pivot]
right--;
if (left <= right)
{
swap(arr, left, right);
left++;
right--;
}
}
return left;
} |
|
e***l
发帖数: 710 | 36 if (left <= right)
应该是if (arr[left] >= arr[right])
正确性是显然的，左边不大于pivot,右边不小于pivot |
|
K*****k
发帖数: 430 | 37 代码来自CareerCup那本书
CLRS和编程珠玑都喜欢讲解Lumoto版本的Partition
编程珠玑提到的Hoare版本Partition，每次都需要检测右边界 (i <= u)，
看去效率稍低
...
t = x[L]; i = L; j = U + 1;
loop
do i++; while i <= u && x[i] < t
do j--; while x[j] > t
if (i > j)
break;
swap(i, j)
end loop
swap(L, j)
... |
|
t*********7
发帖数: 255 | 38 quickSort nlgn
两个INDEX,一前left, 一后right,求和看等不等于指定数.
比指定数大right--,比指定数小left++,等于输出,left++
直到两个指针相差为1 |
|
t*********7
发帖数: 255 | 39 quickSort nlgn
两个INDEX,一前left, 一后right,求和看等不等于指定数.
比指定数大right--,比指定数小left++,等于输出,left++
直到两个指针相差为1 |
|
d**e
发帖数: 6098 | 40 it depends.
主要是要看你的code是做什么，不是为了追求效率就一定传引用或指针，而是需要看
code里面有没必要修改arg,或者修改arg对整个method需要的结果有没影响。
比如quicksort那两个left和right，我觉得用不用引用应该都一样的，因为不影响后面
的结果。但比如说逆序打印数组, 就不需要传引用。
void printArray(int[] array, int index, int length)
{
if(index >= length)
return;
printArray(array, index+1, length);
cout << array[index] << " ";
} |
|
r**********g
发帖数: 22734 | 41 就是考试。比如：写个quicksort，马上给我写出来 |
|
l****c
发帖数: 782 | 42 void kAwaySort(int s[], int n)
{
quickSort(0,k-1);
int i = k;
while(i
merge(s, i-k, i-1, i) //merge s[i] into the subarray s[i-k,i-1];
i++;
} |
|
P*********c
发帖数: 35 | 43 ic，多谢大牛。
那有什么最优解吗？我能想到的就是搞两个数组，一个存word在list里的position，另
一个存integer的position，然后分别对两者quicksort。 |
|
d**********6
发帖数: 4434 | 44 这似乎是命中注定的一份工作。上周一被告知我们公司被收购了，老板换人。上周三新
老板从Durham过来交接。我一开始很慌乱，不知道新老板有什么想法的，于是就开始投
简历。结果上周五刚刚交接完毕，新旧老板刚离开办公室，新公司就打电话来通知面试。
这周二面的试，职位是programmer，主要是做web interface。最近面试过几次这样的
职位，都考js的很多细节，有的公司问的太细了，没准备好；有的公司看沟通，没搞好
，砸过好几次。于是这次我就细细的准备js。结果一上来就发现，面试准备错了，考的
居然是基础算法，三道题：1.searching,2.sorting,3.find median。我当时一下子蒙
了，binary search还记得，但sorting全忘了。教科书上是有三种方法的，但已经有5
年没看过了。坐下来仔细啊仔细想，结果居然把教科书的内容全想起来，先想起
Quicksort,然后想起insertion, 最后连bubble sort都想起来，顺利通过。
对方昨天给的offer，但工资不及预期，争取了一下，今天谈拢。刚好今天是我宝贝的
满月，我实在是爱死我这个宝贝了！
... 阅读全帖 |
|
i*********7
发帖数: 348 | 45 电面的确太水了
就问了我三个超基本的题目：binary search的复杂度，mergesort的复杂度，
quicksort的复杂度。。。。。=。=
然后就让我做题去了。。 |
|
i*********7
发帖数: 348 | 46 电面的确太水了
就问了我三个超基本的题目：binary search的复杂度，mergesort的复杂度，
quicksort的复杂度。。。。。=。=
然后就让我做题去了。。 |
|
c******w
发帖数: 1108 | 47 quicksort不是也可以in place吗? |
|
c******5
发帖数: 84 | 48 来自主题: JobHunting版 - 请教一道题 How to use quicksort? Thanks. |
|
d*******d
发帖数: 2050 | 49 sigh,怎么会这样。好吧，详细说一下面试这些intern的过程吧。
这是个algorithm & coding section（也就是说还有其他section).
2个coding题，题目是公司指定的，顺序问法面试官自己掌握。
1个小时。
最开始5分钟，自我介绍，说说你上过的课，说说你最喜欢的课程（有一半人说的是算
法和数据结构），做过的project等等。
然后5-10分钟，问做过的project，看看是不是真参与了，弄懂了。到目前为止，大多
还不错，个别人很腼腆，问一句答一句。
然后10-15分钟，第一个coding题，10到20行。很简单，没有任何tricky,考察是否能用
简历上claim会的语言编程。版上的混2个星期都该没问题。但是，目前为止，没见过一
个bug free的。一半以上的人，完全不考虑任何edge case。
这个时候，因该已经过去大约25分钟了。
第二个coding题，也是版上反复出现过的经典入门级题目，是个人都该会。要用到
recursion。coding 10-15行。
为了引导candiate的思路到recursion上来，我会花10分钟问问他们学过的... 阅读全帖 |
|
e******o
发帖数: 757 | 50 quicksort 需要前面的后面的swap, 是不稳定的 |
|
