# 百度一面 1、給定一個字符串比如“abcdef”，要求寫個函數編程“defabc”，位數是可變的。這個比較簡單，我用的是strcpy和memcpy，然后他問有什么優化的辦法，我就不知道了。 2、socket過程就是socket的server和client整個流程寫下來，這個還是沒啥問題的。 3、數據結構二叉樹的遍歷，給了個二叉樹，前序、中序、后序寫出來，這個沒什么難度。 [http://blog.csdn.net/hackbuteer1/article/details/6583988](http://blog.csdn.net/hackbuteer1/article/details/6583988) 4、樹的層次遍歷，這個開始真忘了，想了半天才想起來用隊列。然后他又讓我詳細寫出入隊出隊的過程，總之還是搞定了。 5、兩圓相切轉圏問題——一個小圓半徑是1厘米，一個大圓半徑是5厘米，小圓沿著大圓轉圈，請問要轉幾圈可以轉完大圈？這個問題在行測題做過，就是公轉自轉的問題，不管大小圓半徑是多少，外切轉圏要轉R/r+1圏，外切轉圏轉R/r-1圈。 # 百度二面 1、二叉樹的前序遍歷的遞歸和非遞歸的可執行程序 [http://blog.csdn.net/hackbuteer1/article/details/6583988](http://blog.csdn.net/hackbuteer1/article/details/6583988) 2、寫出快速排序的實現代碼，一個是字符串拼接函數的實現strcat()，還有大數相乘，都是基本題。 3、歸并排序的實現。 [http://blog.csdn.net/hackbuteer1/article/details/6568913](http://blog.csdn.net/hackbuteer1/article/details/6568913) 4、文件按a~z編號，aa~az,ba~bz...za...zz...aaa...aaz,aba~abz...這樣的方法進行編號。給定任意一個編號，輸出文件是第幾個文件。并寫出測試方法。簡單，把編號看成26進制，這題就是一個十進制和26進制的進制轉換問題了。 5、編程：兩個鏈表，按升序排序，合并后仍按升序，不準用遞歸，并求復雜度 # 百度電面： 1、談談你對數據庫中索引的理解 2、現在普通關系數據庫用得數據結構是什么類型的數據結構 3、索引的優點和缺點 4、session、cookie和cache的區別是什么 5、如果有幾千個session，怎么提高效率？ 6、session是存儲在什么地方，以什么形式存儲的？ # 新浪技術部筆試題 # 一、數據結構和算法 1、簡述什么是hashtable，如何解決hash沖突 2、什么叫二叉樹，滿二叉樹，完全二叉樹 4、數組和鏈表有什么區別，分別用在什么場合 二、操作系統 1、什么叫虛擬內存 2、塊設備和字符設備有什么區別 3、進程和線程的區別 4、簡述TCP網關連接交互細節 三、Lunix 1、寫出10個常用的linux命令和參數 2、如何查看磁盤剩余空間???????????????? df -h1 3、如何查看端口是否被占用???????? 4、如何查看某個進程所占用的內存??????? 用ps命令查看進程的內存 四、程序題（具體題目記不太清了） 1、用兩個線程實現1-100的輸出 2、把一個文件夾中所有01結尾的文件前十行內容輸出 # 思科一面： # 1、C++和Java最大的區別是什么？ 2、static、extern、global的作用？（再一次出現了static，上鏡率真高挖~）??? [http://blog.csdn.net/hackbuteer1/article/details/7487694](http://blog.csdn.net/hackbuteer1/article/details/7487694) 3、inline內聯函數是否占用運行時間？ 思科二面： 1、進程和線程有什么區別？ 2、進程的調度算法，把記得的全說出來 3、頁面的替換算法都有哪些？ 4、用戶態和內核態的區別？ 5、平面上N個點 沒兩個點都確定一條直線 求出斜率最大 那條直線所通過 兩個點 斜率不存在 情況不考慮 時間效率越高越好 解法：先把N個點按x排序。 斜率k最大值為max(斜率(point[i],point[i+1])) 0<=i<n-2。 復雜度Nlog(N)。 以3個點為例，按照x排序后為ABC，假如3點共線，則斜率一樣，假如不共線，則可以證明在AB或BC中，一定有一個點的斜率大于AC，一個點的斜率小于AC。 # 騰訊一面 # 1、關系型數據庫的特點 2、父類的析構函數為什么要定義為虛函數 3、把一個字符串的大寫字母放到字符串的后面，各個字符的相對位置不變，不能申請額外的空間。? （比較難） 4、快排算法實現程序 [http://blog.csdn.net/hackbuteer1/article/details/6568913](http://blog.csdn.net/hackbuteer1/article/details/6568913) 5、KMP算法實現程序 [http://blog.csdn.net/hackbuteer1/article/details/7319115](http://blog.csdn.net/hackbuteer1/article/details/7319115) 6、override和overload的區別 7、編程并實現一個八皇后的解法 8、鏈表的歸并排序 騰訊二面： 1、在數據庫中如何創建一個表 2、創建后如何添加一個記錄、刪除一個記錄 3、編寫C++中的兩個類 一個只能在棧中分配空間 一個只能在堆中分配。?? （比較難） 4、請編寫實現malloc()內存分配函數功能一樣的代碼。 5、請編寫能直接實現strstr()函數功能的代碼。 6、已知： 每個飛機只有一個油箱， 飛機之間可以相互加油（注意是相互，沒有加油機） 一箱油可供一架飛機繞地球飛半圈， 問題：為使至少一架飛機繞地球一圈回到起飛時的飛機場，至少需要出動幾架飛機？（所有飛機從同一機場起飛，而且必須安全返回機場，不允許中途降落，中間沒有飛機場） 7、static的作用——再一次出現~ [http://blog.csdn.net/hackbuteer1/article/details/7487694](http://blog.csdn.net/hackbuteer1/article/details/7487694) 8、寫string類的構造，析構，拷貝函數——這題大約出現過4次左右，包括編程和程序填空，程序員面試寶典上有這題，也算是個經典筆試題，出現幾率極大~ # 微軟面試題 # 微軟面試題匯總? [http://www.cnblogs.com/qlee/archive/2011/09/16/2178873.html](http://www.cnblogs.com/qlee/archive/2011/09/16/2178873.html) 1、給你一個凸多邊形，你怎么用一條線，把它分成面積相等的兩部分 2、有一條數軸，上有一整數點s，點s兩側分別放了兩個機器人，不知道兩個機器人分別距離s的距離，兩機器人不能相互通信。 現在，給你以下指令： R（往右一格） L（往左一格） IF(S)是否在S點 GOTO A，跳到A代碼段。 設計一套指令給兩個機器人，讓兩個器機可以最終在某一點相遇。 3、怎么判斷兩棵二叉樹是否是同構的 4、按層次打印一個二叉樹 5、給你一個數n（最大為10000），怎么求其階乘 6、判斷兩個單鏈表是否有交叉 # 58同城面試題 # 一面： 1、set(底層基于紅黑樹實現)的操作； 2、手寫快排遞歸與非遞歸實現； [http://blog.csdn.net/hackbuteer1/article/details/6568913](http://blog.csdn.net/hackbuteer1/article/details/6568913) 3、KMP原理解釋 [http://blog.csdn.net/hackbuteer1/article/details/7319115](http://blog.csdn.net/hackbuteer1/article/details/7319115) 4、聚類分類協同過濾算法； 二面： 1、提示詞實現Trie樹+hash 2、最快速度求兩個數組之交集； 3、文章最短摘要生成； # 網易有道 1、試著用最小的比較次數去尋找數組中的最大值和最小值。 解法一： 掃描一次數組找出最大值；再掃描一次數組找出最小值。 比較次數2N-2 解法二： 將數組中相鄰的兩個數分在一組， 每次比較兩個相鄰的數，將較大值交換至這兩個數的左邊，較小值放于右邊。 對大者組掃描一次找出最大值，對小者組掃描一次找出最小值。 比較1.5N-2次，但需要改變數組結構 解法三： 每次比較相鄰兩個數，較大者與MAX比較，較小者與MIN比較，找出最大值和最小值。 # 迅雷面試題 # 1、寫一個字符串插入的函數 2、問了我關于虛函數底層的實現 [http://blog.csdn.net/hackbuteer1/article/details/7883531](http://blog.csdn.net/hackbuteer1/article/details/7883531) 3、寫了快排、堆排 [http://blog.csdn.net/hackbuteer1/article/details/6568913](http://blog.csdn.net/hackbuteer1/article/details/6568913) 4、問我TCP、UDP的一些知識 [http://blog.csdn.net/hackbuteer1/article/details/6845406](http://blog.csdn.net/hackbuteer1/article/details/6845406) 5、還問了我一些Linux的知識 6、讓我實現紅黑樹的刪除操作 [http://blog.csdn.net/hackbuteer1/article/details/7760584](http://blog.csdn.net/hackbuteer1/article/details/7760584) # 網新恒天一面 # 1、考察指針int? (*p)[10]和int *p[10]的區別，用法 2、sizeof(),strlen()的區別和用法 3、堆、棧的區別和用法 4、多繼承的優點與缺點 5、（1）IO2:30ms, CPU 20ms, IO1 20ms, CPU 30ms (2) IO1 20ms, CPU 20ms, IO2 10ms (3) CPU 30ms, IO1 20ms 求三種情況的CPU和IO占用率 網新恒天二面： 1、內聯函數與宏的區別 2、與信號量相關知識的考察，具體題目記不清了，反正知道基本概念就會做 3、填空，考察頁式虛擬內存的缺頁情況，也是知道這部分知識點就會做的題 4、類的繼承相關知識點的考察，是一道程序輸出分析題 5、棧的類的成員函數的實現，程序填空題。 6、模板函數與函數模板的區別 7、函數模板與類模板的區別 # 百度筆試題 # 1、數組，鏈表的優缺點：這個問題比較簡單不過我自己經常會忽略的一點是數組是固定空間，鏈表是可變空間 2、a[N][20]輸入N個長度不超過20的字符串，比較這些字符串中是否有完全相同的字母，且相同字母數是否相等。如何改進該算法，降低復雜度。 3、猜撲克牌——給定一些牌，把花色告訴，把點數告訴乙 ???????????? 甲：我不知道 乙：我知道你不知道 ???????????? 甲：現在我知道了 乙：我也知道了 求是哪張牌。 給定的牌我不記得，反正這個題很簡單，行測中的簡單題，網上比比皆是。 4、A:M*M矩陣，求字符串S是否存在A的連續對角線上。（這題應該有涉及到一個之字二維矩陣方面的知識） A若為內存裝不下的大矩陣該如何處理？ 5、系統接收數據包32字節，第1字節為優先級，其余為數據。設計一個調度算法 （1）優先級高的先處理 （2）同等條件下，請求次數多的先處理 （3）優先級高的一定比優先級低的先處理 寫出所用的數據結構的定義，計算空間容量。 # 阿里巴巴B2B一面 # 1、各種排序算法的比較次數 2、static、auto未初始化的初始值 [http://blog.csdn.net/hackbuteer1/article/details/7487694](http://blog.csdn.net/hackbuteer1/article/details/7487694) 3、x*=y+8，給出x,y的值，求該表達式計算后二者的值 4、enum類型的default賦值規則 5、定義函數F(int x){return (x*x);} 求F（3+5） 6、fgets(s,n,f)函數的功能 7、定義*s="ab\0cdef",輸出該字符可以看到什么結果 8、還是static相關知識——在此說明一下static這個關鍵字相當重要，在筆試中出現率為100%，在面試中出現率為50%。 9、數據庫中索引，簇索引，非簇，唯一，復合，覆蓋索引的區別 10、SQL語句和范式是對數據庫有要求的公司筆試必考點之一 阿里巴巴B2B二面 1、通配符的含義 2、死鎖的基本知識——死鎖是各大筆試面試中出現率50%的知識點 3、信號量P、V原語的相關知識點 4、有向圖的鄰接表表示 **5、STL中迭代器的工作原理，迭代器與普通指針有什么區別？** 迭代器和指針相同的地方： 1、指針和iterator都支持與整數進行+，-運算，而且其含義都是從當前位置向前或者向后移動n個位置 2、指針和iterator都支持減法運算，指針-指針得到的是兩個指針之間的距離，迭代器-迭代器得到的是兩個迭代器之間的距離 3、通過指針或者iterator都能夠修改其指向的元素 通過上面這幾點看，兩者真的很像，但是兩者也有著下面的幾個不同地方 1、out操作符可以直接輸出指針的值，但是對迭代器進行在操作的時候會報錯。通過看報錯信息和頭文件知道，迭代器返回的是對象引用而不是對象的值，所以cout只能輸出迭代器使用*取值后的值而不能直接輸出其自身。 2、指針能指向函數而迭代器不行，迭代器只能指向容器 這就說明了迭代器和指針其實是完全不一樣的概念來的。指針是一種特殊的變量,它專門用來存放另一變量的地址，而迭代器只是參考了指針的特性進行設計的一種STL接口。 筆者曾在網上看到這樣一種說法：迭代器是廣義指針，而指針滿足所有迭代器要求。迭代器是STL算法的接口，而指針是迭代器，因此STL算法可以使用指針來對基于指針的非STL容器進行操作。 筆者覺得上面說法也有幾分道理，但是到底正不正確就留給看官自己判斷了。但是有一點希望大家注意的是：千萬不要把指針和迭代器搞混了。也許某些編譯器使用指針來實現迭代器以至于有些人會誤以為指針和迭代器是一個概念來的。 6、什么是友元？ 7、delete、new的用法 8、typename的用法 9、編程判斷一個數是否為2的冪 10、你怎樣重新改進和設計一個ATM銀行自動取款機？ 12、10000Mbps萬兆交換機怎么實現？ 13、操作符重載的相關知識點，大題，具體記不清了 # 人民搜索的筆試題 # 1、打印漢諾塔移動步驟，并且計算復雜度 2、計算兩個字符串的是否相似（字符的種類，和出現次數相同） 3、定義二叉樹，節點值為int，計算二叉樹中的值在[a,b]區間的節點的個數 4、動態規劃題：一條路有k可坑，每次能跳平方數步長（1 4 9? 16。。），不能跳到坑里，從a跳到b最少幾步？ 5、給一個整數數組，求數組中重復出現次數大于數組總個數一半的數。 1、對以孩子兄弟鏈接的樹進行遍歷，不能用遞歸，也不能借助任何輔助空間 2、假設數組B是升序Int數組A循環移若干得到的位，實現對數組B進行查找的高效算法 3、只有整數和+-*/四種運算組成的算術表達書，實現其求值 4、還有一個是考貪心算法的，你讓他們看算法導論那本書，關于fractional knapsack problem的那一段，就是0-1背包的一種變形； 5、鏈表相鄰元素翻轉，如a->b->c->d->e->f-g，翻轉后變為：b->a->d->c->f->e->g 6、求正整數n所有可能的和式的組合（如；4=1+1+1+1、1+1+2、1+3、2+1+1、2+2） 1、實現一個atoi函數==>'注意正負號的判定' 2、翻轉一個句子，其中單詞是正序的==>兩次旋轉 3、二叉樹兩個結點中的最小公共子結點==>求長度，長度之差，遠的先走，再一起走 4、三角陣中從第一行到最后一行(給出搜索方向的限制)找一個連續的最大和==>廣度優先搜索√ 5、實現一個STL中的vector中的盡量多的方法。 6、字符串移動（字符串為*號和26個字母的任意組合，把*號都移動到最左側，把字母移到最右側并保持相對順序不變），要求時間和空間復雜度最小。 ~~~ /** **author :hackbuteer **date :2012-10-03 **/ void Arrange(char *str , int n) { int i , k = n-1; for(i = n - 1 ; i >= 0 ; --i) { if(str[i] != '*') { if(str[k] == '*') { str[k] = str[i]; str[i] = '*'; } --k; } } } ~~~ 7、說說outer join、inner join、left join、right join的區別是什么？ 內連接：進行連接的兩個表對應的相匹配的字段完全相同的連接。join 外連接又分為左外連接和右外連接。 左連接即LEFT OUTER JOIN： 兩個表進行左連接時會返回左邊表中的所有的行和右邊表中與之相匹配的列值沒有相匹配的用空值代替。 右連接即RIGHT OUTER JOIN： 兩個表進行右連接時會返回右邊表中的所有的行和左邊表中與之相匹配的列值沒有相匹配的用空值代替。 我們建立兩張表，students、class并插入測試數據 students --------------------------- id???? name???? classId 1????? name1??? 1 2????? name2??? null 3????? name3??? 2 --------------------------- class ----------------------- id?????? name 1??????? class1 2??????? class2 3??????? class3 ----------------------- 實驗結果如下： mysql> select s.name,c.name from students s join class c where s.classId=c.id ; （注：inner join和join一樣） +-------+-------+ | name? | class | +-------+-------+ | name1 | 1???? | | name3 | 2???? | +-------+-------+ 2 rows in set mysql> select s.name,c.name from students s left join class c on s.classId=c.id ; （left join 和 left outer join 一樣） +-------+-------+ | name? | class | +-------+-------+ | name1 | 1???? | | name2 | NULL? | | name3 | 2???? | +-------+-------+ 3 rows in set mysql> select s.name,c.name from students s right join class c on s.classId=c.id ; （right join 和 right outer join 一樣） +-------+-------+ | name? | class | +-------+-------+ | name1 | 1???? | | name3 | 2???? | | NULL? | 3???? | +-------+-------+ 3 rows in set