2011-5-7百度實習生筆試

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

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

 解答：
   1 關(guān)于extern"C"
      (1) 首先關(guān)于條件編譯
            #ifdef _cplusplus  #endif _cplusplus及發(fā)散 
            這個屬于條件編譯。比如在a.h中引用了c.h，在a.c中顯式的引入了a.h和c.h頭文件，若不添加條件編譯，就會發(fā)生錯誤。因為可能重復(fù)引入了
            一些結(jié)構(gòu)和函數(shù)的定義。
     (2) extern關(guān)鍵字
           在一個項目中，必須保證函數(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++語言中標示函數(shù)和全局變量的作用范圍，該關(guān)鍵字告訴編譯器該變量或者函數(shù)可以在本模塊之外的其他模塊之中使用。
    通常在本模塊的頭文件中對本模塊提供給其余模塊的函數(shù)和變量添加extern 關(guān)鍵字。
   該關(guān)鍵字對應(yīng)的事static，表示static的變量或者函數(shù)只能在本模塊中使用。
    
  (3)"c" 關(guān)鍵字
       一個c++編寫的代碼中，可能會包哈其余語言編寫的代碼， 不同語言之間編寫的代碼互相調(diào)用是困難的，可能會在注冊變量以及變量在棧上
      的分布不同。
     為了使各個語言之間保持相同的編譯和鏈接規(guī)約，可以使用extern "C" 進行修飾。比如 c/c++的標準函數(shù) strcpy() 
     extern "C" void strcpy(char * dest , const char * src) ;
     注意該聲明與下面的聲明不同的地方  extern  void strcpy(char * dest , const char * src) ;
     "C" 并不指的是 C語言，而指的是一種鏈接規(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言，為了支持函數(shù)重載等特性，c++編譯器將函數(shù)編譯如下
      

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

//編譯如下
_print_int_int 
_print_int_float

  c語言的編譯器不會像c++編譯器那樣，而是直接編譯為_print
 
  具體代碼如下： c++調(diào)用c
  

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

#include <stdio.h>    //c實現(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++ 實現(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è)計模式解答
   (1) 工廠設(shè)計模式
          (a) 簡單工廠模式
            Simple Factory模式（又稱Static Factory模式），一個Simple Factory生產(chǎn)成品，而對客戶端隱藏產(chǎn)品產(chǎn)生的細節(jié)。實作時定義一個產(chǎn)品介面（interface），并透過特定靜態(tài)方法來建立成品。假設(shè)有一個音樂盒工廠，購買音樂盒的客人不用知道音樂盒是如何制作的，他只要知道如何播放音樂盒就可以了。
 

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


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


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


MusicBoxFactory.java 
public class MusicBoxFactory {    public static IMusicBox createMusicBox(String name)                                throws InstantiationException,                                       IllegalAccessException,                                       ClassNotFoundException {        // 這邊使用的是Java的Reflection機制來產(chǎn)生實例        // 不過客戶端不用管啦        // 以后就算改變了這邊的程式，客戶端程式是不用更改的        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è)計模式
      

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) 擴展 TCP建立連接的3次握手操作
       c ---------------  s
         SYN-------->
        <---------ACK-SYN----
         ----------ACK--->               
   (2) tcp關(guān)閉連接過程
       
       主動關(guān)閉方                                              被動關(guān)閉方
      
                           -------------FIN M ----------->
              TIN_WAIT1                                                
                         <---------------ACK-----------  
                                                                                 
             FIN_WAIT2                                                close_wait
                   
                         
                       <---------FIN    N-----------
                                                                                  LAST_ACK

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


         
           CLOSED          
  
          


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

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



   4 接下來的那個任務(wù)題，實質(zhì)上就是為 一個拓撲排序問題。
   


 5 設(shè)計題解析
  

  









 

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