一亩三分地论坛

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

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

11月10号Google面经,求大神看看还有希望没。

[复制链接] |试试Instant~ |关注本帖
FrankShockvan 发表于 2015-11-11 10:41:44 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 博士 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
今天不知道为啥面试官有事,所以只面了一面。 找一个sorted array里面出现次数多于N/4的元素。 开始觉得是Major element的变种,先说了一遍,结果跟他想的不一样,他估计也有点懵。又说了一遍,就10多分钟了,然后他说能提高时间吗? 然后想出来分割加binary search。 代码大概写了7分钟。 然后叫我找个几个test case测试下。 完事33分钟,就问我还有问题没。。。最后问两个问题,40分钟左右就结束了。感觉面试官人很好,就是有点赶。。。 不知道还有希望没有。还有下一面,希望能好点。

评分

2

查看全部评分

本帖被以下淘专辑推荐:

cc11328 发表于 2015-11-12 01:53:18 | 显示全部楼层
  1. vector<int> findOneForth(vector<int>& myvec) {
  2.     int d = myvec.size()/8;
  3.     vector<int>candidate,result;
  4.     if(d == 0){
  5.         for(int i = 0; i < myvec.size(); i++) {
  6.             if(candidate.empty() || myvec[i] != candidate.back())
  7.                candidate.push_back(myvec[i]);
  8.         }
  9.     } else {
  10.         for(int i = 0;i+d < myvec.size();i+=d)
  11.             if(candidate.empty() || (myvec[i] == myvec[i+d] && myvec[i] != candidate.back()))
  12.                candidate.push_back(myvec[i]);
  13.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  14.     for(int i = 0;i < candidate.size();i++) {
  15.         std::vector<int>::iterator low,up;
  16.         low =std::lower_bound (myvec.begin(), myvec.end(), candidate[i]);
  17.         up = std::upper_bound (myvec.begin(), myvec.end(), candidate[i]);
  18.         int n = up - low;
  19.         if(n >= (int)ceil(myvec.size()/4.0)) {. from: 1point3acres.com/bbs
  20.             result.push_back(candidate[i]);
  21.         }
  22.     }

  23.     return result;
  24. }
复制代码
回复 支持 1 反对 0

使用道具 举报

feierqi 发表于 2015-11-12 01:02:14 | 显示全部楼层
写了一下代码,测了几个test cases,应该对了
  1.         public static boolean ifExistMoreThanQuarter(int[] sorted){
  2.                 if(sorted == null || sorted.length == 0){
  3.                         return false;
  4.                 }
  5.                 else if(sorted.length < 4){
  6.                         return true;
  7.                 }
  8.                 int mid = sorted.length / 2;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.                 int target = sorted[mid];
  10.                 int l = binarySearch(sorted, 0, mid, target, true);
  11.                 int r = binarySearch(sorted, mid, sorted.length - 1, target, false);
  12.                 if(r - l + 1 > sorted.length / 4){
  13.                         return true;. 鍥磋鎴戜滑@1point 3 acres
  14.                 }
  15.                 int leftQuarter = sorted.length / 4;
  16.                 target = sorted[leftQuarter];. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.                 l = binarySearch(sorted, 0, leftQuarter, target, true);
  18.                 r = binarySearch(sorted, leftQuarter, mid, target, false);
  19.                 if(r - l + 1 > sorted.length / 4){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.                         return true;
  21.                 }
  22.                 int rightQuarter = sorted.length * 3 / 4;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.                 target = sorted[rightQuarter];
  24.                 l = binarySearch(sorted, mid, rightQuarter, target, true);
  25.                 r = binarySearch(sorted, rightQuarter, sorted.length - 1, target, false);
  26.                 if(r - l + 1 > sorted.length / 4){-google 1point3acres
  27.                         return true; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.                 }
  29.                 return false;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  30.         }
  31.         . From 1point 3acres bbs
  32.         private static int binarySearch(int[] sorted, int left, int right, int target, boolean ifLeftSide){
  33.                 while(left < right){
  34.                         int mid = ifLeftSide? left + (right - left) / 2 : left + (right - left + 1) / 2;
  35.                         if(ifLeftSide){
  36.                                 if(sorted[mid] < target){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  37.                                         left = mid + 1;
  38.                                 }
  39.                                 else{
  40.                                         right = mid;
  41.                                 }
  42.                         }
  43.                         else{
  44.                                 if(sorted[mid] > target){
  45.                                         right = mid - 1;. from: 1point3acres.com/bbs
  46.                                 }
  47.                                 else{
  48.                                         left = mid;
  49.                                 }
  50.                         }
  51.                 }
  52.                 return left;
  53.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

pkqs90 发表于 2015-11-11 10:53:19 | 显示全部楼层
什么叫分割+binary search,LZ 说得再详细一些可以吗?
回复 支持 反对

使用道具 举报

 楼主| FrankShockvan 发表于 2015-11-11 11:01:00 | 显示全部楼层
就是分成四份,然后分别进行binary search
回复 支持 反对

使用道具 举报

 楼主| FrankShockvan 发表于 2015-11-11 11:02:57 | 显示全部楼层
pkqs90 发表于 2015-11-11 10:53
什么叫分割+binary search,LZ 说得再详细一些可以吗?

就是分成四份,然后分别进行binary search,应为大于N/4的话就会跨过分割点
回复 支持 反对

使用道具 举报

kidzlike 发表于 2015-11-11 11:12:35 | 显示全部楼层
pick n[0] n[n_len/4] n[2*n_len/4] n[3*n_len/4] n[4*n_len/4] 类似这样?
回复 支持 反对

使用道具 举报

 楼主| FrankShockvan 发表于 2015-11-11 11:15:09 | 显示全部楼层
kidzlike 发表于 2015-11-11 11:12. 鍥磋鎴戜滑@1point 3 acres
pick n[0] n[n_len/4] n[2*n_len/4] n[3*n_len/4] n[4*n_len/4] 类似这样?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对的,就是0 ,n/4, 2n/4, 3n/4, n。 然后分别左右搜索
回复 支持 反对

使用道具 举报

 楼主| FrankShockvan 发表于 2015-11-11 11:16:02 | 显示全部楼层
kidzlike 发表于 2015-11-11 11:12
pick n[0] n[n_len/4] n[2*n_len/4] n[3*n_len/4] n[4*n_len/4] 类似这样?

题不算太难,他在说的时候我挺快就想出来了,但是最后感觉很赶。。。不知道还有希望没
回复 支持 反对

使用道具 举报

kidzlike 发表于 2015-11-11 11:22:33 | 显示全部楼层
FrankShockvan 发表于 2015-11-11 11:16
题不算太难,他在说的时候我挺快就想出来了,但是最后感觉很赶。。。不知道还有希望没

best wishes.
回复 支持 反对

使用道具 举报

pkqs90 发表于 2015-11-11 11:29:26 | 显示全部楼层
哦,没看到是 sorted array,祝 LZ 好运~
回复 支持 反对

使用道具 举报

 楼主| FrankShockvan 发表于 2015-11-11 11:32:12 | 显示全部楼层
pkqs90 发表于 2015-11-11 11:29
哦,没看到是 sorted array,祝 LZ 好运~

多谢,今天感觉各种不顺,这道题倒是做对了,但是就做了一道,感觉悬啊。。。
回复 支持 反对

使用道具 举报

玉米地York 发表于 2015-11-11 11:45:27 | 显示全部楼层
FrankShockvan 发表于 2015-11-11 11:15. Waral 鍗氬鏈夋洿澶氭枃绔,
对的,就是0 ,n/4, 2n/4, 3n/4, n。 然后分别左右搜索

什么是左右搜索?判断边界lz是怎么处理的?
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-11-11 12:43:21 | 显示全部楼层
玉米地York 发表于 2015-11-11 11:45
什么是左右搜索?判断边界lz是怎么处理的?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
看左右如果一样就是重复出现 n / 4 以上
回复 支持 反对

使用道具 举报

ericawang 发表于 2015-11-11 13:00:09 | 显示全部楼层
实习应该不会一轮直接出结果的,应该会安排第二面的,楼长安心啦~~
回复 支持 反对

使用道具 举报

 楼主| FrankShockvan 发表于 2015-11-11 13:28:16 | 显示全部楼层
ericawang 发表于 2015-11-11 13:00
实习应该不会一轮直接出结果的,应该会安排第二面的,楼长安心啦~~

哎,多谢,后面这个是补面,第一轮面试官有事了
回复 支持 反对

使用道具 举报

 楼主| FrankShockvan 发表于 2015-11-11 13:50:46 | 显示全部楼层
yjfox 发表于 2015-11-11 12:43.鏈枃鍘熷垱鑷1point3acres璁哄潧
看左右如果一样就是重复出现 n / 4 以上
. visit 1point3acres.com for more.
对,如果不同就搜索边界就行了,然后看边界是不是大于N/4,
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-12 00:53:45 | 显示全部楼层
FrankShockvan 发表于 2015-11-11 13:50
对,如果不同就搜索边界就行了,然后看边界是不是大于N/4,

额。。楼主能详细讲讲么?还是没明白这个怎么用binary search的. from: 1point3acres.com/bbs
比如112  233  334  455这么分成四段,怎么找出3呢?
谢谢!
回复 支持 反对

使用道具 举报

feierqi 发表于 2015-11-12 01:00:12 | 显示全部楼层
这道题应该是找到n/2, 1/4, 3/4处的index的element,然后看这三个elements是不是出现超过n/4个,因为如果一个array里有一个element超过n/4,那它肯定在这三个位置中的一个或多个
回复 支持 反对

使用道具 举报

 楼主| FrankShockvan 发表于 2015-11-12 01:00:52 | 显示全部楼层
stonezms 发表于 2015-11-12 00:53
额。。楼主能详细讲讲么?还是没明白这个怎么用binary search的
比如112  233  334  455这么分成四段, ...

跟search for range 差不多,对1/4, 2/4,3/4搜左边右边的开始节点
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-12 01:17:53 | 显示全部楼层
FrankShockvan 发表于 2015-11-12 01:00
跟search for range 差不多,对1/4, 2/4,3/4搜左边右边的开始节点

了解。。谢谢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 08:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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