[閒聊] Intern面試的考題(CS)

看板studyabroad作者chucheng (CHUCHU)時間15年前 (2011/01/12 08:36)推噓7(7推 0噓 21→)

留言28則, 8人參與討論串1/1

我後來重新確認了問題，把一些人來信問我的內容更新如下迷之聲：原來這題有其它人被考過～哈其實原考題和我陳述的有一點不同（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

01/12 08:46, , 1^F

01/12 08:46, 1^F

→

01/12 09:20, , 2^F

01/12 09:20, 2^F

推

Kenzuki

01/12 09:23, , 3^F

01/12 09:23, 3^F

→