轉載請標明出處，原文地址：[http://blog.csdn.net/hackbuteer1/article/details/7348968](http://blog.csdn.net/hackbuteer1/article/details/7348968) 1、實現一個函數，對一個正整數n，算得到1需要的最少操作次數。操作規則為：如果n為偶數，將其除以2；如果n為奇數，可以加1或減1；一直處理下去。 例子： func(7) = 4，可以證明最少需要4次運算 n = 7 n-1 6 n/2 3 n-1 2 n/2 1 要求：實現函數(實現盡可能高效) int func(unsign int n)；n為輸入，返回最小的運算次數。給出思路(文字描述)，完成代碼，并分析你算法的時間復雜度。 答： ~~~ int func(unsigned 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; } ~~~ 假設n表示成二進制有x bit，可以看出計算復雜度為O(2^x)，也就是O(n)。 將n轉換到二進制空間來看（比如7為111，6為110）： - 如果最后一位是0，則對應于偶數，直接進行除2操作。 - 如果最后一位是1，情況則有些復雜。 **如果最后幾位是???01，則有可能為???001，???1111101。在第一種情況下，顯然應該-1；在第二種情況下-1和+1最終需要的步數相同。所以在???01的情況下，應該選擇-1操作。 **如果最后幾位是???011，則有可能為???0011，???11111011。在第一種情況下，+1和-1最終需要的步數相同；在第二種情況下+1步數更少些。所以在???011的情況下，應該選擇+1操作。 **如果最后有更多的連續1，也應該選擇+1操作。 如果最后剩下的各位都是1，則有11時應該選擇-1；111時+1和-1相同；1111時應選擇+1；大于四個1時也應該選擇+1； ~~~ int func(unsigned 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); } ~~~ 由以上的分析可知，奇數的時候加1或減1，完全取決于二進制的后兩位，如果后兩位是10、00那么肯定是偶數，選擇除以2，如果后兩位是01、11，那么選擇結果會不一樣的，如果是***01，那么選擇減1，如果是***11，那么選擇加1，特殊情況是就是n是3的時候，選擇減1操作。 非遞歸代碼如下： ~~~ // 非遞歸寫法 int func(int n) { int count = 0; while(n > 1) { if(n % 2 == 0) n >>= 1; else if(n == 3) n--; else { if(n&2) // 二進制是****11時 n++; else // 二進制是****01時 n--; } count++; } return count; } ~~~ 另外一種寫法如下： ~~~ // 非遞歸寫法 int func(int n) { int count = 0; while(n > 1) { if(n % 2 == 0) // n % 4等于0或2 n >>= 1; else if(n == 3) n--; else n += (n % 4 - 2); // n % 4等于1或3 count++; } return count; } ~~~ 2、找到滿足條件的數組 給定函數d(n)=n+n的各位之和，n為正整數，如d(78)=78+7+8=93。這樣這個函數可以看成一個生成器，如93可以看成由78生成。 定義數A：數A找不到一個數B可以由d(B)=A，即A不能由其他數生成。現在要寫程序，找出1至10000里的所有符合數A定義的數。 回答： 申請一個長度為10000的bool數組，每個元素代表對應的值是否可以有其它數生成。開始時將數組中的值都初始化為false。 由于大于10000的數的生成數必定大于10000，所以我們只需遍歷1到10000中的數，計算生成數，并將bool數組中對應的值設置為true，表示這個數可以有其它數生成。 最后bool數組中值為false的位置對應的整數就是不能由其它數生成的。 3、一個大的含有50M個URL的記錄，一個小的含有500個URL的記錄，找出兩個記錄里相同的URL。 回答： 首先使用包含500個url的文件創建一個hash_set。 然后遍歷50M的url記錄，如果url在hash_set中，則輸出此url并從hash_set中刪除這個url。 所有輸出的url就是兩個記錄里相同的url。 4、海量日志數據，提取出某日訪問百度次數最多的那個IP。 回答： 如果日志文件足夠的大，大到不能完全加載到內存中的話。 那么可以考慮分而治之的策略，按照IP地址的hash(IP)%1024值，將海量日志存儲到1024個小文件中。每個小文件最多包含4M個IP地址。 對于每個小文件，可以構建一個IP作為key，出現次數作為value的hash_map，并記錄當前出現次數最多的1個IP地址。 有了1024個小文件中的出現次數最多的IP，我們就可以輕松得到總體上出現次數最多的IP。 5、有10個文件，每個文件1G，每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。如何按照query的頻度排序？ 回答： 　1）讀取10個文件，按照hash(query)%10的結果將query寫到對應的文件中。這樣我們就有了10個大小約為1G的文件。任意一個query只會出現在某個文件中。 　2）對于1）中獲得的10個文件，分別進行如下操作 　　-利用hash_map（query，query_count）來統計每個query出現的次數。 　　-利用堆排序算法對query按照出現次數進行排序。 　　-將排序好的query輸出的文件中。 　　這樣我們就獲得了10個文件，每個文件中都是按頻率排序好的query。 　3）對2）中獲得的10個文件進行歸并排序，并將最終結果輸出到文件中。 6、螞蟻爬桿問題 　有一根27厘米長的細木桿，在第3厘米，7厘米，11厘米，17厘米，23厘米這五個位置上各有一只螞蟻，木桿很細，不能同時通過兩只螞蟻，開始時，螞蟻的頭朝向左還是右是任意的，他們只會朝前走或掉頭，但不會后退，當兩只螞蟻相遇后，螞蟻會同時掉頭朝反方向走，假設螞蟻們每秒鐘可以走1厘米的距離。求所有螞蟻都離開木桿的最小時間和最大時間。 　答案： 　兩只螞蟻相遇后，各自掉頭朝相反方向走。如果我們不考慮每個螞蟻的具體身份，這和兩只螞蟻相遇后，打個招呼繼續向前走沒有什么區別。 　所有螞蟻都離開木桿的最小時間為 　max(min(3,27-3),min(7,27-7), min(11,27-11), min(17,27-17),min(23,27-23))=11 　所有螞蟻都離開木桿的最大時間為 　max(max(3,27-3),max(7,27-7), max(11,27-11), max(17,27-17),max(23,27-23))=24 7、當在瀏覽器中輸入一個url后回車，后臺發生了什么？比如輸入url后，你看到了百度的首頁，那么這一切是如何發生的呢？ 回答： 　　簡單來說有以下步驟： 　　1、查找域名對應的IP地址。這一步會依次查找瀏覽器緩存，系統緩存，路由器緩存，ISPDNS緩存，根域名服務器。 　　2、向IP對應的服務器發送請求。 　　3、服務器響應請求，發回網頁內容。 　　4、瀏覽器解析網頁內容。 當然，由于網頁可能有重定向，或者嵌入了圖片，AJAX，其它子網頁等等，這4個步驟可能反復進行多次才能將最終頁面展示給用戶。 8、判斷兩棵樹是否相等，請實現兩棵樹是否相等的比較，相等返回1，否則返回其他值，并說明算法復雜度。 數據結構為： ~~~ typedef struct TreeNode { char c; TreeNode *leftchild; TreeNode *rightchild; }TreeNode; ~~~ 函數接口為：int CompTree(TreeNode* tree1,TreeNode* tree2); 注：A、B兩棵樹相等當且僅當RootA->c==RootB-->c,而且A和B的左右子樹相等或者左右互換相等。 遞歸方法： ~~~ bool CompTree(TreeNode *tree1, TreeNode *tree2) { if(tree1 == NULL && tree2 == NULL) return true; if(tree1 == NULL || tree2 == NULL) return false; if(tree1->c != tree2->c) return false; if( (CompTree(tree1->leftchild, tree2->leftchild) && CompTree(tree1->rightchild, tree2->rightchild)) || CompTree(tree1->leftchild, tree2->rightchild) && CompTree(tree1->rightchild, tree2->leftchild)) return true; } ~~~ 時間復雜度： 在樹的第0層，有1個節點，我們會進行1次函數調用； 在樹的第1層，有2個節點，我們可能會進行4次函數調用； 在樹的第2層，有4個節點，我們可能會進行16次函數調用； .... 在樹的第x層，有2^x個節點，我們可能會進行(2^x)^2次函數調用； 所以假設總節點數為n，則算法的復雜度為O(n^2)。 **騰訊面試題：求一個論壇的在線人數，假設有一個論壇，其注冊ID有兩億個，每個ID從登陸到退出會向一個日志文件中記下登陸時間和退出時間，要求寫一個算法統計一天中論壇的用戶在線分布，取樣粒度為秒。** 回答： 　　一天總共有3600*24=86400秒。 　　定義一個長度為86400的整數數組intdelta[86400]，每個整數對應這一秒的人數變化值，可能為正也可能為負。開始時將數組元素都初始化為0。 　　然后依次讀入每個用戶的登錄時間和退出時間，將與登錄時間對應的整數值加1，將與退出時間對應的整數值減1。 　　這樣處理一遍后數組中存儲了每秒中的人數變化情況。 　　定義另外一個長度為86400的整數數組intonline_num[86400]，每個整數對應這一秒的論壇在線人數。 　　假設一天開始時論壇在線人數為0，則第1秒的人數online_num[0]=delta[0]。第n+1秒的人數online_num[n]=online_num[n-1]+delta[n]。 　　這樣我們就獲得了一天中任意時間的在線人數。 9、三個警察和三個囚徒的過河問題 　　三個警察和三個囚徒共同旅行。一條河擋住了去路，河邊有一條船，但是每次只能載2人。存在如下的危險：無論在河的哪邊，當囚徒人數多于警察的人數時，將有警察被囚徒殺死。問題：請問如何確定渡河方案，才能保證6人安全無損的過河。 答案：第一次：兩囚徒同過，回一囚徒 第二次：兩囚徒同過，回一囚徒 第三次：兩警察同過，回一囚徒一警察（此時對岸還剩下一囚徒一警察，是安全狀態） 第四次：兩警察同過，回一囚徒（此時對岸有3個警察，是安全狀態） 第五次：兩囚徒同過，回一囚徒 第六次：兩囚徒同過；over 10、從300萬字符串中找到最熱門的10條 搜索的輸入信息是一個字符串，統計300萬輸入信息中的最熱門的前10條，我們每次輸入的一個字符串為不超過255byte，內存使用只有1G。請描述思想，寫出算法（c語言），空間和時間復雜度。 答案： 　　300萬個字符串最多（假設沒有重復，都是最大長度）占用內存3M*1K/4=0.75G。所以可以將所有字符串都存放在內存中進行處理。 　　可以使用key為字符串（事實上是字符串的hash值），值為字符串出現次數的hash來統計每個每個字符串出現的次數。并用一個長度為10的數組/鏈表來存儲目前出現次數最多的10個字符串。 　　這樣空間和時間的復雜度都是O(n)。 11、如何找出字典中的兄弟單詞。給定一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么定義b是a的兄弟單詞。現在給定一個字典，用戶輸入一個單詞，如何根據字典找出這個單詞有多少個兄弟單詞？ 答案： 　　使用hash_map和鏈表。 　　首先定義一個key，使得兄弟單詞有相同的key，不是兄弟的單詞有不同的key。例如，將單詞按字母從小到大重新排序后作為其key，比如bad的key為abd，good的key為dgoo。 　　使用鏈表將所有兄弟單詞串在一起，hash_map的key為單詞的key，value為鏈表的起始地址。 　　開始時，先遍歷字典，將每個單詞都按照key加入到對應的鏈表當中。當需要找兄弟單詞時，只需求取這個單詞的key，然后到hash_map中找到對應的鏈表即可。 　　這樣創建hash_map時時間復雜度為O(n)，查找兄弟單詞時時間復雜度是O(1)。 12、找出數組中出現次數超過一半的數，現在有一個數組，已知一個數出現的次數超過了一半，請用O(n)的復雜度的算法找出這個數。 答案1： 　　創建一個hash_map，key為數組中的數，value為此數出現的次數。遍歷一遍數組，用hash_map統計每個數出現的次數，并用兩個值存儲目前出現次數最多的數和對應出現的次數。 　　這樣可以做到O(n)的時間復雜度和O(n)的空間復雜度，滿足題目的要求。 　　但是沒有利用“一個數出現的次數超過了一半”這個特點。也許算法還有提高的空間。 答案2： 　　使用兩個變量A和B，其中A存儲某個數組中的數，B用來計數。開始時將B初始化為0。 　　遍歷數組，如果B=0，則令A等于當前數，令B等于1；如果當前數與A相同，則B=B+1；如果當前數與A不同，則令B=B-1。遍歷結束時，A中的數就是要找的數。 　　這個算法的時間復雜度是O(n)，空間復雜度為O(1)。 13、找出被修改過的數字 ???? n個空間（其中n<1M），存放a到a+n-1的數，位置隨機且數字不重復，a為正且未知。現在第一個空間的數被誤設置為-1。已經知道被修改的數不是最小的。請找出被修改的數字是多少。 　　例如：n=6，a=2，原始的串為5,3,7,6,2,4。現在被別人修改為-1,3,7,6,2,4。現在希望找到5。 回答： 　　由于修改的數不是最小的，所以遍歷第二個空間到最后一個空間可以得到a的值。 　　a到a+n-1這n個數的和是total=na+(n-1)n/2。 　　將第二個至最后一個空間的數累加獲得sub_total。 　　那么被修改的數就是total-sub_total。 14、設計DNS服務器中cache的數據結構。 　　要求設計一個DNS的Cache結構，要求能夠滿足每秒5000以上的查詢，滿足IP數據的快速插入，查詢的速度要快。（題目還給出了一系列的數據，比如：站點數總共為5000萬，IP地址有1000萬，等等） 回答： 　　DNS服務器實現域名到IP地址的轉換。 　　每個域名的平均長度為25個字節（估計值），每個IP為4個字節，所以Cache的每個條目需要大概30個字節。 　　總共50M個條目，所以需要1.5G個字節的空間。可以放置在內存中。（考慮到每秒5000次操作的限制，也只能放在內存中。） 　　可以考慮的數據結構包括hash_map，字典樹，紅黑樹等等。 15、找出給定字符串對應的序號。 　　序列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； 16、找出第k大的數字所在的位置。寫一段程序，找出數組中第k大小的數，輸出數所在的位置。例如{2，4，3，4，7}中，第一大的數是7，位置在4。第二大、第三大的數都是4，位置在1、3隨便輸出哪一個均可。 答案： 先找到第k大的數字，然后再遍歷一遍數組找到它的位置。所以題目的難點在于如何最高效的找到第k大的數。 　我們可以通過快速排序，堆排序等高效的排序算法對數組進行排序，然后找到第k大的數字。這樣總體復雜度為O(NlogN)。 　我們還可以通過二分的思想，找到第k大的數字，而不必對整個數組排序。從數組中隨機選一個數t，通過讓這個數和其它數比較，我們可以將整個數組分成了兩部分并且滿足，{x,xx,...,t}<{y,yy,...}。 　在將數組分成兩個數組的過程中，我們還可以記錄每個子數組的大小。這樣我們就可以確定第k大的數字在哪個子數組中。 　然后我們繼續對包含第k大數字的子數組進行同樣的劃分，直到找到第k大的數字為止。 　平均來說，由于每次劃分都會使子數組縮小到原來1/2，所以整個過程的復雜度為O(N)。 17、給40億個不重復的unsigned int的整數，沒排過序的，然后再給幾個數，如何快速判斷這幾個數是否在那40億個數當中? 答案： 　　unsigned int的取值范圍是0到2^32-1。我們可以申請連續的2^32/8=512M的內存，用每一個bit對應一個unsigned int數字。首先將512M內存都初始化為0，然后每處理一個數字就將其對應的bit設置為1。當需要查詢時，直接找到對應bit，看其值是0還是1即可。 18、在一個文件中有10G個整數，亂序排列，要求找出中位數。內存限制為2G。 回答： 　　不妨假設10G個整數是64bit的。 　　2G內存可以存放256M個64bit整數。 　　我們可以將64bit的整數空間平均分成256M個取值范圍，用2G的內存對每個取值范圍內出現整數個數進行統計。這樣遍歷一邊10G整數后，我們便知道中數在那個范圍內出現，以及這個范圍內總共出現了多少個整數。 　　如果中數所在范圍出現的整數比較少，我們就可以對這個范圍內的整數進行排序，找到中數。如果這個范圍內出現的整數比較多，我們還可以采用同樣的方法將此范圍再次分成多個更小的范圍（256M=2^28，所以最多需要3次就可以將此范圍縮小到1，也就找到了中數）。 19、時分秒針在一天之類重合多少次？（24小時） 2次? 而時針和分針重合了22次。 20、將多個集合合并成沒有交集的集合。 　　給定一個字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}要求將其中交集不為空的集合合并，要求合并完成后的集合之間無交集，例如上例應輸出{aaabbbcccdddhhh}，{eeefff}，{ggg}。 　　（1）請描述你解決這個問題的思路； 　　（2）請給出主要的處理流程，算法，以及算法的復雜度 　　（3）請描述可能的改進。 回答： 　　集合使用hash_set來表示，這樣合并時間復雜度比較低。 　　1、給每個集合編號為0，1，2，3... 　　2、創建一個hash_map，key為字符串，value為一個鏈表，鏈表節點為字符串所在集合的編號。遍歷所有的集合，將字符串和對應的集合編號插入到hash_map中去。 　　3、創建一個長度等于集合個數的int數組，表示集合間的合并關系。例如，下標為5的元素值為3，表示將下標為5的集合合并到下標為3的集合中去。開始時將所有值都初始化為-1，表示集合間沒有互相合并。在集合合并的過程中，我們將所有的字符串都合并到編號較小的集合中去。 　? 遍歷第二步中生成的hash_map，對于每個value中的鏈表，首先找到最小的集合編號（有些集合已經被合并過，需要順著合并關系數組找到合并后的集合編號），然后將鏈表中所有編號的集合都合并到編號最小的集合中（通過更改合并關系數組）。 　　4、現在合并關系數組中值為-1的集合即為最終的集合，它的元素來源于所有直接或間接指向它的集合。 　　算法的復雜度為O(n)，其中n為所有集合中的元素個數。 　　題目中的例子： 　　0:{aaabbbccc} 　　1:{bbbddd} 　　2:{eeefff} 　　3:{ggg} 　　4:{dddhhh} 　　生成的hash_map，和處理完每個值后的合并關系數組分別為 　　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個集合合并到了一起， 　21、平面內有11個點，由它們連成48條不同的直，由這些點可連成多少個三角形？ 解析： 首先你要分析，平面中有11個點，如果這些點中任意三點都沒有共線的，那么一共應該有C(11，2)=55，? 可是，題目中說可以連接成48條直線，那么這11個點中必定有多點共線的情況。? 55-48=7，從7來分析： 假設有一組三個點共線，那么可以組成的直線在55的基礎上應該減去C(3，2)-1=2???? 2*3=6≠7，因此，可以斷定不僅有三點共線的，也可能有四個點共線的可能。 假設有一組四個點共線，那么可以組成的直線在55的基礎上應該減去C(4，2)-1=5 （備注，五個點共線的可能不存在，因為，C(5，2)-1=9>7，故不可能有五條直線共線。） 因此，三點共線少2條，4點共線少5條，只有一個4點共線，一個3點共線才能滿足條件，其余情況不能滿足少了7條直線。 那么，這11個點能組成的三角形的個數為，C(11，3)-C(3，3)-C(4，3)=165-1-4=160? （備注，三個點共線不能組成三角形） 轉載請標明出處，原文地址：[http://blog.csdn.net/hackbuteer1/article/details/7348968](http://blog.csdn.net/hackbuteer1/article/details/7348968)