一级毛片免费不卡在线视频,国产日批视频免费在线观看,菠萝菠萝蜜在线视频免费视频,欧美日韩亚洲无线码在线观看,久久精品这里精品,国产成人综合手机在线播放,色噜噜狠狠狠综合曰曰曰,琪琪视频

百度技術(shù)研發(fā)類筆試題(2)

時間:2024-08-31 05:45:07 學人智庫 我要投稿
  • 相關(guān)推薦

百度技術(shù)研發(fā)類筆試題(2)

  2編程:

百度技術(shù)研發(fā)類筆試題(2)

  用C語言實現(xiàn)函數(shù)void*memmove(void*dest,constvoid*src,size_tn)。memmove函數(shù)的功能是拷貝src所指的內(nèi)存內(nèi)容前n個字節(jié)到dest所指的地址上。

  3英文拼寫糾錯:

  在用戶輸入英文單詞時,經(jīng)常發(fā)生錯誤,我們需要對其進行糾錯。假設(shè)已經(jīng)有一個包含了正確英文單詞的詞典,請你設(shè)計一個拼寫糾錯的程序。

  (1)請描述你解決這個問題的思路;

  (2)請給出主要的處理流程,算法,以及算法的復雜度;

  (3)請描述可能的改進(改進的方向如效果,性能等等,這是一個開放問題)。

  4尋找熱門查詢:

  搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來,每個查詢串的長度為1-255字節(jié)。假設(shè)目前有一千萬個記錄,這些查詢串的重復度比較高,雖然總數(shù)是1千萬,但如果除去重復后,不超過3百萬個。一個查詢串的重復度越高,說明查詢它的用戶越多,也就是越熱門。請你統(tǒng)計最熱門的10個查詢串,要求使用的內(nèi)存不能超過1G。

  (1)請描述你解決這個問題的思路;

  (2)請給出主要的處理流程,算法,以及算法的復雜度。

  5集合合并:

  給定一個字符串的集合,格式如:

  {aaabbbccc},{bbbddd},{eeefff},{ggg},{dddhhh}

  要求將其中交集不為空的集合合并,要求合并完成后的集合之間無交集,例如上例應(yīng)輸出

  {aaabbbcccdddhhh},{eeefff},{ggg}

  (1)請描述你解決這個問題的思路;

  (2)請給出主要的處理流程,算法,以及算法的復雜度

  (3)請描述可能的改進(改進的方向如效果,性能等等,這是一個開放問題)。

  ////////////////////////////////1

  1題

  char*revert(char*str)

  {

  intn=strlen(str);

  inti=0;

  charc;

  for(i=0;i

  {

  c=str;

  str=str[n-i];

  str[n-i]=c;

  }

  returnstr;

  }

  ///////////////////////////////////

  2題

  void*memmove(void*dest,constvoid*src,size_tn)

  {

  assert((dest!=0)&&(src!=0));

  char*temp=(char*)dest;

  char*ss=(char*)src;

  inti=0;

  for(;i

  {

  *temp++=*ss++;

  }

  returntemp;

  }

  /////////////////////////////////////////////////

  3題

  (1)思路:

  字典以字母鍵樹組織,在用戶輸入同時匹配

  (2)流程:

  每輸入一個字母:沿字典樹向下一層,

  a)若可以順利下行,則繼續(xù)至結(jié)束,給出結(jié)果;

  b)若該處不能匹配,糾錯處理,給出拼寫建議,繼續(xù)至a);

  算法:

  1.在字典中查找單詞

  字典采用27叉樹組織,每個節(jié)點對應(yīng)一個字母,查找就是一個字母一個字母匹配.算法時間就是單詞的長度k.

  2.糾錯算法

  情況:當輸入的最后一個字母不能匹配時就提示出錯,簡化出錯處理,動態(tài)提示

  可能處理方法:

  (a)當前字母前缺少了一個字母:搜索樹上兩層到當前的匹配作為建議;

  (b)當前字母拼寫錯誤:當前字母的鍵盤相鄰作為提示;(只是簡單的描述,可以有更多的)

  根據(jù)分析字典特征和用戶單詞已輸入部分選擇(a),(b)處理

  復雜性分析:影響算法的效率主要是字典的實現(xiàn)與糾錯處理

  (a)字典的實現(xiàn)已有成熟的算法,改進不大,也不會成為瓶頸;

  (b)糾錯策略要簡單有效,如前述情況,是線性復雜度;

  (3)改進

  策略選擇最是重要,可以采用統(tǒng)計學習的方法改進。

  //////////////////////////////////////////////

  4題

  (1)思路:用哈希做

  (2)首先逐次讀入查詢串,算哈希值,保存在內(nèi)存數(shù)組中,同時統(tǒng)計頻度(注意值與日志項對應(yīng)關(guān)系)

  選出前十的頻度,取出對應(yīng)的日志串,簡單不過了。哈希的設(shè)計是關(guān)鍵。

  //////////////////////////////////////////////////

  5題

  (1)思路:先將集合按照大小排列后,優(yōu)先考慮小的集合是否與大的集合有交集。有就合并,如果小集合與所有其他集合都沒有交集,則獨立。獨立的集合在下一輪的比較中不用考慮。這樣就可以盡量減少字符串的比較次數(shù)。當所有集合都獨立的時候,就終止。

  (2)處理流程:

  1.將集合按照大小排序,組成集合合并待處理列表

  2.選擇最小的集合,找出與之有交集的集合,如果有,合并之;如果無,則與其它集合是獨立集合,從待處理列表中刪除。

  3.重復直到待處理列表為空算法:

  1。將集合按照大小從小到大排序,組成待處理的集合列表。

  2。取出待處理集合列表中最小的集合,對于集合的每個元素,依次在其他集合中搜索是否有此元素存在:

  1>若存在,則將此小集合與大集合合并,并根據(jù)大小插入對應(yīng)的位置。轉(zhuǎn)3。

  2>若不存在,則在該集合中取下一個元素。如果無下一個元素,即所有元素都不存在于其他集合。則表明此集合獨立,從待處理集合列表中刪除。并加入結(jié)果集合列表。轉(zhuǎn)3。

  3。如果待處理集合列表不為空,轉(zhuǎn)2。如果待處理集合列表為空,成功退出,則結(jié)果集合列表就是最終的輸出。算法復雜度分析:

  假設(shè)集合的個數(shù)為n,最大的集合元素為m

  排序的時間復雜度可以達到n*log(n)

  然后對于元素在其他集合中查找,最壞情況下為(n-1)*m

  查找一個集合是否與其他集合有交集的最壞情況是m*m*(n-1)

  合并的時間復雜度不會超過查找集合有交集的最壞情況。

  所以最終最壞時間復雜度為O(m*m*n*n)需要說明的是:此算法的平均時間復雜度會很低,因為無論是查找還是合并,都是處于最壞情況的概率很小,而且排序后優(yōu)先用最小集合作為判斷是否獨立的對象,優(yōu)先與最大的集合進行比較,這些都最大的回避了最壞情況。

  (3)可能的改進:

  首先可以實現(xiàn)將每個集合里面的字符串按照字典序進行排列,這樣就可以將查找以及合并的效率增高。另外,可能采取恰當?shù)臄?shù)據(jù)結(jié)構(gòu)也可以將查找以及合并等操作的效率得到提高。

更多知名企業(yè)的面試試題推薦:

尼爾森公司筆試題

國泰金融筆試題目

網(wǎng)易筆試題

 

http://www.oriental01.com/

【百度技術(shù)研發(fā)類筆試題(2)】相關(guān)文章:

山西中考信息技術(shù)試題(2)07-03

職稱英語真題理工類b級試題(2)10-13

技術(shù)研發(fā)助理求職簡歷08-23

2006年職稱英語考試衛(wèi)生類(A級)試題及答案(2)07-25

2007年職稱英語考試綜合類(A級)試題及答案(2)10-21

2005年職稱英語考試綜合類(A級)試題及答案(2)06-25

2007年職稱英語考試理工類(A級)試題及答案(2)08-27

2005年職稱英語考試衛(wèi)生類(B級)試題及答案(2)10-24

2007年職稱英語考試衛(wèi)生類(C級)試題及答案(2)10-25

2005年職稱英語考試理工類(A級)試題及答案(2)09-08