![中國人才網(wǎng)](http://static.cnrencai.com/img/cn_logo2.jpg"){kind=logo}
給你10分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對應(yīng)的十個(gè)數(shù)
要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。
上排的十個(gè)數(shù)如下：
【0，1，2，3，4，5，6，7，8，9】
舉一個(gè)例子，
數(shù)值:0,1,2,3,4,5,6,7,8,9
分配:6,2,1,0,0,0,1,0,0,0
0在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次，
2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次....
以此類推..
算法面試：精選微軟等公司經(jīng)典的算法面試100題 第1-20題
如下：
--------------- --------------
1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表
題目：
輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。
要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。
10
/ /
6 14
/ / / /
4 8 12 16
轉(zhuǎn)換成雙向鏈表
4=6=8=10=12=14=16。
首先我們定義的二元查找樹 節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
2.設(shè)計(jì)包含min函數(shù)的棧。
定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個(gè)min函數(shù)，能夠得到棧的最小元素。
要求函數(shù)min、push以及pop的時(shí)間復(fù)雜度都是O(1)。
3.求子數(shù)組的最大和
題目：
輸入一個(gè)整形數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。
數(shù)組中連續(xù)的一個(gè)或多個(gè)整數(shù)組成一個(gè)子數(shù)組，每個(gè)子數(shù)組都有一個(gè)和。
求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)。
例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，
因此輸出為該子數(shù)組的和18。
4.在二元樹中找出和為某一值的所有路徑
題目：輸入一個(gè)整數(shù)和一棵二元樹。
從樹的根結(jié)點(diǎn)開始往下訪問一直到葉結(jié)點(diǎn)所經(jīng)過的所有結(jié)點(diǎn)形成一條路徑。
打印出和與輸入整數(shù)相等的所有路徑。
例如 輸入整數(shù)22和如下二元樹
10
/ /
5 12
/ /
4 7
則打印出兩條路徑：10, 12和10, 5, 7。
二元樹節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
5.查找最小的k個(gè)元素
題目：輸入n個(gè)整數(shù)，輸出其中最小的k個(gè)。
例如輸入1，2，3，4，5，6，7和8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字為1，2，3和4。
第6題
騰訊面試題：
給你10分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對應(yīng)的十個(gè)數(shù)
要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。
上排的十個(gè)數(shù)如下：
【0，1，2，3，4，5，6，7，8，9】
初看此題，貌似很難，10分鐘過去了，可能有的人，題目都還沒看懂。
舉一個(gè)例子，
數(shù)值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出現(xiàn)了6次，1在下排出現(xiàn)了2次，
2在下排出現(xiàn)了1次，3在下排出現(xiàn)了0次....
以此類推..
昨天，花了一個(gè)下午，用c++實(shí)現(xiàn)了此題。(*^__^*)
第7題
微軟亞院之編程判斷倆個(gè)鏈表是否相交
給出倆個(gè)單向鏈表的頭指針，比如h1，h2，判斷這倆個(gè)鏈表是否相交。
為了簡化問題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。
問題擴(kuò)展：
1.如果鏈表可能有環(huán)列?
2.如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列?
第8題
此貼選一些 比較怪的題，，由于其中題目本身與算法關(guān)系不大，僅考考思維。特此并作一題。
1.有兩個(gè)房間，一間房里有三盞燈，另一間房有控制著三盞燈的三個(gè)開關(guān)，這兩個(gè)房間是 分割開的，從一間里不能看到另一間的情況。
現(xiàn)在要求受訓(xùn)者分別進(jìn)這兩房間一次，然后判斷出這三盞燈分別是由哪個(gè)開關(guān)控制的。
有什么辦法呢？
2.你讓一些人為你工作了七天，你要用一根金條作為報(bào)酬。金條被分成七小塊，每天給出一塊。如果你只能將金條切割兩次，你怎樣分給這些工人?
3.★鏈接表和數(shù)組之間的區(qū)別是什么?
本文已影響
6827人 上一篇：百度2013招聘筆試及整合答案 下一篇：常見的邏輯筆試題目