狗家实习店面11.15，两轮背靠背

嗯，如果公司能够被多次收购，则映射关系是类似phone letter combination那种backtracking问题，遍历的时间复杂度是exponential, n * 2^n， 如果加Memorization，能优化到O(n)

yxchen_ethan 发表于 2017-11-16 08:00
如果我沒理解錯, 貌似不須要dfs?

#!/bin/env python2

如果同义词可以传递，那么就要dfs了。。

看来狗家最近都是同义词啊

第二题应该O (n)能搞定， 应该可以假设总有一家没被并购过，比如不存在循环并购的情况A并购B，B并购C, C并购A这种情况，另外还可以假设每个点可以有多个出度，但是只有一个入度，也就是公司可以并购多个公司，但是一个公司不能被多个公司同时并购，其实这个图就转成多叉树了
那么可以扫一遍，先把那些入度为0的扫出来，插入Q 然后开始做BFS，看最多扫到了多少层那就是多长了，

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

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

Btw，LZ收到move on的邮件啦，进入project search阶段~

看来印度姐姐对我还是宽容呀……感谢感谢！

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

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

拓扑排序的时候就可以顺路DP了，记录到每个点的最长距离Di。假设当前处理a点，然后去掉儿子b一个入度的时候就可以DP： Db=max(Db,Da+1)。
然后初始入度为0的点D为0。
这样应该不管一个公司能不能被多个公司收购都能做。
但是拓扑排序的负责度是O(V+E)的。
就算确实是个树也是O(N)的。

fsq19474 发表于 2017-12-8 12:14
拓扑排序的时候就可以顺路DP了，记录到每个点的最长距离Di。假设当前处理a点，然后去掉儿子b一个入度的时候 ...

每个点都有有多个儿子的话 你去掉每一个点都要update它的多个儿子 一共是n^2 我假设n是节点数量这里

fsq19474 发表于 2017-12-8 12:14
拓扑排序的时候就可以顺路DP了，记录到每个点的最长距离Di。假设当前处理a点，然后去掉儿子b一个入度的时候 ...

另外没法在拓扑排序的时候update全面 你一个点被标记visit之后 其它指向这个点的父节点就没法继续访问这个点update了