1. 有乙個整數陣列，請求出兩兩之差絕對值最小的值。記住，只要得出最小值即可，不需要求出是哪兩個數。（microsoft）
方法1：兩兩作差求絕對值，並取最小，o( n2 )。
方法2：排序，相鄰兩點作差求絕對值，並取最小，o( nlgn ).
方法3：有沒有o( n )的解法？網上有如下解法：
設陣列a = , 求 s = min( |ai - aj| ), 其中1<= i, j <=n.
設b = , 且 bi = ai – ai+1
即：b1 = a1 – a2, b2 = a2 – a3, b3 = a3 – a4, …
於是有如下規律：
例如：a3 – a5 = ( a3 – a4 ) + ( a4 – a5 ) =b3 + b4
a1 – a6 = b1 + b2 + … + b5
即：ai – aj = bi + … + bj-1
則陣列a中任意兩個數的差，都可以用陣列b中乙個欄位的和表示。
則原問題可以轉換為：
在陣列b中，求連續的某一段，使其和的絕對值最小。（只求最小值，不需要知道具體是哪些數）
例如 b = ；
則絕對值最小值為0，具體是 或
網上的解法，一般到這裡就沒下文了。只是簡單的提了一下，類似於最大子串行的和。具體怎麼做，還要自己想想。
最大子串行和利用dp，可o( n )求解。這題咋做？糾結。
2. 寫乙個函式，檢查字元是否是整數，如果是，返回其整數值。（或者：怎樣只用4行**編寫出乙個從字串到長整形的函式？）
據說此題是，microsoft的大牛只有了4行**就給出了答案。
可惜，不知道是怎麼寫的。自己試著寫寫，當然可能會不至4行。單純追求行數，也沒什麼意義，如果你願意可以把所有的程式都寫成一行。
注意：1. 處理前導空格
2. 處理正負號
3. 處理進製（16進製制、8進製、10進製）
4. 非法字元（ 0---9, a---f, a---f）
5. 注意整數的範圍，不能溢位
view plaincopy to clipboardprint?
1. boolstrtoint(char*pc,long&value)
2. 15.
16. //處理數值
17. longtmp=0;
18. while(*pc!='\0')
19.25. value=tmp*sign;
26. returntrue;
}3. 給出乙個函式來輸出乙個字串的所有排列
方法1：
乙個簡單的dfs。從後往前不斷互動。n個字母求全排列，o( n! )。具體實現，看**吧。
方法2：
如果不會寫遞迴，也可以利用stl。stl裡有乙個next_permutation函式。利用這個函式可以返回大於原字串的下乙個字典序列。
當字串為最大字典序列時，函式返回false。這樣只要先對原字串排序，然後不斷呼叫next_permuation即可。
view plaincopy to clipboardprint?
1. inlinevoidexchange(char*px,char*py)
2. 7.
8. voidprintstrpermut(char*pstr,char*pbegin)
9. 24. }
25. }
26.27. voidprintstrpermut2(char*pstr)
28.}4．請編寫實現malloc()記憶體分配函式功能一樣的**
這題比較難，要是不懂點os的記憶體管理，根本就無從下手。
我們知道呼叫malloc()後，os就要想方設法為我們返回一塊空閒空間。這就涉及到os的記憶體管理。os的記憶體管理可以這樣考慮：
假設整塊記憶體有128k
初始狀態，128k都是空閒
第一次請求，申請了16k，空閒112k
第二次請求，申請了32k，空閒80k
第三次請求，申請了8k，空閒72k
第二次請求申請的32k被釋放，空閒108k
第四次請求，申請了24k，空閒84k
…從上面的例子可以看出，一整塊連續的空閒記憶體塊，經過一段時間的使用，會被無情的劃分為許多小塊。這些小塊大小不等，並且有的空閒、有的被占用。
當呼叫malloc時，os就沿記憶體掃瞄，找到一塊夠大的空閒塊，從中劃分出要使用的部分，將這部分標記為己分配，並返回這部分的首位址。如果，空閒的塊都是些小的碎片，那就悲具了（當然，os可以把將相鄰的空閒塊合併，再嘗試）。
現在，模擬一下malloc的過程：
為了便於管理，首先定義記憶體控制塊mcb。這個mcb記錄兩個資訊：塊是否空閒、塊的大小。
即，每個分配出去的塊，其實都帶有乙個mcb，只不過這個mcb位於塊的最前端，返回該使用者的指標剛好指向mcb之後，所以對使用者是不可見的。
現在，就可以處理free了。free只要把已分配的記憶體塊重新標記為空閒即可，這裡當然要用到該快的mcb了。
malloc簡單來說，就是維護幾個指標，根據分配請求修改指標位置。對於要分配的塊，將標記置位己分配，並返回這部分的首位址。
參考這裡講的很清楚，還附有**，我就不狗尾續貂了。
5. 字串a的後幾個位元組和字串b的前幾個位元組重疊。
這題似乎沒什麼玄機，就是個簡單的字串處理。使用strlen和memcpy可以完成，見**。
view plaincopy to clipboardprint?
1. boolstroverlap(char*stra,char*strb,intcnt,char*strc)
2. 6.怎樣編寫乙個程式，把乙個有序整數陣列放到二叉樹中？
由陣列建立排序二叉樹。因為陣列已排序，所以可以進行類似排序二叉樹上的查詢。感覺有點類似先序遍歷，每次先處理根節點，然後分別是左子樹、右子樹。具體做法是：
1.整個陣列對應乙個二叉樹，則中間元素對應二叉樹的根節點
2.中間元素左邊的部分對應左子樹、右邊的部分對應右子樹
3.對左右兩部分再繼續遞迴呼叫。
view plaincopy to clipboardprint?
1. structbitreenode
2. ;
9. };
10.11. voidarraytotree(int*pi,intleft,intright,bitreenode*&root)
微軟 谷歌 百度等公司經典面試100題
微軟十五道面試題 1 有乙個整數陣列，請求出兩兩之差絕對值最小的值,記住，只要得出最小值即可，不需要求出是哪兩個數。2 寫乙個函式，檢查字元是否是整數，如果是，返回其整數值。或者 怎樣只用4行 編寫出乙個從字串到長整形的函式？3 給出乙個函式來輸出乙個字串的所有排列。4 a 請編寫實現malloc ...
百度面試題
1 題目 兩個檔案都保留有千萬個以上的10位以內的正整數，像qq號碼差不多吧。那如何找出其中的相同的呢？解法 個人理解 基本思想是利用記憶體中的位對數字進行標記。就是對 0000000000 9999999999共100億個數字進行數字的匹配，呵呵，想一下也知道可以使用雜湊表的方法，這裡的方法就是類...
百度筆試面試題
好晶元，說明你所用的比較次數上限 其中 好晶元和其它晶元比較時，能正確給出另一塊晶元是好還是壞 壞晶元和其它晶元比較時，會隨機的給出好或是壞。4 40分 請設計乙個網頁儲存系統，能儲存千萬量級的網頁。要求 1.支援按照url為鍵值的隨機新增，刪除和修改網頁2.支援多個執行緒同時新增，修改和刪除 3....