一亩三分地论坛

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

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

FB 二面

[复制链接] |试试Instant~ |关注本帖
vinoblade 发表于 2015-12-2 09:38:34 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other其他

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

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

x
新鲜二面奉上,很nice的三哥。只面了一道题。
给定一个array,条件:1. A[i] = A[i]+-1; 2. There is only one peek or one valey in the array, return the index of that peek or valey.
刚开始说了一下O(n)顺着找的办法,三哥说更好的办法呢?我说那就是binary search了。结果做着做着发现这样搞还是O(N)。然后三哥开导我不要用recursion呢,用binary search该怎么搞。我又仔细看了一下,发现直接比较头尾大小,O(1)就能解决。。然后压时间写完了。
求offer!!


评分

3

查看全部评分

本帖被以下淘专辑推荐:

woshixuyoudan 发表于 2016-2-17 00:03:46 | 显示全部楼层
不用binary啊,充分利用相邻只相差1
设结果的的index是x,value是y,nums的长度是len,解二元一次方程
x - 0 = y - nums[0].鏈枃鍘熷垱鑷1point3acres璁哄潧
x - (len - 1) = - (y - nums[len - 1])
(这种情况默认的是peak  反正之前判断一下是peak还是valey就行  然后有不同的方程)
这样就是O(1)
回复 支持 2 反对 0

使用道具 举报

小A要当码农 发表于 2015-12-3 01:53:06 | 显示全部楼层
这是我的Binary-Search的code,欢迎改正~
public class FindPeakOrValley{
        public static int find(int[] nums){
                if(nums.length == 0) return -1;
                int len = nums.length;
                if(Math.abs(nums[len - 1] - nums[0]) == len -1) return -1;//There is no such a valley or peak
                return helper(nums, 0 , len - 1);

        }
        public static int helper(int[] nums, int start, int end){
                int mid = start + (end - start) / 2;
                if((nums[mid - 1] - nums[mid]) *  (nums[mid + 1] - nums[mid])> 0)
                        return nums[mid];. 1point 3acres 璁哄潧
                int diffOfIndex = mid - start;
                int diffOfValue = Math.abs(nums[mid] - nums[start]);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                if(diffOfIndex == diffOfValue) start = mid;
                else end = mid;
. 1point3acres.com/bbs                return helper(nums, start, end);

        }
        public static void main(String[] args){
                int[] nums1 = {1,2,3,4,3,2};
                int[] nums2 = {};. more info on 1point3acres.com
                int[] nums3 = {1,2,3,4,5,6,7,8,7};
                int[] nums4 = {1,2,3,4,5};.鐣欏璁哄潧-涓浜-涓夊垎鍦
                int[] nums5 = {5,4,3,2,1,2,3};
                int[] nums6 = {9,8,7,6,7};. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                System.out.println(find(nums1));
                System.out.println(find(nums2));
                System.out.println(find(nums3));
                System.out.println(find(nums4));
                System.out.println(find(nums5));. 鍥磋鎴戜滑@1point 3 acres
                System.out.println(find(nums6));
        }
}
回复 支持 1 反对 0

使用道具 举报

gschengcong 发表于 2015-12-3 09:55:49 | 显示全部楼层
y42353041 发表于 2015-12-3 09:51
不知道我理解对题目没有。.1point3acres缃
这个算合理的test case吗:.鏈枃鍘熷垱鑷1point3acres璁哄潧
1,2,1,2,1,2,3,2,1,2

应该不算。他的意思好像是要么只有一个波峰,要么只有一个波谷。
回复 支持 1 反对 0

使用道具 举报

 楼主| vinoblade 发表于 2015-12-2 09:39:01 | 显示全部楼层
sorry, 应该是A[i] = A[i-1]+-1
回复 支持 1 反对 0

使用道具 举报

gschengcong 发表于 2015-12-3 02:10:01 | 显示全部楼层
我的想法是先用nums[start] - nums[start +1] 的结果的正负判断是先升后降,还是先降后升。然后直接看中间的点处的斜率
front = nums[mid] - nums[mid-1];
Rear = nums[mid +1] - nums[mid]
如果是先降后升,mid这儿又是升的话,就接着判断左边的中点的斜率。同理,mid处降的话就找右边。如果mid这儿的front 和rear异号的话,那mid就是要找的点了。
请问这样对吗?
回复 支持 1 反对 0

使用道具 举报

fireisborn 发表于 2015-12-2 13:25:49 | 显示全部楼层
不大懂為什麼頭尾相比 O(1) 可以解決?可以麻煩 lz 舉個例嗎?謝謝~
回复 支持 反对

使用道具 举报

Howie 发表于 2015-12-2 13:46:19 | 显示全部楼层
这个题就是binary search 吧
3 4 5 6 7 6 5 4 3
O(1) 咋解决。。
回复 支持 反对

使用道具 举报

mynn2003 发表于 2015-12-2 13:54:24 | 显示全部楼层
binary search是logn吧?我也觉得没法O(1)
回复 支持 反对

使用道具 举报

mzhqlh 发表于 2015-12-2 14:19:45 | 显示全部楼层
我觉得因为数字中间相差1, 假设一共有m个元素,假设尾元素大于头元素n(有可能小于),那么往右补n个元素后的中点就是potential peak (m + n - 1) /2, 或者是 (m - n  - 1)/2 就是potential valley. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
例如 1 2 3 4 5 4 3, 尾元素比头元素大2, 那么1 2 3 4 5 4 3中m = 7, 右补上两个元素就变成了1 2 3 4 5 4 3 2 1, (m + n - 1)/2 = 4。同里如果是valley, 那么这个数列可以1 0 -1 0 1 2 3, 对应的index是 (m - n - 1) /2 = 2.. 由于n是正是负不会影响最重结果。。。假设这两个candidate的index是mid, (nums[mid] - nums[mid-1]) * (nums[mid] - nums[mid+1]) > 0 的mid就是答案......其实画个图比较容易看得出....

当然二分也可以.....

补充内容 (2015-12-2 14:20):
typo...最终结果....
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-12-2 21:39:30 | 显示全部楼层
mzhqlh 发表于 2015-12-2 14:19
我觉得因为数字中间相差1, 假设一共有m个元素,假设尾元素大于头元素n(有可能小于),那么往右补n个元素 ...

bingo~思路没问题,但我当时四种情况是分开讨论的,valey+end大,valey+end小,peak+end大,peak+end小
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-12-2 21:43:52 | 显示全部楼层
recursion形式的binary search是O(N),因为要同时向两个方向比较,所以f(n) = 2f(n/2)+O(1)。interviewer说的log(n)的binary search我当时没有想出来。constant time的解法可以参考5楼。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-3 01:36:26 | 显示全部楼层
vinoblade 发表于 2015-12-2 21:43
recursion形式的binary search是O(N),因为要同时向两个方向比较,所以f(n) = 2f(n/2)+O(1)。interviewer说 ...

binary的方法的话, 应该判断|nums[start]-nums[mid]| 和|left - mid|的大小来决定是搜左边还是右边吧?
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-12-3 01:44:09 | 显示全部楼层
小A要当码农 发表于 2015-12-3 01:36. from: 1point3acres.com/bbs
binary的方法的话, 应该判断|nums[start]-nums[mid]| 和|left - mid|的大小来决定是搜左边还是右边吧?

有道理,可能这个是interviewer想要的答案。
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-12-3 01:47:56 | 显示全部楼层
小A要当码农 发表于 2015-12-3 01:36
binary的方法的话, 应该判断|nums[start]-nums[mid]| 和|left - mid|的大小来决定是搜左边还是右边吧?

但是有一个问题,就是像数组1,2,3,4,5,4和2,1,2,3,4,5,这两个的比较结果是一样的,所以还是要两个方向同时查找
回复 支持 反对

使用道具 举报

mzhqlh 发表于 2015-12-3 01:51:33 | 显示全部楼层
vinoblade 发表于 2015-12-3 01:47
但是有一个问题,就是像数组1,2,3,4,5,4和2,1,2,3,4,5,这两个的比较结果是一样的,所以还是要两个方向同 ...

binary search的话,我觉得是先判断第一个元素还有第二个元素之间的大小关系,判断是peak or valley, 然后引入一个sign符号, sign = a[1] > a[0]? 1: -1; 然后复制一个nums每个元素乘以sign, 最后在正常binary search find peak就可以了...sign是为了避免写多个找valley的...
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-3 01:55:19 | 显示全部楼层
vinoblade 发表于 2015-12-3 01:47
但是有一个问题,就是像数组1,2,3,4,5,4和2,1,2,3,4,5,这两个的比较结果是一样的,所以还是要两个方向同 ...

这两个例子 我跑出来并没有错误啊。。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-3 02:03:08 | 显示全部楼层
mzhqlh 发表于 2015-12-3 01:51
binary search的话,我觉得是先判断第一个元素还有第二个元素之间的大小关系,判断是peak or valley, 然 ...
. From 1point 3acres bbs
复制一个nums每一个元素乘以sign?这是哈意思呀? 这样不已经是O(N)了么?
其实,B-search的做法是慢慢往转折点靠近,无所谓是谷点还是峰点,所以每次判断的依据是, left---mid这一段内有没有发生过转折。
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-12-3 02:26:49 | 显示全部楼层
小A要当码农 发表于 2015-12-3 01:55
这两个例子 我跑出来并没有错误啊。。
. 1point3acres.com/bbs
题目要求是返回valey/peak的index,你的做法是有问题的。我跑了一下你得程序,5,4,3,2,1,2,3的结果不对。
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-12-3 02:29:33 | 显示全部楼层
gschengcong 发表于 2015-12-3 02:10
我的想法是先用nums[start] - nums[start +1] 的结果的正负判断是先升后降,还是先降后升。然后直接看中间 ...

我觉得这个方法是靠谱的。
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-12-3 02:35:30 | 显示全部楼层
mzhqlh 发表于 2015-12-3 01:51
binary search的话,我觉得是先判断第一个元素还有第二个元素之间的大小关系,判断是peak or valley, 然 ...

不需要sign,知道了上升下降顺序就可以直接binary search了
回复 支持 反对

使用道具 举报

mzhqlh 发表于 2015-12-3 02:45:58 | 显示全部楼层
小A要当码农 发表于 2015-12-3 02:03
复制一个nums每一个元素乘以sign?这是哈意思呀? 这样不已经是O(N)了么?
其实,B-search的做法是慢慢 ...

有道理,不过我原本想的binary search跟你这个有点不一样。如果没有arr = arr[i-1] +-1 这个条件,只有先增后减,先减后增就不能用diffOfIndex == diffOfValue来判断转折。。zenefits有道原题基本一样,但是没有arr = arr[i-1] +-1,这个条件。。如果是这样的话,就需要先知道是peak或者valley了...复制那个是脑抽了.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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