<pre id="ff7yo"></pre>

      <form id="ff7yo"><legend id="ff7yo"></legend></form>
        <nav id="ff7yo"><listing id="ff7yo"></listing></nav><nav id="ff7yo"></nav>

        <nav id="ff7yo"><listing id="ff7yo"></listing></nav>
        <small id="ff7yo"></small><nav id="ff7yo"><dd id="ff7yo"></dd></nav>
      1. <nav id="ff7yo"></nav>
          <form id="ff7yo"></form><nav id="ff7yo"></nav>
          <nav id="ff7yo"></nav>
          <sub id="ff7yo"></sub>
          更多課程 選擇中心

          軟件測試培訓
          達內IT學院

          400-111-8989

          軟件測試面試題(三):百度軟件測試工程師面試題大全

          • 發布:軟件測試培訓
          • 來源:網絡
          • 時間:2017-05-08 15:59

          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為輸入,返回最小的運算次數。給出思路(文字描述),完成代碼,并分析你算法的時間復雜度。

          答:

          [cpp] view plaincopyint 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;

          [cpp] view plaincopyint 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);

          }

          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地址最多有2^32=4G種取值可能,所以不能完全加載到內存中。

          可以考慮分而治之的策略,按照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,否則返回其他值,并說明算法復雜度。

          數據結構為:

          [cpp] view plaincopytypedef struct TreeNode

          {

          char c;

          TreeNode *leftchild;

          TreeNode *rightchild;

          }TreeNode;

          函數接口為:int CompTree(TreeNode* tree1,TreeNode* tree2);

          注:A、B兩棵樹相等當且僅當RootA->c==RootB-->c,而且A和B的左右子樹相等或者左右互換相等。

          遞歸方法:

          [cpp] view plaincopybool 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人安全無損的過河。

          回答:警察囚徒過去,警察回來

          囚徒囚徒過去,囚徒回來

          警察警察過去,警察囚徒回來

          警察警察過去,囚徒回來

          囚徒囚徒過去,囚徒回來

          囚徒囚徒過去

          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個集合合并到了一起.

          預約申請免費試聽課

          填寫下面表單即可預約申請免費試聽!怕錢不夠?可就業掙錢后再付學費! 怕學不會?助教全程陪讀,隨時解惑!擔心就業?一地學習,可全國推薦就業!

          上一篇:軟件測試面試題(二):阿里巴巴軟件測試最新面試題集錦
          下一篇:軟件測試需要學什么(一):軟件測試入門須知

          變革中的軟件測試——組織篇

          五種比較好Android自動化測試工具推薦

          • 掃碼領取資料

            回復關鍵字:視頻資料

            免費領取 達內課程視頻學習資料

          • 視頻學習QQ群

            添加QQ群:1143617948

            免費領取達內課程視頻學習資料

          Copyright ? 2021 Tedu.cn All Rights Reserved 京ICP備08000853號-56 京公網安備 11010802029508號 達內時代科技集團有限公司 版權所有

          選擇城市和中心
          黑龍江省

          吉林省

          河北省

          陜西省

          湖南省

          貴州省

          云南省

          廣西省

          海南省

          神马影院-战旗影院-首播影院-新视觉影院-在线观看中文字幕dvd播放 百度 好搜 搜狗
          <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>