Google OA 12/1 晚，未换题。

美西时间 12/1 晚上 23 点，google oa 未换题，还是 tree ancestor 和 houses and stores。建议收到 oa 的朋友们尽量在这个周末把 oa 做掉，这两道题好像已经很久了。。
简单说一下解题思路：

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

Google OA 只能 submit 一次，而且 submit 之后不能修改，也看不到结果，所以建议不要用 brute force 方法，因为你也不知道会不会 time limit exeed，提交之前也要检查好 corner cases。

下面附 OA 题，祝大家都有满意offer，顺路求大米~

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

大方 发表于 2018-12-8 10:40
第一题不用构建tree吧？比如找节点i的第2个ancestor, A[A]就行了。
第二题，用两个字典：dict1{key: house ...

第二题返回的时候arr[idx]  = dict2[dict[idx]]

sherrryli 发表于 2018-12-4 06:39
有一点不清楚就是一个parent是只会有一个child么？如果不是的话，path怎么存啊？

可以有多个 child，可以用 list 作 stack 来存，每次一个节点访问结束就 pop 出去。

楼主是申请实习还是full time?

jiangsl 发表于 2018-12-3 09:32
楼主是申请实习还是full time?

申的实习

Summer 2019?

有一点不清楚就是一个parent是只会有一个child么？如果不是的话，path怎么存啊？

jiangsl 发表于 2018-12-3 13:23
Summer 2019?

是的~ summer intern 2019

sherrryli 发表于 2018-12-4 06:39
有一点不清楚就是一个parent是只会有一个child么？如果不是的话，path怎么存啊？

抱歉，不常上地里，回复比较慢。给加个米呗~

请问第二题 lz是用了两个for Loop吗？

第一题不是应该dp做吗，不用建树吧，建树路径不就反了。