經(jīng)典算法面試題及答案

1、經(jīng)典算法面試題及答案1 .時針分針重合幾次表面上有60個小格，每小格代表一分鐘，時針每分鐘走1/12 小格，分針每分鐘走1小格，從第一次重合到第二次重合分針比時針多走一圈即60小格，因此60/(1-1/12) =720/11每隔720/11分才重合一次(而并不是每小時重合一次)1440 里有22個720/11,如果說算上0點和24點，那也是重合 23次而已，但我覺得0點應(yīng)該算到前一天的24點頭上，因此每一天循環(huán)下來重合22次啊2 .找出字符串的最長不重復(fù)子用，輸出長度建一個256個單元的數(shù)組，每一個單元代表一個字符，數(shù)組中保存上次該字符上次出現(xiàn)的位置；依次讀入字符串，同時維護數(shù)組的值；如果遇到

2、沖突了，就返回沖突字符中保存的位置，繼續(xù)第二步。也能夠用hashmap 保存已經(jīng)出現(xiàn)的字符和字符的位置3 .說是有一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁出 現(xiàn)的前十個詞先用哈希，統(tǒng)計每個詞出現(xiàn)的次數(shù)，然后在用在N個數(shù)中找出前K大個數(shù)的方法找出出現(xiàn)次數(shù)最多的前10個詞。4 .如題3,可是車次文件特別大，沒有辦法一次讀入內(nèi)存。1)直接排序，寫文件時，同時寫入字符串及其出現(xiàn)次數(shù)。2)能夠用哈希，比如先根據(jù)字符串的第一個字符將字符串換分為多個區(qū)域，每個區(qū)域的字符串寫到一個文件內(nèi)，然后再用哈希+堆統(tǒng)計每個區(qū)域內(nèi)前10個頻率最高的字符串，最后求出所有字符串中前10個頻率最高的字符串。

3、5 .有一個整數(shù)n,將n分解成若干個整數(shù)之和，問如何分解能使這些數(shù)的乘積最大，輸出這個乘積 m o例如：n=12(1)分解為 1+1+1 + - +1, 12 個 1, m=1*1*1 *1=1(2)分解為2+2+2, 6個2, m=64(3)分解為 3+3+3+3, 4 個3, m=81(4)大于等于4時分解時只能分解為2和3 ,且2最多兩個f(n) = 3*f(n-3) n>4f=2*2f(3) = 3f=2分解為 4+4+4 , 3 個 4 , m=646.求數(shù)組n中出現(xiàn)次數(shù)超過一半的數(shù)把數(shù)組分成n/2 組，則至少有一組包含重復(fù)的數(shù)，因為如果無重復(fù)數(shù)，則最 多只有出現(xiàn)次數(shù)等于一半的

4、數(shù)。算法如下：k<-n;while k>3 do把數(shù)組分成k/2 組；for i=1 to k/2 doif組內(nèi)2個數(shù)相同，則任取一個數(shù)留下；else 2 個數(shù)同時扔掉；k<-剩下的數(shù)if k=3then 任取2個數(shù)進行比較；if兩個數(shù)不同，則2個數(shù)都扔掉else 任取一個數(shù)if k=2 or 1 then任取一數(shù)7 . A文件中最多有n個正整數(shù)，而且每個數(shù)均小于 n, n <=10的七次方不會出現(xiàn)重復(fù)的數(shù)。要求對A文件中的數(shù)進行排序，可用內(nèi)存為 1M ,磁盤可用空間足夠。不要把任何問題都往很復(fù)雜的算法上靠，最直接最簡單的解決問題才是工程師 應(yīng)有的素質(zhì),題目給的很有分寸

5、：n個數(shù)，都小于n ,兩兩不同，1M=10A6byte=10A7bit的內(nèi)存,n <10A7思路：把1M內(nèi)存看作是一個長度為10A7 的位數(shù)組，每一位都初始化為 0從頭掃描n個數(shù)，如果碰到i,就把位數(shù)組的第i個位置置為1 ,1M 內(nèi)存有點少，(1M = 8M bits),能夠代表8M 整數(shù)，現(xiàn)在n <=10的七次方，你能夠讀2遍文件，就能夠完成排序了。第一次排n <8M 得數(shù),第 2 遍排 8M<="" div="" style="word-wrap: break-word;">8 .有10億個雜亂無章的數(shù)，怎樣最快地求出其中前1000大的數(shù)。1) 建一個1000 個數(shù)的堆，復(fù)雜度為 N*(log1000)=10N2) 1.用每一個BIT標(biāo)識一個整數(shù)的存在與否，這樣一個字節(jié)能夠標(biāo)識8個整數(shù)的存在與否，對于所有32位的整數(shù)，需要512Mb ,因此開辟一個512Mb 的字符數(shù)組A ,初始全02 .依次讀取每個數(shù)n ,將An>>3 設(shè)置為An>>3|(1<<=""div="" style="word-wrap: bre