亚洲v欧美v国产v在线成_制服丝袜中文字幕丝袜专区_一区二区三区韩国电影_激情欧美一区二区中文字幕

我要投稿 投訴建議

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

時(shí)間:2023-03-27 03:28:28 面試試題 我要投稿
  • 相關(guān)推薦

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

  有一根27厘米的細(xì)木桿,在第3厘米、7厘米、11厘米、17厘米、23厘米這五個(gè)位置上各有一只螞蟻。木桿很細(xì),不能同時(shí)通過一只螞蟻。開始時(shí),螞蟻的頭朝左還是朝右是任意的,它們只會(huì)朝前走或調(diào)頭,但不會(huì)后退。當(dāng)任意兩只螞蟻碰頭時(shí),兩只螞蟻會(huì)同時(shí)調(diào)頭朝反方向走。假設(shè)螞蟻們每秒鐘可以走一厘米的距離。

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

  編寫程序,求所有螞蟻都離開木桿的最小時(shí)間和最大時(shí)間。

  分析:題目中的螞蟻只可能相遇在整數(shù)點(diǎn),不可以相遇在其它點(diǎn),比如3.5cm處之類的,也就是可以讓每只螞蟻?zhàn)?秒,然后查看是否有相遇的即可.這樣我的程序?qū)崿F(xiàn)思路就是,初始化5只螞蟻,讓每只螞蟻?zhàn)?秒,然后看是否有相遇的,如果有則做相應(yīng)處理.當(dāng)每只螞蟻都走出木桿時(shí),我就記錄當(dāng)前時(shí)間.這樣就可以得到當(dāng)前狀態(tài)情況下,需要多久可以走出木桿,然后遍歷所有狀態(tài)則可以得到所有可能.

  */

  packagebaidu;

  publicclassAnt{

  /*

  *step表示螞蟻每一個(gè)單位時(shí)間所走的長度

  */

  privatefinalstaticintstep=1;

  /*

  *position表示螞蟻所處的初始位置

  */

  privateintposition;

  /*

  *direction表示螞蟻的前進(jìn)方向,如果為1表示向27厘米的方向走,如果為-1,則表示往0的方向走。

  */

  privateintdirection=1;

  /*

  *此函數(shù)運(yùn)行一次,表示螞蟻前進(jìn)一個(gè)單位時(shí)間,如果已經(jīng)走下木桿則會(huì)拋出異常

  */

  publicvoidwalk(){

  if(isOut()){

  thrownewRuntimeException("theantisout");

  }

  position=position+this.direction*step;

  };

  /**

  *檢查螞蟻是否已經(jīng)走出木桿,如果走出返回true

  *

  */

  publicbooleanisOut(){

  returnposition<=0||position>=27;

  }

  /**

  *檢查此螞蟻是否已經(jīng)遇到另外一只螞蟻

  *@paramant

  *@return如果遇到返回true

  */

  publicbooleanisEncounter(Antant){

  returnant.position==this.position;

  }

  /**

  *改變螞蟻的前進(jìn)方向

  */

  publicvoidchangeDistation(){

  direction=-1*direction;

  }

  /**

  *構(gòu)造函數(shù),設(shè)置螞蟻的初始前進(jìn)方向,和初始位置

  *@paramposition

  *@paramdirection

  */

  publicAnt(intposition,intdirection){

  this.position=position;

  if(direction!=1){

  this.direction=-1;//方向設(shè)置初始位置,比如為0時(shí),也將其設(shè)置為1.這樣可以方便后面的處理

  }else{

  this.direction=1;

  }

  }

  }

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

  packagebaidu;

  publicclassController{

  publicstaticvoidmain(String[]args){

  inttime=0;

  for(inti=0;i<32;i++){

  Ant[]antArray=getAntList(getPoistions(),getDirections(i));

  while(!isAllOut(antArray)){

  for(Antant:antArray){

  if(!ant.isOut()){

  ant.walk();

  }

  }

  time++;

  //查看是否有已經(jīng)相遇的Ant,如果有則更改其前進(jìn)方向

  dealEncounter(antArray);

  }

  System.out.println(time);

  //將時(shí)間歸0,這樣可以重新設(shè)置條件,再次得到全部走完所需要的時(shí)間.

  time=0;

  }

  }

  /**

  *這個(gè)函數(shù)的算法很亂,但暫時(shí)能解決問題

  *

  *@paramlist

  */

  publicstaticvoiddealEncounter(Ant[]antArray){

  intnum_ant=antArray.length;

  for(intj=0;j

  for(intk=j+1;k

  if(antArray[j].isEncounter(antArray[k])){

  antArray[j].changeDistation();

  antArray[k].changeDistation();

  }

  }

  }

  }

  /**

  *因?yàn)橛?只Ant,所以組合之后有32種組合.剛好用5位二進(jìn)制來表示,如果為0則表示Ant往0的方向走如果為1,則表示往27的方向走

  *

  *注:在通過Ant的構(gòu)造函數(shù)設(shè)置初始值時(shí),通過過濾把0修改成了-1.

  */

  publicstaticint[]getDirections(intseed){

  intresult[]=newint[5];

  result[0]=seed%2;

  result[1]=seed/2%2;

  result[2]=seed/4%2;

  result[3]=seed/8%2;

  result[4]=seed/16%2;

  System.out.println("directionsis"+result[0]+"|"+result[1]+"|"

  +result[2]+"|"+result[3]+"|"+result[4]);

  returnresult;

  }

  /**

  *批量設(shè)置Ant的初始位置,這樣設(shè)置不是十分必要,可以直接在代碼中設(shè)置

  *

  *@return

  */

  publicstaticint[]getPoistions(){

  returnnewint[]{3,7,11,17,23};

  }

  /**

  *取得設(shè)置好初始值的5只Ant

  *

  *@parampositions

  *@paramdirections

  *@return

  */

  publicstaticAnt[]getAntList(int[]positions,int[]directions){

  Antant3=newAnt(positions[0],directions[0]);

  Antant7=newAnt(positions[1],directions[1]);

  Antant11=newAnt(positions[2],directions[2]);

  Antant17=newAnt(positions[3],directions[3]);

  Antant23=newAnt(positions[4],directions[4]);

  returnnewAnt[]{ant3,ant7,ant11,ant17,ant23};

  }

  /**

  *判斷是否所有的Ant都已經(jīng)走出了木桿,也就是設(shè)置退出條件

  *

  *@paramantArray

  *@return

  */

  publicstaticbooleanisAllOut(Ant[]antArray){

  for(Antant:antArray){

  if(ant.isOut()==false){

  returnfalse;

  }

  }

  returntrue;

  }

  }

  編程:用C語言實(shí)現(xiàn)一個(gè)revert函數(shù),它的功能是將輸入的字符串在原串上倒序后返回。

  2編程:

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

  3英文拼寫糾錯(cuò):

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

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

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

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

  4尋找熱門查詢:

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

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

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

  5集合合并:

  給定一個(gè)字符串的集合,格式如:

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

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

  {aaabbbcccdddhhh},{eeefff},{ggg}

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

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

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

  ////////////////////////////////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)思路:

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

  (2)流程:

  每輸入一個(gè)字母:沿字典樹向下一層,

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

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

  算法:

  1.在字典中查找單詞

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

  2.糾錯(cuò)算法

  情況:當(dāng)輸入的最后一個(gè)字母不能匹配時(shí)就提示出錯(cuò),簡化出錯(cuò)處理,動(dòng)態(tài)提示

  可能處理方法:

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

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

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

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

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

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

  (3)改進(jìn)

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

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

  4題

  (1)思路:用哈希做

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

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

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

  5題

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

  (2)處理流程:

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

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

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

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

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

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

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

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

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

  排序的時(shí)間復(fù)雜度可以達(dá)到n*log(n)

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

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

  合并的時(shí)間復(fù)雜度不會(huì)超過查找集合有交集的最壞情況。

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

  (3)可能的改進(jìn):

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




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

尼爾森公司筆試題
國泰金融筆試題目
網(wǎng)易筆試題

 

http://fnhaliao.com/

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

2017百度銷售類筆試題09-25

2014百度android開發(fā)類面試題目07-20

百度筆試題及答案07-27

百度校園招聘深度學(xué)習(xí)算法研發(fā)工程師面試試題07-30

百度算法面試題07-30

百度校園招聘筆試題09-26

2015百度PHP面試題07-31

百度面試Android面試題08-01

百度php面試題目09-25