在这里感谢板上的一个兄弟给了interview的机会 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

在这里感谢板上的一个兄弟给了interview的机会

在这里感谢板上的一个兄弟给了interview的机会# JobHunting - 待字闺中

J*R2013-02-12 08:02

1 楼

题目问的不难，但是我答题的时候脑子有点短路，等挂了电话以后开始恍然大悟，呵呵
。不管怎么样，在此表示感谢！
题目如下，供大家嘲笑一下：）
有如下机票：
LA-NY
NY-NV
NV-ATL
ATL-DC
SFO-LA
要求找出从头到尾的机票顺序：SFO-LA-NY-NV-ATL-DC
挺简单的一个题目，我吭哧了20多分钟，最后想出来了，还不是最简单的方法。

t*h2013-02-12 08:02

2 楼

头尾各出现一次吧找到后穿起来就醒了 O(N)

【在 J****R 的大作中提到】

: 题目问的不难，但是我答题的时候脑子有点短路，等挂了电话以后开始恍然大悟，呵呵
: 。不管怎么样，在此表示感谢！
: 题目如下，供大家嘲笑一下：）
: 有如下机票：
: LA-NY
: NY-NV
: NV-ATL
: ATL-DC
: SFO-LA
: 要求找出从头到尾的机票顺序：SFO-LA-NY-NV-ATL-DC

J*R2013-02-12 08:02

3 楼

对的，但我当时没想明白，净琢磨怎么hash了。

【在 t*********h 的大作中提到】

: 头尾各出现一次吧找到后穿起来就醒了 O(N)

d*x2013-02-12 08:02

4 楼

You need to merge disjoint cycles. Otherwise you may miss this test data:
LA-NY
NY-SFO
NY-DC
DC-ATL
ATL-NY

呵呵

【在 t*********h 的大作中提到】

: 头尾各出现一次吧找到后穿起来就醒了 O(N)

J*R2013-02-12 08:02

5 楼

是的，后来为了简单化，cycle的情况被排除了。
我的思路是建2个hashtable:
hashtable1
hashtable2
从第一张机票开始找，用hashtable1找到后面的iterate,然后反过来，用hashtable2找
到之前的iterate.

【在 d**********x 的大作中提到】

: You need to merge disjoint cycles. Otherwise you may miss this test data:
: LA-NY
: NY-SFO
: NY-DC
: DC-ATL
: ATL-NY
:
: 呵呵

h*n2013-02-12 08:02

6 楼

典型的topological sorting吧？

【在 J****R 的大作中提到】

t*h2013-02-12 08:02

7 楼

如果复杂情况的话比如有cycle和multiple path 要先建立graph 在bfs找shortest
path 就变的和上面的word ladder本质一样了

【在 d**********x 的大作中提到】

: You need to merge disjoint cycles. Otherwise you may miss this test data:
: LA-NY
: NY-SFO
: NY-DC
: DC-ATL
: ATL-NY
:
: 呵呵

d*x2013-02-12 08:02

8 楼

bfs最短路径。。只是找一条路吧？
我的意思是说，实际上要找的可能是个从0入度节点开始到0出度节点的euler
traversal
当然后来lz补充说复杂情形去掉了。。所以就忽略吧

【在 t*********h 的大作中提到】

: 如果复杂情况的话比如有cycle和multiple path 要先建立graph 在bfs找shortest
: path 就变的和上面的word ladder本质一样了

f*e2013-02-12 08:02

9 楼

Eulerian traversal有现成的非常有趣的算法，那本combinatorial generation书里有
，虽然写的乱七八糟，不过还是有部分价值。不过这题好像是经过每个node一次，不是
经过每条edge一次。

【在 d**********x 的大作中提到】

: bfs最短路径。。只是找一条路吧？
: 我的意思是说，实际上要找的可能是个从0入度节点开始到0出度节点的euler
: traversal
: 当然后来lz补充说复杂情形去掉了。。所以就忽略吧

d*x2013-02-12 08:02

10 楼

这道题是每个edge一次啊。。。
你想想机票是干啥的 = =|||

【在 f*****e 的大作中提到】

: Eulerian traversal有现成的非常有趣的算法，那本combinatorial generation书里有
: ，虽然写的乱七八糟，不过还是有部分价值。不过这题好像是经过每个node一次，不是
: 经过每条edge一次。

2024-01-28 18:01

2024-01-09 19:01

2024-01-07 18:01

2024-01-06 18:01

2024-01-06 18:01

2023-12-13 17:12

2023-12-02 07:12

2023-11-26 18:11

中美航班重磅消息！每周85班，直飞更方便！

微软、亚马逊、谷歌大裁员！哪些科技和零售公司有缩减规模计划？

中国外长王毅：中美关系已经止跌回稳

脱轨事故造成20多人受伤联邦调查纽约市全部地铁系统

更多 2024-06-02 的新闻