作者chucheng (CHUCHU)
看板Oversea_Job
標題[閒聊] Intern面試的考題(CS)
時間Wed Jan 12 09:08:19 2011
※ [本文轉錄自 studyabroad 看板 #1DBFT-Dh ]
作者: 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
推 poplin:最後一個問題用DP可解嗎? 第一個想到的是這個 01/12 08:46
推 tiwei:看到這題難度 我想大約是google or facebook 01/12 09:18
→ tiwei:MS, Amazon 一搬不會問到這麼難 01/12 09:18
推 eshai:所以面試前演算法的東西其實要很熟練耶! (我在講廢話嗎? XD) 01/12 09:37
→ kruz:會問到這樣應該是PhD等級的.. 01/12 09:43
→ chucheng:是PhD Level:) 01/12 09:45
推 pest:某e公司表示:這是公司機密 實作出來的那個人已經領股票養老了 01/12 09:47
推 pest:第一個部份感覺用Dijkstra解比較快 01/12 09:57
→ chucheng:一開始想到A*是想省空間,把這想成是下棋 01/12 10:03
→ chucheng:但Dijkstra似乎像BFS(要走過所有的可能),沒有pruning? 01/12 10:06
※ 編輯: chucheng 來自: 131.179.64.154 (01/12 10:13)
推 nukchichi:第一個我想到的也是Dijkstra. 其他不知道@@" 好難喔~ 01/12 10:40
推 vgod:看起來只是基本的single-pair和all-pairs shortest path? 01/12 10:50
推 ksl871:有沒有提到轉機的機場能不能重複? 01/12 11:47
推 gasper:轉機機場能不能重複沒差 最佳解一定不會有重複機場(loop) 01/12 12:23
推 NoisyNose:不一定喔,應該要看網路吧,可能重複某個hub解會更好 01/13 01:11
→ chucheng:可重覆,因為假設抵達B為一的路徑 是A,則唯一的方法就 01/13 01:32
→ chucheng:是從A->B, B->A, 再去其它點 01/13 01:33
※ 編輯: chucheng 來自: 131.179.64.241 (01/13 02:24)
推 pest:第二個問題好像還變更簡單了,找出讓所有機場雙向互連的edge? 01/13 03:05
→ chucheng:不一定是雙向互連,繞圈也行,這個後來我有找到 01/13 10:19
→ chucheng:應該是NP-HARD的....囧 01/13 10:19
推 smi1e:1.dijkstra 2.minimal spanning tree 01/13 16:07
推 smi1e:2 應該是 nlogn, 是要求要 n 嗎? 01/13 16:09
推 shaopin:你朋友後來有上嗎? 應該就是smi1e說得兩個類型沒錯.. 01/16 14:31