一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1153|回复: 7
收起左侧

刚面完的Bloomberg面经

[复制链接] |试试Instant~ |关注本帖
玛奇朵肉丝 发表于 2016-2-11 03:56:09 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Bloomberg - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
一接电话发现是烙印,口音不是很重,语速也挺慢的,但是人感觉不是很热情,让我自我介绍的时候面试官说电话里老有echo......我说让他重打,他说不用就这样吧。。我就继续说了
题目给的是一个sorted array,但是不知道array的长度,给了一个判断outOfBound(int idx)的函数,再给一个target numbet,让我找target是否存在于array中。
大概思路就是从第一个index开始找,如果array[index]<target,则index*=2,继续找,如果array[index]<target,那么就bianery search index/2和index这个区间。如果index outOfBound,那就继续while判断array[(index/2+index)/2]是不是outOfBound......

代码没有写完,估计跪了.鏈枃鍘熷垱鑷1point3acres璁哄潧
大家加油!

评分

4

查看全部评分

 楼主| 玛奇朵肉丝 发表于 2016-2-12 08:08:50 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
想了一下其实不难,代码如下

  1. boolean findElement(int[] arr, int target) {
  2.             if(!outOfBound(0) && arr[0] == target)
  3.                 return true;
  4.             int cur = 1;
  5.             while(!outOfBound(cur)) {
  6.                     if (arr[cur] == target)
  7.                             return true;
  8.                     else if(arr[cur] < target) {
  9.                     cur = cur * 2;. visit 1point3acres.com for more.
  10.                 }else if (arr[cur] > target) {-google 1point3acres
  11.                     return binarySearch(arr, cur/2, cur, target);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  12.                 }
  13.            }
  14.            int l = cur/2, r = cur;
  15.            int mid;
  16.            while(l <= r) {
  17.                    mid = (l + r)/2;
  18.                    if(outOfBound(mid)) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  19.                            r = mid - 1;
  20.                    } else {
  21.                            if(arr[mid] == target)
  22.                                    return true;
  23.                            else if(arr[mid] < target) {
  24.                                    l = mid + 1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  25.                            } else {
  26.                                    return binarySearch(arr, l, mid - 1, target);
  27.                            }
  28.                    }
  29.            }
  30.            return false;
  31.         }. 1point3acres.com/bbs
  32.         . Waral 鍗氬鏈夋洿澶氭枃绔,
  33.         public boolean binarySearch(int[] arr, int l, int r, int target) {
  34.                 int mid;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  35.                 while(l <= r) {
  36.                         mid = (l + r)/2;
  37.                         if(arr[mid] == target)
  38.                                 return true;
  39.                         else if(arr[mid] < target) {.1point3acres缃
  40.                                 l = mid + 1;
  41.                         }else {
  42.                                 r = mid - 1;
  43.                         }
  44.                 }
  45.                 return false;
  46.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| 玛奇朵肉丝 发表于 2016-2-11 03:57:38 | 显示全部楼层
关注一亩三分地微博:
Warald
手误写错了一点。。如果array[index]>target, 那么久binary search index/2和index这个区间
回复 支持 反对

使用道具 举报

nnno 发表于 2016-3-2 14:19:46 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| 玛奇朵肉丝 发表于 2016-3-3 11:11:51 | 显示全部楼层
nnno 发表于 2016-3-2 14:19
Leetcode两道题的混合 https://leetcode.com/problems/add-two-numbers/ https://leetcode.com/problems/re ...

为啥是这两道题的混合?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

yalyka 发表于 2016-3-15 03:01:15 | 显示全部楼层
我觉得更整洁的办法是先用bsearch和outOfBound(int i)求出array长度,然后再bsearch判断有没有target
回复 支持 反对

使用道具 举报

 楼主| 玛奇朵肉丝 发表于 2016-3-15 04:41:47 | 显示全部楼层
yalyka 发表于 2016-3-15 03:01
我觉得更整洁的办法是先用bsearch和outOfBound(int i)求出array长度,然后再bsearch判断有没有target

嗯对呀,我就是基于这种方法又优化了一点点,就是在求出array长度的同时顺便找出target
回复 支持 反对

使用道具 举报

zsz1990ustc 发表于 2016-3-24 05:57:11 | 显示全部楼层
玛奇朵肉丝 发表于 2016-2-12 08:08
想了一下其实不难,代码如下

楼主的代码有些冗余,第一部分, 在发现了 outOfBound 之后 或者 arr[cur] > target 之后,就直接 break,进入下面的二分查找了,就完事了。不用再单独写个二分法函数到处调用。

        public boolean findElement(int[] arr, int target){
                if (arr == null || arr.length == 0){
                        return false;
                }
                if (arr[0] == target){
                        return true;. 1point 3acres 璁哄潧
                }
                int cur = 1;
                while (!outOfBound(cur)){
                        if (arr[cur] == target){
                                return true;
                        } else if (arr[cur] < target){
                                cur = cur * 2;
                        } else {
                                break;
                        }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                }
                int left = cur / 2;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                int right = cur;
                while (left < right){
                        int mid = left + (right - left) / 2;
                        if (outOfBound(mid)){
                                right = mid - 1;
                        } else {
                                if (arr[mid] == target){
                                        return true;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                                } else if (arr[mid] < target){
                                        left = mid + 1;
                                } else {
                                        right = mid - 1;
                                }
                        }
                }
                return false;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }

. 鍥磋鎴戜滑@1point 3 acres谢谢楼主分享~ 我也要面BB了,求人品啊~~~

补充内容 (2016-3-24 05:59):
第一句应该
. 鍥磋鎴戜滑@1point 3 acres
if(outOfBound(0)){
   return false;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}
写惯了。。囧。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-25 23:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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