作者chucheng (CHUCHU)
看板studyabroad
标题[闲聊] Intern面试的考题(CS)
时间Wed Jan 12 08:36:11 2011
我後来重新确认了问题，把一些人来信问我的内容更新如下
迷之声：原来这题有其它人被考过 ～ 哈
其实原考题和我陈述的有一点不同（So Sorry) 以下黄色是更新
(Sorry, 我没把问题搞清楚就Po了，原来是买航线不是买机票…)
这是我朋友遇到…面试的考题…
美国某家 超大 软体公司…
他不问还好，一问了…愈想愈头痛，不想出答案不行…(怒)
所以发来版上给大家一起想想(面试已结束)
以下给CS(Computer Science)的人服用，其它科系请左转离开(或是看有趣也行)
一开始是先简单问一下知不知道什麽是Travelling Salesman Problem...
这里：
http://en.wikipedia.org/wiki/Travelling_salesman_problem
这个问题已经都知道是NP-HARD，所以基本上就是确定一下你修过演算法(我猜)
接下来面试官说…
我们把问题简化一点
假设某国家有n个城市
彼此之间飞机互连(但是机票价格不一定)
为了复杂问题，A飞B，和B飞A的价格是不一样的
到这里，他和我都猜测…可以想像成一个Graph,
假设G好了，其中节点为V，连结为E
则G(V,E)是一个有向图(每个E有权重，代表飞机票的价格)
第一个问题(我们有想出来了)
就是给定一个起点，问你飞到终点(可能需要转机)，最便宜的总价是多少
考官要求答案一定要正确(最佳解)，然後程式的时间/空间复杂度愈佳 愈好
最笨的解法就是把所有可能的路线都列出来
当然修过AI的我，就想起A* Search...
我的同学很紧张时，是回答用BFS(Breadth-First Search)
考官当然问他有没更好的解法…所以我猜他在这已经阵亡了…
接下来就是…implement …(时间流逝)
考官结束前，顺口讲了，叫他回去想一想(丢了另一个"
问题")
(我们一致认为这个就是考官要问的第二个问题，只不过因为该受测者提早阵亡XD)
这个问题就难倒好几个同学了(包含我)
----正文开始----
考官说，如果
你要开始经营一间航空公司
因此，客人来自四面八方
故：
(1) 起点不知道(每个点都可能，出发地不明)，终点当然要包含所有的点（客人目的地未知）
(2)
你的任务是找出该买的所有航线
注：假设所有的
航线都买是最差的解(因为很贵)
你的任务是：
讲白一点，就是要用最便宜的航线串好
所有的机场
(
要能去能回，不然客人不就跑去别家航空了)
这个问题该怎麽解呢？(当然，时间和空间复杂度要愈佳愈好)
一开始我们认为这个问题很简单，先把所有的航线(Edge)列出来
例如
起 价格 终
V1 100 V2
V2 200 V3
…
不列出所有可能的组合，而直接Reversely Sort 所有的 Edge based on Weighting
注：航线 V1-->V2 的价格不保证等於V2->V1的价格
然後Greedy的方式，把由高到低的把贵的航线给干掉…
每干掉一个Edge，要确定不影响条件1，直到没有可以干的Edge就停…
这样得到的保证是解，但是不是最佳解就不得而知了…
检查条件就是确定indegree >1(保证到得了)
，以及out-degree >1(保证出得去)
假设有m个机场，n个路线，存在array里的话
时间的难点应该是在sort，应是 O(n log n) ，只有的检查很快
空间的话，需要 m * 2 (indegree + outdegree) for 机场(检查条件1)
以及 2 * n for 路线(起点+终点) <--用来sort
应该是O(n) (n > m，不然串不起来)
正当我很高兴的觉得这样搞定了
心里总觉得…好像怪怪的，会不会太简单了
以上是心得分享…
下面是问题…
有人能帮忙举个反例，否定我们想出来的演算法
OR
能提出更好的演算法就更佳了…
总之觉得这个interview的问题蛮有趣的… :)
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 131.179.64.154
1F：推 poplin:最後一个问题用DP可解吗? 第一个想到的是这个 01/12 08:46
2F：→ yr:不就 all-pair shortest path ，关键字 Floyd-Warshall 01/12 09:20
3F：推 Kenzuki:楼上,shortest path不需要包含"所有"的点 01/12 09:23
4F：→ CryAll:Max-flow Min-cut? 01/12 09:57
5F：→ chucheng:To 楼上 Max Flow限制是single source/single sink 01/12 09:59
6F：推 genghiskii:好文一定推 01/12 11:13
7F：→ yr:shortest path 本来就不需要包含所有的点，F-W alg 也没包含 01/12 11:37
8F：→ yr:这个问题本来就是很简单，如果知道起点就是 single source 01/12 11:38
9F：→ yr:shortest path tree ，不知道起点用 Floyd-Warshall Alg. 01/12 11:38
10F：→ yr:可以解。 01/12 11:38
11F：→ yr:称为 all-pair shortest path 不是因为包含所有点，是因为是要 01/12 11:40
12F：→ yr:找所有的 src/dest 之间的最短（便宜）路径 01/12 11:41
13F：→ yr:如果起点已知，那跑个 Dijkstra's alg 就可以了 01/12 11:49
14F：推 chees:原PO第二题的检查条件似乎有问题? 例如两个点最便宜是对飞 01/12 16:01
15F：→ chees:这样的话 最後会造成其他点飞不到这两个点吧? 01/12 16:02
16F：推 Kenzuki:to yr,你看清楚,第二个问题是要找一个path包含所有的点 01/12 16:16
17F：推 Kenzuki:第一个问题是shortest path problem没错,但第二个不是 01/12 16:21
18F：→ yr:这是他没写清楚，终点要包含所有点是什麽意思？ 01/13 01:57
19F：→ yr:一个 path 的终点就只有一个，所以这会让人误解成找出从这个 01/13 01:58
20F：→ yr:src 到其它点的最短路径。如果不是终点，那应该是 intermediate 01/13 01:58
21F：→ yr:nodes 吧？ 01/13 01:58
22F：→ chucheng:我自己想到反例了，想像二个圈圈（A->B->C->A)及 01/13 02:37
23F：→ chucheng:(X->Y->Z->X) 假设原先还有A<-->X有互连（但很贵) 01/13 02:37
24F：→ chucheng:我的笨方法会砍掉A<-->X，然後每个点还是InDegree=1 且 01/13 02:38
25F：→ chucheng:OutDegree=1 ，但其实图不连通…因此这个检查方法是错误的 01/13 02:38
※ 编辑: chucheng 来自: 131.179.64.241 (01/13 02:40)
26F：推 wenjoseph:minimum strongly connected subgraph? 01/13 05:42
27F：→ chucheng:minimum spanning strong sub(di)graph (MSSS) 01/13 06:57