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