回复: 20
跳转到指定楼层
上一主题 下一主题
收起左侧

谷歌onsite面经

全局:

2019(1-3月) 码农类General 硕士 全职@google - 内推 - Onsite  | | Pass | 在职跳槽

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

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

x
第一轮: lc739, 另一题是:给你一个word的idctionary, 在给你一个word, 问你word是否在dictionary里面, word最多可以修改一个字符。这题我给出了用hashset存的方法,和trie的方法,最后只让实现了hashset的方法。
第二轮: 给一个表达式字符串,比如“(1+2)*3”, 假设分为parsing team 和compute team, parsing team 可以把它parse成你想要的数据结构,然后我要做的就是实现compute(T t)并给出T的定义. 当时我定义t为一个表达式树,然后写了compute的code, 之后,又改了下表达式树,把c
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
ndex tree方法,最后让写了binary index tree 的code。的code。并要求处理了multithreading safe的问题。(用synchronized。。)

感觉第四轮hint有点多,然后code没有全部写完。。。 第三轮followup code也没写。



评分

参与人数 12大米 +48 收起 理由
tuntunzzz + 1 很有用的信息!
lljjccsskk + 1 欢迎分享你知道的情况,会给更多积分奖励!
zdzapple + 2 给你点个赞!
jih23 + 2 很有用的信息!
lorixx + 2 很有用的信息!

查看全部评分


上一篇:阿里巴巴Alibaba第二轮电面
下一篇:有知道Google ATAP这个组现在大概情况的吗?
推荐
 楼主| dragonlanding 2019-4-6 11:36:43 | 只看该作者
全局:
第四题我一开始也以为是二分图问题,但被面试官否认了,然后在hint下, 才反应过来是toposort,code没写完,但思路面试官说是正确的。

第四题是这样子的,就是首先,肯定有2n个人,然后对于一个pair(m, n), 表示m喜欢n,但n不一定喜欢m。并且,每一个人只会喜欢1个人, 所以m喜欢了n,就不存在m喜欢l。所以,如果把人作为node的话,就相当于,每个node出度<=1。因此,把喜欢这种关系建成一个图之后,每次都从入度为0的node出发(比如m喜欢n,但没人喜欢m,这样的话把<m, n>配在一起,同时把m,n从图中去掉), 这样一直做下去,直到最后要么剩下了环,也有可能剩下了几个单点),就是toposort。

(假设不会存在强耦合环,即a->b, b->a,若存在的话,可以先preprocess, 让强耦合两两匹配,之后再跑toposort)

证明最优性:如果选了(m,n)这条边,就使得m和自己喜欢的人配到了一起,也就相当于给最终答案贡献了1,然而这种贡献并不会影响到全局最优,因为首先m入度为0,所以m只能配n,并且,n在最优解当中至多被一个人匹配,所以选择(m,n)这条边不会影响全局最优。(有点像贪心的意思)。

最后如果是单点,可以随意匹配其它单点,如果是环,可以选任意一边解环。

评分

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

查看全部评分

回复

使用道具 举报

推荐
mhsasd 2019-4-4 10:29:18 | 只看该作者
全局:
lz可以讲下第四题怎么用拓扑排序吗
回复

使用道具 举报

全局:
umialpha 发表于 2019/04/02 14:42:07
第五轮这个要求高度最小楼主是怎么考虑的?貌似用union算法的话还挺麻烦?

我看有的面经说那题input和馏粑舞不一样给的是一个root,如果是这样的话BFS+set()就能秒了
回复

使用道具 举报

🔗
janetding 2019-4-2 13:27:07 | 只看该作者
全局:
感谢分享 很有用的信息。愿你H1B 抽签顺利!
回复

使用道具 举报

全局:
除了第四问以外好像还可以,感谢楼主分享
回复

使用道具 举报

全局:
第四题是人车匹配的follow up 。二分图的最大匹配。匈牙利算法。妈呀,看来又要去默写几遍了。
回复

使用道具 举报

全局:
kaipeng21 发表于 2019/04/02 14:29:40
除了第四问以外好像还可以,感谢楼主分享

第四问是不是二分图的最大匹配,匈牙利算法?
回复

使用道具 举报

全局:
umialpha 发表于 2019/04/02 14:29:45
第四题是人车匹配的follow up 。二分图的最大匹配。匈牙利算法。妈呀,看来又要去默写几遍了。

不说我还没看出来,我一直不想去读匈牙利啊,但好像不读不行了
回复

使用道具 举报

全局:
第五轮这个要求高度最小楼主是怎么考虑的?貌似用union算法的话还挺麻烦?
回复

使用道具 举报

全局:
kaipeng21 发表于 2019/04/02 14:52:49


我看有的面经说那题input和馏粑舞不一样给的是一个root,如果是这样的话BFS+set()就能秒了

嗯嗯,给了root的话一个层次遍历(或者bfs)就ok了,感谢
回复

使用道具 举报

🔗
jy_121 2019-4-4 02:20:49 | 只看该作者
全局:
umialpha 发表于 2019-4-2 15:06
嗯嗯,给了root的话一个层次遍历(或者bfs)就ok了,感谢

请问下具体怎么做呢?谢谢
回复

使用道具 举报

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

本版积分规则

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