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 阅读(2075) 评论(1)  编辑 收藏 引用 所属分类: 算法相关