出版時間:2008-3 出版社:電子工業(yè)出版社 作者:《編程之美》小組 編 頁數(shù):327
Tag標(biāo)簽:無
前言
推薦序我在卡內(nèi)基梅隆大學(xué)畢業(yè)找工作的時候,經(jīng)常和其他同學(xué)一起交流面試的經(jīng)驗(yàn)。當(dāng)時“聞面色變”的公司有微軟,研究所有DEC的SRC。每次有同學(xué)去微軟或SRC面試回來都被其他人追問有沒有什么有趣的面試題。我也是那時第一次聽說下水道井蓋為什么是圓的。我自己申請微軟美國研究院時被面試了兩天,見了15個人,感覺壓力很大。至今還記得被一位面試官不斷追問我論文中一個算法的收斂性的熱烈討論。在微軟工作的十幾年中,我自己也面試了非常多的新員工。特別在微軟亞洲研究院的九年,經(jīng)常感覺很多剛剛畢業(yè)的優(yōu)秀學(xué)生基礎(chǔ)很好,但面試的準(zhǔn)備不足。我非常欣慰地看到鄒欣工程師和微軟亞洲研究院其他同事們努力編寫了這本好書,和大家一起分享微軟的面試心得和編程技巧。相信更多的同學(xué)會因此成為“筆霸”,“面霸”,甚至“offer霸”。程序很美妙,雖然很難寫。程序要想寫的好,需要學(xué)好一定的基礎(chǔ)知識,包括編程語言,數(shù)據(jù)結(jié)構(gòu)和算法。程序?qū)懙暮玫娜送ǔ6加猩髅艿倪壿嬎季S能力和良好的數(shù)理基礎(chǔ)。還需要熟悉編程環(huán)境和編程工具。古人說“見文如見人”。我覺得程序同樣也能反映出一個人的功力和風(fēng)格。好的程序讀來非常賞心悅目。我以前常問的一道面試題是“寫一段自己覺得寫過的最好的程序”。編程很艱苦,但是很有趣。本書的作者們從游戲中遇到的編程問題談起,介紹了數(shù)字和字符串中的很多技巧,探索了數(shù)據(jù)結(jié)構(gòu)的竅門,還發(fā)掘了數(shù)學(xué)游戲的樂趣。我希望讀者在閱讀本書是能找到編程的快樂,欣賞到編程之美。本書適合計算機(jī)學(xué)院、軟件學(xué)院、信息學(xué)院高年級本科生、研究生作為軟件開發(fā)的參考教材。也是程序員繼續(xù)進(jìn)修的優(yōu)秀閱讀材料。更是每位申請微軟公司和其他公司軟件工程師面試的必讀秘笈。人類的生活因?yàn)閮?yōu)秀的程序員和美妙的程序而變得更加美好。
內(nèi)容概要
本書收集了約60道算法和程序設(shè)計題目,這些題目大部分在近年的筆試,面試中出現(xiàn)過,或者是被微軟員工熱烈討論過。作者試圖從書中各種有趣的問題出發(fā),引導(dǎo)讀者發(fā)現(xiàn)問題,分析問題,解決問題,尋找更優(yōu)的解法。本書的內(nèi)容分為下面幾個部分:
? 游戲之樂:從游戲和其他有趣問題出發(fā),化繁為簡,分析總結(jié)。
? 數(shù)字之魅:編程的過程實(shí)際上就是和數(shù)字及字符打交道的過程。這一部分收集了一些好玩的對數(shù)字進(jìn)行處理的題目。
? 結(jié)構(gòu)之法:匯集了常見的對字符串、鏈表、隊列,以及樹等進(jìn)行操作的題目。
? 數(shù)學(xué)之趣:列舉了一些不需要寫具體程序的數(shù)學(xué)問題,鍛煉讀者的抽象思維能力。
書中絕大部分題目都提供了詳細(xì)的解說。 每道題目后面還有一至兩道擴(kuò)展問題,供讀者進(jìn)一步鉆研。
書中還講述了面試的各種小故事,告訴讀者微軟需要什么樣的技術(shù)人才,重視什么樣的能力,如何甄別人才?;卮鹱x者關(guān)于IT業(yè)面試,招聘,職業(yè)發(fā)展的疑問。這本書的很多題目會出現(xiàn)在IT
行業(yè)的各種筆試,面試中。但本書更深層的意義在于引導(dǎo)讀者思考,和讀者共享思考之樂,編程之美。
作者簡介
鄒欣,現(xiàn)任微軟亞洲研究院技術(shù)創(chuàng)新組研發(fā)主管。他從1996年起在微軟Outlook 產(chǎn)品團(tuán)隊從事開發(fā)工作, 2003 年到2005 年,在微軟Visual Studio Team System產(chǎn)品團(tuán)隊負(fù)責(zé)軟件質(zhì)量管理工具的開發(fā)。加入微軟前,鄒欣從事過商用Unix系統(tǒng)、GPS/GIS軟件開發(fā)以及軟件測試工作。2007年出版了《移山之道——VSTS軟件開發(fā)指南》一書。他1991年獲北京大學(xué)計算機(jī)軟件專業(yè)學(xué)士學(xué)位。1996 年獲美國Wayne State University(韋恩州立大學(xué))計算機(jī)軟件專業(yè)碩士學(xué)位。
書籍目錄
第1章 游戲之樂——游戲中碰到的題目
1.1 讓CPU占用率曲線聽你指揮
1.2 中國象棋將帥問題
1.3 一摞烙餅的排序
1.4 買書問題
1.5 快速找出故障機(jī)器
1.6 飲料供貨
1.7 光影切割問題
1.8 小飛的電梯調(diào)度算法
1.9 高效率地安排見面會
1.10 雙線程高效下載
1.11 NIM(1)一排石頭的游戲
1.12 NIM(2)“拈”游戲分析
1.13 NIM(3)兩堆石頭的游戲
1.14 連連看游戲設(shè)計
1.15 構(gòu)造數(shù)獨(dú)
1.16 點(diǎn)游戲
1.17 俄羅斯方塊游戲
1.18 挖雷游戲
第2章 數(shù)字之魅——數(shù)字中的技巧
2.1 求二進(jìn)制數(shù)中1的個數(shù)
2.2 不要被階乘嚇倒
2.3 尋找發(fā)帖“水王”
2.4 的數(shù)目
2.5 尋找最大的K個數(shù)
2.6 精確表達(dá)浮點(diǎn)數(shù)
2.7 最大公約數(shù)問題
2.8 找符合條件的整數(shù)
2.9 斐波那契(Fibonacci)數(shù)列
2.10 尋找數(shù)組中的最大值和最小值
2.11 尋找最近點(diǎn)對
2.12 快速尋找滿足條件的兩個數(shù)
2.13 子數(shù)組的最大乘積
2.14 求數(shù)組的子數(shù)組之和的最大值
2.15 子數(shù)組之和的最大值(二維)
2.16 求數(shù)組中最長遞增子序列
2.17 數(shù)組循環(huán)移位
2.18 數(shù)組分割
2.19 區(qū)間重合判斷
2.20 程序理解和時間分析
2.21 只考加法的面試題
第3章 結(jié)構(gòu)之法——字符串及鏈表的探索
3.1 字符串移位包含的問題
3.2 電話號碼對應(yīng)英語單詞
3.3 計算字符串的相似度
3.4 從無頭單鏈表中刪除節(jié)點(diǎn)
3.5 最短摘要的生成
3.6 編程判斷兩個鏈表是否相交
3.7 隊列中取最大值操作問題
3.8 求二叉樹中節(jié)點(diǎn)的最大距離
3.9 重建二叉樹
3.10 分層遍歷二叉樹
3.11 程序改錯
第4章 數(shù)學(xué)之趣——數(shù)學(xué)游戲的樂趣
4.1 金剛坐飛機(jī)問題
4.2 瓷磚覆蓋地板
4.3 買票找零
4.4 點(diǎn)是否在三角形內(nèi)
4.5 磁帶文件存放優(yōu)化
4.6 桶中取黑白球
4.7 螞蟻爬桿
4.8 三角形測試用例
4.9 數(shù)獨(dú)知多少
4.10 數(shù)字啞謎和回文
4.11 挖雷游戲的概率
章節(jié)摘錄
插圖:
媒體關(guān)注與評論
這是一本讓人著迷的書! 從我得到樣書的那一刻起,在每天的閑暇時間閱讀和思索這本書中的題目就成了我的一個新習(xí)慣。雖然網(wǎng)絡(luò)上早就流傳著不少微軟面試題,坊間也不乏一些程序員面試類的圖書,但是像這樣集中展示高水平編程面試題目,并且以啟發(fā)性方式對這些題目予以權(quán)威解答的圖書,這還是第一本。對于那些正在準(zhǔn)備面試的同學(xué)來說,這本書毫無疑問是寶貴的學(xué)習(xí)資料。而在我看來,即使是對于已經(jīng)工作的程序員來說,這本書也是非常值得用心閱讀的。 實(shí)話實(shí)說,對于算法和數(shù)學(xué)類謎題的意義和價值,在程序員社群里長期以來就存在很大的爭議。CSDN上每隔一段時間就會有人討論“算法真的重要嗎”或者“數(shù)學(xué)真的重要嗎”這樣的問題。很多人對此都持質(zhì)疑甚至是否定態(tài)度,他們認(rèn)為,對于企業(yè)來說,是軟件產(chǎn)品而不是具體的程序創(chuàng)造了價值,而創(chuàng)造成功的軟件產(chǎn)品是一個龐大而復(fù)雜的系統(tǒng)工程,優(yōu)質(zhì)的算法和程序在其中的作用是有限的,相反,對平臺和系統(tǒng)的理解、對領(lǐng)域知識和規(guī)則的掌握、軟件質(zhì)量的控制、產(chǎn)品設(shè)計、架構(gòu)的選擇和設(shè)計、平臺和工具選型,以至于團(tuán)隊管理和有效溝通,對于軟件工程師來說是更為重要的技能和素質(zhì)。相比之下,算法和數(shù)學(xué)只要基礎(chǔ)扎實(shí)就可以了,在實(shí)踐當(dāng)中反而不如上面那些要素顯得重要,更沒有必要在類似智力測試般的面試謎題和奇技淫巧上花費(fèi)太多心思了。 這樣的看法,當(dāng)然有很有價值的方面。當(dāng)代的軟件工程師,確實(shí)需要建立更全面的知識技能體系和系統(tǒng)思維,但是以此來否定和貶低算法和數(shù)學(xué)基本功的重要性,否定面試謎題的意義和價值,則又屬于只見樹木不見森林。事實(shí)上,這些謎題考察和鍛煉的,并不是算法和數(shù)學(xué)的“奇技淫巧”,而是扎實(shí)、嚴(yán)密和具有創(chuàng)造性的思考能力,面對問題有條不紊的分析能力,和不斷深入、刨根問底的精神。毫無疑問,這些素質(zhì),都是軟件工程師身上最寶貴的東西。 本書就是對這一問題的有力證明。請翻開這本書,隨便挑選幾個問題,認(rèn)真思考,嘗試解答,再看看作者的思路,在其啟發(fā)下更進(jìn)一步思考,嘗試給出更多更好的解決方案,甚至更進(jìn)一步,提出書中都沒有提出的問題,把問題想透,把程序?qū)崿F(xiàn)出來,驗(yàn)證自己的想法。毫無疑問這樣的閱讀方法是相當(dāng)吃功夫的,但通過這樣的方式,不但能夠最大程度地獲得本書的價值,也能夠?qū)崒?shí)在在提高讀者的基本功、思考力和創(chuàng)造力。毫無疑問,這些能力的意義要遠(yuǎn)比任何具體知識和技能的獲得都更重要。對系統(tǒng)與平臺的理解也好,對領(lǐng)域知識的掌握也好,產(chǎn)品的設(shè)計、架構(gòu)的選擇也好,所有這些算法之外的技能,不都需要強(qiáng)悍的思考能力的支撐才能獲得嗎?事實(shí)上,在這個知識開放共享的時代,頭腦和思維才是唯一核心的競爭力,從這個意義上講,這本書是直接面向核心競爭力發(fā)展的,其意義何其大也! 這本書另一個必須要提的意義,就是它的“美”。真正的程序員都領(lǐng)略過程序之美,那些簡潔有力的代碼,精巧嚴(yán)密的構(gòu)思,高效直接的解決方案,美得令人窒息。可惜,在日益工業(yè)化和利益驅(qū)動的IT中,這種美已經(jīng)是越來越少見的東西。但我想每一個真正熱愛編程的人,都渴望欣賞這種美,渴望在思考過程中一次次“Aha!”式的愉悅。這本書就能夠最有效地滿足我們欣賞編程之美的渴望,題目的美,思考過程的美,解答的美,延伸思考的美,這種美的感覺,對于真正的程序員來說,本身就是一種精神享受。 雖然這本書表面上是指導(dǎo)面試的,但是依我來看,已經(jīng)工作的職業(yè)程序員更有必要好好讀讀這本書。畢竟世界很大,不是每個人都要去微軟或者谷歌,而這本書的意義絕不僅僅在面試,更重要的是在編程之美,思考之美。 潘愛民傾力推薦《編程之美——微軟技術(shù)面試心得》 我很早知道鄒欣計劃要寫這樣一本書,也能夠預(yù)計到這本書定會廣受歡迎,因?yàn)樗袭?dāng)前大量求職人員的需求,畢竟于他們而言,誰不想知道微軟亞洲研究院在招人時候問些什么問題呢。另一方面,把考察軟件技術(shù)人員專業(yè)知識和相應(yīng)技能的各種手段加以歸納和整理,這本身也是對業(yè)界的貢獻(xiàn),所以,我相信,一旦這本書如計劃般完成,其對業(yè)界的影響將是深遠(yuǎn)的。 在我的面試經(jīng)歷中,通過一些具體的程序問題來考察人,往往是最有效的,即使是一些人所皆知的問題,也往往能夠挖掘出被面試者的亮點(diǎn)或弱點(diǎn),原因在于,每個問題都有不同層次的解答之辭,面試者總是可以刨根究底地問下去。我們在看一段程序的時候,思路固然重要,細(xì)節(jié)也是不可忽視的,比如整數(shù)是否越界、指針是否為空,等等。這些細(xì)節(jié)可以用于考察基本功,毫無疑問,基本功不扎實(shí)的人通常很難得到面試者的青睞。 當(dāng)拿到這本書的樣稿時,我迫不及待地放下手頭工作,閱讀起來。有些題目的內(nèi)容會引起強(qiáng)烈的共鳴,尤其是那些自己非常熟悉并且又深知解答的題目;也有一些題目讓我異常驚詫,原來除了我所知道的解答思路之外,還有更好的解答以及更深層次的原因。還有一些題目是從來沒想到過的。閱讀過程是一次愉快的享受,也是腦細(xì)胞持續(xù)活躍的過程。 充滿好奇心的人們總是能從生活的點(diǎn)點(diǎn)滴滴中想到或找到各種優(yōu)化的余地,比如說,樓宇中的電梯常常顯得很“傻”(微軟研究院所在的希格瑪大廈的電梯是一個典型的例子),更智能或更有效的調(diào)度策略完全有可能;近距離內(nèi)的交通燈聯(lián)動可以有效地提高行車效率。程序員在玩電腦游戲的時候常常會想著怎么自動完成一些過程,比如說,本書中提到的俄羅斯方塊游戲中如何有效地旋轉(zhuǎn)和移動可快速地消除積木塊、24點(diǎn)游戲如何自動求解、推箱子游戲如何自動求解,掃地雷游戲如何自動完成,等等。實(shí)際上,這些自然的疑問正是訓(xùn)練程序能力的好來源,本書采錄了不少此類題目。因此,閱讀本書可以滿足很多人的好奇心,這也正是我自己的體會。 盡管作者在前言中聲稱“雖經(jīng)過幾輪審核,不少解法仍可能有漏洞或錯誤”,但事實(shí)上,在絕大多數(shù)題目的講解中,作者已經(jīng)由淺入深地把問題分析透了,而且,作者也為讀者指出了進(jìn)一步思考這些題目的方向。不同背景的人在看到這些題目的時候,可能會有不同的解法,甚至完全不同的思路。舉例而言,鄒欣曾經(jīng)問過我如何控制CPU占用率曲線的問題,我當(dāng)時的直覺是,直接截取Taskmgr調(diào)用的相關(guān)API函數(shù),從而達(dá)到隨意控制CPU占用率曲線的目的。顯然這不是規(guī)范的做法,本書的分析揭示了這個問題背后的本質(zhì)道理以及考問要點(diǎn)。另一種情況,即使有的問題你深知其理,但看過本書仍然很有收獲。例如,在斐波那契數(shù)列問題中,我知道直接遞歸法的缺陷,也知道如何簡化成迭代法來改進(jìn)效率,還會推導(dǎo)通項(xiàng)公式,但是,書中的細(xì)致講解仍然讓我對這個問題有了更進(jìn)一步的認(rèn)識。這是本書的深度所在,如果讀者更加在意所選題目背后的深層次道理,相信書中的講解不會讓你失望。 除了趣味性以外,本書中的題目講解之中也融入了大量專業(yè)知識。這使得本書可以作為計算機(jī)數(shù)據(jù)結(jié)構(gòu)課程或算法課程的輔助參考書。比如,有些問題的解答涉及到貪心算法或動態(tài)規(guī)劃方法,算法的復(fù)雜度分析更是無處不在。數(shù)據(jù)結(jié)構(gòu)教科書中介紹的鏈表(list)、隊列、hash表和二叉樹等常用數(shù)據(jù)結(jié)構(gòu)也多有提及。因此,對于正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)或算法課程的學(xué)生來說,本書中的問題正是對課程中所學(xué)知識的一次檢閱,通過本書他們可以看到這些知識是如何用于解決實(shí)際問題的。從我自己的教學(xué)經(jīng)驗(yàn)來看,這樣的題解分析有助于提高學(xué)生的學(xué)習(xí)興趣。另一方面,閱讀本書也需要有必要的計算機(jī)算法和程序設(shè)計知識作為基礎(chǔ),否則閱讀的效果會大打折扣。 我大致了解本書的成書過程,從策劃階段到題目收集,再到成稿和改稿,我能體會到鄒欣和他的寫作團(tuán)隊傾注了大量的精力來寫作這本書。他們盡了最大的努力來編寫這本書,無論是原創(chuàng)的題目,還是傳統(tǒng)的題目,他們都努力把題目分析透徹并提供擴(kuò)展思考的余地。鄒欣在發(fā)送樣稿給我的信中說道:“Our goal is to ship a top quality book. I can't say "world class", but definitely "best in China" level.”以我閱讀這本書的體會來講,他們做到了這一點(diǎn)。我相信,這本書的出版會符合我當(dāng)初的預(yù)期,它會影響到很多人。 潘愛民 2008年2月
編輯推薦
夢想改變世界,據(jù)說編程的人都懷揣著一個改變世界的夢想:編程神奇而充滿力量。無數(shù)的年輕人投身其中,用夢想和思考改變世界?!毒幊讨?微軟技術(shù)面試心得》是來自微軟技術(shù)人員的杰作,他們和你有同樣的夢想。
圖書封面
圖書標(biāo)簽Tags
無
評論、評分、閱讀與下載