onsite写完题还剩20分钟，没让优化 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

onsite写完题还剩20分钟，没让优化

onsite写完题还剩20分钟，没让优化# JobHunting - 待字闺中

e*x2015-04-24 07:04

1 楼

面的一个startup，leetcode原题median of two sorted array。想稳一点所以用merge
sort写了个O(N)/O(N)的，打算慢慢优化，因为这题的O(logN)有很多edge case我怕写
不好。然后面试官让我优化空间写了个O(N)/O(1)，写完还剩20多分钟就和我聊天了(中
间我一直在等他让我写better solution...)，是要挂的节奏么？对方给的feedback感
觉挺active，他说他面试从来就是问这道题，90%以上的人写不好，然后说我是new
grad, your solution is good enough for me。感觉自己作死啊，应该上来就写个O(
logN)的……

h*32015-04-24 07:04

2 楼

楼主放心吧

b*52015-04-24 07:04

3 楼

int findMedian (int[] A, int[] B) {
int aLen = A.length;
int bLen= B.length;
if (aLength+bLength % 2 == 0) {
return (helper(A, B, (aLen+bLen)/2, 0, aLen, 0, bLen) +
helper(A, B, (aLen+bLen)/2-1, 0, aLen, 0, bLen))/2;
}
else {
return helper(A, B, (aLen+bLen)/2, 0, aLen, 0, bLen);
}
}
int helper (int[] A, int[] B, int k, int aStart, int aEnd, int bstart, int
bEnd) {
int aLen = aEnd-aStart+1;
int bLen = bEnd-bStart+1;
if (aLen == 0) {
return b[bStart+k];
}
else if (bLen == 0) {
return a[aStart+k];
}
else if (k == 0) {
return Math.min(A[0], B[0]);
}

int aMid = aLen*k / (aLen+bLen);
int bMid = k-aMid-1;
aMid = aStart+aMid;
bMid = bStart+bMid;
if (A[aMid] < B[bMid] {
return (A, B, k-(aMid-aStart+1), aMid+1, aEnd, bStart, bMid);
}
else {
return (A, B, k-(bMid-bStart+1), aStart, aMid, bMid+1, bEnd);
}
}

merge

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

: 面的一个startup，leetcode原题median of two sorted array。想稳一点所以用merge
: sort写了个O(N)/O(N)的，打算慢慢优化，因为这题的O(logN)有很多edge case我怕写
: 不好。然后面试官让我优化空间写了个O(N)/O(1)，写完还剩20多分钟就和我聊天了(中
: 间我一直在等他让我写better solution...)，是要挂的节奏么？对方给的feedback感
: 觉挺active，他说他面试从来就是问这道题，90%以上的人写不好，然后说我是new
: grad, your solution is good enough for me。感觉自己作死啊，应该上来就写个O(
: logN)的……

c*n2015-04-24 07:04

4 楼

这个题要没见过还是很难的

merge

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

l*n2015-04-24 07:04

5 楼

我面试总结出经验教训了，别play什么先写出一般solution，然后再优化啥的戏码了。
时间不够啊，直接上最优解，然后让他多问几个问题都比慢慢面试的好！

g*y2015-04-24 07:04

6 楼

我是先会说比较简单易想的答案，最多多花30秒，跟他说完后，来个but神马的把最优
解说出来。

e*x2015-04-24 07:04

7 楼

嗯，希望能过……

【在 h****3 的大作中提到】

: 楼主放心吧

e*x2015-04-24 07:04

8 楼

algorithm design里的hw原题，感觉大部分人都应该见过？

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

: 这个题要没见过还是很难的
:
: merge

e*x2015-04-24 07:04

9 楼

问题是我留出了充足的时间给优化……结果人面试官直接说good enough然后开始聊天
了……囧

【在 l*****n 的大作中提到】

: 我面试总结出经验教训了，别play什么先写出一般solution，然后再优化啥的戏码了。
: 时间不够啊，直接上最优解，然后让他多问几个问题都比慢慢面试的好！

e*x2015-04-24 07:04

10 楼

这是用kth smallest element in two sorted arrays来做的吧？这样确实不用考虑
edge case了……我当时想到的是那个一般二分法的solution，aLen不等于bLen的情况
下很多edge cases的那个，不确定能写好就想先写个O(N)的算了...
: int bLen= B.length;
: if (aLength+bLength % 2 == 0) {
: return (helper(A, B, (aLen+bLen)/2, 0, aLen, 0, bLen) +
: helper(A, B, (aLen+bLen)/2-1, 0, aLen, 0, bLen))/2;
: }
: else {
: return helper(A, B, (aLen+bLen)/2, 0, aLen, 0, bLen);
: }