在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3788|回复: 25
收起左侧

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

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

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

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

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

x
刚刚结束的第三轮实习加面,听上去是白人小哥,新鲜出炉两道题:
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++;. 围观我们@1point 3 acres
  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
楼主能举例说一下算法吗?

比如说一个array是[1.2, 2.4, 2.6, 2.9, 3.2, 5.3, 6.9]吧,求[x,x+1],这个区间包含有这个array里最多的数. 1point 3acres 论坛
[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. from: 1point3acres
第二题可以这样么 来源一亩.三分地论坛.
sort, 然后两个指针 start和end, 开始都指向0, x = A[start], 然后移动end,直到 A[end]> ...
-google 1point3acres
如果这样的话,就跳过了一切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。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| xin_gator 发表于 2015-11-17 08:07:06 | 显示全部楼层
majia113 发表于 2015-11-17 07:59
第二题可以这样么
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啊?. From 1point 3acres bbs
谢谢
回复 支持 反对

使用道具 举报

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

.本文原创自1point3acres论坛第一题很明显呀,用HashMap存储扫过的edge,for loop里新的edge只用look up是否存在它的reciprocated edge,有的话+2,没有的话就把这个edge存在HashMap里。代码:
class Edge{
. 牛人云集,一亩三分地  int start;
  int end;.本文原创自1point3acres论坛
  public Edge(int s,int e){ start = s; end = e;}
}
int count(List<Edge> edges){.留学论坛-一亩-三分地
     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;
}
回复 支持 反对

使用道具 举报

 楼主| 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
. 1point 3acres 论坛
了解。。谢了!祝早日拿到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
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 07:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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