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

雅虎

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

　　編程實現：找出兩個字符串中最大公共子字符串,如"abccade","dgcadde"的最大子串為"cad"

　　有雙向循環鏈表結點定義為：

　　1

　　struct node

　　2

　　{

　　3

　　int data;

　　4

　　struct node front,next;

　　5

　　}; 有兩個雙向循環鏈表A，B，知道其頭指針為：pHeadA,pHeadB，請寫一函數將兩鏈表中data值相同的結點刪除。

網易

　　兩個圓相交，交點是A1，A2。現在過A1點做一直線與兩個圓分別相交另外一點B1，B2。B1B2可以繞著A1點旋轉。問在什么情況下，B1B2最長

　　Smith夫婦召開宴會，并邀請其他4對夫婦參加宴會。在宴會上，他們彼此握手，并且滿足沒有一個人同自己握手，沒有兩個人握手一次以上，并且夫妻之間不握手。然后Mr. Smith問其它客人握手的次數，每個人的答案是不一樣的。求Mrs Smith握手的次數

　　有6種不同顏色的球，分別記為1,2,3,4,5,6，每種球有無數個。現在取5個球，求在一下 的條件下：

　　5種不同顏色，

　　4種不同顏色的球，

　　3種不同顏色的球，

　　2種不同顏色的球，

　　它們的概率。

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

　　從尾到頭輸出鏈表，題目：輸入一個鏈表的頭結點，從尾到頭反過來輸出每個結點的值。鏈表結點定義如下：

　　1

　　struct ListNode

　　2

　　{

　　3

　　int m_nKey;

　　4

　　ListNode m_pNext;

　　5

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

其它

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

　　找出數組中唯一的重復元素，1-1000放在含有1001個元素的數組中，只有唯一的一個元素值重復，其它均只出現一次.每個數組元素只能訪問一次，設計一個算法，將它找出來;不用輔助存儲空間，能否設計一個算法實現?

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

　　題目：輸入四個點的坐標，求證四個點是不是一個矩形，關鍵點：

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

　　矩形邊與坐標系平行的情況下，斜率無窮大不能用積判斷。

　　輸入四點可能不按順序，需要對四點排序。

　　矩陣式螺旋輸出

　　求兩個或N個數的最大公約數和最小公倍數。

　　最長遞增子序列。題目描述：設L=是n個不同的實數的序列，L的遞增子序列是這樣一個子序列Lin=，其中k1

　　字符串原地壓縮，題目描述："eeeeeaaaff" 壓縮為 "e5a3f2"，請編程實現。

　　字符串匹配實現，請以倆種方法，回溯與不回溯算法實現。

　　一個含n個元素的整數數組至少存在一個重復數，請編程實現，在O(n)時間內找出其中任意一個重復數。

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