2011-5-7百度實(shí)習(xí)生筆試

                  百度實(shí)習(xí)生筆試總結(jié)

試題：
 一。簡(jiǎn)答
   1.extern“c”{是什么含義，有什么作用
   2.寫(xiě)出至少兩種經(jīng)典設(shè)計(jì)模式，最好寫(xiě)偽代碼
   3.TCP中time_wait什么含義，在什么情境下發(fā)生，以及它的好處和壞處
二。編程
   1.一個(gè)服務(wù)器每天定時(shí)執(zhí)行一定任務(wù)（N<1000），各任務(wù)間有一定依賴，如執(zhí)行任務(wù)A需要先執(zhí)行任務(wù)B，但無(wú)死循環(huán)。
      請(qǐng)?jiān)O(shè)計(jì)適當(dāng)?shù)娜蝿?wù)執(zhí)行順序。寫(xiě)出算法過(guò)程，分析時(shí)間空間復(fù)雜度。
   2.統(tǒng)計(jì)一個(gè)英文文本中的句子數(shù)，文本中含有大小寫(xiě)字母、空格、點(diǎn)號(hào)（.）、逗號(hào)（，），一個(gè)句子的結(jié)尾必須至少是一個(gè)字母加點(diǎn)好。給出詳細(xì)代碼。
三。設(shè)計(jì)題
    服務(wù)器記錄url、訪問(wèn)ip、訪問(wèn)時(shí)間，服務(wù)器有100億條記錄，設(shè)計(jì)一個(gè)系統(tǒng)：
   1.當(dāng)知道訪問(wèn)時(shí)間（精確到分鐘）和ip，可以統(tǒng)計(jì)url的總訪問(wèn)量
   2.當(dāng)知道訪問(wèn)時(shí)間（精確到分鐘）和url，可以統(tǒng)計(jì)ip的總訪問(wèn)量

 解答：
   1 關(guān)于extern"C"
      (1) 首先關(guān)于條件編譯
            #ifdef _cplusplus  #endif _cplusplus及發(fā)散 
            這個(gè)屬于條件編譯。比如在a.h中引用了c.h，在a.c中顯式的引入了a.h和c.h頭文件，若不添加條件編譯，就會(huì)發(fā)生錯(cuò)誤。因?yàn)榭赡苤貜?fù)引入了
            一些結(jié)構(gòu)和函數(shù)的定義。
     (2) extern關(guān)鍵字
           在一個(gè)項(xiàng)目中，必須保證函數(shù)、變量、枚舉在所有文件中保持一致，除非你定義的變量是局部的。
           ；

int{}

//file1.c
  int x = 1 ;
  int foo(){doSomething here}

//file2.c
  extern int x ;
   int foo() ;
  int goo(return foo());

     在file1.c中定義了變量c,然后在file2.c中的變量x ，以及函數(shù)foo() 都是引用的文件file1.c中。

    extern 是c/c++語(yǔ)言中標(biāo)示函數(shù)和全局變量的作用范圍，該關(guān)鍵字告訴編譯器該變量或者函數(shù)可以在本模塊之外的其他模塊之中使用。
    通常在本模塊的頭文件中對(duì)本模塊提供給其余模塊的函數(shù)和變量添加extern 關(guān)鍵字。
   該關(guān)鍵字對(duì)應(yīng)的事static，表示static的變量或者函數(shù)只能在本模塊中使用。
    
  (3)"c" 關(guān)鍵字
       一個(gè)c++編寫(xiě)的代碼中，可能會(huì)包哈其余語(yǔ)言編寫(xiě)的代碼， 不同語(yǔ)言之間編寫(xiě)的代碼互相調(diào)用是困難的，可能會(huì)在注冊(cè)變量以及變量在棧上
      的分布不同。
     為了使各個(gè)語(yǔ)言之間保持相同的編譯和鏈接規(guī)約，可以使用extern "C" 進(jìn)行修飾。比如 c/c++的標(biāo)準(zhǔn)函數(shù) strcpy() 
     extern "C" void strcpy(char * dest , const char * src) ;
     注意該聲明與下面的聲明不同的地方  extern  void strcpy(char * dest , const char * src) ;
     "C" 并不指的是 C語(yǔ)言，而指的是一種鏈接規(guī)約  ，比如Fortran、assembler 等都使用的和C一樣的編譯和鏈接規(guī)約。
     
  (4) 綜上：
       extern "c" 表示的是 在C++ 源文件中使用 該定義，使c++代碼按照c的編譯和鏈接規(guī)約，這樣在c源文件中，就可以使用C++中定義的變量
       和函數(shù)。使用在c/c++混合編程的情況下，

  (5) c 與c++互相調(diào)用
       
       c++是面向?qū)ο蟮恼Z(yǔ)言，為了支持函數(shù)重載等特性，c++編譯器將函數(shù)編譯如下
      

void print(int , int) ;
void print(int , float) ;

//編譯如下
_print_int_int 
_print_int_float

  c語(yǔ)言的編譯器不會(huì)像c++編譯器那樣，而是直接編譯為_(kāi)print
 
  具體代碼如下： c++調(diào)用c
  

#ifndef _C_HEADER_H   //c語(yǔ)言的頭文件
#define _C_HEADER_H 
 void print(int x) ;
#endif

#include <stdio.h>    //c實(shí)現(xiàn)文件
#include "cheader.h"
 void print(int x)
 {
      printf("%d\n" , x) ;
 }


#include "cheader.h"  //c++調(diào)用文件
#include "iostream"
 int main()
 {
   print(3);
   system("pause") ;
   return 0 ;    
 }

   c 調(diào)用c++代碼
  
   

#ifndef _C_PLUS_H      //c++頭文件
#define _C_PLUS_H
extern "C"  void print(int x) ;
#endif

#include <iostream>    //c++ 實(shí)現(xiàn)文件
#include "cplus.h"
  void print(int x) 
  {
    printf("%d\n" , x) ;   
    system("pause") ;  
  }

#include "cplus.h" //c調(diào)用文件
 int main()
 {
   print(3) ;    
 }

 2 設(shè)計(jì)模式解答
   (1) 工廠設(shè)計(jì)模式
          (a) 簡(jiǎn)單工廠模式
            Simple Factory模式（又稱Static Factory模式），一個(gè)Simple Factory生產(chǎn)成品，而對(duì)客戶端隱藏產(chǎn)品產(chǎn)生的細(xì)節(jié)。實(shí)作時(shí)定義一個(gè)產(chǎn)品介面（interface），并透過(guò)特定靜態(tài)方法來(lái)建立成品。假設(shè)有一個(gè)音樂(lè)盒工廠，購(gòu)買(mǎi)音樂(lè)盒的客人不用知道音樂(lè)盒是如何制作的，他只要知道如何播放音樂(lè)盒就可以了。
 

IMusicBox.java 
public interface IMusicBox {    public void play();}


PianoBox.java 
public class PianoBox implements IMusicBox {    public void play() {        System.out.println("撥放鋼琴音樂(lè):)");    }}


ViolinBox.java 
public class ViolinBox implements IMusicBox {    public void play() {        System.out.println("撥放小提琴音樂(lè)^_^");    }}


MusicBoxFactory.java 
public class MusicBoxFactory {    public static IMusicBox createMusicBox(String name)                                throws InstantiationException,                                       IllegalAccessException,                                       ClassNotFoundException {        // 這邊使用的是Java的Reflection機(jī)制來(lái)產(chǎn)生實(shí)例        // 不過(guò)客戶端不用管啦        // 以后就算改變了這邊的程式，客戶端程式是不用更改的        return (IMusicBox) Class.forName(name).newInstance();    }}


MusicBoxDemo.java 
public class MusicBoxDemo {    public static void main(String[] args) throws Exception {        playMusicBox(MusicBoxFactory.createMusicBox("PianoBox"));        playMusicBox(MusicBoxFactory.createMusicBox("ViolinBox"));    }        public static void playMusicBox(IMusicBox musicBox) {        musicBox.play();    }}

 
  (2) 單例設(shè)計(jì)模式
      

public Runtime
{
  private static Runtime currrentRuntime = new
  Runtime();
  
  public static Runtime getRuntime()
  {
    return currentTime ;
  }   

   private RunTime() ; //注意構(gòu)造函數(shù)定義為私有

}

        注意成員變量定義為私有，而且構(gòu)造函數(shù)定義為私有。

 3 TCP 中的 time_wait 狀態(tài)
    
    (1) 擴(kuò)展 TCP建立連接的3次握手操作
       c ---------------  s
         SYN-------->
        <---------ACK-SYN----
         ----------ACK--->               
   (2) tcp關(guān)閉連接過(guò)程
       
       主動(dòng)關(guān)閉方                                              被動(dòng)關(guān)閉方
      
                           -------------FIN M ----------->
              TIN_WAIT1                                                
                         <---------------ACK-----------  
                                                                                 
             FIN_WAIT2                                                close_wait
                   
                         
                       <---------FIN    N-----------
                                                                                  LAST_ACK

                        -----------ACK ----------->
          TIME_WAIT                                               CLOSED
                                                                                    


         
           CLOSED          
  
          


      time_wait的作用：
        (1)  最后一個(gè)發(fā)送的ACK 很可能丟失，則服務(wù)器會(huì)重發(fā)一個(gè)FIN ， 客戶端可以在time_wait階段再次接受。

       (2) 網(wǎng)絡(luò)上可能還有一些沒(méi)有到達(dá)的數(shù)據(jù)包，或者老的重復(fù)數(shù)據(jù)包，在該階段可以接受。



   4 接下來(lái)的那個(gè)任務(wù)題，實(shí)質(zhì)上就是為 一個(gè)拓?fù)渑判騿?wèn)題。
   


 5 設(shè)計(jì)題解析
  

  









 

posted on 2011-05-08 21:35 kahn 閱讀(2092) 評(píng)論(1)  編輯 收藏 引用 所屬分類(lèi): 算法相關(guān)