百度2014软件开发工程师笔试题详解

一.简答题

1.简述iso的7层设计

解析：

1. 应用层：提供应用程序间通信
2. 表示层：处理数据格式、数据加密等
3. 会话层：建立、维护和管理会话
4. 运输层：建立主机端到端连接
5. 网络层：寻址和路由选择
6. 数据链路层：介质访问，链路管理
7. 物理层：比特流传输

2.如何在多个进程间进行数据共享（至少写出3种）

Linux下：

• 管道
• 信号量
• 共享内存
• 消息队列
• 本地域socket

Windows下：

1. 文件映射；文件映射(Memory-Mapped Files)能使进程把文件内容当作进程地址区间一块内存那样来对待。因此，进程不必使用文件I/O操作，只需简单的指针操作就可读取和修改文件的内容。
2. 共享内存：Win32 API中共享内存(SharedMemory)实际就是文件映射的一种特殊情况。进程在创建文件映射对象时用0xFFFFFFFF来代替文件句柄(HANDLE)，就表示了对应的文件映射对象是从操作系统页面文件访问内存，其它进程打开该文件映射对象就可以访问该内存块。由于共享内存是用文件映射实现的，所以它也有较好的安全性，也只能运行于同一计算机上的进程之间。
3. 匿名管道：管道(Pipe)是一种具有两个端点的通信通道：有一端句柄的进程可以和有另一端句柄的进程通信。管道可以是单向－一端是只读的，另一端点是只写的；也可以是双向的一管道的两端点既可读也可写。
4. 命名管道：命名管道(Named Pipe)是服务器进程和一个或多个客户进程之间通信的单向或双向管道。不同于匿名管道的是命名管道可以在不相关的进程之间和不同计算机之间使用，服务器建立命名管道时给它指定一个名字，任何进程都可以通过该名字打开管道的另一端，根据给定的权限和服务器进程通信。
5. 邮件槽：邮件槽(Mailslots)提供进程间单向通信能力，任何进程都能建立邮件槽成为邮件槽服务器。其它进程，称为邮件槽客户，可以通过邮件槽的名字给邮件槽服务器进程发送消息。进来的消息一直放在邮件槽中，直到服务器进程读取它为止。一个进程既可以是邮件槽服务器也可以是邮件槽客户，因此可建立多个邮件槽实现进程间的双向通信。
6. 剪贴板：剪贴板(Clipped Board)实质是Win32 API中一组用来传输数据的函数和消息，为Windows应用程序之间进行数据共享提供了一个中介，Windows已建立的剪切(复制)－粘贴的机制为不同应用程序之间共享不同格式数据提供了一条捷径。当用户在应用程序中执行剪切或复制操作时，应用程序把选取的数据用一种或多种格式放在剪贴板上。然后任何其它应用程序都可以从剪贴板上拾取数据，从给定格式中选择适合自己的格式。
7. 动态数据交换：动态数据交换(DDE)是使用共享内存在应用程序之间进行数据交换的一种进程间通信形式。应用程序可以使用DDE进行一次性数据传输，也可以当出现新数据时，通过发送更新值在应用程序间动态交换数据。
8. WM_COPYDATA消息：WM_COPYDATA是一种非常强大却鲜为人知的消息。当一个应用向另一个应用传送数据时，发送方只需使用调用SendMessage函数，参数是目的窗口的句柄、传递数据的起始地址、WM_COPYDATA消息。接收方只需像处理其它消息那样处理WM_COPY

3.简述TCP与UDP的区别

二.算法题

1.有一个数据A = [a_1,a_2,a_3.....a_n],n的大小不定，请设计算法将A中的所有数据组合进行输出

解析：可以采用递归的方式来实现，每次取一个元素，在剩下元素的数组中递归，要注意递归结束的条件。 

2.有这样一个数组A，大小为n，相邻元素差的绝对值都是1，如A={4,5,6,5,6,7,8,9,10,9}，现在给定数组A和目标整数t，请找到t在A中的位置。(15分)

解析：

解法一：常规解法：遍历，时间复杂度O(n)

解法二：快速定位到第一个目标整数，后面继续遍历，最好情况下是O(1)，最坏情况是O(n)

快速定位方法：以A[0]<t为例：

1. dis = t - A[0]，如果A[dis] = t，则定位到，
2. 否则A[dis]必然小于t，重复步骤1

3.二叉树的面积等于二叉树的长乘以二叉树的宽，二叉树的宽等于最长节点间的距离，二叉树的长等于根节点到子节点的最长长度，请设计算法计算二叉树的面积？

解析：面积 = 长 * 宽 = 树的深度 * （左子树的深度 ＋ 右子树的深度 + 1）

三.算法设计题

百度地图中存在需要标注的很多点，并且这些点都需要带描述，现将描述假设为矩形，并且可以位于点的左边或右边，但点不能移动，如果两个点间的描述发生覆盖，则

需要将其中的一个点进行删除

1.在一个区域内，请设计算法将有效的点进行输出（尽可能多的点）？

2.如果区域足够大，点足够多，算法会出现性能的瓶颈，请设计详细的算法来说明并解决问题？

解析：个人理解

1 关键是在怎么样解决两个点之间发生冲突的情况，在发生冲突时应该如何调整。

1.     从地铁左上角开始标记，逐行标记
2.     默认的标记位置为点的右边
3.     当发生冲突时，查看冲突区域的负责点，询问是否可以调整为左置
4.     如果被冲突点可以重置方向，则重置；否则，同样发起询问动作，直到有一个点重置成功为止。

2 性能瓶颈应该出现在调整算法上，当发生一次冲突时，可能会引起连带的反应，造成多次调整。

    解决方案：对点进行分级，每个点增加权重，按级别进行标记，优先标记权重值较高的点。

参考资料：

如何实现进程间通信？

http://feinibuke.blog.51cto.com/1724260/340272 TCP和UDP之间的区别