2014百度校招研发工程师笔试题

2015-04-02 19:08 作者 : 围观 : 次 TAG标签：笔经研

职位类型：研发工程师 礼仪

礼仪

面试时间：

面试网

qzm4

招聘公司： 求职面试

qzm4

满分：100分

求职信息

qzm4

礼仪

1.简答题(本题共30分)

面试网

1）当前计算机系统一般会采用层次结构存储数据，请介绍下典型计算机存储系统一般分为哪几个层次，为什么采用分层存储数据能有效提高程序的执行效率？（10分）面试网

qzm4

答案：

面试问题

（1）典型计算机存储系统一般分为：高速缓存（Cache），主存，辅存；三者速度递减，价格递减，容量递增。 qzm4

礼仪

面试网

（2）危害：Linux系统对运行的进程数量有限制，如果产生过多的僵尸进程占用了可用的进程号，将会导致新的进程无法生成。这就是僵尸进程对系统的最大危害。

求职信息

（3）避免：面试问题

1》signal(SIGCHLD,SIG_IGN);

求职面试

2》fork 2次，让孙子进程由 init（1）进程接管

求职信息

3》用waitpid等待子进程返回

求职面试

qzm4

3）简述Unix/Linux系统中使用socket库编写服务器程序的流程，请分别用对应socket通信函数表示。（10分）面试网

礼仪

答案：礼仪

        服务器端流程如下：
        ①创建serverSocket
        ②初始化 serverAddr（服务器地址）
        ③将socket和serverAddr 绑定 bind
        ④开始监听 listen
        ⑤进入while循环，不断的accept接入的客户端socket，进行读写操作write和read
        ⑥关闭serverSocket 求职信息

        客户端流程：
        ①创建clientSocket
        ②初始化 serverAddr
        ③链接到服务器 connect
        ④利用write和read 进行读写操作
        ⑥关闭clientSocket 面试网

面试网

2.算法与程序设计题(本题共45分) 礼仪

1）使用C/C 语言写一个函数，实现字符串的反转，要求不能用任何系统函数，且时间复杂度最小。函数原型是：char *reverse_str(char *str)(15分)

求职面试

答案：

面试网

char* reverse_str( char str[] )
{
//char *cp_left = str;
//char *cp_right = str; 面试网

    int l = 0;
    int r = 0;
    while( *(str r) != '\0' )
        r ;
    r--;

礼仪

    char tmp='\0';
    while( l <= r )
    {
        tmp = str[l];
        str[l] = str[r];
        str[r] = tmp;

求职信息

        l ;
        r--;
    }

求职信息

return str;
} qzm4

2）给定一个如下输入格式的字符串，(1，(2，3)，(4，(5，6)，7))括号内的元素可以是数字，也可以另一个括号，请实现一个算法消除嵌套的括号。比如把上面的表达式变成：(1，2，3，4，5，6，7)，如果表达式有误请报错。(15分) 求职面试

面试网

答案：

礼仪

int reg_str( char *cp_src, char *cp_des )
{
int stack_num = 0;
*(cp_des ) = '('; 面试网

    while( *cp_src!= '\0' )
    {
        if( *cp_src == '(' )
        {
            stack_num ; 面试网

        }
        else if( *cp_src == ')' && stack_num >0 )
            stack_num--;
        else if( *cp_src == ',' )
        {
            *cp_des = *cp_src ;
            continue;
        }
        else if ( '0' <= *cp_src && *cp_src <= '9' )
        {
            *(cp_des ) = *cp_src;
        }
        else
        {
            printf( "Expression ERROR!\n" );

求职信息

return 0;
} 面试网

cp_src ;
} 面试网

    *(cp_des ) = ')';
    *(cp_des ) = '\0';
    return 1;
}

面试问题

3）相似度计算用于衡量对象之间的相似程度，在数据挖据，自然语言处理中使一个基础性计算，在广告检索服务中往往也会判断网民检索Query和广告Adword的主题相似度。假设Query或者Adword的主题属性定义为一个长度为10000的浮点数据Pr[10000](称之为主题概率数组)，其中Pr[i]表示Query或者Adword属于主题Id为i的概率，而Query和Adword的相似度简化定义为两者主题概率数组的内积，即sim(Query,Adword)=sum(QueryPr[i]*AdwordPr[i])(0<==i<10000).在实际应用场景中，由于大多数主题的概率都为0，所以主题概率数组往往比较稀疏，在实现时会以一个紧凑型数组topic_info_t[]的方式保存，其中100<=数组大小<=1000，并按照topic_id递增排列，0<=topic_id<10000,0< p="">

求职面试

现在给出Query的topic_info_t数组和N(N>=5000)个Adwords的 topic_info-t数组，现要求出Query与Adwords的相似度最大值，即max(sim(Query,Adword[i])(0<=i& query_topic_info, Const vector adwords_topic_info[], Int adwords_number); 面试问题

求职面试

编写代码求时间复杂度最低的算法，并给出时间复杂度分析。(15分)

礼仪

跪求答案！！！%>_<%< p="">

面试问题

3.系统设计题(本题共25分)

qzm4

求职信息

在企业中，对生产数据进行分析具有很重要的意义。但是生产数据通常不能直接用于数据分析，通常需要进行抽取，转换和加载，也就是业界常识的ETL.生产数据

求职面试

文件格式例子任务定义文件

每行表示一个任务，3列：求职信息

1， ID

求职面试

2，开始运行时间面试网

3，最大运行时长（分钟）面试问题

100,01:00:00,60

求职信息

110,02:00:00,30 礼仪

任务依赖关系

每行表示一个关系，2列：

面试问题

1，前置任务

求职面试

2，后置任务面试问题

100,110

求职面试

问题：
1. 下图是ETL调度系统的模块图。请描述各个模块的主要职责，以及各个线条的含义。

求职面试

qzm4

        a) 函数名：checkCycle
        b) 输入：pairs，已存在的依赖关系（（pre,post））,newPair新的依赖关系（pre,post）
        c) 输出：True：不存在环，False：存在环

求职信息

3. 如果调度时，某个任务在其依赖的任务之前执行，必然导致错误，请实现调度算法，确保任务按照依赖顺序执行？

面试网

        a) 函数名 schedule
        b) 输入1：tasks，整型数组
        c) 输入2：tasks-relations，二元组数组，每个二元组表示一组关系
        d) 输出：task_id序列，并行执行的用“,”分隔，其他的用“;”分隔

求职面试

4. 给定一个任务，如何计算出他的最晚完成时间？

面试网

        a) 函数名：calMaxEndTime
        b) 输入1：tasks,3元组数组，（task_id,start_time,max_run_time）;
        c) 输入2：task-relations，2元组数组，每个二元组表示一组关系；
        d) 输入3：task-id
        e) 输出：最晚完成时间；面试问题

求职面试