※ [本文转录自 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 ※ 编辑: chucheng 来自: 131.179.64.154 (01/12 10:13) ※ 编辑: chucheng 来自: 131.179.64.241 (01/13 02:24)