j********e
发帖数: 1192 | 1 1. http get和post的区别，追问到了具体http包里面的内容
2. 对web 安全的了解
3. 数据库问题，建表记录employee，department等
4. int数组，找出和为零的数字对 （老题了）
5. int数组，kth largest number （老题也有春天)
6. web问题，用户登录这些怎么在客户端记录（答曰饼干），后面一直追问
到php的session
|
p*****2
发帖数: 21240 | 2
第五题空间复杂度什么要求？
【在 j********e 的大作中提到】
: 1. http get和post的区别，追问到了具体http包里面的内容
: 2. 对web 安全的了解
: 3. 数据库问题，建表记录employee，department等
: 4. int数组，找出和为零的数字对 （老题了）
: 5. int数组，kth largest number （老题也有春天)
: 6. web问题，用户登录这些怎么在客户端记录（答曰饼干），后面一直追问
: 到php的session
:
|
j********e
发帖数: 1192 | 3 面试官没说，我说建个大小为K的heap，然后worst case
是O(N * logK)，他就说OK了，没往下问。
【在 p*****2 的大作中提到】
:
: 第五题空间复杂度什么要求？
|
w****x
发帖数: 2483 | 4 第5题用selection algorithm吧 |
j********e
发帖数: 1192 | 5 median of median 那个?
【在 w****x 的大作中提到】
: 第5题用selection algorithm吧
|
w****x
发帖数: 2483 | 6 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];
} |
j********e
发帖数: 1192 | 7 没看懂，介绍下思路？
感觉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]);
|
w****x
发帖数: 2483 | 8 刚才随手写的, 改正:
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****x
发帖数: 2483 | 9 k忘缩小了, i <= j 不是 i < j, 和p[j]交换不是p[i], bug啊~~ |
j********e
发帖数: 1192 | 10 看明白了。如果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****x
发帖数: 2483 | 11
考虑worst case的话那快排比堆排序慢多了. 但是一般情况下快排比对排序快,这体差
不多的感觉
【在 j********e 的大作中提到】
: 看明白了。如果pivot选的很倒霉，worst case会到O(N^2)?
: 一般再用median of median来选pivot，那就麻烦了
|
