面試演算法100題
1. 面試中的計算題
算題者自己搞糊塗了，犯了邏輯上的錯誤。其實，根本就不存在少了10美元的問題。錯誤在於，說每個人實際交了90美元，共收3×90＝270美元，這是對的，但不用這270美元去加20美元，而應加退給他們的30美元，正好等於300美元。因為人家交的270美元中，被服務員拿了20美元，這20美元就在270美元裡面，怎麼還能去和270美元相加呢？如果20美元要加，只能與經理那裡的250美元相加，再加退給三人的30美元，總計300美元。這個問題實際上是個數學問題，也是個邏輯問題。
看了兩行看不下去了，吐槽一下。
現在某些小公司的面試官，面試題花式秀智商，一副全世界都求著他賜予工作的樣子。
3. 如何准備互聯網公司面試（演算法相關）
書籍： 《演算法導論》 這本是大部頭，很多人都看不完。我本人也並沒有看完，它跟了我這么多年，完全是屬於常看常新的牛書。每一次看，都發現會有新的收獲。比如，以前並不知道求K位數或者中位數有平均為O(n)復雜度的演算法。看到了別的地方的參考資料，才知道，原來《算導》上專門有一小節講這個內容。我基本上是本科比較集中的看了一遍，研一的時候又集中的看了一遍，才算是粗略的看完。但是其實，很多理論性的，以及圖論一部分依然還是沒有看完。個人推薦，先從簡單的開始，挑選比較熟悉的一些偏重與數據結構方面的知識作為起點。這本書的習題非常重要，要是有時間，能夠全部做完，那絕對是能夠神功在手了。其實，集中把，第二部分（排序），第三部分（數據結構），第四部分（高級設計，我基本主要看動態規劃和貪心），第五部分（高級數據結構，B樹和二項堆，並差集），第六部分（圖演算法，最大流部分較難，自己可以看情況掌握）。這些部分可以先從演算法本身開始，偽代碼全部看懂。因為演算法導論講的很詳細，而且有來龍去脈，基本不會有太大難度。數學證明，推薦大家掌握，但是，突擊或者第一次，可以選擇性的看看。我自己是重復看，才把證明看掉的。第一次看的時候，基本都跳過了。不過，證明和習題是精髓！希望如果有時間，一定要補回來。 《編程之美》《挑戰編程》 這本書絕對是將全中國企業，或者說是一部分懶惰的企業面試題庫提升了一個檔次的一本神書。網路面我師兄的時候，我師兄直接把有一道題的最優解答出來了。但是，那個面試官顯然是不知道最優解，一直在引導我師兄答出，這本書裡面的第四個解。呵呵。書很不錯。全部看一遍並不難。說個不好聽的，可以背下來，而且相信我，基本上絕對有用！比如說，n!後面有多少個0。我相信，你們今年面試或者筆試，一定會碰到這道題。《挑戰編程》大家可以自行考慮一下吧，這個完全是針對acm競賽的，不過，看看題也不錯。 《編程珠璣》 業界神書嘛。習題全部做完就是了。其實都是些小東西，但是，基本上一步步考察你的解決問題的能力。個人覺得，最常用的就是bit map做排序或者去重，拓展一下就是bloom filter，我當時都是在這本書裡面看到的。 《演算法技術手冊》 這本書貌似出鏡不多。書很薄，代碼寫的非常好，其實基本上全部都是基礎演算法和數據結構的實現。但是，它牛逼就在於，代碼寫的太好了，基本上，看一遍，絕對能背下來。面試基礎很重要。基本上每個筆試或者面試，都會考一個100行以內的小程序。比如，給定一棵樹，以及其中一個節點x，要求出這棵樹的中序遍歷序列中，x的後續節點，非遞歸實現。這種題非常簡單，但是，真正寫對的，其實並不多。《STL源碼剖析》《C標准庫》 都不厚。挑著看一遍非常舒服。特別是，看看STL每個數據結構迭代器類型啊，紅黑書如何實現啊。C標准庫，最常見的，比如strcpy()和memcpy()有什麼區別啊。特別是，STL，看過之後，對泛型還是能有一定了解的。《C專家編程》《Effective c++》《深度探索C++對象模型》 第一本比較簡單，可以當八卦書看。後兩本其實也沒啥好說的，其實都是些業界公認的牛書。我再重復一遍也沒什麼意義。但是，的確，考察基本上也就都是這么幾本書上面的東西。基本上後兩本主要側重看c++對象方面的一些指示，特別是多態相關的。 《具體數學》《組合數學》 這兩本其實可以看作修身養性的書。我當時是時間比較充裕的時候看完的。純突擊，大家就可以跳過了。但是，看完真的很有用。比如說，你們就可以跟面試官扯約瑟夫環的構造解了（這道題我覺得80%會遇到），直接推推公式，就不用寫模擬代碼了。《組合數學》也是，很多筆試一般會有些小智力題。不過，其實一般的題目，不看這本書也可以搞定。所以，這兩本僅供參考。大家有興趣的時候，可以翻翻。《Linux內核源碼剖析》《Linux環境高級編程》…… 要是有機會，能看看最好。因為很多公司都會考察Linux相關的知識。最少要會點腳本，一些簡單的Linux命令，以及正則表達式什麼的。要是能聊聊內核源碼或者驅動開發什麼的東西，面試官肯定更加喜歡了。 知識： c & c++ 首先要知道c和c++的區別。常考的有const的用法，一些生僻關鍵字比如extern，static的用法。 結構體與類的差別。類裡面的字對齊問題，也就是說一個類到底有多大。以及一個空的類有多大。 虛函數以及多態相關的顯然是重點。比如析構函數什麼時候需要寫成虛函數，構造函數是否可以是虛函數。 int a[10]; a 和 &a的區別。 java java我並不熟。但是基本上肯定會考一些虛擬機相關的，以及GC等知識。然後，一般招聘的java程序員都會問到很多多線程編程的東西，以及hadoop！這個絕對是重點，淘寶絕對就是問這個的。 操作系統 這個看工作崗位的實際要求。基本的進程線程區別==肯定是會問到的。要是要求高一些，就會問很多多線程編程的問題。一些競爭死鎖等基礎知識，一些進程調度的演算法，最近的kernel好像用的是CFS調度演算法。shell編程，如何讀取程序堆棧，寫一些core mp的讀取程序等等的。 數據結構 基本上所有的排序都要會寫。與樹有關的操作都要會些非遞歸版本。圖一般考的不多。Flood-Fill演算法等等。查找中位數。B樹和紅黑書最好要掌握，不用會寫，能扯扯基本就行。KMP，這個很有可能考！而且的確真的不好懂。要是實在不行，背下來吧。哈哈。 網路 這個其實比較基礎了。我個人網路方面的知識並不好。但是各種協議的基礎，幾次握手啊，一些操作系統的api實現到底是單工還是雙工用的是TCP還是UDP。我個人網路純粹靠拼RP。 資料庫 資料庫非常重要。基本的SQL肯定是要會的。最常見有一道題，inner join和out join的區別。MySQL是重點，基本上很多企業都是問這個。然後，網路扯多了會跟你扯MySQL引擎 的一些東西。這些我就不太懂了。要是能准備的話，或者說的確是做這方面的，就可以著重多准備下。 大規模數據處理這一塊絕對是重點！而且本身不是一個系統的學科分支。但是，基本上幾家大公司都會問這方面的。推薦先讀讀google那幾篇論文。Page Rank那一篇，然後Map Rece好像有幾篇吧。Big Table什麼的。推薦一個網址。這篇貌似是轉載的，我以前找到的源地址現在找不到了。處理這一類問題基本上思路都是，哈希，map rece以及bit map等等的。對了，推薦看一下外排序以及相關的敗者樹。這些都是大規模數據處理的一些典型問題。掌握了這些其實也就夠了。這塊有點屠龍之技的感覺，特別是對於學生，基本沒有誰能有機會把這些代碼實現出來。但是，沒辦法，這些公司就是喜歡考。看完那篇博客的，然後再自行查找一些資料，基本就夠了。萬變不離其中，而且，這些東西，沒辦法考那麼難的。 推薦一個博客吧，作者收集了100+道面試題，並且全部給出了代碼。把這個全部看完，基本上很多面試筆試，都是這些原題。 推薦Top Language裡面的今天我們思考系列，好幾年前的了。看大牛的思考過程，非常有幫助。希望自己能多想想再看答案。注意，google group好像有時被牆。 我把發芽網的題庫版塊也掃了一遍。 還有好多一時想不起來了。
4. 演算法面試
我在《再談「我是怎麼招程序員」》中比較保守地說過，「問難的演算法題並沒有錯，錯的很多面試官只是在膚淺甚至錯誤地理解著面試演算法題的目的。」，今天，我想加強一下這個觀點——我反對純演算法題面試！（注意，我說的是純演算法題）圖片源Wikipedia（點擊圖片查看詞條）我再次引用我以前的一個觀點——能解演算法題並不意味著這個人就有能力就能在工作中解決問題，你可以想想，小學奧數題可能比這些題更難，但並不意味著那些奧數能手就能解決實際問題。好了，讓我們來看一個示例（這個示例是昨天在微博上的一個討論），這個題是——「找出無序數組中第2大的數」，幾乎所有的人都用了O(n)的演算法，我相信對於我們這些應試教育出來的人來說，不用排序用O(n)演算法是很正常的事，連我都不由自主地認為O(n)演算法是這個題的標准答案。我們太習慣於標准答案了，這是我國教育最悲哀的地方。（廣義的洗腦就是讓你的意識依賴於某個標准答案，然後通過給你標准答案讓你不會思考而控制你）功能性需求分析試想，如果我們在實際工作中得到這樣一個題 我們會怎麼做？我一定會分析這個需求，因為我害怕需求未來會改變，今天你叫我找一個第2大的數，明天你找我找一個第4大的數，後天叫我找一個第100大的數，我不搞死了。需求變化是很正常的事。分析完這個需求後，我會很自然地去寫找第K大數的演算法——難度一下子就增大了。很多人會以為找第K大的需求是一種「過早擴展」的思路，不是這樣的，我相信我們在實際編碼中寫過太多這樣的程序了，你一定不會設計出這樣的函數介面 —— Find2ndMaxNum(int* array, int len)，就好像你不會設計出 DestroyBaghdad(); 這樣的介面，而是設計一個DestoryCity( City& ); 的介面，而把Baghdad當成參數傳進去！所以，你應該是聲明一個叫FindKthMaxNum(int* array, int len, int kth)，把2當成參數傳進去。這是最基本的編程方法，用數學的話來說，叫代數！最簡單的需求分析方法就是把需求翻譯成函數名，然後看看是這個介面不是很二？！（註：不要糾結於FindMaxNum()或FindMinNum()，因為這兩個函數名的業務意義很清楚了，不像Find2ndMaxNum()那麼二）非功能性需求分析性能之類的東西從來都是非功能性需求，對於演算法題，我們太喜歡研究演算法題的空間和時間復雜度了。我們希望做到空間和時間雙豐收，這是演算法學術界的風格。所以，習慣於標准答案的我們已經失去思考的能力，只會機械地思考演算法之內的性能，而忽略了演算法之外的性能。如果題目是——「從無序數組中找到第K個最大的數」，那麼，我們一定會去思考用O(n)的線性演算法找出第K個數。事實上，也有線性演算法——STL中可以用nth_element求得類似的第n大的數，其利用快速排序的思想，從數組S中隨機找出一個元素X，把數組分為兩部分Sa和Sb。Sa中的元素大於等於X，Sb中元素小於X。這時有兩種情況：1）Sa中元素的個數小於k，則Sb中的第 k-|Sa|個元素即為第k大數；2） Sa中元素的個數大於等於k，則返回Sa中的第k大數。時間復雜度近似為O(n)。搞學術的nuts們到了這一步一定會歡呼勝利！但是他們哪裡能想得到性能的需求分析也是來源自業務的！我們一說性能，基本上是個人都會問，請求量有多大？如果我們的FindKthMaxNum()的請求量是m次，那麼你的這個每次都要O(n)復雜度的演算法得到的效果就是O(n*m)，這一點，是書獃子式的學院派人永遠想不到的。因為應試教育讓我們不會從實際思考了。工程式的解法根據上面的需求分析，有軟體工程經驗的人的解法通常會這樣：1）把數組排序，從大到小。2）於是你要第k大的數，就直接訪問 array[k]。排序只需要一次，O(n*log(n))，然後，接下來的m次對FindKthMaxNum()的調用全是O(1)的，整體復雜度反而成了線性的。其實，上述的還不是工程式的最好的解法，因為，在業務中，那數組中的數據可能會是會變化的，所以，如果是用數組排序的話，有數據的改動會讓我重新排序，這個太耗性能了，如果實際情況中會有很多的插入或刪除操作，那麼可以考慮使用B+樹。工程式的解法有以下特點：1）很方便擴展，因為數據排好序了，你還可以方便地支持各種需求，如從第k1大到k2大的數據（那些學院派寫出來的代碼在拿到這個需求時又開始撓頭苦想了）2）規整的數據會簡化整體的演算法復雜度，從而整體性能會更好。（公欲善其事，必先利其器）3）代碼變得清晰，易懂，易維護！（學院派的和STL一樣的近似O(n)復雜度的演算法沒人敢動）爭論你可能會和我有以下爭論，如果程序員做這個演算法題用排序的方式，他一定不會像你想那麼多。是的，你說得對。但是我想說，很多時候，我們直覺地思考，恰恰是正確的路。因為「排序」這個思路符合人類大腦處理問題的方式，而使用學院派的方式是反大腦直覺的。反大腦直覺的，通常意味著晦澀難懂，維護成本上升。就是一道面試題，我就是想測試一下你的演算法技能，這也扯太多了。沒問題，不過，我們要清楚我們是在招什麼人？是一個只會寫演算法的人，還是一個會做軟體的人？這個只有你自己最清楚。這個演算法題太容易誘導到學院派的思路了。是的這道「找出第K大的數」，其實可以變換為更為業務一點的題目——「我要和別的商戶競價，我想排在所有競爭對手報價的第K名，請寫一個程序，我輸入K，和一個商品名，系統告訴我應該訂多少價？（商家的所有商品的報價在一數組中）」——業務分析，整體性能，演算法，數據結構，增加需求讓應聘者重構，這一個問題就全考了。你是不是在說演算法不重要，不用學？千萬別這樣理解我，搞得好像如果面試不面，我就可以不學。演算法很重要，演算法題能鍛煉我們的思維，而且也有很多實際用處。我這篇文章不是讓大家不要去學演算法，這是完全錯誤的，我是讓大家帶著業務問題去使用演算法。問你業務問題，一樣會問到演算法題上來。小結看過這上面的分析，我相信你明白我為什麼反對純演算法面試題了。原因就是純演算法的面試題根本不能反應一個程序的綜合素質！那麼，在面試中，我們應該要考量程序員的那些綜合素質呢？我以為有下面這些東西：會不會做需求分析？怎麼理解問題的？解決問題的思路是什麼？想法如何？會不會對基礎的演算法和數據結構靈活運用？另外，我們知道，對於軟體開發來說，在工程上，難是的下面是這些挑戰：軟體的維護成本遠遠大於軟體的開發成本。軟體的質量變得越來越重要，所以，測試工作也變得越來越重要。軟體的需求總是在變的，軟體的需求總是一點一點往上加的。程序中大量的代碼都是在處理一些錯誤的或是不正常的流程。所以，對於編程能力上，我們應該主要考量程序員的如下能力：設計是否滿足對需求的理解，並可以應對可能出現的需求變化。
5. JAVA演算法面試題：哪位高人會做
就把演算法給你寫一下：
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
for(int k = 1;k<=n;k++)
{
if(i==j || i==k || j==k)
continue;
else
System.out.println(i*100+j*10+k);
}
6. 演算法面試題 無序數組判斷是否有重復數 面試題 時間on 空間o1
//100萬不是很大
import java.util.*;
public class Test{
public static void main(String[] args){
int[] a = new int[1000000];
for(int i = 0; i<1000000;i++){
a[i] = i+1; //從1--1000000沒有重復的
}
a[355] = 100;//將第356個數改成100，這樣就只有兩個重復的數100
List list = new ArrayList();
for(int i = 0 ; i < 1000000;i++){
Integer temp = new Integer(a[i]);
if(!list.contains(temp)){
list.add(temp);
}else{
int j = list.indexOf(temp) ;//第一次出現
System.out.println("第"+(j+1)+"個數和第"+(i+1)+"個數重復為："+temp);
break; //找到即退出
}
}
}
}
7. java 演算法簡單面試題：要源碼！
package tv.bilibili;
import java.util.Scanner;
import java.util.regex.MatchResult;
public class test3 {
public static void main(String[] args) {
double price, money;
Scanner input = new Scanner(System.in);
System.out.println("請輸入物品價格：");
price = input.nextDouble();// 接受輸入數字
System.out.println("請輸入支付金額：");
money = input.nextDouble();// 接受輸入數字
if (price <= money) {
money = money - price;
int , wushi, ershi, shi, wu, yi, wujiao, yijiao;
= (int) (money / 100);
money = money - * 100;
wushi = (int) (money / 50);
money = money - wushi * 50;
ershi = (int) (money / 20);
money = money - ershi * 20;
shi = (int) (money / 10);
money = money - shi * 10;
wu = (int) (money / 5);
money = money - wu * 5;
yi = (int) (money / 1);
money = money - yi * 1;
wujiao = (int) (money / 0.5);
money = money - wujiao * 0.5;
yijiao = (int) (money / 0.1);
money = money - yijiao * 0.1;
System.out.println("主要支付給顧客100元：" + + "張;" + "50元：" + wushi
+ "張;" + "20元：" + ershi + "張;" + "10元：" + shi + "張;"
+ "5元：" + wu + "張;" + "1元：" + yi + "張;" + "5角："
+ wujiao + "張;" + "1角：" + yijiao + "張;");
} else {
System.out.println("您所支付的金額不足！");
}
}
}
算是寫完了，其實很簡單自己不動手只會害了自己，既然選擇這個，以後問問題不要直接求代碼，而是求方法，不然你永遠從事不了這一行
8. 大公司筆試面試有哪些經典演算法題目
1、二維數組中的查找
具體例題：如果一個數字序列逆置之後跟原序列是一樣的就稱這樣的數字序列為迴文序列。例如：{1, 2, 1}, {15, 78, 78, 15} , {112} 是迴文序列, {1, 2, 2}, {15, 78, 87, 51} ,{112, 2, 11} 不是迴文序列。現在給出一個數字序列，允許使用一種轉換操作：選擇任意兩個相鄰的數，然後從序列移除這兩個數，並用這兩個數字的和插入到這兩個數之前的位置(只插入一個和)。現在對於所給序列要求出最少需要多少次操作可以將其變成迴文序列？
9. 一道面試題，找出1-100中沒有插入的兩個數
恩 將下我的思路吧： （演算法自己實現，不會再聯系我）：
假設這連個數是a和b：
1. 對數組中的98個元素，進行求和為c， a+b = 5050-c
2. 1到100求平方在求和，數組中98個元素求平方在求和，求差 a2+b2=...
3. 這就類似一個一元二次方程，在解方程就可以了
10. JAVA面試題求大神幫忙，給滿分100分
1: D | javac 命令編譯指定類和該類依賴的類。編譯後的文件為二進制文件class
2：C
3：B
4：C | IOException，runtimeException 編譯時不要求強行處理，只在運行期發生。IOException編譯時強行要求處理，繼承自Exception
5：B | Set無序隊列，用get（index）游標無法獲取
6：C
7：A | 不使用關鍵字相當於default
8：D | 二進制演算法 11為 111 | 10 = 111(只要有一個是1就是1） 也就是11
9: C | ''表示位元組char。"/u0020" 是Unico的空格編碼
10：B
三
1、publicstaticObject[]arraySubtract(Object[]array1,Object[]array2){
ArrayList<Object>list=newArrayList<Object>();
//選出屬於數組1但不屬於數組2的元素
for(inti=0;i<array1.length;++i){
booleanbContained=false;
for(intj=0;j<array2.length;++j){
if(array1[i].equals(array2[j])){
bContained=true;
break;
}
}
if(!bContained){
list.add(array1[i]);
}
}
Objectres[]=newObject[list.size()];
for(inti=0;i<list.size();++i)
res[i]=list.get(i);
returnres;
}
2、
intcount(intn)
{
intresult=0;
for(inti=1;i<n;i++)
{
result+=i;
}
returnresult;
}
3、select*fromAwherenamein((name)>1)