s***h
发帖数: 662 | 1 贡献一点面经.
我准备的时间还不够, 今天这二面有点忐忑.面我的人是个白人小伙子, 说话很快, 不
停的提附加问题.
1. how to pick first k maximum numbers in an array.
me: most straightforward, sort then pick, nlgn + k
he: ok...
me: better way, quick select, n * k
he: what is quick select, why is it linear time?
me: talking...
he: what if array is way bigger than the memory, can this work?
me:...yes...but slower due to swapping...
he: anything better?
me: ...
我不太明白他想问什么,所以没答上这一问,最后他问我有什么问题的时候我就
问了他,他说,你可以构造一个size k heap. then it is nlogk. 哎, 我当时真
没往这想. 还是准备不够.
2. write a c program to reverse a string, read to me.
me: reading...
he: how do you test? what parameter will you pass to it?
me: char *, but can't be string literal
he: what is string literal? why can't?
me: talking...
he: what if there are unexpected results, say garbage char?
me: ..? the trailing \0 is not right after the valid char?
he: no, let's say they use this to sort german, and garbage char.
me: it should work?
he: what is char set of german?
me: oh, you are talking about unicode, 2 bytes per char?
he: what would that affect your program?
me: just swap 2 bytes instead of 1 then.
he: ok...
3. design a card game in c++
这个题很无聊,我也不玩牌,只好一边想一边写,
class card
{
...
int suit,
int rank,
...
}
class app
{
struct { card mycard,
card * next;
}
...
}
这个不work,而且实际很傻,把next定义在card里不就完了.
当然他就问了,说你这个如果超过两张不就不行了,我才发现
card里面需要有个 card * next, 我跟他说了他就ok了.
4. explain mutex & deadlock, how to avoid deadlock.
这个标准概念题. 然后我们讨论了下第一题的那个heap. 之后就挂了,
刚好一小时. 他说如果有下一轮,那么可能是onsite.
不知道吉凶如何. 心里七上八下. 不过还是自己准备的时间太短.
过一段应该状态有提升. 诸位有人这些天拿到他们的onsite吗? | p****z
发帖数: 55 | | P**********c
发帖数: 3417 | 3 他们不是开始用google doc了吗。看来很多人还是要朗诵code. | c*****l
发帖数: 879 | | S**I
发帖数: 15689 | 5 a variant of quick sort
【在 c*****l 的大作中提到】
: 呃 哥们能展开讲讲quick select么？
| P**********c
发帖数: 3417 | 6 n*k的话，用一个array存k个数即可。
【在 S**I 的大作中提到】
: a variant of quick sort
| v***n
发帖数: 5085 | 7 sounds like you did a good job. | s***h
发帖数: 662 | 8
就是你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也对. :-)
【在 c*****l 的大作中提到】
: 呃 哥们能展开讲讲quick select么？
| d***n
发帖数: 65 | 9 so you know quick select is faster than heap select, not as what the
interviewer said. | s***h
发帖数: 662 | 10
Usually it is, but, not really when your array is 1000 times bigger than
memory. if you use quick select, then you will sometimes need to read the
chunk that you read before, that will cause disk seeking and be expensive.
On the other hand, his heap select only needs to read the whole array
sequentially, this is actually the highest efficiency for disk access.
what do you think?
【在 d***n 的大作中提到】
: so you know quick select is faster than heap select, not as what the
: interviewer said.
| c**********e
发帖数: 2007 | 11 Quick Selection:
选target个最小的。最终目的是，使a[0], …, a[target-1]为最小的。因为是递归调用子函数，子函数对数组的一部分a[low], …, a[high]操作。
#include
using namespace std;
#define swap(x,y) { int z=x; x=y; y=z; }
int low_n(int a[], int low, int high, int target) {
int pivot; int mid=(low+high)/2;
if(a[low]<=a[mid])
{
if(a[high]<=a[low]) pivot=a[low];
else if(a[high]<=a[mid]) pivot=a[high];
else pivot=a[mid];
} else
{
if(a[high]<=a[mid]) pivot=a[mid];
else if(a[high]<=a[low]) pivot=a[high];
else pivot=a[low];
}
// cout << "pivot=" << pivot << endl;
int i=low, j=high;
while(i
{
while(a[i]
while(a[j]>pivot) j--;
if(i
{ swap(a[i],a[j]);
i++;
j--;
}
}
if(high-low <=1) return 0;
if(i>j) { int k=i; i=j; j=k; }
if(i>=target) {
int x=low_n(a,low,i,target);
} else {
int y=low_n(a,j,high,target);
}
return i;
}
int main() {
int a[20]={4,3,2,8,9,10,1,5,7,6,11,12,13,14,15,16,17,18,19,20};
cout << low_n(a,0,10,8) << endl;
for(int i=0;i<20;i++) cout << a[i] << " ";
return 0;
} | q****x
发帖数: 7404 | 12 where's the 1st one?
【在 s***h 的大作中提到】
: 贡献一点面经.
: 我准备的时间还不够, 今天这二面有点忐忑.面我的人是个白人小伙子, 说话很快, 不
: 停的提附加问题.
: 1. how to pick first k maximum numbers in an array.
: me: most straightforward, sort then pick, nlgn + k
: he: ok...
: me: better way, quick select, n * k
: he: what is quick select, why is it linear time?
: me: talking...
: he: what if array is way bigger than the memory, can this work?
|
|
