一亩三分地论坛

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

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

11月25日G实习面经

[复制链接] |试试Instant~ |关注本帖
cwjade 发表于 2015-12-4 06:35:37 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
题比较水。。面试官也都超nice。。今天接到邮件进pool,发帖攒人品,就算match不到我也很知足了。。.鏈枃鍘熷垱鑷1point3acres璁哄潧

第一轮 中国小哥 边写还边鼓励我:that's awesome, this is what i want... 太感动了第一题,给一个数组,一个sliding window size,求sliding window size里的平均数
e.g. input:[3,2,1,2,3], 2; output: [2.5, 1.5, 1.5, 2.5]
=> 扫一遍数组,维护一个sum和两个pointer
第二题,给一个数组,实现next()函数,是的数组里数出现的概率和它的值成正比
e.g. input: [1,2,3,4] if next() is called, 0.1 chance to return 1, 0.2 chance to return 2, 0.3 chance to return 3, 0.4 chance to return 5
=>hashmap
Follow up: 如果给的是double array呢 => TreeMap

第二轮 白人小哥 通话质量很差,我说啥都听不清,都是回音。。小哥说尼再忍忍,再过几分钟就结束了。。
先聊简历
第一题,find majority element in a sorted array, whose occurance is more than 1/4
=> binarysearch find quarter point, binarysearch for start and end point
第二题,design greedy snake
这题懵了,写了30多分钟也没写完。。. Waral 鍗氬鏈夋洿澶氭枃绔,


补充内容 (2015-12-4 07:44):.鏈枃鍘熷垱鑷1point3acres璁哄潧
求点大米。。。

评分

2

查看全部评分

stormy1991 发表于 2015-12-4 07:06:48 | 显示全部楼层
恭喜lz!话说24号的现在没消息是不是要悲剧了。。。
回复 支持 反对

使用道具 举报

 楼主| cwjade 发表于 2015-12-4 07:09:41 | 显示全部楼层
stormy1991 发表于 2015-12-4 07:06
恭喜lz!话说24号的现在没消息是不是要悲剧了。。。

别着急。。不同面试官HR效率不同。。Good Luck!
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-4 07:28:49 | 显示全部楼层
请问楼主第一轮第二题 HashMap里边是怎么存的呢?
回复 支持 反对

使用道具 举报

 楼主| cwjade 发表于 2015-12-4 07:43:55 | 显示全部楼层
小A要当码农 发表于 2015-12-4 07:28
请问楼主第一轮第二题 HashMap里边是怎么存的呢?
.1point3acres缃
Integer -> Integer. 鍥磋鎴戜滑@1point 3 acres
e.g. 0->1,1->2,2->2, 3->3, 4->3, 5->3, 6->4, 7->4, 8-> 4, 9->4
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-4 07:47:02 | 显示全部楼层
cwjade 发表于 2015-12-4 07:43
Integer -> Integer
e.g. 0->1,1->2,2->2, 3->3, 4->3, 5->3, 6->4, 7->4, 8-> 4, 9->4

谢谢,然后直接keySet()一下嘛?
回复 支持 反对

使用道具 举报

 楼主| cwjade 发表于 2015-12-4 07:50:44 | 显示全部楼层
小A要当码农 发表于 2015-12-4 07:47
谢谢,然后直接keySet()一下嘛?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后Ramdom得到一个【0,sum)的整数,用这个整数去hashmap里get value
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-4 07:54:52 | 显示全部楼层
cwjade 发表于 2015-12-4 07:50
然后Ramdom得到一个【0,sum)的整数,用这个整数去hashmap里get value

懂啦~ 多谢, 祝早日Match~
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-12-4 08:33:59 | 显示全部楼层
double[] 怎么用treemap呀?
回复 支持 反对

使用道具 举报

 楼主| cwjade 发表于 2015-12-4 08:47:50 | 显示全部楼层
七夜雪 发表于 2015-12-4 08:33
double[] 怎么用treemap呀?

HashMap<Integer, Integer>
TreeMap<Double, Integer>
回复 支持 反对

使用道具 举报

beefcurtain5 发表于 2015-12-4 09:05:39 | 显示全部楼层
cwjade 发表于 2015-12-4 08:47
HashMap. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
TreeMap

HashMap《Double,Integer>不行么?
回复 支持 反对

使用道具 举报

 楼主| cwjade 发表于 2015-12-4 09:17:03 | 显示全部楼层
beefcurtain5 发表于 2015-12-4 09:05
HashMap《Double,Integer>不行么?

用next()的时候,会有一个Ramdom的Integer/Double,怎么用这个再hashmap里搜呢?
也就是说Tree支持range操作,map行吗?
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-12-4 09:29:17 | 显示全部楼层

想了一下还是不大明白...比如一个array是[0.2, 0.4, 0.6, 0.8],怎么保证0.2被选的概率是0.1呢?
也就是说TreeMap<Double, Integer>里面的那个Integer应该放什么呀?

还有这题的next之后会影响概率吗?比如next我随机到了0.2,那这个0.2之后还能出现吗?
回复 支持 反对

使用道具 举报

 楼主| cwjade 发表于 2015-12-4 10:23:05 | 显示全部楼层
七夜雪 发表于 2015-12-4 09:29
想了一下还是不大明白...比如一个array是[0.2, 0.4, 0.6, 0.8],怎么保证0.2被选的概率是0.1呢?
也就是 ...

不好意思,我写错了,应该是<Double, Double>。。。
第一个Double应该是前面所有double总和,第二个应该是当前Double
这个就是最后几分钟问的,也没让写代码,我就提了TreeMap,他就说Good。。。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-4 10:26:46 | 显示全部楼层
cwjade 发表于 2015-12-4 10:23
不好意思,我写错了,应该是。。。.鏈枃鍘熷垱鑷1point3acres璁哄潧
第一个Double应该是前面所有double总和,第二个应该是当前Double
这 ...

可是这么存了以后,比如random出来一个数0.5,是要通过二分去找么?发现它位于0.2-0.6之间,所以输出的应该是0.4这样子?
回复 支持 反对

使用道具 举报

 楼主| cwjade 发表于 2015-12-4 10:40:22 | 显示全部楼层
小A要当码农 发表于 2015-12-4 10:26. visit 1point3acres.com for more.
可是这么存了以后,比如random出来一个数0.5,是要通过二分去找么?发现它位于0.2-0.6之间,所以输出的应 ...

用TreeMap的floorEntry(K key)找到对应value. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
TreeMap=Red Black Tree+Binary Search Tree用法和hashmap一样,就是O(lgn)而已
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2015-12-4 10:41:12 | 显示全部楼层
cwjade 发表于 2015-12-4 10:40
用TreeMap的floorEntry(K key)找到对应value
TreeMap=Red Black Tree+Binary Search Tree用法和hashmap ...

懂了,多谢指点!
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-12-4 13:03:21 | 显示全部楼层
cwjade 发表于 2015-12-4 10:40
用TreeMap的floorEntry(K key)找到对应value
TreeMap=Red Black Tree+Binary Search Tree用法和hashmap ...

nice...我一直就只知道算partial sum+binary search...谢谢LZ
回复 支持 反对

使用道具 举报

vivaroma 发表于 2015-12-6 01:11:55 | 显示全部楼层
中国小哥太好了 = =  恭喜楼主!
回复 支持 反对

使用道具 举报

 楼主| cwjade 发表于 2015-12-6 04:16:52 | 显示全部楼层
vivaroma 发表于 2015-12-6 01:11
中国小哥太好了 = =  恭喜楼主!

谢谢 Good luck to you!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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