一亩三分地论坛

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

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

问一道谷歌面经题

[复制链接] |试试Instant~ |关注本帖
melody_qyao 发表于 2015-9-16 11:33:22 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
问一道google面经题,在glassdoor上面看到的:given a list of elements arranged in ascending and then descending order(e.g. 1,3,5,7,6,4,2), write a function to determine if a target number in in this list.. 鍥磋鎴戜滑@1point 3 acres
我知道可以O(n)的方法扫一遍,但是在想O(logn)的方法,本来以为跟find element in rotated sorted array一样,写起来发现根本不是那么回事,求大神解答!!!.鏈枃鍘熷垱鑷1point3acres璁哄潧
SDU_Phonism 发表于 2015-9-16 11:57:14 | 显示全部楼层
我有个想法。。先二分找到最大值的下标。这个和普通二分一样。就是判断mid的时候,要满足mid的value比两边大。。然后分成2个单调的数组,分别二分。
回复 支持 2 反对 0

使用道具 举报

edna 发表于 2015-9-16 13:33:32 | 显示全部楼层
这不就是find peak element么,换了身衣服而已啊。
  1. int findPeak(vector<int> nums) {
  2.         int start = 0, end = nums.size()-1;
  3.         while (start < end) {
  4.                 int mid = start + (end-start)/2;
  5.                 int midNext = mid+1;
  6.                 if (nums[mid] > nums[midNext]) {
  7.                         end = mid;
  8.                 } else {
  9.                         start = midNext;
  10.                 }
  11.         }
  12.         return nums[start];
  13. }
复制代码
测试过
1 2 3 4 5
5 4 3 2 1
1 4 5 3 2
都返回5

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

kelvinzhong 发表于 2015-9-16 11:50:39 | 显示全部楼层
wenqiang88 发表于 2015-9-16 11:42
感觉没有O(n)的解法吧,因为找到中间点后没法判断是在它的左边还是右边

我觉得这题可以先去找peak, 然后对两边用binary search。
. From 1point 3acres bbs
补充内容 (2015-9-16 11:51):
我觉得找peak应该可以binary search的,因为能判读peak在左边还是右边

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

wenqiang88 发表于 2015-9-16 11:42:28 | 显示全部楼层
感觉没有O(n)的解法吧,因为找到中间点后没法判断是在它的左边还是右边
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-9-16 11:54:32 | 显示全部楼层
wenqiang88 发表于 2015-9-16 11:42
感觉没有O(n)的解法吧,因为找到中间点后没法判断是在它的左边还是右边

O(n)就是从头到尾扫一遍啊,你的意思是没有O(logn)的解法吗
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-9-16 12:13:24 | 显示全部楼层
kelvinzhong 发表于 2015-9-16 11:50
我觉得这题可以先去找peak, 然后对两边用binary search。

补充内容 (2015-9-16 11:51):

说的好有道理,这么说来应该算是O(logn)的复杂度
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-17 11:26:20 | 显示全部楼层
三次二分查找,还是logn的复杂度
回复 支持 反对

使用道具 举报

zws0818 发表于 2015-9-18 06:11:04 | 显示全部楼层
这就不就是find peak element吗?leetcode有原题啊
回复 支持 反对

使用道具 举报

zws0818 发表于 2015-9-18 06:13:39 | 显示全部楼层
或者说可以吧数组分成两部分,一个升序,一个降序,用一个变量记录peak element,然后两边分别二分
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-4 15:46:54 | 显示全部楼层
edna 发表于 2015-9-16 13:33.鏈枃鍘熷垱鑷1point3acres璁哄潧
这不就是find peak element么,换了身衣服而已啊。测试过 .1point3acres缃
1 2 3 4 5
5 4 3 2 1

start+(end-start)/2 和 (end+start)/2有什么不同吗?
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-10-4 20:55:55 | 显示全部楼层
hj867955629 发表于 2015-10-4 15:46
start+(end-start)/2 和 (end+start)/2有什么不同吗?

防止溢出
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-10-7 01:40:52 | 显示全部楼层
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-7 22:57:50 | 显示全部楼层
在没有duplicate value的情况下,二分找到最大值,然后对两边做二分,如果有重复值的话,二分就不好找到最大值了,这时候还是老实的遍历一遍吧。
回复 支持 反对

使用道具 举报

returning 发表于 2015-10-8 03:40:34 | 显示全部楼层
同问,如果有重复元素情况下,如何找最大值。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-25 15:28:06 | 显示全部楼层
returning 发表于 2015-10-8 03:40
同问,如果有重复元素情况下,如何找最大值。

class Solution2 {
        private int binarySearchIncrease(int[] nums, int sta, int end, int target) {
                int l = sta, r = end, mid = 0;
                while (l <= r) {. 1point3acres.com/bbs
                        mid = (l+r)/2;
                        if (nums[mid] == target) {
                                return mid;
                        }. 1point3acres.com/bbs
                        if (nums[mid] > target) {
                                r = mid-1;
                        }
                        else {
                                l = mid+1;
                        }
                }
                return Integer.MIN_VALUE;
-google 1point3acres        }
       
        private int binarySearchDecrease(int[] nums, int sta, int end, int target) {
                int l = sta, r = end, mid = 0;
                while (l <= r) {
                        mid = (l+r)/2;
                        if (nums[mid] == target) {
                                return mid;
                        }
                        if (nums[mid] > target) {
                                l = mid+1;
                        }. from: 1point3acres.com/bbs
                        else {
                                r = mid-1;. visit 1point3acres.com for more.
                        }-google 1point3acres
                }
                return Integer.MIN_VALUE;
        }
       
        public int getMax(int[] nums, int target) {
                int l = 0, r = nums.length-1, mid = 0;
                while (l < r) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        mid = (l+r+1)/2;
                        if (nums[mid] >= nums[mid-1]) {. from: 1point3acres.com/bbs
                                l = mid;
                        }
                        else {
                                r = mid-1;
                        }
                }.1point3acres缃
                int left = binarySearchIncrease(nums, 0, l, target);
                if (left != Integer.MIN_VALUE) {
                        return left;
                }
                int right = binarySearchDecrease(nums, l, nums.length-1, target);
                if (right != Integer.MIN_VALUE) {
                        return right;
                }
                return Integer.MIN_VALUE;
        }
}
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 19:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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