|
騰訊面試題：tcp三次握手的過(guò)程，accept發(fā)生在三次握手哪個(gè)階段？ 答accept發(fā)生在三次握手之后。 第一次握手：客戶端發(fā)送syn包(syn=j)到服務(wù)器。 第二次握手：服務(wù)器收到syn包，必須確認(rèn)客戶的SYN（ack=j+1），同時(shí)自己也發(fā)送一個(gè)ASK包（ask=k）。 第三次握手：客戶端收到服務(wù)器的SYN＋ACK包，向服務(wù)器發(fā)送確認(rèn)包ACK(ack=k+1)。 三次握手完成后，客戶端和服務(wù)器就建立了tcp連接。這時(shí)可以調(diào)用accept函數(shù)獲得此連接。
const的含義及實(shí)現(xiàn)機(jī)制，比如：const int i,是怎么做到i只可讀的？ const用來(lái)說(shuō)明所定義的變量是只讀的。 這些在編譯期間完成，編譯器可能使用常數(shù)直接替換掉對(duì)此變量的引用。
用UDP協(xié)議通訊時(shí)怎樣得知目標(biāo)機(jī)是否獲得了數(shù)據(jù)包 可以在每個(gè)數(shù)據(jù)包中插入一個(gè)唯一的ID，比如timestamp或者遞增的int。 發(fā)送方在發(fā)送數(shù)據(jù)時(shí)將此ID和發(fā)送時(shí)間記錄在本地。 接收方在收到數(shù)據(jù)后將ID再發(fā)給發(fā)送方作為回應(yīng)。 發(fā)送方如果收到回應(yīng)，則知道接收方已經(jīng)收到相應(yīng)的數(shù)據(jù)包；如果在指定時(shí)間內(nèi)沒(méi)有收到回應(yīng)，則數(shù)據(jù)包可能丟失，需要重復(fù)上面的過(guò)程重新發(fā)送一次，直到確定對(duì)方收到。
求一個(gè)論壇的在線人數(shù)，假設(shè)有一個(gè)論壇，其注冊(cè)ID有兩億個(gè)，每個(gè)ID從登陸到退出會(huì)向一個(gè)日志文件中記下登陸時(shí)間和退出時(shí)間，要求寫(xiě)一個(gè)算法統(tǒng)計(jì)一天中論壇的用戶在線分布，取樣粒度為秒。 一天總共有 3600*24 = 86400秒。 定義一個(gè)長(zhǎng)度為86400的整數(shù)數(shù)組int delta[86400]，每個(gè)整數(shù)對(duì)應(yīng)這一秒的人數(shù)變化值，可能為正也可能為負(fù)。開(kāi)始時(shí)將數(shù)組元素都初始化為0。 然后依次讀入每個(gè)用戶的登錄時(shí)間和退出時(shí)間，將與登錄時(shí)間對(duì)應(yīng)的整數(shù)值加1，將與退出時(shí)間對(duì)應(yīng)的整數(shù)值減1。 這樣處理一遍后數(shù)組中存儲(chǔ)了每秒中的人數(shù)變化情況。 定義另外一個(gè)長(zhǎng)度為86400的整數(shù)數(shù)組int online_num[86400]，每個(gè)整數(shù)對(duì)應(yīng)這一秒的論壇在線人數(shù)。 假設(shè)一天開(kāi)始時(shí)論壇在線人數(shù)為0，則第1秒的人數(shù)online_num[0] = delta[0]。第n+1秒的人數(shù)online_num[n] = online_num[n-1] + delta[n]。 這樣我們就獲得了一天中任意時(shí)間的在線人數(shù)。
在一個(gè)文件中有 10G 個(gè)整數(shù)，亂序排列，要求找出中位數(shù)。內(nèi)存限制為 2G。 不妨假設(shè)10G個(gè)整數(shù)是64bit的。 2G內(nèi)存可以存放256M個(gè)64bit整數(shù)。 我們可以將64bit的整數(shù)空間平均分成256M個(gè)取值范圍，用2G的內(nèi)存對(duì)每個(gè)取值范圍內(nèi)出現(xiàn)整數(shù)個(gè)數(shù)進(jìn)行統(tǒng)計(jì)。這樣遍歷一邊10G整數(shù)后，我們便知道中數(shù)在那個(gè)范圍內(nèi)出現(xiàn)，以及這個(gè)范圍內(nèi)總共出現(xiàn)了多少個(gè)整數(shù)。 如果中數(shù)所在范圍出現(xiàn)的整數(shù)比較少，我們就可以對(duì)這個(gè)范圍內(nèi)的整數(shù)進(jìn)行排序，找到中數(shù)。如果這個(gè)范圍內(nèi)出現(xiàn)的整數(shù)比較多，我們還可以采用同樣的方法將此范圍再次分成多個(gè)更小的范圍（256M=2^28，所以最多需要3次就可以將此范圍縮小到1，也就找到了中數(shù)）。
兩個(gè)整數(shù)集合A和B，求其交集。 1. 讀取整數(shù)集合A中的整數(shù)，將讀到的整數(shù)插入到map中，并將對(duì)應(yīng)的值設(shè)為1。 2. 讀取整數(shù)集合B中的整數(shù)，如果該整數(shù)在map中并且值為1，則將此數(shù)加入到交集當(dāng)中，并將在map中的對(duì)應(yīng)值改為2。 通過(guò)更改map中的值，避免了將同樣的值輸出兩次。 2. 也可以將A和B分別排序，然后利用歸并的思想搞定。
有1到10w這10w個(gè)數(shù)，去除2個(gè)并打亂次序，如何找出那兩個(gè)數(shù)？ 申請(qǐng)10w個(gè)bit的空間，每個(gè)bit代表一個(gè)數(shù)字是否出現(xiàn)過(guò)。 開(kāi)始時(shí)將這10w個(gè)bit都初始化為0，表示所有數(shù)字都沒(méi)有出現(xiàn)過(guò)。 然后依次讀入已經(jīng)打亂循序的數(shù)字，并將對(duì)應(yīng)的bit設(shè)為1。 當(dāng)處理完所有數(shù)字后，根據(jù)為0的bit得出沒(méi)有出現(xiàn)的數(shù)字。
首先計(jì)算1到10w的和，平方和。 然后計(jì)算給定數(shù)字的和，平方和。 兩次的到的數(shù)字相減，可以得到這兩個(gè)數(shù)字的和，平方和。 所以我們有 x + y = n x^2 + y^2 = m 解方程可以得到x和y的值。
有1000瓶水，其中有一瓶有毒，小白鼠只要嘗一點(diǎn)帶毒的水24小時(shí)后就會(huì)死亡，至少要多少只小白鼠才能在24小時(shí)時(shí)鑒別出那瓶水有毒？ 最容易想到的就是用1000只小白鼠，每只喝一瓶。但顯然這不是最好答案。
既然每只小白鼠喝一瓶不是最好答案，那就應(yīng)該每只小白鼠喝多瓶。那每只應(yīng)該喝多少瓶呢？
首先讓我們換種問(wèn)法，如果有x只小白鼠，那么24小時(shí)內(nèi)可以從多少瓶水中找出那瓶有毒的？ 由于每只小白鼠都只有死或者活這兩種結(jié)果，所以x只小白鼠最大可以表示2^x種結(jié)果。如果讓每種結(jié)果都對(duì)應(yīng)到某瓶水有毒，那么也就可以從2^x瓶水中找到有毒的那瓶水。那如何來(lái)實(shí)現(xiàn)這種對(duì)應(yīng)關(guān)系呢？ 第一只小白鼠喝第1到2^(x-1)瓶，第二只小白鼠喝第1到第2^(x-2)和第2^(x-1)+1到第2^(x-1) + 2^(x-2)瓶....以此類(lèi)推。
回到此題，總過(guò)1000瓶水，所以需要最少10只小白鼠。
根據(jù)上排給出十個(gè)數(shù)，在其下排填出對(duì)應(yīng)的十個(gè)數(shù), 要求下排每個(gè)數(shù)都是上排對(duì)應(yīng)位置的數(shù)在下排出現(xiàn)的次數(shù)。上排的數(shù)：0，1，2，3，4，5，6，7，8，9。 0，1，2，3，4，5，6，7，8，9 6，2，1，0，0，0，1，0，0，0 通過(guò)一個(gè)循環(huán)做，三次循環(huán)搞定. 任意0-N，都是N-3的位置是1，前面是N-4,2,1，其他是0
給40億個(gè)不重復(fù)的unsigned int的整數(shù)，沒(méi)排過(guò)序的，然后再給幾個(gè)數(shù)，如何快速判斷這幾個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中? unsigned int 的取值范圍是0到2^32-1。我們可以申請(qǐng)連續(xù)的2^32/8=512M的內(nèi)存，用每一個(gè)bit對(duì)應(yīng)一個(gè)unsigned int數(shù)字。首先將512M內(nèi)存都初始化為0，然后每處理一個(gè)數(shù)字就將其對(duì)應(yīng)的bit設(shè)置為1。當(dāng)需要查詢時(shí)，直接找到對(duì)應(yīng)bit，看其值是0還是1即可。
IBM面試題：c++中引用和指針有什么不同？指針加上什么限制等于引用？ 引用不是一個(gè)變量，它只表示該引用名是目標(biāo)變量名的一個(gè)別名，它本身不是一種數(shù)據(jù)類(lèi)型，因此引用本身不占存儲(chǔ)單元，系統(tǒng)也不給引用分配存儲(chǔ)單元。引用一經(jīng)確定就不能修改。 指針是一個(gè)變量，需要在內(nèi)存中分配空間，此空間中存儲(chǔ)所指對(duì)象的地址。由于指針是一個(gè)普通變量，所以其值還可以通過(guò)重新賦值來(lái)改變。 把指針定義為const后，其值就不能改變了，功能和引用類(lèi)似，但有本質(zhì)的區(qū)別。
谷歌面試題：1024! 末尾有多少個(gè)0？ 末尾0的個(gè)數(shù)取決于乘法中因子2和5的個(gè)數(shù)。顯然乘法中因子2的個(gè)數(shù)大于5的個(gè)數(shù)，所以我們只需統(tǒng)計(jì)因子5的個(gè)數(shù)。 是5的倍數(shù)的數(shù)有： 1024 / 5 = 204個(gè) 是25的倍數(shù)的數(shù)有：1024 / 25 = 40個(gè) 是125的倍數(shù)的數(shù)有：1024 / 125 = 8個(gè) 是625的倍數(shù)的數(shù)有：1024 / 625 = 1個(gè) 所以1024! 中總共有204+40+8+1=253個(gè)因子5。 也就是說(shuō)1024! 末尾有253個(gè)0。
谷歌面試題：給定能隨機(jī)生成整數(shù)1到5的函數(shù)，寫(xiě)出能隨機(jī)生成整數(shù)1到7的函數(shù) 只要我們可以從 n 個(gè)數(shù)中隨機(jī)選出 1 到 n 個(gè)數(shù)，反復(fù)進(jìn)行這種運(yùn)算，直到剩下最后一個(gè)數(shù)即可。 我們可以調(diào)用 n 次給定函數(shù)，生成 n 個(gè) 1 到 5 之間的隨機(jī)數(shù)，選取最大數(shù)所在位置即可滿足以上要求。 例如 初始的 7 個(gè)數(shù) [1,2,3,4,5,6,7]. 7 個(gè) 1 到 5 的隨機(jī)數(shù) [5, 3,1,4,2,5,5] 那么我們保留下[1,6,7], 3 個(gè)1 到 5 的隨機(jī)數(shù)[2,4,1] 那么我們保留下[6] 6 就是我們這次生成的隨機(jī)數(shù)。
產(chǎn)生K個(gè)數(shù)(k>1) 假定產(chǎn)生的數(shù)分別為n1,n2,n3,n4... 那么定義產(chǎn)生的數(shù)為n1-1+（n2-2）*5+（n3-1）*5^2+（n4-1）*5^3........ 于是產(chǎn)生的數(shù)位于區(qū)間（0，5^k-1) 然后把5^k分成k等分，產(chǎn)生的數(shù)位于哪個(gè)等分就是那個(gè)產(chǎn)生的隨機(jī)數(shù)（0~6），然后+1即可 如果位于k等分的余數(shù)范圍，則重新執(zhí)行一次上述過(guò)程 不用擔(dān)心余數(shù)問(wèn)題，當(dāng)k取3時(shí)落到余數(shù)范圍的概率就已經(jīng)降低為6/125
判斷一個(gè)自然數(shù)是否是某個(gè)數(shù)的平方。當(dāng)然不能使用開(kāi)方運(yùn)算。 假設(shè)待判斷的數(shù)字是 N。
方法1： 遍歷從1到N的數(shù)字，求取平方并和N進(jìn)行比較。 如果平方小于N，則繼續(xù)遍歷；如果等于N，則成功退出；如果大于N，則失敗退出。 復(fù)雜度為O(n^0.5)。
方法2： 使用二分查找法，對(duì)1到N之間的數(shù)字進(jìn)行判斷。 復(fù)雜度為O(log n)。
方法3： 由于 (n+1)^2 =n^2 + 2n + 1， = ... = 1 + (2*1 + 1) + (2*2 + 1) + ... + (2*n + 1) 注意到這些項(xiàng)構(gòu)成了等差數(shù)列（每項(xiàng)之間相差2）。 所以我們可以比較 N-1， N - 1 - 3， N - 1 - 3 - 5 ... 和0的關(guān)系。 如果大于0，則繼續(xù)減；如果等于0，則成功退出；如果小于 0，則失敗退出。 復(fù)雜度為O(n^0.5)。不過(guò)方法3中利用加減法替換掉了方法1中的乘法，所以速度會(huì)更快些。
給定一個(gè)未知長(zhǎng)度的整數(shù)流，如何隨機(jī)選取一個(gè)數(shù)？ 方法1. 將整個(gè)整數(shù)流保存到一個(gè)數(shù)組中，然后再隨機(jī)選取。 如果整數(shù)流很長(zhǎng)，無(wú)法保存下來(lái)，則此方法不能使用。
方法2. 如果整數(shù)流在第一個(gè)數(shù)后結(jié)束，則我們必定會(huì)選第一個(gè)數(shù)作為隨機(jī)數(shù)。 如果整數(shù)流在第二個(gè)數(shù)后結(jié)束，我們選第二個(gè)數(shù)的概率為1/2。我們以1/2的概率用第2個(gè)數(shù)替換前面選的隨機(jī)數(shù)，得到滿足條件的新隨機(jī)數(shù)。 .... 如果整數(shù)流在第n個(gè)數(shù)后結(jié)束，我們選第n個(gè)數(shù)的概率為1/n。我們以1/n的概率用第n個(gè)數(shù)替換前面選的隨機(jī)數(shù)，得到滿足條件的新隨機(jī)數(shù)。 .... 利用這種方法，我們只需保存一個(gè)隨機(jī)數(shù)，和迄今整數(shù)流的長(zhǎng)度即可。所以可以處理任意長(zhǎng)的整數(shù)流。
設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，其中包含兩個(gè)函數(shù)，1.插入一個(gè)數(shù)字，2.獲得中數(shù)。并估計(jì)時(shí)間復(fù)雜度。 1. 使用數(shù)組存儲(chǔ)。 插入數(shù)字時(shí)，在O(1)時(shí)間內(nèi)將該數(shù)字插入到數(shù)組最后。 獲取中數(shù)時(shí)，在O(n)時(shí)間內(nèi)找到中數(shù)。（選數(shù)組的第一個(gè)數(shù)和其它數(shù)比較，并根據(jù)比較結(jié)果的大小分成兩組，那么我們可以確定中數(shù)在哪組中。然后對(duì)那一組按照同樣的方法進(jìn)一步細(xì)分，直到找到中數(shù)。）
2. 使用排序數(shù)組存儲(chǔ)。 插入數(shù)字時(shí)，在O(logn)時(shí)間內(nèi)找到要插入的位置，在O(n)時(shí)間里移動(dòng)元素并將新數(shù)字插入到合適的位置。 獲得中數(shù)時(shí)，在O(1)復(fù)雜度內(nèi)找到中數(shù)。
3. 使用大根堆和小根堆存儲(chǔ)。 使用大根堆存儲(chǔ)較小的一半數(shù)字，使用小根堆存儲(chǔ)較大的一半數(shù)字。 插入數(shù)字時(shí)，在O(logn)時(shí)間內(nèi)將該數(shù)字插入到對(duì)應(yīng)的堆當(dāng)中，并適當(dāng)移動(dòng)根節(jié)點(diǎn)以保持兩個(gè)堆數(shù)字相等（或相差1）。 獲取中數(shù)時(shí)，在O(1)時(shí)間內(nèi)找到中數(shù)。
谷歌面試題：在一個(gè)特殊數(shù)組中進(jìn)行查找 給定一個(gè)固定長(zhǎng)度的數(shù)組，將遞增整數(shù)序列寫(xiě)入這個(gè)數(shù)組。當(dāng)寫(xiě)到數(shù)組尾部時(shí)，返回?cái)?shù)組開(kāi)始重新寫(xiě)，并覆蓋先前寫(xiě)過(guò)的數(shù)。請(qǐng)?jiān)谶@個(gè)特殊數(shù)組中找出給定的整數(shù)。 假設(shè)數(shù)組為a[0, 1, ..., N-1]。 我們可以采用類(lèi)似二分查找的策略。 首先比較a[0]和a[N/2]，如果a[0] < a[N/2]，則說(shuō)明a[0,1,...,N/2]為遞增子序列，否則另一部分是遞增子序列。 然后判斷要找的整數(shù)是否在遞增子序列范圍內(nèi)。如果在，則使用普通的二分查找方法繼續(xù)查找；如果不在，則重復(fù)上面的查找過(guò)程，直到找到或者失敗為止。
谷歌面試題：給定兩個(gè)已排序序列，找出共同的元素 不妨假設(shè)序列是從小到大排序的。定義兩個(gè)指針?lè)謩e指向序列的開(kāi)始。 如果指向的兩個(gè)元素相等，則找到一個(gè)相同的元素；如果不等，則將指向較小元素的指針向前移動(dòng)。 重復(fù)執(zhí)行上面的步驟，直到有一個(gè)指針指向序列尾端。如果兩個(gè)數(shù)組大小差不多，用你的方法就行了，如果數(shù)組大小差得很多，就遍歷小的，然后在大的里二分查找~
編程實(shí)現(xiàn)兩個(gè)正整數(shù)的除法，當(dāng)然不能用除法操作符。
// return x/y. int div(const int x, const int y) { .... } int div(const int x, const int y) { int left_num = x; int result = 0; while (left_num >= y) { int multi = 1; while (y * multi <= (left_num >> 1)) { multi = multi << 1; } result += multi; left_num -= y * multi; } return result; }
微軟面試題：計(jì)算n bit的整數(shù)中有多少bit 為1 設(shè)此整數(shù)為x。 方法1： 讓此整數(shù)除以2，如果余數(shù)為1，說(shuō)明最后一位是1，統(tǒng)計(jì)值加1。 將除得的結(jié)果進(jìn)行上面運(yùn)算，直到結(jié)果為0。
方法2： 考慮除法復(fù)雜度有些高，可以使用移位操作代替除法。 將 x 和 1 進(jìn)行按位與操作（x&1），如果結(jié)果為1，說(shuō)明最后一位是1，統(tǒng)計(jì)值加1。 將x 向右一位（x >> 1），重復(fù)上面過(guò)程，直到移位后結(jié)果為0。
方法3： 如果需要統(tǒng)計(jì)很多數(shù)字，并且內(nèi)存足夠大，可以考慮將每個(gè)數(shù)對(duì)應(yīng)的bit為1的數(shù)量記錄下來(lái)，這樣每次計(jì)算只是一次查找操作。
微軟面試題：快速求取一個(gè)整數(shù)的7倍 乘法相對(duì)比較慢，所以快速的方法就是將這個(gè)乘法轉(zhuǎn)換成加減法和移位操作。 可以將此整數(shù)先左移三位（×8）然后再減去原值：X << 3 - X。
微軟面試題：判斷一個(gè)數(shù)是不是2的n次冪 設(shè)要判斷的數(shù)是無(wú)符號(hào)整數(shù)X。 首先判斷X是否為0，如果為0則不是2的n次冪，返回。 X和X-1進(jìn)行按位與操作，如果結(jié)果是0，則說(shuō)明這個(gè)數(shù)是2的n次冪；如果結(jié)果非0，則說(shuō)明這個(gè)數(shù)不是2 的n次冪。
證明： 如果是2的n次冪，則此數(shù)用二進(jìn)制表示時(shí)只有一位是1，其它都是0。減1后，此位變成0，后面的位變成1，所以按位與后結(jié)果是0。 如果不是2的n次冪，則此數(shù)用二進(jìn)制表示時(shí)有多位是1。減1后，只有最后一個(gè)1變成0，前面的 1還是1，所以按位與后結(jié)果不是0。
微軟面試題：判斷數(shù)組中是否包含重復(fù)數(shù)字 給定一個(gè)長(zhǎng)度為N的數(shù)組，其中每個(gè)元素的取值范圍都是1到N。判斷數(shù)組中是否有重復(fù)的數(shù)字。（原數(shù)組不必保留） 方法1. 對(duì)數(shù)組進(jìn)行排序（快速，堆），然后比較相鄰的元素是否相同。 時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)。
方法2. 使用bitmap方法。 定義長(zhǎng)度為N/8的char數(shù)組，每個(gè)bit表示對(duì)應(yīng)數(shù)字是否出現(xiàn)過(guò)。遍歷數(shù)組，使用 bitmap對(duì)數(shù)字是否出現(xiàn)進(jìn)行統(tǒng)計(jì)。 時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。
方法3. 遍歷數(shù)組，假設(shè)第 i 個(gè)位置的數(shù)字為 j ，則通過(guò)交換將 j 換到下標(biāo)為 j 的位置上。直到所有數(shù)字都出現(xiàn)在自己對(duì)應(yīng)的下標(biāo)處，或發(fā)生了沖突。 時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。
微軟面試題：刪除鏈表中的重復(fù)項(xiàng) 一個(gè)沒(méi)有排序的鏈表，比如list={a,l,x,b,e,f,f,e,a,g,h,b,m}，請(qǐng)去掉重復(fù)項(xiàng)，并保留原順序，以上鏈表去掉重復(fù)項(xiàng)后為newlist={a,l,x,b,e,f,g,h,m}，請(qǐng)寫(xiě)出一個(gè)高效算法(時(shí)間比空間更重要)。 建立一個(gè)hash_map，key為鏈表中已經(jīng)遍歷的節(jié)點(diǎn)內(nèi)容，開(kāi)始時(shí)為空。 從頭開(kāi)始遍歷鏈表中的節(jié)點(diǎn)： - 如果節(jié)點(diǎn)內(nèi)容已經(jīng)在hash_map中存在，則刪除此節(jié)點(diǎn)，繼續(xù)向后遍歷； - 如果節(jié)點(diǎn)內(nèi)容不在hash_map中，則保留此節(jié)點(diǎn)，將節(jié)點(diǎn)內(nèi)容添加到hash_map中，繼續(xù)向后遍歷。
微軟面試題：編一個(gè)程序求質(zhì)數(shù)的和 編一個(gè)程序求質(zhì)數(shù)的和，例如F(7) = 2+3+5+7+11+13+17=58。
方法1： 對(duì)于從2開(kāi)始的遞增整數(shù)n進(jìn)行如下操作： 用 [2，n-1] 中的數(shù)依次去除n，如果余數(shù)為0，則說(shuō)明n不是質(zhì)數(shù)；如果所有余數(shù)都不是0，則說(shuō)明n是質(zhì)數(shù)，對(duì)其進(jìn)行加和。
空間復(fù)雜度為O(1)，時(shí)間復(fù)雜度為O(n^2)，其中n為需要找到的最大質(zhì)數(shù)值（例子對(duì)應(yīng)的值為17） 方法2： 可以維護(hù)一個(gè)質(zhì)數(shù)序列，這樣當(dāng)需要判斷一個(gè)數(shù)是否是質(zhì)數(shù)時(shí)，只需判斷是否能被比自己小的質(zhì)數(shù)整除即可。
對(duì)于從2開(kāi)始的遞增整數(shù)n進(jìn)行如下操作： 用 [2，n-1] 中的質(zhì)數(shù)（2，3，5，7，開(kāi)始時(shí)此序列為空）依次去除n，如果余數(shù)為0，則說(shuō)明n不是質(zhì)數(shù)；如果所有余數(shù)都不是0，則說(shuō)明n是質(zhì)數(shù)，將此質(zhì)數(shù)加入質(zhì)數(shù)序列，并對(duì)其進(jìn)行加和。
空間復(fù)雜度為O(m)，時(shí)間復(fù)雜度為O(mn)，其中m為質(zhì)數(shù)的個(gè)數(shù)（例子對(duì)應(yīng)的值為7），n為需要找到的最大質(zhì)數(shù)值（例子對(duì)應(yīng)的值為17）。 方法3： 也可以不用除法，而用加法。 申請(qǐng)一個(gè)足夠大的空間，每個(gè)bit對(duì)應(yīng)一個(gè)整數(shù)，開(kāi)始將所有的bit都初始化為0。 對(duì)于已知的質(zhì)數(shù)（開(kāi)始時(shí)只有2），將此質(zhì)數(shù)所有的倍數(shù)對(duì)應(yīng)的bit都改為1，那么最小的值為0的bit對(duì)應(yīng)的數(shù)就是一個(gè)質(zhì)數(shù)。對(duì)新獲得的質(zhì)數(shù)的倍數(shù)也進(jìn)行標(biāo)注。 對(duì)這樣獲得的質(zhì)數(shù)序列累加就可以獲得質(zhì)數(shù)和。
空間復(fù)雜度為O(n)，時(shí)間負(fù)責(zé)度為O(n)，其中n為需要找到的最大質(zhì)數(shù)值（例子對(duì)應(yīng)的值為17）
微軟面試題：給出一種洗牌算法 給出洗牌的一個(gè)算法，并將洗好的牌存儲(chǔ)在一個(gè)整形數(shù)組里。 假設(shè)數(shù)組Card[0 - 53]中的54個(gè)數(shù)對(duì)應(yīng)54張牌，從第一張牌（i = 0）開(kāi)始直到倒數(shù)第二張牌（i = 52），每次生成一個(gè)[ i, 53]之間的數(shù)r，將Card[i]和Card[r]中的數(shù)互換。
微軟面試題：找到兩個(gè)單向鏈表的第一個(gè)公共節(jié)點(diǎn) 如果兩個(gè)單向鏈表有公共節(jié)點(diǎn)，則兩個(gè)鏈表會(huì)構(gòu)成Y型結(jié)構(gòu)，最后一個(gè)節(jié)點(diǎn)相同。
我們可以從頭開(kāi)始遍歷兩個(gè)鏈表，找到最后一個(gè)節(jié)點(diǎn)的指針，設(shè)為p_a，p_b。同時(shí)記錄下兩個(gè)鏈表的長(zhǎng)度len_a，len_b（假設(shè)len_a >= len_b)。 如果p_a == p_b，則說(shuō)明兩個(gè)鏈表有公共節(jié)點(diǎn)，否則沒(méi)有。 如果有公共節(jié)點(diǎn)，則第一個(gè)公共節(jié)點(diǎn)距起始節(jié)點(diǎn)的距離滿足 len_a - start_a == len_b - start_b。 所以第一個(gè)可能的公共節(jié)點(diǎn)距起始節(jié)點(diǎn)的距離是 len_a - len_b, 0。我們從這兩個(gè)節(jié)點(diǎn)開(kāi)始比較，直到找到第一個(gè)公共節(jié)點(diǎn)。
微軟面試題：如何在鏈表里如何發(fā)現(xiàn)循環(huán)鏈接? 解答： 從鏈表的開(kāi)始處，由兩個(gè)指針A和B同時(shí)開(kāi)始遍歷鏈表。指針A每向前移動(dòng)一步，指針B都向前移動(dòng)兩步。如果在移動(dòng)了N步以后，指針A和B指向了同一個(gè)節(jié)點(diǎn)，則此鏈表中存在循環(huán)鏈表。 分析： 當(dāng)然還可以在遍歷的過(guò)程中存儲(chǔ)節(jié)點(diǎn)的地址，通過(guò)不斷的比較地址來(lái)判斷有沒(méi)有循環(huán)鏈表。但這種算法會(huì)使用更多的內(nèi)存。 如果考官比較變態(tài)，還可以直接考復(fù)制鏈表。如果復(fù)制前沒(méi)有測(cè)試循環(huán)鏈表，那不好意思，只能扣分了
谷歌面試題：找到鏈表的倒數(shù)第m個(gè)節(jié)點(diǎn) 方法1： 首先遍歷鏈表，統(tǒng)計(jì)鏈表的長(zhǎng)度N。 然后再次遍歷鏈表，找到第N-m個(gè)節(jié)點(diǎn)，即為倒數(shù)第m個(gè)節(jié)點(diǎn)。
方法2： 使用兩個(gè)指針，并使它們指向的節(jié)點(diǎn)相距m-1個(gè)。 然后同時(shí)向前移動(dòng)兩個(gè)指針，當(dāng)一個(gè)指針指最后一個(gè)節(jié)點(diǎn)時(shí)，第二個(gè)指針指向倒數(shù)第m個(gè)節(jié)點(diǎn)。
兩個(gè)方法的復(fù)雜度都是O(n)。 但是當(dāng)N較大而m較小時(shí)，方法2可能會(huì)更快一些。因?yàn)榉椒?能更好利用CPU的緩存。
谷歌面試題：給定一個(gè)排序數(shù)組，如何構(gòu)造一個(gè)二叉排序樹(shù)？ 采用遞歸算法。 選取數(shù)組中間的一個(gè)元素作為根節(jié)點(diǎn)，左邊的元素構(gòu)造左子樹(shù)，右邊的節(jié)點(diǎn)構(gòu)造有子樹(shù)。
谷歌面試題：數(shù)組中是否有兩個(gè)數(shù)的和為10 1. 比較任意兩個(gè)數(shù)的和是否為10。如 for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { .... }} 復(fù)雜度為O(n*n)。
2. 將數(shù)組排序后，對(duì)每個(gè)數(shù)m，使用二分查找在數(shù)組中尋找10-m。 復(fù)雜度為O(nlogn)。
3. 將數(shù)組存儲(chǔ)到hash_set中去，對(duì)每個(gè)數(shù)m，在hash_set中尋找10-m。 復(fù)雜度為O(n)。
4. 如果數(shù)組很大，超過(guò)內(nèi)存的容量，可以按照hash(max(m, 10-m))%g，將數(shù)據(jù)分到g個(gè)小的group中。然后對(duì)每個(gè)小的group進(jìn)行單獨(dú)處理。 復(fù)雜度為O(n)。
谷歌面試題：找到兩個(gè)字符串的公共字符，并按照其中一個(gè)的排序 寫(xiě)一函數(shù)f(a,b)，它帶有兩個(gè)字符串參數(shù)并返回一串字符，該字符串只包含在兩個(gè)串中都有的并按照在a中的順序。寫(xiě)一個(gè)版本算法復(fù)雜度O(N^2)和一個(gè)O(N) 。 O(N^2)： 對(duì)于a中的每個(gè)字符，遍歷b中的每個(gè)字符，如果相同，則拷貝到新字符串中。
O(N)： 首先使用b中的字符建立一個(gè)hash_map，對(duì)于a中的每個(gè)字符，檢測(cè)hash_map中是否存在，如果存在則拷貝到新字符串中。
在給定整數(shù)序列中，找出最大和的子序列 給定一個(gè)整數(shù)序列，其中有些是負(fù)數(shù)，有些是正數(shù)，從該序列中找出最大和的子序列。比如：-5，20，-4，10，-18，子序列[20，-4，10]具有最大和26。 int GetMaxSubArraySum(int* array, int array_len) { ` int current_sum = 0; ` int max_sum = 0; ` for (int i = 0; i < array_len; ++i) { ` current_sum += array[i]; ` if (current_sum > max_sum) { ` max_sum = current_sum; ` } else if (current_sum < 0) { ` current_sum = 0; ` } ` } ` return max_sum; ` }
谷歌面試題：將無(wú)向無(wú)環(huán)連通圖轉(zhuǎn)換成深度最小的樹(shù) 已知一個(gè)無(wú)向無(wú)環(huán)連通圖T的所有頂點(diǎn)和邊的信息，現(xiàn)需要將其轉(zhuǎn)換為一棵樹(shù)，要求樹(shù)的深度最小，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找到所有滿足要求的樹(shù)的根結(jié)點(diǎn)，并分析時(shí)空復(fù)雜度。
最簡(jiǎn)單直接的方法就是把每個(gè)節(jié)點(diǎn)都試一遍： 假設(shè)某個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，計(jì)算樹(shù)的深度。當(dāng)遍歷完所有節(jié)點(diǎn)后，也就找到了使樹(shù)的深度最小的根節(jié)點(diǎn)。 但這個(gè)方法的復(fù)雜度很高。如果有n個(gè)節(jié)點(diǎn)，則時(shí)間復(fù)雜度為O(n^2)。
樹(shù)的深度取決于根節(jié)點(diǎn)到最深葉節(jié)點(diǎn)的距離，所以我們可以從葉節(jié)點(diǎn)入手。 葉節(jié)點(diǎn)會(huì)且只會(huì)和某一個(gè)節(jié)點(diǎn)連通（反之不成立，因?yàn)楦?jié)點(diǎn)也可能只和一個(gè)節(jié)點(diǎn)連通），所以我們很容易找到所有可能的葉節(jié)點(diǎn)。 題目可以等價(jià)于找到了兩個(gè)葉節(jié)點(diǎn)，使得兩個(gè)葉節(jié)點(diǎn)之間的距離最遠(yuǎn)。根節(jié)點(diǎn)就是這兩個(gè)葉節(jié)點(diǎn)路徑的中間點(diǎn)（或者中間兩個(gè)點(diǎn)的任意一個(gè)）。 我們可以每次都將連接度為1的節(jié)點(diǎn)刪掉，直到最后只剩下1個(gè)或2個(gè)節(jié)點(diǎn)，則這一個(gè)節(jié)點(diǎn)，或者兩個(gè)節(jié)點(diǎn)中的任意一個(gè)，就是我們要找的根節(jié)點(diǎn)。
谷歌面試題：將字符串中的小寫(xiě)字母排在大寫(xiě)字母的前面 有一個(gè)由大小寫(xiě)組成的字符串，現(xiàn)在需要對(duì)它進(jìn)行修改，將其中的所有小寫(xiě)字母排在大寫(xiě)字母的前面（大寫(xiě)或小寫(xiě)字母之間不要求保持原來(lái)次序）。 初始化兩個(gè)int變量A和B，代表字符串中的兩個(gè)位置。開(kāi)始時(shí)A指向字符串的第一個(gè)字符，B指向字符串的最后一個(gè)字符。 逐漸增加A的值使其指向一個(gè)大寫(xiě)字母，逐漸減小B使其指向一個(gè)小寫(xiě)字母，交換A，B所指向的字符，然后繼續(xù)增加A，減小B....。 當(dāng)A>=B時(shí)，就完成了重新排序。
谷歌面試題：如何拷貝特殊鏈表 有一個(gè)特殊的鏈表，其中每個(gè)節(jié)點(diǎn)不但有指向下一個(gè)節(jié)點(diǎn)的指針pNext，還有一個(gè)指向鏈表中任意節(jié)點(diǎn)的指針pRand，如何拷貝這個(gè)特殊鏈表？ 拷貝pNext指針?lè)浅Ｈ菀?，所以題目的難點(diǎn)是如何拷貝pRand指針。 假設(shè)原來(lái)鏈表為A1 -> A2 ->... -> An，新拷貝鏈表是B1 -> B2 ->...-> Bn。 為了能夠快速的找到pRand指向的節(jié)點(diǎn)，并把對(duì)應(yīng)的關(guān)系拷貝到B中。我們可以將兩個(gè)鏈表合并成 A1 -> B1 -> A2 -> B2 -> ... -> An -> Bn。 從A1節(jié)點(diǎn)出發(fā)，很容易找到A1的pRand指向的節(jié)點(diǎn)Ax,然后也就找到了Bx，將B1的pRand指向Bx也就完成了B1節(jié)點(diǎn)pRand的拷貝。依次類(lèi)推。 當(dāng)所有節(jié)點(diǎn)的pRand都拷貝完成后，再將合并鏈表分成兩個(gè)鏈表就可以了。
谷歌面試題：10分鐘內(nèi)看到一輛車(chē)的概率是多少？ 如果在高速公路上30分鐘內(nèi)看到一輛車(chē)開(kāi)過(guò)的幾率是0.95，那么在10分鐘內(nèi)看到一輛車(chē)開(kāi)過(guò)的幾率是多少？(假設(shè)為常概率條件下) 假設(shè)10分鐘內(nèi)看到一輛車(chē)開(kāi)過(guò)的概率是x，那么沒(méi)有看到車(chē)開(kāi)過(guò)的概率就是1-x，30分鐘沒(méi)有看到車(chē)開(kāi)過(guò)的概率是(1-x)^3，也就是0.05。所以得到方程 (1-x)^3 = 0.05 解方程得到x大約是0.63。
百度面試題：從輸入url到顯示網(wǎng)頁(yè)，后臺(tái)發(fā)生了什么？ 簡(jiǎn)單來(lái)說(shuō)有以下步驟： 1. 查找域名對(duì)應(yīng)的IP地址。這一步會(huì)依次查找瀏覽器緩存，系統(tǒng)緩存，路由器緩存，ISP DNS緩存，根域名服務(wù)器。 2. 向IP對(duì)應(yīng)的服務(wù)器發(fā)送請(qǐng)求。 3. 服務(wù)器響應(yīng)請(qǐng)求，發(fā)回網(wǎng)頁(yè)內(nèi)容。 4. 瀏覽器解析網(wǎng)頁(yè)內(nèi)容。 當(dāng)然，由于網(wǎng)頁(yè)可能有重定向，或者嵌入了圖片，AJAX，其它子網(wǎng)頁(yè)等等，這4個(gè)步驟可能反復(fù)進(jìn)行多次才能將最終頁(yè)面展示給用戶。 百度面試題：設(shè)計(jì)DNS服務(wù)器中cache的數(shù)據(jù)結(jié)構(gòu) 要求設(shè)計(jì)一個(gè)DNS的Cache結(jié)構(gòu)，要求能夠滿足每秒5000以上的查詢，滿足IP數(shù)據(jù)的快速插入，查詢的速度要快。（題目還給出了一系列的數(shù)據(jù)，比如：站點(diǎn)數(shù)總共為5000萬(wàn)，IP地址有1000萬(wàn)，等等） DNS服務(wù)器實(shí)現(xiàn)域名到IP地址的轉(zhuǎn)換。
每個(gè)域名的平均長(zhǎng)度為25個(gè)字節(jié)（估計(jì)值），每個(gè)IP為4個(gè)字節(jié)，所以Cache的每個(gè)條目需要大概30個(gè)字節(jié)。 總共50M個(gè)條目，所以需要1.5G個(gè)字節(jié)的空間?？梢苑胖迷趦?nèi)存中。（考慮到每秒5000次操作的限制，也只能放在內(nèi)存中。） 可以考慮的數(shù)據(jù)結(jié)構(gòu)包括hash_map，字典樹(shù)，紅黑樹(shù)等等。
百度面試題：將多個(gè)集合合并成沒(méi)有交集的集合 給定一個(gè)字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求將其中交集不為空的集合合并，要求合并完成后的集合之間無(wú)交集，例如上例應(yīng)輸出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。 （1）請(qǐng)描述你解決這個(gè)問(wèn)題的思路； （2）請(qǐng)給出主要的處理流程，算法，以及算法的復(fù)雜度 （3）請(qǐng)描述可能的改進(jìn)。 集合使用hash_set來(lái)表示，這樣合并時(shí)間復(fù)雜度比較低。
1. 給每個(gè)集合編號(hào)為0，1，2，3... 2. 創(chuàng)建一個(gè)hash_map，key為字符串，value為一個(gè)鏈表，鏈表節(jié)點(diǎn)為字符串所在集合的編號(hào)。 遍歷所有的集合，將字符串和對(duì)應(yīng)的集合編號(hào)插入到hash_map中去。 3. 創(chuàng)建一個(gè)長(zhǎng)度等于集合個(gè)數(shù)的int數(shù)組，表示集合間的合并關(guān)系。例如，下標(biāo)為5的元素值為3，表示將下標(biāo)為5的集合合并到下標(biāo)為3的集合中去。 開(kāi)始時(shí)將所有值都初始化為-1，表示集合間沒(méi)有互相合并。 在集合合并的過(guò)程中，我們將所有的字符串都合并到編號(hào)較小的集合中去。 遍歷第二步中生成的hash_map，對(duì)于每個(gè)value中的鏈表，首先找到最小的集合編號(hào)（有些集合已經(jīng)被合并過(guò)，需要順著合并關(guān)系數(shù)組找到合并后的集合編號(hào)），然后將鏈表中所有編號(hào)的集合都合并到編號(hào)最小的集合中（通過(guò)更改合并關(guān)系數(shù)組）。 4.現(xiàn)在合并關(guān)系數(shù)組中值為-1的集合即為最終的集合，它的元素來(lái)源于所有直接或間接指向它的集合。
算法的復(fù)雜度為O(n)，其中n為所有集合中的元素個(gè)數(shù)。 題目中的例子： 0: {aaa bbb ccc} 1: {bbb ddd} 2: {eee fff} 3: {ggg} 4: {ddd hhh} 生成的hash_map，和處理完每個(gè)值后的合并關(guān)系數(shù)組分別為 aaa: 0。[-1, -1, -1, -1, -1] bbb: 0, 1。[-1, 0, -1, -1, -1] ccc: 0。[-1, 0, -1, -1, -1] ddd: 1, 4。[-1, 0, -1, -1, 0] eee: 2。[-1, 0, -1, -1, 0] fff: 2。[-1, 0, -1, -1, 0] ggg: 3。[-1, 0, -1, -1, 0] hhh: 4。[-1, 0, -1, -1, 0] 所以合并完后有三個(gè)集合，第0，1，4個(gè)集合合并到了一起， 第2，3個(gè)集合沒(méi)有進(jìn)行合并。
百度面試題：用C語(yǔ)言將輸入的字符串在原串上倒序 void revert(char* str) { ` char c; ` for (int front = 0, int back = strlen(str) - 1; ` front < back; ` ++front, --back) { ` c = str[back]; ` str[back] = str[front]; ` str[front] = c; ` } ` }
百度面試題：找出給定字符串對(duì)應(yīng)的序號(hào) 序列Seq=[a,b,…z,aa,ab…az,ba,bb,…bz,…,za,zb,…zz,aaa,…] 類(lèi)似與excel的排列，任意給出一個(gè)字符串s=[a-z]+(由a-z字符組成的任意長(zhǎng)度字符串），請(qǐng)問(wèn)s是序列Seq的第幾個(gè)。 注意到每滿26個(gè)就會(huì)向前進(jìn)一位，類(lèi)似一個(gè)26進(jìn)制的問(wèn)題。 比如ab，則位置為26*1 + 2； 比如za，則位置為26*26 + 1； 比如abc，則位置為26*26*1 + 26*2 + 3
百度面試題：找出第k大的數(shù)字所在的位置 寫(xiě)一段程序，找出數(shù)組中第k大小的數(shù)，輸出數(shù)所在的位置。例如{2，4，3，4，7}中，第一大的數(shù)是7，位置在4。第二大、第三大的數(shù)都是4，位置在1、3隨便輸出哪一個(gè)均可。 先找到第k大的數(shù)字，然后再遍歷一遍數(shù)組找到它的位置。所以題目的難點(diǎn)在于如何最高效的找到第k大的數(shù)。
我們可以通過(guò)快速排序，堆排序等高效的排序算法對(duì)數(shù)組進(jìn)行排序，然后找到第k大的數(shù)字。這樣總體復(fù)雜度為O(N logN)。
我們還可以通過(guò)二分的思想，找到第k大的數(shù)字，而不必對(duì)整個(gè)數(shù)組排序。 從數(shù)組中隨機(jī)選一個(gè)數(shù)t，通過(guò)讓這個(gè)數(shù)和其它數(shù)比較，我們可以將整個(gè)數(shù)組分成了兩部分并且滿足，{x, xx, ..., t} < {y, yy, ...}。 在將數(shù)組分成兩個(gè)數(shù)組的過(guò)程中，我們還可以記錄每個(gè)子數(shù)組的大小。這樣我們就可以確定第k大的數(shù)字在哪個(gè)子數(shù)組中。 然后我們繼續(xù)對(duì)包含第k大數(shù)字的子數(shù)組進(jìn)行同樣的劃分，直到找到第k大的數(shù)字為止。 平均來(lái)說(shuō)，由于每次劃分都會(huì)使子數(shù)組縮小到原來(lái)1/2，所以整個(gè)過(guò)程的復(fù)雜度為O(N)。
百度面試題：找到滿足條件的數(shù)組 給定函數(shù)d(n) = n + n的各位之和，n為正整數(shù)，如 d(78) = 78+7+8=93。 這樣這個(gè)函數(shù)可以看成一個(gè)生成器，如93可以看成由78生成。 定義數(shù)A：數(shù)A找不到一個(gè)數(shù)B可以由d(B)=A，即A不能由其他數(shù)生成?，F(xiàn)在要寫(xiě)程序，找出1至10000里的所有符合數(shù)A定義的數(shù)。 申請(qǐng)一個(gè)長(zhǎng)度為10000的bool數(shù)組，每個(gè)元素代表對(duì)應(yīng)的值是否可以有其它數(shù)生成。開(kāi)始時(shí)將數(shù)組中的值都初始化為false。 由于大于10000的數(shù)的生成數(shù)必定大于10000，所以我們只需遍歷1到10000中的數(shù)，計(jì)算生成數(shù)，并將bool數(shù)組中對(duì)應(yīng)的值設(shè)置為true，表示這個(gè)數(shù)可以有其它數(shù)生成。 最后bool數(shù)組中值為false的位置對(duì)應(yīng)的整數(shù)就是不能由其它數(shù)生成的。
百度面試題：對(duì)正整數(shù)，算得到1需要操作的次數(shù) 實(shí)現(xiàn)一個(gè)函數(shù)，對(duì)一個(gè)正整數(shù)n，算得到1需要的最少操作次數(shù)。 操作規(guī)則為：如果n為偶數(shù)，將其除以2；如果n為奇數(shù)，可以加1或減1；一直處理下去。 例子： func(7) = 4，可以證明最少需要4次運(yùn)算 n = 7 n-1 6 n/2 3 n-1 2 n/2 1 要求：實(shí)現(xiàn)函數(shù)(實(shí)現(xiàn)盡可能高效) int func(unsign int n)；n為輸入，返回最小的運(yùn)算次數(shù)。 給出思路(文字描述)，完成代碼，并分析你算法的時(shí)間復(fù)雜度。
int func(unsign int n) { if (n == 1) { return 0; } if (n%2 == 0) { return 1 + func(n/2); } int x = func(n+1); int y = func(n-1); if (x > y) { return y + 1; } else { return x + 1; } } 假設(shè)n表示成二進(jìn)制有x bit，可以看出計(jì)算復(fù)雜度為O(2^x)，也就是O(n)。 int func(unsign int n) { ` if (n == 1) { ` return 0; ` } ` if (n % 2 == 0) { ` return 1 + func(n/2); ` } ` if (n == 3) { ` return 2; ` } ` if ( n & 2) { ` return 1 + func(n + 1); ` } else { ` return 1 + func(n - 1); ` } ` } 百度面試題：找出N！后面的0的個(gè)數(shù) 容易理解，題目等價(jià)于求因子2和因子5出現(xiàn)的次數(shù)。 對(duì)于因子2來(lái)說(shuō)，數(shù)字2，4，6，8，10....2n...中存在因子2，這樣就獲得了 N/2 （其中N/2只取結(jié)果的整數(shù)部分）個(gè)因子2。這些數(shù)字去除因子2后，變成1，2，3....N/2，又可以提取N/4個(gè)因子2....這樣一直到只剩下1個(gè)數(shù)（1）。所以N！中總共可以獲得N/2 + N/4 + N/8 +....個(gè)因子2。 同理，N！中可以獲得N/5 + N/25 + ... 個(gè)因子5。 尾部連續(xù)0的個(gè)數(shù)就是因子2和因子5較少的那個(gè)。
對(duì)于題目中的例子，18！中包含9+4+2+1個(gè)因子2，包含3個(gè)因子5。所以尾部有3個(gè)連續(xù)0。
計(jì)算的復(fù)雜度為O(logN)。
百度面試題：找出被修改過(guò)的數(shù)字 n個(gè)空間（其中n<1M），存放a到a+n-1的數(shù)，位置隨機(jī)且數(shù)字不重復(fù)，a為正且未知?，F(xiàn)在第一個(gè)空間的數(shù)被誤設(shè)置為-1。已經(jīng)知道被修改的數(shù)不是最小的。請(qǐng)找出被修改的數(shù)字是多少。 例如：n=6，a=2，原始的串為5, 3, 7, 6, 2, 4?，F(xiàn)在被別人修改為-1, 3, 7, 6, 2, 4?，F(xiàn)在希望找到5。
由于修改的數(shù)不是最小的，所以遍歷第二個(gè)空間到最后一個(gè)空間可以得到a的值。 a 到 a+n-1這 n個(gè)數(shù)的和是 total = na + (n - 1)n/2。 將第二個(gè)至最后一個(gè)空間的數(shù)累加獲得 sub_total。 那么被修改的數(shù)就是 total - sub_total。
百度面試題：在100w個(gè)數(shù)中找最大的前100個(gè)數(shù) 應(yīng)該使用某種數(shù)據(jù)結(jié)構(gòu)保存迄今最大的100個(gè)數(shù)。每讀到一個(gè)新數(shù)時(shí)，將新數(shù)和保存的100個(gè)數(shù)中的最小一個(gè)相比較，如果新數(shù)更大些，則替換。這樣掃描一遍100w個(gè)數(shù)也就獲得了最大的100個(gè)數(shù)。 對(duì)于保存的100個(gè)數(shù)的數(shù)據(jù)結(jié)構(gòu)，應(yīng)該在最小復(fù)雜度的條件下滿足 1）可以獲得最小的數(shù)； 2）將最小數(shù)替換為另一個(gè)數(shù)后可以重新調(diào)整，使其可以滿足條件1。 可見(jiàn)小根堆可以滿足這些條件。 所以應(yīng)該采用小根堆+掃描的方法。
方法1：類(lèi)似《算法導(dǎo)論》中用二分法求第K大數(shù)，理想TC是O(n)。
百度面試題：正向最大匹配分詞，怎么做最快？ 用所有詞生成一個(gè)字典樹(shù)，匹配的過(guò)程就是查字典的過(guò)程。 假設(shè)我們有兩個(gè)詞”百度“，”百家姓“，那么生成的字典樹(shù)就是：
百---度* | |-----家----姓*
其中“度”和“姓”旁邊的星號(hào)表示這是一個(gè)有效詞。 對(duì)于句子“百度面試題“，首先在字典中找”百“，找到了；繼續(xù)向下查找”度“，又找到了；繼續(xù)向下查找”面“，沒(méi)有找到。那么”百度“就是我們分出來(lái)的第一個(gè)詞。 還可以用hash_map來(lái)做。 首先用所有的詞生成一個(gè)hash_map，假設(shè)我們有兩個(gè)詞“百度，“百家姓”，那么生成hash_map如下： { 百：0 百度：1 百家：0 百家姓：1 } 其中值為0表示對(duì)應(yīng)的key不是一個(gè)詞，但有更長(zhǎng)的詞包括這個(gè)key；值為1表示這是一個(gè)詞。 對(duì)于句子“百度面試題”，首先在hash_map中查找“百”，找到對(duì)應(yīng)值為0，繼續(xù)；查找“百度”，找到對(duì)應(yīng)值為1，說(shuō)明這是一個(gè)詞，記下來(lái)并繼續(xù)；查找“百度面”，沒(méi)有找到，說(shuō)明沒(méi)有更長(zhǎng)的詞包含“百度面”。所以“百度”就是我們分出來(lái)的第一個(gè)詞。
和字典法相比，hash_map法可能會(huì)用到更多的存儲(chǔ)空間（因?yàn)橛行┳?，比如“百”字，都存?chǔ)了多次。但這還取決于字典樹(shù)的具體實(shí)現(xiàn)），但程序設(shè)計(jì)會(huì)更加簡(jiǎn)單，不容易出錯(cuò)。
session和cache的區(qū)別是什么？ session是針對(duì)單個(gè)連接（會(huì)話）來(lái)使用的，主要存儲(chǔ)和連接相關(guān)的上下文信息，比如登錄信息等等。 cache是應(yīng)用程序級(jí)的，主要用來(lái)緩存計(jì)算結(jié)果，減輕服務(wù)器負(fù)擔(dān)，并加快響應(yīng)速度。
百度面試題：找出數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù) 答案： 創(chuàng)建一個(gè)hash_map，key為數(shù)組中的數(shù)，value為此數(shù)出現(xiàn)的次數(shù)。遍歷一遍數(shù)組，用hash_map統(tǒng)計(jì)每個(gè)數(shù)出現(xiàn)的次數(shù)，并用兩個(gè)值存儲(chǔ)目前出現(xiàn)次數(shù)最多的數(shù)和對(duì)應(yīng)出現(xiàn)的次數(shù)。 這樣可以做到O(n)的時(shí)間復(fù)雜度和O(n)的空間復(fù)雜度，滿足題目的要求。 但是沒(méi)有利用“一個(gè)數(shù)出現(xiàn)的次數(shù)超過(guò)了一半”這個(gè)特點(diǎn)。也許算法還有提高的空間。 答案2： 使用兩個(gè)變量A和B，其中A存儲(chǔ)某個(gè)數(shù)組中的數(shù)，B用來(lái)計(jì)數(shù)。開(kāi)始時(shí)將B初始化為0。 遍歷數(shù)組，如果B=0，則令A(yù)等于當(dāng)前數(shù)，令B等于1；如果當(dāng)前數(shù)與A相同，則B=B+1；如果當(dāng)前數(shù)與A不同，則令B=B-1。遍歷結(jié)束時(shí)，A中的數(shù)就是要找的數(shù)。 這個(gè)算法的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度為O(1)。
百度面試題：如何找出字典中的兄弟單詞 給定一個(gè)單詞a，如果通過(guò)交換單詞中字母的順序可以得到另外的單詞b，那么定義b是a的兄弟單詞。現(xiàn)在給定一個(gè)字典，用戶輸入一個(gè)單詞，如何根據(jù)字典找出這個(gè)單詞有多少個(gè)兄弟單詞？ 答案： 使用hash_map和鏈表。 首先定義一個(gè)key，使得兄弟單詞有相同的key，不是兄弟的單詞有不同的key。例如，將單詞按字母從小到大重新排序后作為其key，比如bad的key為abd，good的key為dgoo。 使用鏈表將所有兄弟單詞串在一起，hash_map的key為單詞的key，value為鏈表的起始地址。 開(kāi)始時(shí)，先遍歷字典，將每個(gè)單詞都按照key加入到對(duì)應(yīng)的鏈表當(dāng)中。當(dāng)需要找兄弟單詞時(shí)，只需求取這個(gè)單詞的key，然后到hash_map中找到對(duì)應(yīng)的鏈表即可。 這樣創(chuàng)建hash_map時(shí)時(shí)間復(fù)雜度為O(n)，查找兄弟單詞時(shí)時(shí)間復(fù)雜度是O(1)。
網(wǎng)易面試題：new/delete和malloc/free的區(qū)別 new/delete：給定數(shù)據(jù)類(lèi)型，new/delete會(huì)自動(dòng)計(jì)算內(nèi)存大小，并進(jìn)行分配或釋放。如果是對(duì)類(lèi)進(jìn)行操作，new/delete還會(huì)自動(dòng)調(diào)用相應(yīng)的構(gòu)造函數(shù)和析構(gòu)函數(shù)。 malloc/free：沒(méi)有進(jìn)行任何數(shù)據(jù)類(lèi)型檢查，只負(fù)責(zé)分配和釋放給定大小的內(nèi)存空間。 有些情況下，new/delete和malloc/free都不能滿足性能的要求，我們需要自建內(nèi)存分配來(lái)提高效率。比如，如果程序需要?jiǎng)討B(tài)分配大量很小的對(duì)象，我們可以一次分配可以容納很多小對(duì)象的內(nèi)存，將這些小對(duì)象維護(hù)在鏈表中，當(dāng)程序需要時(shí)直接從鏈表中返回一個(gè)。還有一點(diǎn)，new返回指定類(lèi)型的指針；而malloc返回void*，必須強(qiáng)制類(lèi)型轉(zhuǎn)化。 有個(gè)比較有意思的地方是:int *p=(void*)malloc(1);可以編譯并運(yùn)行。
網(wǎng)易面試題：沒(méi)有拷貝構(gòu)造函數(shù)和重載＝運(yùn)算符的string類(lèi) c++中，一個(gè)沒(méi)有拷貝構(gòu)造函數(shù)和重載＝運(yùn)算符的string類(lèi)，會(huì)出現(xiàn)什么問(wèn)題，如何解決？ 如果沒(méi)有定義拷貝構(gòu)造函數(shù)和重載=運(yùn)算符，則系統(tǒng)會(huì)自動(dòng)生成逐位拷貝的函數(shù)。 當(dāng)我們用string初始化string時(shí)，（比如 string a("abc"); string b = a;），兩個(gè)對(duì)象會(huì)指向同樣的內(nèi)存地址。在兩個(gè)對(duì)象的析構(gòu)函數(shù)中，我們會(huì)對(duì)同一個(gè)內(nèi)存塊調(diào)用兩次刪除，導(dǎo)致不確定的結(jié)果。 當(dāng)我們將一個(gè)string賦值給另外一個(gè)string時(shí)，（比如 string a("abc"); string b(“cde"); b = a;）除了上面的多次調(diào)用析構(gòu)函數(shù)的問(wèn)題外，由于原來(lái)對(duì)象b指向的數(shù)據(jù)沒(méi)有被正確刪除，會(huì)導(dǎo)致內(nèi)存泄漏。
解決辦法： 1. 添加這兩個(gè)函數(shù)。 2. 不使用這兩個(gè)函數(shù)。 - 不用string初始化string：可以使用string a（”abc"); string b(a.c_str()); 代替。 - 不用string給string賦值，包括不能通過(guò)傳值方法傳遞string參數(shù)：盡量使用指針。
網(wǎng)易面試題：寫(xiě)一段程序，實(shí)現(xiàn)atoi(const char* s)方法 atoi用于將字符串轉(zhuǎn)換成為整數(shù)。 比如 “123” =》 123， “-246” =》 -246。
` int atoi(const char*s) { ` int result = 0; ` bool is_plus = true; ` if (*s == '+') { ` ++s; ` } else if (*s == '-') { ` ++s; ` is_plus = false; ` } ` while (*s >= '0' && *s <= '9') { ` result = result * 10 + *s - '0'; ` ++s; ` } ` if (is_plus) { ` return result; ` } else { ` return -result; ` } ` }
網(wǎng)易面試題：給出若干個(gè)單詞，組成字典，要求查找速度最快。 為使查找速度最快，可以要使用hash_map。 如果每個(gè)單詞還有對(duì)應(yīng)的解釋和例句，可以將解釋和例句對(duì)應(yīng)的指針存放在hash_map的值中?；蛟S可以嘗試使用 TRIE 結(jié)構(gòu)。
迅雷面試題：門(mén)面模式的解釋、適用場(chǎng)合？ 門(mén)面模式又被稱(chēng)為外觀模式，為子系統(tǒng)中的一組接口提供一個(gè)一致的界面，該模式定義了一個(gè)高層接口，使得這個(gè)子系統(tǒng)更加容易使用。 舉個(gè)例子：在做項(xiàng)目或產(chǎn)品的過(guò)程中進(jìn)行跨部門(mén)合作的時(shí)候，每個(gè)部門(mén)都有個(gè)相應(yīng)的接口人，那么我們只需和對(duì)應(yīng)部門(mén)的接口人交互即可。
適用場(chǎng)合： 為一個(gè)復(fù)雜子系統(tǒng)提供一個(gè)簡(jiǎn)單接口：子系統(tǒng)往往因?yàn)椴粩嘌莼兊迷絹?lái)越復(fù)雜，使用門(mén)面模式可以使得子系統(tǒng)更具有可復(fù)用性。 子系統(tǒng)的獨(dú)立性：引入門(mén)面模式將一個(gè)子系統(tǒng)與它的客戶端以及其他子系統(tǒng)分離，可以提高子系統(tǒng)的獨(dú)立性和可移植性。 層次化結(jié)構(gòu)：在構(gòu)建一個(gè)層次化的系統(tǒng)時(shí)，可以使用 門(mén)面模式定義系統(tǒng)中每一層的入口。如果層與層之間是相互依賴的，則可以限定它們僅通過(guò)門(mén)面進(jìn)行通信，簡(jiǎn)化層與層之間的依賴關(guān)系。
迅雷面試題：AJAX的原理、如何實(shí)現(xiàn)刷新及其優(yōu)點(diǎn) AJAX即“Asynchronous JavaScript and XML”（異步JavaScript和XML)，是指一種創(chuàng)建交互式網(wǎng)頁(yè)應(yīng)用的網(wǎng)頁(yè)開(kāi)發(fā)技術(shù)。
使用了AJAX技術(shù)的網(wǎng)頁(yè)，利用Javascript和服務(wù)器通信，獲取數(shù)據(jù)，然后再通過(guò)修改網(wǎng)頁(yè)的DOM中的某些元素來(lái)實(shí)現(xiàn)刷新網(wǎng)頁(yè)的特定部分。
使用了AJAX技術(shù)后，由于只需要更新網(wǎng)頁(yè)的一部分，而不是全部，所以和服務(wù)器交互的數(shù)據(jù)比較少。這就降低了服務(wù)器的負(fù)載，并提高了用戶端的響應(yīng)速度。另外，AJAX并不需要在瀏覽器中安裝插件。
迅雷面試題：數(shù)組與鏈表的區(qū)別？ 在數(shù)組中，元素在內(nèi)存中連續(xù)存放。對(duì)于訪問(wèn)操作，由于元素類(lèi)型相同，占用內(nèi)存相同，所以可以通過(guò)數(shù)組的下標(biāo)計(jì)算出元素所在的內(nèi)存地址，便于快速訪問(wèn)。但對(duì)于插入或刪除操作，需要移動(dòng)大量元素，所以速度比較慢。 在鏈表中，元素在內(nèi)存中沒(méi)有連續(xù)存放，而是通過(guò)元素中的指針將各個(gè)元素連接在一起。對(duì)于訪問(wèn)操作，需要從鏈表頭部開(kāi)始順序遍歷鏈表，直到找到需要的元素，所以速度比較慢。對(duì)于插入或刪除操作，只需修改元素中的指針即可完成，速度比較快。 所以，如果需要頻繁訪問(wèn)數(shù)據(jù)，很少插入刪除操作，則使用數(shù)組；反之，如果頻繁插入刪除，則應(yīng)使用鏈表。
迅雷面試題：最快的排序法的性能，并列舉至少三個(gè) 最快的排序算法是O(N*lgN)。，快排序，堆排序，歸并排序
迅雷面試題：合并用戶基本信息和看電影的記錄 如何有效合并兩個(gè)文件：一個(gè)是1億條的用戶基本信息，另一個(gè)是用戶每天看電影連續(xù)劇等的記錄，5000萬(wàn)條。其中內(nèi)存只有1G。 顯然內(nèi)存不能同時(shí)存下所有的數(shù)據(jù)，所以考慮分而治之的思想。 假設(shè)1K Byte可以保存一個(gè)用戶的基本信息和看電影記錄。我們可以將基本信息和看電影記錄都按照hash(user_name)%100的余數(shù)各分成100個(gè)小文件。利用1G內(nèi)存，我們可以每次只處理一對(duì)小文件，然后將結(jié)果輸出到一個(gè)文件中即可。 在處理一對(duì)小文件時(shí)，可以利用key為用戶名的hash_map將基本信息和看電影記錄合并在一起。
迅雷面試題：c語(yǔ)言中不同include方法的差別 #include "filename.h" 首先在程序原文件所在目錄下查找，如果找不到，再到系統(tǒng)目錄中查找。 #include <filename.h> 直接去系統(tǒng)目錄中查找。
在1億條用戶記錄里，如何快速查詢統(tǒng)計(jì)出看了5個(gè)電影以上的用戶？ 構(gòu)建一個(gè)hash map，key為用戶名，value為已經(jīng)看過(guò)的電影數(shù)量。 遍歷所有用戶記錄，然后根據(jù)用戶名和已經(jīng)看過(guò)電影數(shù)量的情況進(jìn)行處理： - 如果用戶名不在hash map中，則添加對(duì)應(yīng)用戶名，并將值設(shè)為1。 - 如果用戶名對(duì)應(yīng)的值小于5，則將值加1。如果加1后值為5，則輸出此用戶名。 - 如果用戶名對(duì)應(yīng)的值等于5，則不進(jìn)行任何操作。
oracle面試題：數(shù)據(jù)庫(kù)冷備份和熱備份的不同點(diǎn)以及各自的優(yōu)點(diǎn) 熱備份針對(duì)歸檔模式的數(shù)據(jù)庫(kù)，在數(shù)據(jù)庫(kù)仍舊處于工作狀態(tài)時(shí)進(jìn)行備份。而冷備份指在數(shù)據(jù)庫(kù)關(guān)閉后，進(jìn)行備份，適用于所有模式的數(shù)據(jù)庫(kù)。熱備份的優(yōu)點(diǎn)在于當(dāng)備 份時(shí)，數(shù)據(jù)庫(kù)仍舊可以被使用并且可以將數(shù)據(jù)庫(kù)恢復(fù)到任意一個(gè)時(shí)間點(diǎn)。冷備份的優(yōu)點(diǎn)在于它的備份和恢復(fù)操作相當(dāng)簡(jiǎn)單，并且由于冷備份的數(shù)據(jù)庫(kù)可以工作在非歸 檔模式下，數(shù)據(jù)庫(kù)性能會(huì)比歸檔模式稍好。（因?yàn)椴槐貙rchive log寫(xiě)入硬盤(pán)）
華為面試題：IP，TCP和UDP協(xié)議的定義和主要作用 IP協(xié)議是網(wǎng)絡(luò)層的協(xié)議。IP協(xié)議規(guī)定每個(gè)互聯(lián)網(wǎng)網(wǎng)上的電腦都有一個(gè)唯一的IP地址，這樣數(shù)據(jù)包就可以通過(guò)路由器的轉(zhuǎn)發(fā)到達(dá)指定的電腦。但I(xiàn)P協(xié)議并不保證數(shù)據(jù)傳輸?shù)目煽啃浴?/p> TCP協(xié)議是傳輸層的協(xié)議。它向下屏蔽了IP協(xié)議不能可靠傳輸?shù)娜秉c(diǎn)，向上提供面向連接的可靠的數(shù)據(jù)傳輸。 UDP協(xié)議也是傳輸層的協(xié)議。它提供無(wú)連接的不可靠傳輸。
華為面試題：全局變量和局部變量有什么區(qū)別 全局變量是整個(gè)程序都可訪問(wèn)的變量，生存期從程序開(kāi)始到程序結(jié)束；局部變量存在于模塊中(比如某個(gè)函數(shù))，只有在模塊中才可以訪問(wèn)，生存期從模塊開(kāi)始到模塊結(jié)束。 全局變量分配在全局?jǐn)?shù)據(jù)段，在程序開(kāi)始運(yùn)行的時(shí)候被加載。局部變量則分配在程序的堆棧中。因此，操作系統(tǒng)和編譯器可以通過(guò)內(nèi)存分配的位置來(lái)知道來(lái)區(qū)分全局變量和局部變量。全局變量和局部變量的區(qū)別是在存儲(chǔ)器中位置不同，具體說(shuō)，全局變量存儲(chǔ)在數(shù)據(jù)段中，局部變量一般來(lái)說(shuō)在堆棧段
華為面試題：析構(gòu)函數(shù)和虛函數(shù)的用法和作用？ 析構(gòu)函數(shù)是在類(lèi)對(duì)象消亡時(shí)由系統(tǒng)自動(dòng)調(diào)用。主要用來(lái)做對(duì)象的清理工作，比如來(lái)釋放對(duì)象申請(qǐng)的動(dòng)態(tài)空間。 基類(lèi)中用virtual修飾的函數(shù)稱(chēng)為虛函數(shù)。在派生類(lèi)中可以對(duì)虛函數(shù)進(jìn)行重新定義，這樣同樣的函數(shù)接口可以在不同的派生類(lèi)中對(duì)應(yīng)不同的實(shí)現(xiàn)。當(dāng)通過(guò)基類(lèi)的指針來(lái)調(diào)用虛函數(shù)時(shí)，程序會(huì)根據(jù)指針實(shí)際指向的對(duì)象來(lái)決定調(diào)用哪個(gè)實(shí)現(xiàn)。
華為面試題：如何引用一個(gè)已經(jīng)定義過(guò)的全局變量？ 可以用引用頭文件的方式，也可以使用extern關(guān)鍵字。 用引用頭文件方式，如果將那個(gè)變量寫(xiě)錯(cuò)了，那么在編譯期間會(huì)報(bào)錯(cuò)。 用extern方式，如果將變量名寫(xiě)錯(cuò)了，那么在編譯期間不會(huì)報(bào)錯(cuò)，而在連接期間報(bào)錯(cuò)。
華為面試題：c語(yǔ)言中局部變量能否和全局變量重名？ 局部變量可以與全局變量同名。在函數(shù)內(nèi)引用這個(gè)變量時(shí)，會(huì)用到同名的局部變量，而不會(huì)用到全局變量。要用全局變量，需要使用"::"。 對(duì)于有些編譯器而言，在同一個(gè)函數(shù)內(nèi)可以定義多個(gè)同名的局部變量，比如在兩個(gè)循環(huán)體內(nèi)都定義一個(gè)同名的局部變量，而那個(gè)局部變量的作用域就在那個(gè)循環(huán)體內(nèi)。
完美時(shí)空面試題：memcpy 和 memmove 有什么區(qū)別？ memcpy和memmove都是將源地址的若干個(gè)字符拷貝到目標(biāo)地址。 如果源地址和目標(biāo)地址有重疊，則memcpy不能保證拷貝正確，但memmove可以保證拷貝正確。
例如： char src[20]; // set src char* dst = src + 5; 此時(shí)如果要從src拷貝10個(gè)字符到dst，則么memcpy不能保證拷貝正確，但是memmove可以保證。
雅虎面試題：HTTP中Get和Post的區(qū)別 Get和Post都是瀏覽器向網(wǎng)頁(yè)服務(wù)器提交數(shù)據(jù)的方法。 Get把要提交的數(shù)據(jù)編碼在url中，比如 http://hi.baidu.com/mianshiti?key1=value1&key2=value2 中就編碼了鍵值對(duì) key1，value1 和key2，value2。受限于url的長(zhǎng)度限制，Get方法能傳輸?shù)臄?shù)據(jù)有限（不同瀏覽器對(duì)url長(zhǎng)度限制不同，比如微軟IE設(shè)為2048）。 Post把要提交的數(shù)據(jù)放在請(qǐng)求的body中，而不會(huì)顯示在url中，因此，也沒(méi)有數(shù)據(jù)大小的限制。
由于Get把數(shù)據(jù)編碼在URL中，所以這些變量顯示在瀏覽器的地址欄，也會(huì)被記錄在服務(wù)器端的日志中。所以Post方法更加安全。 |
|
|
