Zillow 二面

给一个sorted array和threshold value， 找出数组中所有大于或者等于该value的数的中位数。array可能有dupli

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

气发邮件过去问个结果，死也死得明明白白，结果回复我过了，有onsite。。

meeegooo 发表于 2014-11-21 05:19
就是Java，input是int[]，额，好吧，他当时估计就随便举个例子，没有注意，主要是我的mid是直接(start+en ...

我今天面，贴一个我写的code， 求点拨

1. public class MedianOfSubarray {
   
2.         public static int median (int[] arr, int target){
   
3.                 if(arr[arr.length - 1] < target)        return 0;               
   
4.                 int ind = binarySearch(arr, target, 0, arr.length - 1);
   
5.                 return ind + (arr.length - 1 - ind) / 2;
   
6.         }
   
7.        
   
8.         private static  int binarySearch(int[] arr, int target, int s, int t) {
   
9.                 if(s == t)        { return s; }
   
10.                 int mid = s + (t - s) / 2;
    
11.                 if(arr[mid] >= target)        { return binarySearch(arr, target, s, mid); }
    
12.                 return binarySearch(arr, target, mid + 1, t);
    
13.         }
    
14.        
    
15.         public static void main(String[] args) {
    
16.                 int[] arr = new int[]{1,3,5,5,6, 7};
    
17.                 System.out.println(median(arr, 8));
    
18.         }
    
19. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

扫一遍找到第一个match，然后剩下的部分取中间的？。。感觉没什么trick吧这里面。。

我写了一个很傻逼的方法，直接O(n)搞的，直接找到对应>=threshold 的index, st, 然后和末尾end取中位数，A[(st+end)/2]
第一面是这个题，也跪掉了，你是店面完多久收到2面的phone的？

这个是我一面的题目。。。

写一个binary search就可以了。
难点在什么地方？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

fangl086 发表于 2014-11-20 03:35
我写了一个很傻逼的方法，直接O(n)搞的，直接找到对应>=threshold 的index, st, 然后和末尾end取中位数，A[ ...

我的一面很简单，就是lowest common ancestor，一周后收到的二面。。

nullas 发表于 2014-11-20 04:06
这个是我一面的题目。。。

为啥大家都说一面碰到这道题= =。。我也没想到是这道题，心里面本来还expect 4sum之类的题目。。

我的理解是，只要你在面试官指出你的bug后，能够迅速理解以及更正了就可以了。不用太担心了。

fangl086 发表于 2014-11-20 03:35
我写了一个很傻逼的方法，直接O(n)搞的，直接找到对应>=threshold 的index, st, 然后和末尾end取中位数，A[ ...

mid 不能用 （st + en） / 2 来做。会overflow的。