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

                  百度實習生筆試總結

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

 解答：
   1 關于extern"C"
      (1) 首先關于條件編譯
            #ifdef _cplusplus  #endif _cplusplus及發散 
            這個屬于條件編譯。比如在a.h中引用了c.h，在a.c中顯式的引入了a.h和c.h頭文件，若不添加條件編譯，就會發生錯誤。因為可能重復引入了
            一些結構和函數的定義。
     (2) extern關鍵字
           在一個項目中，必須保證函數、變量、枚舉在所有文件中保持一致，除非你定義的變量是局部的。
           ；

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 ，以及函數foo() 都是引用的文件file1.c中。

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

  (5) c 與c++互相調用
       
       c++是面向對象的語言，為了支持函數重載等特性，c++編譯器將函數編譯如下
      

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

//編譯如下
_print_int_int 
_print_int_float

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

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

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


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

   c 調用c++代碼
  
   

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

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

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

 2 設計模式解答
   (1) 工廠設計模式
          (a) 簡單工廠模式
            Simple Factory模式（又稱Static Factory模式），一個Simple Factory生產成品，而對客戶端隱藏產品產生的細節。實作時定義一個產品介面（interface），并透過特定靜態方法來建立成品。假設有一個音樂盒工廠，購買音樂盒的客人不用知道音樂盒是如何制作的，他只要知道如何播放音樂盒就可以了。
 

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機制來產生實例        // 不過客戶端不用管啦        // 以后就算改變了這邊的程式，客戶端程式是不用更改的        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) 單例設計模式
      

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

   private RunTime() ; //注意構造函數定義為私有

}

        注意成員變量定義為私有，而且構造函數定義為私有。

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

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


         
           CLOSED          
  
          


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

       (2) 網絡上可能還有一些沒有到達的數據包，或者老的重復數據包，在該階段可以接受。



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


 5 設計題解析
  

  









 

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