百度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的区别

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之间的区别

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CSDN技术头条

Java 9的14个新特性总结

Java 9 包含了丰富的特性集。虽然Java 9没有新的语言概念,但是有开发者感兴趣的新的API和诊断命令。 我们将快速的,着重的浏览其中的几个新特性: ? ...

22050
来自专栏Java帮帮-微信公众号-技术文章全总结

【大牛经验】Java9的新特性

Java 9 包含了丰富的特性集。虽然Java 9没有新的语言概念,但是有开发者感兴趣的新的API和诊断命令。 我们将快速的,着重的浏览其中的几个新特性: ? ...

37680
来自专栏FreeBuf

Phpcms v9漏洞分析

最近研究源码审计相关知识,会抓起以前开源的CMS漏洞进行研究,昨天偶然看见了这个PHPCMS的漏洞,就准备分析研究一番,最开始本来想直接从源头对代码进行静态分析...

36670
来自专栏腾讯Bugly的专栏

Duang~ Android堆栈慘遭毁容?精神哥揭露毁容真相!

最近精神哥接到多个小伙伴的投诉,说无法看懂Bugly崩溃克星页面上显示的堆栈信息!精神哥赶紧把正研究的Top Crash崩溃和心爱的鸡爪放下,开始着手跟进。经分...

35350
来自专栏程序员互动联盟

【C语言系列】C语言编译流程分析

前几天看了《程序员的自我修养——链接、装载与库》中的第二章“编译和链接”,主要根据其中的内容简单总结一下C程序编译的过程吧。 我现在一般都是用gcc,所以自然以...

37250
来自专栏蓝天

需要使用一致性哈希吗?

在普通的哈希中,如果节点个数(分母)发生变化,原先的次序会被完全打乱重来,一致性哈希解决了这个问题。实际可看成普通的哈希对着的是物理节点,而一致性哈希对着的是虚...

10310
来自专栏Java编程技术

UML建模(状态图)

状态机图是一种行为图,它通过使用有限的状态转移展示了一个系统中一个模块的一些离散的行为,在UML2.4里面有两种状态机图:行为状态机(behavioral st...

13920
来自专栏用户2442861的专栏

使用JAVA如何对图片进行格式检查以及安全检查处理

本文出自冯立彬的博客,原地址:http://www.fenglibin.com/use_java_to_check_images_type_and_secur...

16410
来自专栏牛客网

百度Android开发面经(共三面)

今天早上现场面的,一共三面,由于问的问题确实太多了,所以有些遗漏,把记得的问题记录了下。每面差不多一小时。 一面: 1、聊项目 2、MVP模式的优缺点 3、图片...

42950
来自专栏闻道于事

vim命令

9010

扫码关注云+社区

领取腾讯云代金券