一亩三分地论坛

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

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

刚面完的Bloomberg面经

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

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

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

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

x
一接电话发现是烙印,口音不是很重,语速也挺慢的,但是人感觉不是很热情,让我自我介绍的时候面试官说电话里老有echo......我说让他重打,他说不用就这样吧。。我就继续说了. 1point 3acres 璁哄潧
题目给的是一个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......

代码没有写完,估计跪了
大家加油!

评分

4

查看全部评分

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

  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) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.                     cur = cur * 2;
  10.                 }else if (arr[cur] > target) {
  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)) {
  19.                            r = mid - 1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  20.                    } else {
    . From 1point 3acres bbs
  21.                            if(arr[mid] == target). Waral 鍗氬鏈夋洿澶氭枃绔,
  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.         }
  32.        
  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) {
  40.                                 l = mid + 1;
  41.                         }else {. more info on 1point3acres.com
  42.                                 r = mid - 1;
  43.                         }
  44.                 }
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  45.                 return false;
  46.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

 楼主| 玛奇朵肉丝 发表于 2016-2-11 03:57:38 | 显示全部楼层
手误写错了一点。。如果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 ...

为啥是这两道题的混合?
回复 支持 反对

使用道具 举报

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;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                }
                int cur = 1;
                while (!outOfBound(cur)){
                        if (arr[cur] == target){
                                return true;
                        } else if (arr[cur] < target){
                                cur = cur * 2;
                        } else {
                                break;
                        }. 1point 3acres 璁哄潧
                }
                int left = cur / 2;
                int right = cur; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                while (left < right){
                        int mid = left + (right - left) / 2;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        if (outOfBound(mid)){
                                right = mid - 1;
                        } else {
                                if (arr[mid] == target){. Waral 鍗氬鏈夋洿澶氭枃绔,
                                        return true;
                                } else if (arr[mid] < target){
                                        left = mid + 1;
                                } else {
                                        right = mid - 1;
                                }
                        }
                }. more info on 1point3acres.com
                return false;. 1point3acres.com/bbs
        }

谢谢楼主分享~ 我也要面BB了,求人品啊~~~

补充内容 (2016-3-24 05:59):
第一句应该

if(outOfBound(0)){
   return false;
}
写惯了。。囧。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 16:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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