一亩三分地论坛

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

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

GOOGLE 1116新鲜电面--实习第三轮

[复制链接] |试试Instant~ |关注本帖
xin_gator 发表于 2015-11-17 06:30:30 | 显示全部楼层 |阅读模式

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

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

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

x
刚刚结束的第三轮实习加面,听上去是白人小哥,新鲜出炉两道题:. From 1point 3acres bbs
1. Find number of reciprocated edges in directed graph
第一道题灰常简单,给你一个set 的edges, 比如[[0,1],[1,2],[2,1]],[1,2]跟[2,1]就是eciprocated edges,return 2


2. Given a double array, find x such that [x,x+1] contains most numbers in the array
这道题有些复杂,因为double的话可能有无数种可能,我纠结半天后没想出怎么reason x一定是其中的element,口语着急,小哥看我太纠结了就规定了x是array中的一个element,那就简单多了,一上来先用最基础的brute force给出了解法。复杂度O(n^2)。
被问到了怎么improve,灵光一闪就喊出了double linked queue,小哥说idea是对的,只是不用queue,用两个指针就行了,我又大喊了一声对对对2 pointers,后来给出了用两个指针实现的类似deque的解法,小哥非常认真,检查半天,细致到检查出typo好几个,我就一直战战兢兢的候着,最后终于说looks good。。也没时间多跑几次test就到点了。
现在又开始等着feedback。。希望好运气


补充内容 (2015-11-17 23:24):
第一题就是最基础的reciprocated edge count,不用考虑loop,不用考虑strong connected,最基础的

补充内容 (2015-12-3 03:41):
进入team match了,祈祷早日被捞走

补充内容 (2016-1-23 23:53):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
马克下,把offer签了今天,一块大石落了地了

评分

1

查看全部评分

本帖被以下淘专辑推荐:

atwoodwang0918 发表于 2016-1-25 08:43:36 | 显示全部楼层
我也写了下第二题代码 边界条件没考虑 nums的个数小于2的情况我没考虑 因为不知道该返回什么。。其他情况应该都是对的了。。。吧??大家用作参考咯~
  1. <blockquote><pre>public double MostElements(double[] nums){
  2.     Arrays.sort(nums);
  3.     int start = 0;
  4.     int end = 0;
  5.     int max = 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.     int index = 0;
  7.     while(start<=end&&end<nums.length){
  8.         while(end<nums.length&&nums[start]+1>nums[end]) end++;
  9.         if(end-start>max){
  10.             max = end-start;
  11.             index = start;
  12.         }
  13.         start++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14.     }
  15.     return nums[index];
  16. }</pre>
复制代码
回复 支持 0 反对 1

使用道具 举报

宝贝忆彼岸 发表于 2015-11-17 06:39:03 | 显示全部楼层
请问第二题的array是sorted吗?
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-17 07:30:26 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-17 06:39
请问第二题的array是sorted吗?

可能不是,但是只要用Arrays.sort就行了,不太要求这个
回复 支持 反对

使用道具 举报

cocaptainco 发表于 2015-11-17 07:51:25 | 显示全部楼层
楼主能举例说一下算法吗?
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-17 07:58:43 | 显示全部楼层
cocaptainco 发表于 2015-11-17 07:51. more info on 1point3acres.com
楼主能举例说一下算法吗?

比如说一个array是[1.2, 2.4, 2.6, 2.9, 3.2, 5.3, 6.9]吧,求[x,x+1],这个区间包含有这个array里最多的数.鏈枃鍘熷垱鑷1point3acres璁哄潧
[1.2, 2.2] 这个区间仅有1个值,
[2.4, 3.4] 这个区间却又4个,是最多的,返回2.4。
回复 支持 反对

使用道具 举报

majia113 发表于 2015-11-17 07:59:43 | 显示全部楼层
第二题可以这样么
sort, 然后两个指针 start和end, 开始都指向0, x = A[start], 然后移动end,直到 A[end]>=x+1, 这时候计算这个window中的数字个数end-start+1, 如果比当前已经知道的最优还好,更新,然后start=end, end继续向前移动
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-17 08:04:00 | 显示全部楼层
majia113 发表于 2015-11-17 07:59
第二题可以这样么
sort, 然后两个指针 start和end, 开始都指向0, x = A[start], 然后移动end,直到 A[end]> ...

如果这样的话,就跳过了一切start 与 end之间的值 比如[1.2, 2.4, 2.6, 3.0, 3.5, 3.55] 吧,你在扫到2.4的时候更新到end在3.0,于是移动start到3.5,但是最大的区间却是2.6, 3.0, 3.5, 3.55。
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-17 08:07:06 | 显示全部楼层
majia113 发表于 2015-11-17 07:59. Waral 鍗氬鏈夋洿澶氭枃绔,
第二题可以这样么
sort, 然后两个指针 start和end, 开始都指向0, x = A[start], 然后移动end,直到 A[end]> ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
所以应该是像一个double linked queue一样,start与end之间的数永远差值小于一,每从deque 的尾部push进一个新的元素(end++),都要从头弹出所有超出新的范围的元素(increment start)
回复 支持 反对

使用道具 举报

fireisborn 发表于 2015-11-17 12:11:53 | 显示全部楼层
樓主可以分享一下你第一題的思路嘛?我今天也被問這題
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-17 12:31:36 | 显示全部楼层
同问第一题,如果有[0,1],[1,2],[2,3],[3,0]这种算有几条reciprocated edges啊?
谢谢
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-17 23:22:14 | 显示全部楼层
fireisborn 发表于 2015-11-17 12:11
樓主可以分享一下你第一題的思路嘛?我今天也被問這題

第一题很明显呀,用HashMap存储扫过的edge,for loop里新的edge只用look up是否存在它的reciprocated edge,有的话+2,没有的话就把这个edge存在HashMap里。代码:
class Edge{
  int start;-google 1point3acres
  int end;
  public Edge(int s,int e){ start = s; end = e;}
}
int count(List<Edge> edges){. from: 1point3acres.com/bbs
     HashMap<Edge,Integer> map = new HashMap<Edge,Integer>();
     int count =0;
     for(Edge edge: edges){
          Edge reciEdge = new Edge(edge.end, edge.start);
         if(!map.containsKey(reciEdge)){
                 map.put(edge,1);
          }else{
                 count += 2;
           }
           return count;
}. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-17 23:23:30 | 显示全部楼层
stonezms 发表于 2015-11-17 12:31. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
同问第一题,如果有[0,1],[1,2],[2,3],[3,0]这种算有几条reciprocated edges啊?
谢谢

这算0条,[0,1]跟[1,0]这种算两条,最直接的,不用考虑loop
回复 支持 反对

使用道具 举报

stonezms 发表于 2015-11-17 23:33:42 | 显示全部楼层
xin_gator 发表于 2015-11-17 23:23. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这算0条,[0,1]跟[1,0]这种算两条,最直接的,不用考虑loop

了解。。谢了!祝早日拿到offer :)
回复 支持 反对

使用道具 举报

yanguango 发表于 2015-11-18 00:56:06 | 显示全部楼层
第二题是不是能把 array 都转成 int,然后找里面最多的重复的数。
回复 支持 反对

使用道具 举报

fireisborn 发表于 2015-11-18 00:57:14 | 显示全部楼层
xin_gator 发表于 2015-11-17 23:22
第一题很明显呀,用HashMap存储扫过的edge,for loop里新的edge只用look up是否存在它的reciprocated edg ...

了解,看來我的思路跟樓主一樣,有點小改動而已,只是我被問了很多之後的 follow up,祝福樓主早日拿到 offer
回复 支持 反对

使用道具 举报

yanguango 发表于 2015-11-18 01:00:27 | 显示全部楼层
xin_gator 发表于 2015-11-17 23:22 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第一题很明显呀,用HashMap存储扫过的edge,for loop里新的edge只用look up是否存在它的reciprocated edg ...

楼主的 Edge 类是不是需要overwrite equals 和 hashCode 方法。
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-18 01:42:19 | 显示全部楼层
fireisborn 发表于 2015-11-18 00:57
了解,看來我的思路跟樓主一樣,有點小改動而已,只是我被問了很多之後的 follow up,祝福樓主早日拿到 o ...

这样呀,我的面试官一开始就直接跟我讲说不用考虑一切的复杂状况,只用solve这个base case就行,你也好运!!
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-18 01:43:38 | 显示全部楼层
yanguango 发表于 2015-11-18 01:00
楼主的 Edge 类是不是需要overwrite equals 和 hashCode 方法。

啊啊啊好复杂,我没有诶,就提供了上面那个solution,面试小哥就仔仔细细检查了一遍就没再继续问follow up了
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-18 01:47:35 | 显示全部楼层
yanguango 发表于 2015-11-18 00:56
第二题是不是能把 array 都转成 int,然后找里面最多的重复的数。

不行这么做吧,如果是[2.0001 2.9 2.99 2.999 3.8 3.88]呢,转成int了的话只能求出4 返回2.0001,但解应该是5 返回2.9呀
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 04:09:37 | 显示全部楼层
xin_gator 发表于 2015-11-17 23:22
第一题很明显呀,用HashMap存储扫过的edge,for loop里新的edge只用look up是否存在它的reciprocated edg ...

这个应该跑不过吧,因为你每次都new 了一个新的object,一个简单的办法是,直接 edge[end] + "" + edge[start],就是变成string
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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