e****x
发帖数: 148 | 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****3
发帖数: 89 | | b**********5
发帖数: 7881 | 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******n
发帖数: 4965 | 4 这个题要没见过还是很难的
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)的……
| l*****n
发帖数: 246 | 5 我面试总结出经验教训了，别play什么先写出一般solution，然后再优化啥的戏码了。
时间不够啊，直接上最优解，然后让他多问几个问题都比慢慢面试的好！ | g*****y
发帖数: 94 | 6 我是先会说比较简单易想的答案，最多多花30秒，跟他说完后，来个but神马的把最优
解说出来。 | e****x
发帖数: 148 | 7 嗯，希望能过……
【在 h****3 的大作中提到】
: 楼主放心吧
| e****x
发帖数: 148 | 8 algorithm design里的hw原题，感觉大部分人都应该见过？
【在 c******n 的大作中提到】
: 这个题要没见过还是很难的
:
: merge
| e****x
发帖数: 148 | 9 问题是我留出了充足的时间给优化……结果人面试官直接说good enough然后开始聊天
了……囧
【在 l*****n 的大作中提到】
: 我面试总结出经验教训了，别play什么先写出一般solution，然后再优化啥的戏码了。
: 时间不够啊，直接上最优解，然后让他多问几个问题都比慢慢面试的好！
| e****x
发帖数: 148 | 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);
: } |
|
