一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1261|回复: 30
收起左侧

Zillow 二面

[复制链接] |试试Instant~ |关注本帖
meeegooo 发表于 2014-11-20 03:08:37 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Zillow - 网上海投 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
给一个sorted array和threshold value, 找出数组中所有大于或者等于该value的数的中位数。array可能有duplicates。不知道今天是怎么了,脑袋发晕,好多edge case没考虑到,都是靠他提示,跪的节奏。哎。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2014-12-12 04:45):
都过了三个星期还没收到回复,一直以为悲剧了,今天收到了一个local的offer,才鼓起勇气发邮件过去问个结果,死也死得明明白白,结果回复我过了,有onsite。。
neusharon 发表于 2014-11-20 03:33:40 | 显示全部楼层
扫一遍找到第一个match,然后剩下的部分取中间的?。。感觉没什么trick吧这里面。。
回复 支持 反对

使用道具 举报

fangl086 发表于 2014-11-20 03:35:22 | 显示全部楼层
我写了一个很傻逼的方法,直接O(n)搞的,直接找到对应>=threshold 的index, st, 然后和末尾end取中位数,A[(st+end)/2]
第一面是这个题,也跪掉了,你是店面完多久收到2面的phone的?
回复 支持 反对

使用道具 举报

nullas 发表于 2014-11-20 04:06:44 | 显示全部楼层
这个是我一面的题目。。。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-20 04:36:24 | 显示全部楼层
写一个binary search就可以了。
难点在什么地方?. 鍥磋鎴戜滑@1point 3 acres
回复 支持 反对

使用道具 举报

 楼主| meeegooo 发表于 2014-11-20 04:41:15 | 显示全部楼层
averillzheng 发表于 2014-11-20 04:36
写一个binary search就可以了。
难点在什么地方?

要考虑到duplicate,还有难点主要是edge case,比如可能数组的length超过了integer的最大值,然后求mid除以2的时候可能会溢出,还有其他的类似的我现在想不起了。。
回复 支持 反对

使用道具 举报

 楼主| meeegooo 发表于 2014-11-20 04:42:23 | 显示全部楼层
fangl086 发表于 2014-11-20 03:35
我写了一个很傻逼的方法,直接O(n)搞的,直接找到对应>=threshold 的index, st, 然后和末尾end取中位数,A[ ...
. from: 1point3acres.com/bbs
我的一面很简单,就是lowest common ancestor,一周后收到的二面。。
回复 支持 反对

使用道具 举报

 楼主| meeegooo 发表于 2014-11-20 04:43:20 | 显示全部楼层
nullas 发表于 2014-11-20 04:06. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个是我一面的题目。。。

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

使用道具 举报

averillzheng 发表于 2014-11-20 05:31:18 | 显示全部楼层
我的理解是,只要你在面试官指出你的bug后,能够迅速理解以及更正了就可以了。不用太担心了。
回复 支持 反对

使用道具 举报

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

mid 不能用 (st + en) / 2 来做。会overflow的。
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-20 05:39:42 | 显示全部楼层
meeegooo 发表于 2014-11-20 04:41
要考虑到duplicate,还有难点主要是edge case,比如可能数组的length超过了integer的最大值,然后求mid除 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
input 是什么?请问你用的什么语言写的? 如果是用java的话,给你的input是int[] 的话,length是不会超过Integer.MAX_VALUE. 你可用用一个long的常量作为一个array的length, java是会报错的。
回复 支持 反对

使用道具 举报

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

至少要binary search吧, 有duplicate,要用一点变形找到第一个,o(logn),  然后再考虑些edge cases
回复 支持 反对

使用道具 举报

 楼主| meeegooo 发表于 2014-11-21 05:19:01 | 显示全部楼层
averillzheng 发表于 2014-11-20 05:39. 鍥磋鎴戜滑@1point 3 acres
input 是什么?请问你用的什么语言写的? 如果是用java的话,给你的input是int[] 的话,length是不会超过 ...

就是Java,input是int[],额,好吧,他当时估计就随便举个例子,没有注意,主要是我的mid是直接(start+end)除以2的,现在才知道要start+(end-start)/2,哎,自己太水了
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-11-21 14:45:39 | 显示全部楼层
meeegooo 发表于 2014-11-21 05:19. Waral 鍗氬鏈夋洿澶氭枃绔,
就是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.         }. 1point3acres.com/bbs
  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. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| meeegooo 发表于 2014-11-22 03:20:53 | 显示全部楼层
averillzheng 发表于 2014-11-21 14:45. 鍥磋鎴戜滑@1point 3 acres
我今天面,贴一个我写的code, 求点拨

不好意思现在才看到。。我觉得蛮好,就是最好前面加上如果array为空的情况。
回复 支持 反对

使用道具 举报

davidzeng1990 发表于 2014-12-3 03:03:48 | 显示全部楼层
请问楼主拿到onsite了吗?
回复 支持 反对

使用道具 举报

金妮韦崽 发表于 2014-12-3 08:56:00 | 显示全部楼层
meeegooo 发表于 2014-11-19 15:41
要考虑到duplicate,还有难点主要是edge case,比如可能数组的length超过了integer的最大值,然后求mid除 ...

居然还要考虑溢出ORZ
. 1point 3acres 璁哄潧
话说我说一下我的思路求楼主指导
.鏈枃鍘熷垱鑷1point3acres璁哄潧
大概首先看看ARRAY到底有没有大于等于THRESHOLD VALUE的数,没有就怎么样我也不知道。。。这时候可能array是空的也可能全部都比它大 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
现在我们通过二分法找到第一个符合条件的数的INDEX,假设是N,那么总共有多少数符合要求呢,就是ARRAY.LENGTH - N
如果有奇数个数符合要求,那就找到INDEX N + FLOOR((ARRAY.LENGTH - N)/2)
如果有偶数个数如何要求,那就是找到最中间的两个INDEX上的数,取平均

我不明白DUPLICATE在这里怎么会成为EDGE CASE啊,反正数组都排序了,重复的数肯定是排一块儿的牙

最后再问问LZ进入下一关没有?我下周ZILLOW第一轮电面

补充内容 (2014-12-2 23:17):
问一下 所谓的说要考虑duplicate是不是就是说 可能给的数是n 然后数组里有很多个n,然后我得去找第一个。。。不能说二分法一看到n就拍板觉得是了
回复 支持 反对

使用道具 举报

bjik 发表于 2014-12-3 10:23:21 | 显示全部楼层
弱问一下mid能写成 mid = s/2 +t/2么?
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-12-10 06:57:02 | 显示全部楼层
averillzheng 发表于 2014-11-19 12:36
写一个binary search就可以了。
难点在什么地方?

难点在于写出一个正确的binary search
回复 支持 反对

使用道具 举报

averillzheng 发表于 2014-12-10 07:23:15 | 显示全部楼层
pyemma 发表于 2014-12-10 06:57
难点在于写出一个正确的binary search

这有什么好难的。如果给定的threshold 是int, 你只用binary search  threshold - 0.5。.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 12:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表