知名公司經典算法筆試題和面試題答案

微軟

　　有一個整數數組，請求出兩兩之差絕對值最小的值，記住，只要得出最小值即可，不需要求出是哪兩個數。

　　寫一個函數，檢查字符是否是整數，如果是，返回其整數值。(或者：怎樣只用4行代碼編寫出一個從字符串到長整形的函數?)

　　給出一個函數來輸出一個字符串的所有排列。

　　請編寫實現malloc()內存分配函數功能一樣的代碼。給出一個函數來復制兩個字符串A和B。字符串A的后幾個字節和字符串B的前幾個字節重疊。

　　怎樣編寫一個程序，把一個有序整數數組放到二叉樹中?

　　怎樣從頂部開始逐層打印二叉樹結點數據?請編程。

　　怎樣把一個鏈表掉個順序(也就是反序，注意鏈表的邊界條件并考慮空鏈表)?

　　請編寫能直接實現int atoi(const char pstr)函數功能的代碼。

　　編程實現兩個正整數的除法，編程實現兩個正整數的除法，當然不能用除法操作符。

　　1

　　// return x/y.

　　2

　　int span(const int x, const int y)

　　3

　　{

　　4

　　....

　　5

　　}

　　在排序數組中，找出給定數字的出現次數，比如 [1, 2, 2, 2, 3] 中2的出現次數是3次。

　　平面上N個點，每兩個點都確定一條直線，求出斜率最大的那條直線所通過的兩個點(斜率不存在的情況不考慮)。時間效率越高越好。

　　一個整數數列，元素取值可能是0~65535中的任意一個數，相同數值不會重復出現。0是例外，可以反復出現。請設計一個算法，當你從該數列中隨意選取5個數值，判斷這5個數值是否連續相鄰。注意：

　　5個數值允許是亂序的。比如：8 7 5 0 6

　　0可以通配任意數值。比如：8 7 5 0 6 中的0可以通配成9或者4

　　0可以多次出現。

　　復雜度如果是O(n2)則不得分。

　　設計一個算法，找出二叉樹上任意兩個結點的最近共同父結點。復雜度如果是O(n2)則不得分。

　　一棵排序二叉樹，令 f=(最大值+最小值)/2，設計一個算法，找出距離f值最近、大于f值的結點。復雜度如果是O(n2)則不得分。

　　一個整數數列，元素取值可能是1~N(N是一個較大的正整數)中的任意一個數，相同數值不會重復出現。設計一個算法，找出數列中符合條件的數對的個數，滿足數對中兩數的和等于N+1。復雜度最好是O(n)，如果是O(n2)則不得分。

　　Google

　　正整數序列Q中的每個元素都至少能被正整數a和b中的一個整除，現給定a和b，需要計算出Q中的前幾項，例如，當a=3，b=5，N=6時，序列為3，5，6，9，10，12 (1)、設計一個函數void generate(int a,int b,int N ,int Q)計算Q的前幾項(2)、設計測試數據來驗證函數程序在各種輸入下的正確性。

　　有一個由大小寫組成的字符串，現在需要對他進行修改，將其中的所有小寫字母排在答謝字母的前面(大寫或小寫字母之間不要求保持原來次序)，如有可能盡量選擇時間和空間效率高的算法 c語言函數原型void proc(char str) 也可以采用你自己熟悉的語言。

　　如何隨機選取1000個關鍵字，給定一個數據流，其中包含無窮盡的搜索關鍵字(比如，人們在谷歌搜索時不斷輸入的關鍵字)。如何才能從這個無窮盡的流中隨機的選取1000個關鍵字?

　　判斷一個自然數是否是某個數的平方。說明：當然不能使用開方運算。

　　給定能隨機生成整數1到5的函數，寫出能隨機生成整數1到7的函數。

　　1024! 末尾有多少個0?

　　有5個海盜，按照等級從5到1排列，最大的海盜有權提議他們如何分享100枚金幣。但其他人要對此表決，如果多數反對，那他就會被殺死。他應該提出怎樣的方案，既讓自己拿到盡可能多的金幣又不會被殺死?(提示：有一個海盜能拿到98%的金幣)

　　23、Google2015華南地區筆試題。給定一個集合A=[0,1,3,8](該集合中的元素都是在0，9之間的數字，但未必全部包含)，指定任意一個正整數K，請用A中的元素組成一個大于K的最小正整數。比如，A=[1,0] K=21 那么輸出結構應該為100。

百度

　　用C語言實現一個revert函數，它的功能是將輸入的字符串在原串上倒序后返回。

　　用C語言實現函數void memmove(void dest, const void src, size_t n)。memmove 函數的功能是拷貝src所指的內存內容前n個字節到dest所指的地址上。分析：由于可以把任何類型的指針賦給void類型的指針，這個函數主要是實現各種數據類型的拷貝。

　　有一根27厘米的細木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這五個位置上各有一只螞蟻。木桿很細，不能同時通過一只螞蟻。開始時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調頭，但不會后退。當任意兩只螞蟻碰頭時，兩只螞蟻會同時調頭朝反方向走。假設螞蟻們每秒鐘可以走一厘米的距離。編寫程序，求所有螞蟻都離開木桿的最小時間和最大時間。

騰訊

　　請定義一個宏，比較兩個數a、b的大小，不能使用大于、小于、if語句

　　兩個數相乘，小數點后位數沒有限制，請寫一個高精度算法

　　有A、B、C、D四個人，要在夜里過一座橋。他們通過這座橋分別需要耗時1、2、5、10分鐘，只有一支手電，并且同時最多只能兩個人一起過橋。請問，如何安排，能夠在17分鐘內這四個人都過橋?

　　有12個小球,外形相同,其中一個小球的質量與其他11個不同，給一個天平,問如何用3次把這個小球找出來，并且求出這個小球是比其他的輕還是重

　　在一個文件中有 10G 個整數，亂序排列，要求找出中位數。內存限制為 2G。只寫出思路即可。

　　一個文件中有40億個整數，每個整數為四個字節，內存為1GB，寫出一個算法：求出這個文件里的整數里不包含的一個整數。

　　騰訊服務器每秒有2w個QQ號同時上線，找出5min內重新登入的qq號并打印出來。