一亩三分地论坛

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

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

Google电面面经 估计一轮游2016

[复制链接] |试试Instant~ |关注本帖
msu_HIDDEN 发表于 2016-3-26 03:28:05 | 显示全部楼层 |阅读模式

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

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

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

x
直接上题
. 1point 3acres 璁哄潧
给一个sorted int array 定义popular item的frequency/occurerence 大于N/4. 鍥磋鎴戜滑@1point 3 acres
求item 值最小的frequency.

写了个O(N)
说不行。。(第一次没看清题 写了个return popular item value的。。。。)
要更快(<O(N))
想了半天没想出来,,,,然后把frequency的threshold改成N/2
提出了把array切成2份看
然后就卡这了
期间给了我个例子要我找pattern 死活没找出来,感觉被误导了
整个面试45分钟就一道题,可能是没解出来就不让进下一题

面试结束后 想到了。。。。用binary search 在切好的两个array里找到canditate 的index 两个index减一下得出frequency,应该是个O(lgN)的解法。. Waral 鍗氬鏈夋洿澶氭枃绔,
基本走远了。。。但还是祈祷给我个机会。

评分

3

查看全部评分

cervantes 发表于 2016-3-28 11:21:59 | 显示全部楼层
Array时sort好了的,所以大于1/4 的元素只可能出现在1/4,1/2,3/4处,分别对这三处的数检测。检测方法就是binary search 找出出现的最左边的index,和最右边的index,index之差就是frequence。如果超过1/3 加入到结果里
回复 支持 2 反对 0

使用道具 举报

DaveLiu 发表于 2016-6-7 12:17:28 | 显示全部楼层
大致写了一下,不知道有没有cover不到的corner case:

  1. class PopularItemInSortedArray {
  2.         public int pupularItem(int[] nums) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  3.                 int seg = nums.length / 4;
  4.                 for (int i = seg; i < nums.length; i += seg) {
  5.                         int first = findFirst(nums[i], 0, i - 1, nums);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  6.                         if (first == -1) first = i;
  7.                         int last = findLast(nums[i], i + 1, nums.length - 1, nums);
  8.                         if (last == -1) last = i;. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.                         if (last - first + 1 >= seg) {
  10.                                 return nums[i];
  11.                         }
  12.                 }. 鍥磋鎴戜滑@1point 3 acres
  13.                 return -1;
  14.         }
  15.         . 1point 3acres 璁哄潧
  16.         private int findFirst(int t, int s, int e, int[] nums) {
  17.                 while (s <= e) {
  18.                         int m = s + (e - s) / 2;
  19.                         if (nums[m] == t && (nums[m - 1] != t || nums[m + 1] != t)) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.                                 return m;
  21.                         } else if (nums[m] < t) {
  22.                                 s = m + 1;
  23.                         } else {
  24.                                 e = m - 1;
  25.                         }
  26.                 }
  27.                 return -1;
  28.         }
  29.        
  30.         private int findLast(int t, int s, int e, int[] nums) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  31.                 while (s <= e) {
  32.                         int m = s + (e - s) / 2;
  33.                         if (nums[m] == t && (nums[m - 1] != t || nums[m + 1] != t)) {
  34.                                 return m;
  35.                         } else if (nums[m] > t) {
  36.                                 e = m - 1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  37.                         } else {. 1point 3acres 璁哄潧
  38.                                 s = m + 1;. 1point 3acres 璁哄潧
  39.                         }. from: 1point3acres.com/bbs
  40.                 }-google 1point3acres
  41.                 return -1;
  42.         }
  43.          
  44.         public static void main(String[] args) {
  45.                 PopularItemInSortedArray p = new PopularItemInSortedArray();
  46.                 System.out.println(p.pupularItem(new int[]{1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5, 5, 6}));. Waral 鍗氬鏈夋洿澶氭枃绔,
  47.         }. 1point 3acres 璁哄潧
  48. }
复制代码
回复 支持 1 反对 0

使用道具 举报

ykwwind 发表于 2016-3-26 03:43:13 | 显示全部楼层
2分左右逼近...

pattern是啥?
回复 支持 反对

使用道具 举报

 楼主| msu_HIDDEN 发表于 2016-3-26 04:09:32 | 显示全部楼层
ykwwind 发表于 2016-3-26 03:43
2分左右逼近....鐣欏璁哄潧-涓浜-涓夊垎鍦

pattern是啥?

1 1 2 2 2 2 2 3 4
分成.鐣欏璁哄潧-涓浜-涓夊垎鍦
1  1 2 2 2     . 1point3acres.com/bbs
2 2 3 5. 1point3acres.com/bbs
他就让我找 也没说是啥
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-3-26 08:04:40 | 显示全部楼层
sorted int array 一定是从1开始的连续整数么?
回复 支持 反对

使用道具 举报

Fustang 发表于 2016-3-26 08:58:48 | 显示全部楼层
N/4才算popular item, 那不是最多只有四个?
分成四段 只有每段的头尾才是candidate 然后从最小段开始check哪个有N/4 freq。。。?
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-3-28 07:33:23 | 显示全部楼层
跪拜楼上 原来是这样思考。。 跪拜。。
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-28 08:42:11 | 显示全部楼层
感觉这题和leetcode上的major element是一个解法的
回复 支持 反对

使用道具 举报

slashGu 发表于 2016-3-28 08:50:25 | 显示全部楼层
Fustang 发表于 2016-3-26 08:58
N/4才算popular item, 那不是最多只有四个?
分成四段 只有每段的头尾才是candidate 然后从最小段开始chec ...

要大于N/4才行,所以最多应该是3个。.鏈枃鍘熷垱鑷1point3acres璁哄潧
另外,我觉得应该是用建一个BST,每个节点记录出现的次数,然后从小到大找第一个出现次数大于N/4的。
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-28 08:56:51 | 显示全部楼层
slashGu 发表于 2016-3-28 08:50
要大于N/4才行,所以最多应该是3个。
另外,我觉得应该是用建一个BST,每个节点记录出现的次数,然后从 ...

从小到大找第一个popular num应该是O(n)时间吧
回复 支持 反对

使用道具 举报

 楼主| msu_HIDDEN 发表于 2016-3-28 09:46:10 | 显示全部楼层
slashGu 发表于 2016-3-28 08:50
要大于N/4才行,所以最多应该是3个。
另外,我觉得应该是用建一个BST,每个节点记录出现的次数,然后从 ...

建bst要O(N)   面试官要求至少是O(lgN)的算法
回复 支持 反对

使用道具 举报

 楼主| msu_HIDDEN 发表于 2016-3-28 09:46:42 | 显示全部楼层
hison7463 发表于 2016-3-28 08:42
感觉这题和leetcode上的major element是一个解法的

不太一样。。。这题要求的是popular element 的出现次数
回复 支持 反对

使用道具 举报

dimi 发表于 2016-3-28 10:04:18 | 显示全部楼层
切成4分,
头尾是candidates。一共有8个,
然後从小開始測試。
这满足要求么
回复 支持 反对

使用道具 举报

 楼主| msu_HIDDEN 发表于 2016-3-28 10:16:36 | 显示全部楼层
dimi 发表于 2016-3-28 10:04
切成4分,
头尾是candidates。一共有8个,-google 1point3acres
然後从小開始測試。
. from: 1point3acres.com/bbs
要怎么测试呢?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-29 21:52:47 | 显示全部楼层
请问楼主有结果了吗?面完几天后有结果呢?
回复 支持 反对

使用道具 举报

 楼主| msu_HIDDEN 发表于 2016-4-26 01:59:50 | 显示全部楼层
bobzhang2004 发表于 2016-3-29 21:52
请问楼主有结果了吗?面完几天后有结果呢?

妥妥被拒啊
回复 支持 反对

使用道具 举报

robinali 发表于 2016-6-7 13:01:05 | 显示全部楼层
感觉楼主没有问前提: 是否sorted?
嗯,确实是binary search比较快。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 10:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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