作者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