百度2014校园招聘笔试题（成都站，软件研发岗）——2014.09.21

一、简答题&＃xff08;本题共30分&＃xff09;

1. 当前计算机系统一般会采用层次结构来存储数据&＃xff0c;请介绍下典型的计算机存储系统一般分为哪几个层次&＃xff0c;为什么采用分层存储数据能有效提高程序的执行效率&＃xff1f;&＃xff08;10分&＃xff09;

2. Unix/Linux系统中僵尸进程是如何产生的&＃xff1f;有什么危害&＃xff1f;如何避免&＃xff1f;&＃xff08;10分&＃xff09;

3. 简述Unix/Linux系统中使用socket库编写服务器端程序的流程&＃xff0c;请分别用对应的socket通信函数表示&＃xff08;10分&＃xff09;

二、算法与程序设计题&＃xff08;本题共45分&＃xff09;

1. 使用C/C&＃43;&＃43;编写函数&＃xff0c;实现字符串反转&＃xff0c;要求不使用任何系统函数&＃xff0c;且时间复杂度最小&＃xff0c;函数原型&＃xff1a;char* reverse_str(char* str)。(15分)

2. 给定一个如下格式的字符串&＃xff0c;(1,(2,3),(4,(5,6),7))括号内的元素可以是数字&＃xff0c;也可以是另一个括号&＃xff0c;请实现一个算法消除嵌套的括号&＃xff0c;比如把上面的表达式变成&＃xff1a;(1,2,3,4,5,6,7)&＃xff0c;如果表达式有误请报错。(15分)

3. &＃xff08;见下图&＃xff09;

三、系统设计题&＃xff08;本题共25分&＃xff09;

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

为了便于开发和维护&＃xff0c;并提高数据实时性&＃xff0c;通常将一个完整的ETL过程分为多个任务&＃xff0c;组成流水线&＃xff0c;如下图所示&＃xff1a;

假设任务定义和任务之间的依赖关系都保存在文件中&＃xff0c;文件格式分别如下&＃xff1a;

问题&＃xff1a;

1.  下面是ETL调度系统的模块图&＃xff0c;请描述各个模块呃主要职责&＃xff0c;以及各个线条的 含义。&＃xff08;10分&＃xff09;

2.  添加依赖关系时要避免出现环&＃xff0c;假设系统同一个时刻只允许一个人添加任务依赖&＃xff0c;请实现一个函数来检查新的依赖是否导致环&＃xff0c;依赖的上游存在环会导致非正常的调度&＃xff0c;因此也希望能避免。&＃xff08;10分&＃xff09;

a)  函数名&＃xff1a;checkCycle

b)  输入&＃xff1a;pairs&＃xff0c;已存在的依赖关系((pre,post)……), newPair新的依赖关系(pre,post)

c)  输出&＃xff1a;True: 不存在环&＃xff0c;False: 存在环

3. 如果调度时&＃xff0c;某个任务在其依赖的任务之前执行&＃xff0c;必然导致错误&＃xff0c;请实现调度算法&＃xff0c;确保任务按照依赖顺序执行&＃xff1f;&＃xff08;10分&＃xff09;

a)  函数名&＃xff1a;schedule

b)  输入1&＃xff1a;tasks&＃xff0c;整数数组&＃xff1b;

c)  输入2&＃xff1a;task-relation&＃xff0c;二元组数组&＃xff0c;每个二元组表示一组关系&＃xff1b;

d)  输出&＃xff1a;task id序列&＃xff0c;并行执行的用","分隔&＃xff0c;其他的用";"分隔&＃xff1b;

4. 给定一个任务&＃xff0c;如何计算出他的最晚完成时间&＃xff1f;&＃xff08;10分&＃xff09;

a)  函数名&＃xff1a;calMaxEndTime

b)  输入1&＃xff1a;tasks&＃xff0c;3元组数组&＃xff0c;&＃xff08;task_id, start_time, max_run_time&＃xff09;&＃xff1b;

c)  输入2&＃xff1a;task-relations&＃xff0c;二元组数组&＃xff0c;每个二元组表示一组关系&＃xff1b;

d)  输入3&＃xff1a;task-id

e)  输出&＃xff1a;最晚完成时间&＃xff1b;