Twitter电面

地里Twitter面经不多 给小伙伴们发来面经参考 希望自己能赶快找到工作
是印度小哥 LZ第一次跟印度人面试 其实感觉还不错 一上来没有问任何问题、简历、之类的 直接就说我们做题吧 题目是：print all acyclic path in a graph

就只有这一句很简单话 L

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

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

4-19 16:41):
忘记说了 输入还有告诉你start node 就是path从哪个点开始走

补充内容 (2016-4-19 16:44):
还有就是 如果这是一个complete graph 告诉start node 那么一共有多少条path

这样做可以吗：
1. 先loop一遍，分别把每个节点的后序节点存起来到hashmap<node, List<node>>里
2. 从起始点开始，做dfs，用hashmap记录这次路径上出现过的点，遇到出现过的或者没有后续节点的就停止（按照楼主的提示，应该每一层都加到结果的List里。。）
时间复杂度感觉是O(n!)？。。不太会算。。

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

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

感谢分享，问下楼主时间复杂度应该是多少？

忘记说了 输入还有一个start node 就是告诉你path从哪里开始走

jy_121 发表于 2016-4-19 16:39
感谢分享，问下楼主时间复杂度应该是多少？

我觉得worst case是n^n吧。。。

感谢分享！
感觉Twitter好难啊，电面就出这么复杂的图，又是烙印，楼主居然轻松搞定，太厉害了！zhu楼主offer多多~

什么时候收到电面通知的？

ffllgg 发表于 2016-4-19 21:36
什么时候收到电面通知的？

大概在4.8号 他们家hr很慢。。。这是上周面的

所以楼主pass 了？ 恭喜哇