校园招聘 - 比较容易的面试题
又到校園招聘的季節(jié)了, 自從和一些同事出版了《編程之美》一書之后, 我經(jīng)常收到一些關(guān)于面試, 編程,? 和“題庫”的詢問。 其實我自己對算法沒有什么研究, 有些問題都答不上,? 研究院最近搬了一次家， 原來的 “題庫”也不知道搬到那一層樓去了。? 不過, 常在河邊走, 哪能不濕鞋?? 在微軟亞洲研究院這個水很深的地方混,? 一些題目還是打濕了我的腳。? 今天新的校園招聘 正式開始了,? 我準備了幾個比較容易的題目， 作為 “獻禮”。這些題目不是一上來就刷刷刷寫代碼的那種, 我自己都不知道最佳解法是什么, 如果你有好的想法, 可以討論一下.?
1. 只考數(shù)據(jù)結(jié)構(gòu)的題目
不少同學(xué)覺得《編程之美》上面的題目太難了, 還要寫那么多程序… 好, 其實也有很簡單的問題, 例如這一個 - 只考數(shù)據(jù)結(jié)構(gòu)的知識:
?
《編程之美》 中提到 “求數(shù)組最大子數(shù)組的和”這一題目，
?
?（圖1）
?
腦快手快的同學(xué)寫一個 10 行的程序就把這個問題搞定了。?
?
我們還把這個問題擴展到二維， 例如:
?
?
(圖2)
?
我還問過一些同學(xué), 如果數(shù)組首尾相連, 像一個輪胎一樣, 又怎么辦呢？ 這些同學(xué)也給出了漂亮的答案, 并且用 SilverLight/WPF 給畫了出來:
(圖3)
?
好，設(shè)想我們有一張紙帶，兩面都寫滿了像 [圖2] 那樣的數(shù)字, 我們把紙帶的一端扭轉(zhuǎn), 和另一端接起來, 構(gòu)成一個莫比烏斯環(huán) （M?bius Strip）.?
?
(圖4 – wikipedia)
?
我想盡管這個紙帶扭了一下,? 但是上面還是有數(shù)組, 還是有最大子數(shù)組的和， 對么？ 在求最大子數(shù)組的和之前, 我們用什么樣的數(shù)據(jù)結(jié)構(gòu)來表示這些數(shù)字呢? 你可以用 Java, C, C#， 或其他語言的數(shù)據(jù)結(jié)構(gòu)來描述這個莫比烏斯環(huán)上的數(shù)組。數(shù)據(jù)結(jié)構(gòu)搞好了, 算法自然就有了。?
?
?
?
2. 舉一反一的問題
《編程之美》的第一題是讓W(xué)indows 任務(wù)管理器的CPU 使用率曲線畫出一個正弦波。我一直在想, 能不能把CPU 使用率邊上的網(wǎng)絡(luò)使用率也如法炮制一下呢?? 比如, 也來一個正弦曲線?
?
?
?
3. 人月的問題
如果你沒看過, 也至少聽說<人月神話>? (The Mythical Man-month) 這本在軟件工程領(lǐng)域很有影響的書.? 當你在微軟學(xué)術(shù)搜索中輸入 “manmonth” 這個詞的時候, 你會意外地碰到下面這個錯誤:
?
?
經(jīng)過幾次試驗之后, 你發(fā)現(xiàn)必須要輸入 “man-month” 才能得到希望的結(jié)果。 這不就是只差一個? ‘-’ 符號么?? 為什么這個搜索引擎不能做得聰明一些, 給一些提示 (Query Suggestion)? 或者自動把用戶想搜的結(jié)果展現(xiàn)出來 (Query Alteration)??? 我們在輸入比較長的英文單詞的時候, 也難免會敲錯一兩個字母, 網(wǎng)站應(yīng)該幫助用戶, 而不是冷冰冰地拒絕用戶啊。
?
微軟的學(xué)術(shù)搜索 (Microsoft Academic Search) 索引了超過 3千萬的文獻,? 2 千萬的人名, 怎么能以比較小的代價, 對經(jīng)常出現(xiàn)的輸入錯誤提供提示? 或直接顯示相關(guān)結(jié)果, 避免用戶反復(fù)嘗試輸入的煩惱???
?
你可能會說, 這很難吧,?? 但是另一家搜索引擎似乎輕易地解決了這個問題 (例子)。 所以, 還是有辦法的。
?
這個題目要求你:
1) 試驗不同的輸入, 反推出目前微軟的學(xué)術(shù)搜索是如何實現(xiàn)搜索建議 （Query Suggestion）的。
2) 提出自己的改進建議,? 并論證這個解決方案在千萬級數(shù)據(jù)規(guī)模上能達到 “足夠好” 的時間 (speed) 和空間 （memory usage）效率。
3) 估計這事需要幾個 人·月 （man-month） 才能做完?
?
?
----
有人問, 把題目都公開出去, 大家都知道答案了, 我們還怎么面試啊??
回答: 這就看面試官的功夫了.
?
三個題目都做好的應(yīng)屆畢業(yè)生, 請直接找我。
總結(jié)
以上是生活随笔為你收集整理的校园招聘 - 比较容易的面试题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 现代软件工程系列 结对编程 两周写好3D
- 下一篇： 现代软件工程讲义 5 项目经理 Prog