盛传的某新加坡朋友的求职信 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

盛传的某新加坡朋友的求职信

盛传的某新加坡朋友的求职信# Joke - 肚皮舞运动

j*e2012-04-18 07:04

1 楼

1. http get和post的区别，追问到了具体http包里面的内容
2. 对web 安全的了解
3. 数据库问题，建表记录employee，department等
4. int数组，找出和为零的数字对（老题了）
5. int数组，kth largest number （老题也有春天)
6. web问题，用户登录这些怎么在客户端记录（答曰饼干），后面一直追问
到php的session

G*o2012-04-18 07:04

2 楼

p*22012-04-18 07:04

3 楼

第五题空间复杂度什么要求？

【在 j********e 的大作中提到】

: 1. http get和post的区别，追问到了具体http包里面的内容
: 2. 对web 安全的了解
: 3. 数据库问题，建表记录employee，department等
: 4. int数组，找出和为零的数字对（老题了）
: 5. int数组，kth largest number （老题也有春天)
: 6. web问题，用户登录这些怎么在客户端记录（答曰饼干），后面一直追问
: 到php的session
:

s*s2012-04-18 07:04

4 楼

赞 red handed

j*e2012-04-18 07:04

5 楼

面试官没说，我说建个大小为K的heap，然后worst case
是O(N * logK)，他就说OK了，没往下问。

【在 p*****2 的大作中提到】

:
: 第五题空间复杂度什么要求？

h*n2012-04-18 07:04

6 楼

LOL

w*x2012-04-18 07:04

7 楼

第5题用selection algorithm吧

s*y2012-04-18 07:04

8 楼

lol

【在 G***o 的大作中提到】

j*e2012-04-18 07:04

9 楼

median of median 那个?

【在 w****x 的大作中提到】

: 第5题用selection algorithm吧

x*i2012-04-18 07:04

10 楼

there's still no vacancy because the position was eliminated upon the
manager's death~~~

【在 G***o 的大作中提到】

w*x2012-04-18 07:04

11 楼

int GetKth(int a[], int n, int k)
{
assert(a && n > 0 && k <= n);

int* p = a;
int m = n;
while (k > 1)
{
int nMid = m/2;
swap(p[0], p[nMid]);

int i = 1;
int j = m-1;
while (i < j)
{
if (p[i] <= p[0])
i++;
else if (p[j] > p[0])
j--;
else swap(p[i], p[j]);
}

swap(p[0], p[i]);

if (i >= k)
m = i;
else
{
p = a+1+i;
m -= i+1;
}
}

return p[0];
}

st2012-04-18 07:04

12 楼

death certificate...

j*e2012-04-18 07:04

13 楼

没看懂，介绍下思路？
感觉while（k>1)会导致死循环吧？好像while里没有改变k，也米有break

【在 w****x 的大作中提到】

: int GetKth(int a[], int n, int k)
: {
: assert(a && n > 0 && k <= n);
:
: int* p = a;
: int m = n;
: while (k > 1)
: {
: int nMid = m/2;
: swap(p[0], p[nMid]);

c*e2012-04-18 07:04

14 楼

Dear Applicant,
We're sorry to tell you that there is still no vacancy available. You just
misunderstand the cause-and-effect relationship between the death of manager
and vacancy. In fact, it is the elimination of the position caused the
death of the manager. 你懂的.

【在 G***o 的大作中提到】

w*x2012-04-18 07:04

15 楼

刚才随手写的, 改正:
int GetKth(int a[], int n, int k)
{
assert(a && n > 0 && k <= n);
int* p = a;
int m = n;
while (k > 1)
{
int nMid = m/2;
swap(p[0], p[nMid]);
int i = 1;
int j = m-1;
while (i <= j)
{
if (p[i] <= p[0])
i++;
else if (p[j] > p[0])
j--;
else swap(p[i], p[j]);
}
swap(p[0], p[j]);
if (i >= k)
m = i;
else
{
p = a+1+i;
m -= i+1;
k -= i+1;
}
}
return p[0];
}

w*12012-04-18 07:04

16 楼

LOL

w*x2012-04-18 07:04

17 楼

k忘缩小了, i <= j 不是 i < j, 和p[j]交换不是p[i], bug啊~~

w*z2012-04-18 07:04

18 楼

功课做到家了

【在 G***o 的大作中提到】

j*e2012-04-18 07:04

19 楼

看明白了。如果pivot选的很倒霉，worst case会到O(N^2)?
一般再用median of median来选pivot，那就麻烦了

【在 w****x 的大作中提到】

: 刚才随手写的, 改正:
: int GetKth(int a[], int n, int k)
: {
: assert(a && n > 0 && k <= n);
: int* p = a;
: int m = n;
: while (k > 1)
: {
: int nMid = m/2;
: swap(p[0], p[nMid]);

w*g2012-04-18 07:04

20 楼

the position is "terminated"

manager

【在 c******e 的大作中提到】

: Dear Applicant,
: We're sorry to tell you that there is still no vacancy available. You just
: misunderstand the cause-and-effect relationship between the death of manager
: and vacancy. In fact, it is the elimination of the position caused the
: death of the manager. 你懂的.

w*x2012-04-18 07:04

21 楼

考虑worst case的话那快排比堆排序慢多了. 但是一般情况下快排比对排序快,这体差
不多的感觉

【在 j********e 的大作中提到】

: 看明白了。如果pivot选的很倒霉，worst case会到O(N^2)?
: 一般再用median of median来选pivot，那就麻烦了