知名公司經(jīng)典算法筆試題和面試題答案(二)

雅虎

　　編程實(shí)現(xiàn)：把十進(jìn)制數(shù)(long型)分別以二進(jìn)制和十六進(jìn)制形式輸出，不能使用printf系列

　　編程實(shí)現(xiàn)：找出兩個(gè)字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串為"cad"

　　有雙向循環(huán)鏈表結(jié)點(diǎn)定義為：

　　1

　　struct node

　　2

　　{

　　3

　　int data;

　　4

　　struct node front,next;

　　5

　　}; 有兩個(gè)雙向循環(huán)鏈表A，B，知道其頭指針為：pHeadA,pHeadB，請(qǐng)寫(xiě)一函數(shù)將兩鏈表中data值相同的結(jié)點(diǎn)刪除。

網(wǎng)易

　　兩個(gè)圓相交，交點(diǎn)是A1，A2。現(xiàn)在過(guò)A1點(diǎn)做一直線與兩個(gè)圓分別相交另外一點(diǎn)B1，B2。B1B2可以繞著A1點(diǎn)旋轉(zhuǎn)。問(wèn)在什么情況下，B1B2最長(zhǎng)

　　Smith夫婦召開(kāi)宴會(huì)，并邀請(qǐng)其他4對(duì)夫婦參加宴會(huì)。在宴會(huì)上，他們彼此握手，并且滿足沒(méi)有一個(gè)人同自己握手，沒(méi)有兩個(gè)人握手一次以上，并且夫妻之間不握手。然后Mr. Smith問(wèn)其它客人握手的次數(shù)，每個(gè)人的答案是不一樣的。求Mrs Smith握手的次數(shù)

　　有6種不同顏色的球，分別記為1,2,3,4,5,6，每種球有無(wú)數(shù)個(gè)。現(xiàn)在取5個(gè)球，求在一下 的條件下：

　　5種不同顏色，

　　4種不同顏色的球，

　　3種不同顏色的球，

　　2種不同顏色的球，

　　它們的概率。

　　有一次數(shù)學(xué)比賽，共有A，B和C三道題目。所有人都至少解答出一道題目，總共有25人。在沒(méi)有答出A的人中，答出B的人數(shù)是答出C的人數(shù)的兩倍;單單答出A的人，比其他答出A的人總數(shù)多1;在所有只有答出一道題目的人當(dāng)中，答出B和C的人數(shù)剛好是一半。求只答出B的人數(shù)。

　　從尾到頭輸出鏈表，題目：輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過(guò)來(lái)輸出每個(gè)結(jié)點(diǎn)的值。鏈表結(jié)點(diǎn)定義如下：

　　1

　　struct ListNode

　　2

　　{

　　3

　　int m_nKey;

　　4

　　ListNode m_pNext;

　　5

　　}; 分析：這是一道很有意思的面試題。該題以及它的變體經(jīng)常出現(xiàn)在各大公司的面試、筆試題中。

其它

　　金幣概率問(wèn)題，題目：10個(gè)房間里放著隨機(jī)數(shù)量的金幣。每個(gè)房間只能進(jìn)入一次，并只能在一個(gè)房間中拿金幣。一個(gè)人采取如下策略：前四個(gè)房間只看不拿。隨后的房間只要看到比前四個(gè)房間都多的金幣數(shù)，就拿。否則就拿最后一個(gè)房間的金幣。編程計(jì)算這種策略拿到最多金幣的概率。

　　找出數(shù)組中唯一的重復(fù)元素，1-1000放在含有1001個(gè)元素的數(shù)組中，只有唯一的一個(gè)元素值重復(fù)，其它均只出現(xiàn)一次.每個(gè)數(shù)組元素只能訪問(wèn)一次，設(shè)計(jì)一個(gè)算法，將它找出來(lái);不用輔助存儲(chǔ)空間，能否設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)?

　　一排N(最大1M)個(gè)正整數(shù)+1遞增，亂序排列，第一個(gè)不是最小的，把它換成-1，最小數(shù)為a且未知求第一個(gè)被-1替換掉的數(shù)原來(lái)的值，并分析算法復(fù)雜度。

　　題目：輸入四個(gè)點(diǎn)的坐標(biāo)，求證四個(gè)點(diǎn)是不是一個(gè)矩形，關(guān)鍵點(diǎn)：

　　相鄰兩邊斜率之積等于-1，

　　矩形邊與坐標(biāo)系行的情況下，斜率無(wú)窮大不能用積判斷。

　　輸入四點(diǎn)可能不按順序，需要對(duì)四點(diǎn)排序。

　　矩陣式螺旋輸出

　　求兩個(gè)或N個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)。

　　最長(zhǎng)遞增子序列。題目描述：設(shè)L=是n個(gè)不同的實(shí)數(shù)的序列，L的遞增子序列是這樣一個(gè)子序列Lin=，其中k1

　　字符串原地壓縮，題目描述："eeeeeaaaff" 壓縮為 "e5a3f2"，請(qǐng)編程實(shí)現(xiàn)。

　　字符串匹配實(shí)現(xiàn)，請(qǐng)以倆種方法，回溯與不回溯算法實(shí)現(xiàn)。

　　一個(gè)含n個(gè)元素的整數(shù)數(shù)組至少存在一個(gè)重復(fù)數(shù)，請(qǐng)編程實(shí)現(xiàn)，在O(n)時(shí)間內(nèi)找出其中任意一個(gè)重復(fù)數(shù)。

　　給定一個(gè)存放整數(shù)的數(shù)組，重新排列數(shù)組使得數(shù)組左邊為奇數(shù)，右邊為偶數(shù)。要求：空間復(fù)雜度O(1)，時(shí)間復(fù)雜度為O(n)。