查看: 4226|回复: 42
收起左侧

google VO

|只看干货
匿名用户-EE9  发表于 2021-12-4 10:18:49 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎

2021(10-12月) 码农类General 硕士 全职@Google - 内推 - Onsite  | 😐 Neutral 😐 AverageOther | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 匿名 于 2021-12-3 18:25 编辑

十一月中旬面的Google VO, 投的L4, 今天通知被down level到L3并且还要加面两轮

VO 总共五轮,1轮BQ 4轮coding
BQ:国人大哥,问一些虚拟场景你会怎么处理
coding1: 国人小哥,设计一个function 随机从一个playlist 里面播放歌曲,播放过的歌曲冷却时间为k,也就是说当前播放的一首歌,在接下来k首里面不能出现。implement了logn的,O(1)的思路没说完时间到了
coding2: 白人大哥,有很多通信基站的位置,[[lat1, long1], [lat2, long2] ... ],这些位置信息会load到手机里,手机可以随时获取到自己的位置,设计一个数据结构能够快速查找距离手机最近的基站。感觉描述的很不清楚,答的一团糟,这一轮肯定挂了。quadTree?二维list把地图画成格子?geohashing?跪求大家有没有什么好的想法。。
coding3: 国人大哥,有碳氢氧三种原子,每个碳原子需要有4个化学键,氧原子2个,氢原子1个,才能算是满足要求。提供一个叫做atoms的map,key是原子的id,value是原子的元素 {1: "C", 2: "O", 3: &quo
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
输出task的执行顺序。用heap做的复杂度nlogn



补充内容 (2021-12-04 11:27 +8:00):
coding2 里面手机的位置是一直在变的,所以和每个基站的距离也在变,而且查找最近基站的方法会被调用很多次。感觉是需要把基站的数据做些处理,处理成某个合适的数据结构,以便查找的时候能很快

评分

参与人数 5大米 +10 收起 理由
enjoynet + 1 给你点个赞!
月黑风高 + 1 给你点个赞!
清道神君 + 5
akdhfikbk + 2 很有用的信息!
inVictUs. + 1 赞一个!

查看全部评分


上一篇:巨硬ADS过经
下一篇:亚麻 OA1
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   99% (205)
 
 
0% (2)    👎
第二题貌似是个kd tree 的问题:https://kanoki.org/2020/08/05/fi ... hbor-using-kd-tree/

评分

参与人数 1大米 +1 收起 理由
shiry10 + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   93% (30)
 
 
6% (2)    👎
1. Queue + Set + hash for random。为什么需要用到BST?维持一个k大小的queue和set,每次放下一首的时候queue pop和set remove。再播放选曲子的时候如果random到了Set里的歌,跳到idx+1直到选到下一个available的song。在曲库远大于k的时候可以有O(1)表现。
2. KDTree之类的是把基站变成Tree里的点,但是题目要求nearest,可能找到的基站并不是最近的,那不是还要做Tree里那个点附近的traversal?如果把基站group进一个一个小格子里,每次currentLocation可以确定一个格子,然后做一圈BFS应该可以filter掉很多基站吧(前提是基站不扎堆)
3. 有点难写啊,[[1,2], [1,2]]可以是c=o也可以是c-o-c或者o-c-o?
4. CPU/meeting变体,heap就好了。看起来这题最简单。。。
回复

使用道具 举报

地里的匿名用户
匿名用户-EE9  发表于 2021-12-5 12:44:20
本楼: 👍   100% (1)
 
 
0% (0)   👎
匿名者 发表于 2021-12-4 18:37
能否稍微展开一下,如何用bst来存歌曲id,然后更新时间点?bst的顺序怎么决定?

每个歌曲就是一个node,node.id,node.available_time,available_time就是这首歌在这个时间之后可以重新播放,comparator是available time。初始所有node,available_time都是0. 同时维护一个current time。每播放一首歌,current time++, 同时更新这个歌曲node的available time为current time + k,并更新整个树。随机的时候可以先从BST里面找到当前有x个歌曲可以播放, 从1~x里面随机一个数y,BST里面排在第y个的node就是随机出来的歌曲。node里面还要维护一个subtree的size,以便快速找到第y个node。
总之还挺啰嗦的,推荐楼上lc伞巴陵的O(1)解法,感觉思路很清楚
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (32)
 
 
3% (1)    👎
Q2 感觉像酒企伞, k=1
按lee神的做法就是一个std::nth_element
但面试不能这么写吧。。。
回复

使用道具 举报

地里的匿名用户
匿名用户-B57  发表于 2021-12-4 11:16:10
本楼: 👍   0% (0)
 
 
0% (0)   👎
狗真逗,2年downgrade到l3还要加面,不知道哪来的自信。
回复

使用道具 举报

地里的匿名用户
匿名用户-EE9  发表于 2021-12-4 11:27:36
本楼: 👍   0% (0)
 
 
0% (0)   👎
fanx95 发表于 2021-12-3 18:54
Q2 感觉像酒企伞, k=1
按lee神的做法就是一个std::nth_element
但面试不能这么写吧。。。

似乎不太像,帖子里忘了提了,手机的位置是一直在变的,所以和每个基站的距离也在变,而且查找最近基站的方法会被调用很多次。感觉是需要把基站的数据做些处理,处理成某个合适的数据结构,以便查找的时候能很快
回复

使用道具 举报

地里的匿名用户
匿名用户-EE9  发表于 2021-12-4 11:32:25
本楼: 👍   0% (0)
 
 
0% (0)   👎
匿名者 发表于 2021-12-3 19:16
狗真逗,2年downgrade到l3还要加面,不知道哪来的自信。

嗨,狗家家大业大。。
回复

使用道具 举报

地里的匿名用户
匿名用户-D2D  发表于 2021-12-4 12:22:51
本楼: 👍   0% (0)
 
 
0% (0)   👎
同求第二问,我实在没想出什么好办法。。我的想法是可以先把所有point根据x坐标 sort一遍,然后binary search新点的x坐标,再从这个点往左右查找,一旦哪边的(x - x0) ^ 2 大于最小的(x - x0) ^ 2 + (y - y0) ^ 2就停止往那边继续查找。 然而这个办法可能还不如直接tranverse 一遍所有的点。。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
100% (1)   👎
全局: 👍   92% (25)
 
 
7% (2)    👎
请问coding3的follow up,意思是不需要管键的大小吗?比如给了1,2 是不是默认co之间是2呀...
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (118)
 
 
7% (9)    👎
第二題如果原點一直移動真的難 沒想法
回复

使用道具 举报

地里的匿名用户
匿名用户-EE9  发表于 2021-12-4 13:58:20
本楼: 👍   0% (0)
 
 
0% (0)   👎
匿名者 发表于 2021-12-3 20:22
同求第二问,我实在没想出什么好办法。。我的想法是可以先把所有point根据x坐标 sort一遍,然后binary sear ...

嗯感觉这样最坏情况可能还是N,不过如果基站分布比较均匀的话应该是比直接暴力检查所有点更快
回复

使用道具 举报

地里的匿名用户
匿名用户-EE9  发表于 2021-12-4 14:02:57
本楼: 👍   0% (0)
 
 
0% (0)   👎
本帖最后由 匿名 于 2021-12-3 22:10 编辑
inVictUs. 发表于 2021-12-3 21:29
请问coding3的follow up,意思是不需要管键的大小吗?比如给了1,2 是不是默认co之间是2呀...

follow up就是说bonds里面的每个键可以有多个,比如有两个[1,2],有两个[1,3],这样碳原子和氧原子A之间就有两个键,碳原子和氧原子B之间也有两个键,O=C=O,碳原子上共有4个,两个氧原子各有2个,就满足条件。如果只用了一个[1,2],用了一个[1,3],结果就是O-C-O就不满足条件了
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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