Failed G 还是觉得不明白为什么 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Failed G 还是觉得不明白为什么

Failed G 还是觉得不明白为什么# JobHunting - 待字闺中

H*M2013-07-03 07:07

1 楼

题目都做出来了嘛，交流也还好。
想了很久觉得可能是思路不够清晰流畅，然后就是有些小错误。我在G的朋友说应该是
缺少亮点－他们想看到1-2个高分。
转专业过来的，所以不晓得怎样才能拿高分？
绝望中。。。求内推。

H*M2013-07-03 07:07

2 楼

只碰到了一个见过的题：2D array, 行递增，列递增，找一个数。我没想好是不是应该
告诉他我知道这题，就没说，装装地想了一会，就告诉他答案了。但是他也没让我写
code，然后直接问了下一题：两个sorted arrays, 找kth element, 我上来就说了
merge sort, 但他要更好效率的。

h*t2013-07-03 07:07

3 楼

better than O(log(m+n))?

【在 H**M 的大作中提到】

: 只碰到了一个见过的题：2D array, 行递增，列递增，找一个数。我没想好是不是应该
: 告诉他我知道这题，就没说，装装地想了一会，就告诉他答案了。但是他也没让我写
: code，然后直接问了下一题：两个sorted arrays, 找kth element, 我上来就说了
: merge sort, 但他要更好效率的。

z*y2013-07-03 07:07

4 楼

一看Merge sort 估计这一轮只能拿个一般的面试分数了
不是最优解

r*n2013-07-03 07:07

5 楼

not a very efficient answer. You need to consider that if k is very small
comparing to m+n.

【在 H**M 的大作中提到】

a*u2013-07-03 07:07

6 楼

kth element这题, 比merge sort好的方法很多，仔细看这个http://leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html

z*e2013-07-03 07:07

7 楼

这题是有点小难，而且写起来很容易错
边界处理挺麻烦的

【在 z*******y 的大作中提到】

: 一看Merge sort 估计这一轮只能拿个一般的面试分数了
: 不是最优解

c*y2013-07-03 07:07

8 楼

记得版上有人给出过2 sorted array求k-th的code，recursive的方法，是O（log(n+m)
)，写的很好。哪位记得给找找？

z*e2013-07-03 07:07

9 楼

给一个java的解法
第二个prvaite方法就是找第k个数
package test;
public class Test {
public double findMedianSortedArrays(int a[], int b[]) {
// Start typing your Java solution below
// DO NOT write main() function
return findMedian(a,0,a.length,b,0,b.length);
}

private double findMedian(int[] a, int a0, int m, int[] b, int b0, int
n){
if((m+n)%2==0)
return (findK(a, a0,m, b, b0,n, (m+n)/2)+findK(a,a0,m,b,b0,n,(m+
n)/2+1))/2;
else return findK(a, a0, m,b, b0, n,(m+n)/2+1);
}

private double findK(int[] a, int a0, int m, int[] b, int b0, int n,
int k){
System.out.println("a0:"+a0+",m:"+m+",b0:"+b0+",n:"+n+",k:"+k);
if(m<=0) return b[b0+k-1];
if(n<=0) return a[a0+k-1];
if(k<=1) return Math.min(a[a0], b[b0]);
if(a[a0+m/2]>=b[b0+n/2]){
if(m/2+n/2>=k-1) return findK(a,a0,m/2,b,b0,n,k);
else return findK(a,a0,m,b,b0+n/2+1,n-n/2-1,k-n/2-1);
}else{
if(m/2+n/2>=k-1) return findK(a,a0,m,b,b0,n/2,k);
else return findK(a,a0+m/2+1,m-m/2-1,b,b0,n,k-m/2-1);
}
}

public static void main(String[] args) {
int[] a = {2,4};
int[] b = {3};
Test test = new Test();
System.out.println(test.findMedianSortedArrays(a, b));
}
}