airbnb 电面+skype 三轮

电面round那题，求|xi-yi|最小。followup是|xi-yi|*i求最小。


skype1
外星人字典。followup是如何输出所有解。

skype2

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

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

Q/em34.gif" smilieid="112" border="0" alt="" />

楼主，如何输出所有解什么思路呀？

小A要当码农 发表于 2016-12-9 04:08
楼主，如何输出所有解什么思路呀？

backtracking吧。做topo sort的时候，选择下一个访问的node的顺序是按照自己生成的graph的。但其实对于所有的neighbors，只要没访问过，就可以选择它作为下个访问的节点。

goodluck888 发表于 2016-12-9 04:17
backtracking吧。做topo sort的时候，选择下一个访问的node的顺序是按照自己生成的graph的。但其实对于所 ...

你是BFS做的还是DFS呢？ 能再解释一下不？ 刚刚想了一下 没想出来呀。。

我觉得可以bfs， 每层都是当前入度为0， 然后一层里面可以随便顺序？ 然后组合一下就是所有结果？

小A要当码农 发表于 2016-12-9 04:24
你是BFS做的还是DFS呢？ 能再解释一下不？ 刚刚想了一下 没想出来呀。。

toposort我写的是dfs。
比如有a->b,a->c 这样的图。先选b和c都行，会有不同的解，所以我觉得就是backrtracking啦

期末求过 发表于 2016-12-9 06:09
我觉得可以bfs， 每层都是当前入度为0， 然后一层里面可以随便顺序？ 然后组合一下就是所有结果？

嗯 差不多这个意思

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

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

小A要当码农 发表于 2016-12-11 04:38
我想了一下， 大概意思是不是每一层都会有一个available list（当下degree为0的点），然后遍历所有可能？

没错 我觉得是这样的～～

goodluck888 发表于 2016-12-11 04:44
没错 我觉得是这样的～～

谢谢 祝好运～