2015最新笔试题(阿里百度等).doc

1. 请简要描述一下Hadoop, Spark, MPI三种计算框架的特点以及分别适用于什么样的场景2. 请解释tcp连接建立过程，如果可能，请结合相应系统调用函数解释交互过程。3. 给定一个整数的数组，相邻的数不能同时选，求从该数组选取若干整数，使得他们的和最大，要求只能使用o(1)的空间复杂度。要求给出伪码。4. 二分查找是常用的编程方法，请用完整代码实现该函数（不许调用库函数） void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *);5. 有编号1100个灯泡，起初所有的灯都是灭的。有100个同学来按灯泡开关，如果灯是亮的，那么按过开关之后，灯会灭掉。如果灯是灭的，按过开关之后灯会亮。现在开始按开关。第1个同学，把所有的灯泡开关都按一次(按开关灯的编号： 1,2,3,.100)。第2个同学，隔一个灯按一次(按开关灯的编号： 2,4,6,.,100)。第3个同学，隔两个灯按一次(按开关灯的编号： 3,6,9,.,99)。. 问题是，在第100个同学按过之后，有多少盏灯是亮着的？这些灯的编号是多少？要求给出解题思路或给出伪码。6. 打长沙麻将在一开始，只有庄家可得到十四张牌，其余的人十三张。现在庄家手里拿到十四张牌，他想请你写个程序帮忙判断一下，庄家是否已经胡牌。如果你会打麻将，请忽略以下背景，如果不会，简单了解一下背景有助于理解本题： 长沙麻将打法简单、节奏快速，极易胡牌。长沙麻将共一百零八张牌：包括筒、索、万；不带东、南、西、北风、中、发、白。： 1、万子牌：从一万至九万，各4张，共36张。2、筒子牌：从一筒至九筒，各4张，共36张。也有的地方称为饼，从一饼到九饼。3、束子牌：从一束至九束，各4张，共36张。也有的地方称为条，从一条到九条。组牌规则： 1，对子：两张一样花色，一样大小的牌，组成对子。2，顺子：三张相同花色，连续的牌，组成顺子。3，刻子：三张一样花色，一样大小的牌，组成刻子。胡牌规则：每人有十四张牌，如果这十四张牌可以组成：一个对子，若干个顺子和刻子，则表示胡牌。比如以下牌型已经胡牌： 一万，一万，二万，三万，四万，二条，三条，四条，四条，四条，四条，五筒，六筒，七筒。1. 请描述你对这个问题的理解，并写出你的解题思路。1.1， 按花色细分处理，必须是一个花色的牌个数3的倍数余2（留对子），其它花色的个数都是3的倍数。否则不能胡牌1.2， 从3的倍数余2的花色中选出一对，剩下的牌的处理和其它花色一样。如果没有对子，则不能胡牌。1.3， 对于某一个花色的牌，由于个数为3的倍数，判断其是否可以组成若干个顺子或刻子，否则不能胡牌。1.4， 对相同花色的牌进行排序和计数，判断第一张牌能否和其它牌组成顺子或刻子，若不能，则回溯。若能，由继续处理剩下的牌。1.5， 最后判断是否可以胡牌2. 请设计解决问题需要的数据结构。需要设计一个花色的数据结构，包括type（花色）， id（牌的大小），count（牌出现的次数）百度2015安全研发笔试卷1. 请解释下常见利用内存断点调试的原理?2. 对于Edit控件，你如何抓防止密码框内容被抓取？3. DNS欺骗的方式有哪些？4. 列举两种应用层中简单的跨进程DLL注入的方法。5. 以下是一段汇编代码，请用C语言实现相同功能。.dataSourceStringdb Hello, World!,0.codestart:cldxoreax, eaxmovedi, offset SourceStringmov al, dmovecx, 13repnescasjz wowinvokeExitProcess, 0wow:invokeExitProcess, 1end start6. 假设有如下所示的一个数字金字塔，现在，要求写一个程序来查找从顶点到底部任意处结束的路径，使路径经过的数字的和最大，并输出该路径的最大和。比如以下金字塔的和最大路径的和为7+3+8+7+5=30。73 2 8 1 0 2 7 4 4 4 5 2 6 57. 假设有如下字符串： (234453)2342324 现在，要求编程分析其括号配对是否正确。请自行选择下列两种方案之一实现该程序： 方案一：不考虑括号优先级，只考虑配对正确性；方案二：考虑括号优先级，比如12（3）45 是正确的。但是123是不正确的。8. 百度是一个大型网站，内部含有多个产品线，比如广为人知的贴吧、知道、空间等应用。然而设计这些应用的统一登录平台却是一件非常艰巨的挑战。需要考虑到通用性和安全性。1) 对于一个Web应用程序，主要的身份验证和凭证保持的方法主要有cookie和session两种。他们又是如何起作用的？各有哪些优缺点？ 2) 影响到cookie值作用范围的因素有哪些？请一一说明。3) 从安全角度来考虑，一个大型网站的单点登录可能会引入哪些安全问题？如何设计安全的在线单点登录系统？百度研发工程师2015深圳笔试卷1. C+有哪些数据类型?为什么long和int都是4字节?2. JAVA和C+的区别是什么?分别用在什么情景比较好?3. 编程题：给定一个文件每一行是字符串，找出所有的逆序对，比如abc和cba是逆序的对。4. 给定一个奇数n，比如n=3，生成1到n平方的数，如1到9，填入九宫格，使得横竖斜的和都相等。5. C和C+有什么区别，能用C实现C+所有功能吗?C能实现多态吗?6. 逻辑题：25匹马，5条赛道，一匹马一个赛道，比赛只能得到5匹马之间的快慢程度，而不是速度，求决胜1，2，3名至少多少场。7. 请用c+ 实现stl中的string类，实现构造，拷贝构造，析构，赋值，比较，字符串相加，获取长度及子串等功能。百度2013研发工程师A笔试卷1. 动态链接库和静态链接库的优缺点2. 列出数据库中常用的锁及其应用场景3. 给定N是一个正整数，求比N大的最小“不重复数”，这里的不重复是指没有两个相等的相邻位，如1102中的11是相等的两个相邻位故不是不重复数，而12301是不重复数。4. 轮询任务调度和可抢占式调度有什么区别？5. 设N是一个大整数，求长度为N的字符串的最长回文子串。6. 数轴上从左到右有n 个点a0,a1,an-1,给定一根长度为L 的绳子,求绳子最多能覆盖其中的几个点。7. 在现代系统的设计过程中,为了减轻请求的压力,通常采用缓存技术。为了进一步提升缓存的命中率,通常采用分布式缓存方案。即前端的调度模块,将针对不同内容的用户请求分配不同的缓存服务器向用户提供服务。请给出一个分布式缓存方案,满足如下要求: 1)单台缓存服务器故障,整个分布式缓存集群,可以继续提供服务; 2)通过一定的分配策略,可以保证充分利用每个缓存服务的存储空间,及负载均衡。当部分服务器故障或系统扩容时,该分配策略可以保证较小的缓存文件重分配开销。3)当不同缓存服务器的存储空间存在差异时,分配策略可以满足比例分配百度2013研发工程师笔试卷B1. 数据库以及线程发生死锁的原理及必要条件，如何避免死锁2. 面向对象的三个基本元素，五个基本原则3. 公司里面有1001个员工，现在要在公司里面找到最好的羽毛球选手，也就是第一名，每个人都必须参赛，问至少要比赛多少次才能够找到最好的羽毛球员工。4. 现在有100个灯泡，每个灯泡都是关着的，第一趟把所有的灯泡灯泡打开，第二趟把偶数位的灯泡制反（也就是开了的关掉，关了的打开），第三趟让第3,6,9.的灯泡制反.第100趟让第100个灯泡制反，问经过一百趟以后有多少灯泡亮着。5. 有20个数组，每个数组有500个元素，并且是有序排列好的，现在在这20*500个数中找出排名前500的数。6. 字符串左移:void *pszStringRotate(char *pszString, intnCharsRotate)比如ABCDEFG，移3位变DEFGABC，要求空间复杂度O（1），时间复杂度O（n）。7. 现在有一个手机，手机上的键盘上有这样的对应关系，2对应abc,3对应def.手机里面有一个userlist用户列表，当我们输入942的时候出来拼音的对应可能是“xia”，“zha”，“xi”，“yi”等，当我们输入9264的时候出来是yang，可能是“样”，“杨”，“往”等，现在我们输入一个字符串数字，比如926等，要在电话簿userlist中查找出对应的用户名和电话号码并返回结果。C+语言: 电话号码对应的英语单词(注意此题的非递归做法)8. windows内存管理的机制以及优缺点百度2012研发工程师笔试卷1. 用 C 语言写一个函数来执行一串任务。任务是互相依赖的。比如B 任务依赖A 任务，则A 完成B 才能执行。不考虑并发限制，假设所有的任务都能一次执行成功， 所有的任务执行时间都相等。任务数据结构原型为：typedef struct /该任务的 IDint id;/该任务依赖的任务的 IDint *child;/该任务依赖的任务个数int child_num; task;/ 函数原型：bool doschedule(task*pask，inttask_num);/以下函数可以直接调用：void dotask(int id); /执行一个进程/等待 timeout 时间，并返回一个执行成功的任务的 id，如果没有任务在时间片内完成，int waittask(int timeout);bool killtask(int id); /杀掉一个进程2. 阐述栈和堆在生命周期、速度、内存性能等方面的不同点。假如现在有一个缓冲区域绝大多数只需要1KB 空间，极少数极端情况下需要100MB，怎么样合理分配内存？3. 说明以下包含const 修饰符的语句的意义a). double * ptr=&value；b). const double * ptr=&value;c). double *constptr =&value;d).const double *const ptr=&value;4. 请问 c 语言中怎么去除const 修饰？ 比如：const double value=0.2f； double *ptr； ptr 怎么样获取value 的值？5. 在一维坐标轴上存在许多条线段， 用最简单的算法找出重合长度最长得两条线段。比如线段A（1,5）、B（2,8）、C（3,9），则B 和C 的重合长度最长，为5。6. 百度的某服务机制类似于CS（customer-server），有时候大量用户访问服务器S， 导致S 运行效率缓慢。为了提升效率， 拟在 C 上利用一些空余的结果空间作为缓存。已知在 C 的一台客户机上，每天接收1000w query，其中500w uniq query，每个query 5KB，客户机内存3GB，硬盘500GB。做出一个方案，说明系统结构、存储结构、性能优化等方面的设计。7. 判断一个括号字符串是否匹配正确，如果括号有多种，怎么做？如（）正确，()错误。8. 搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万要统计最热门的10条查询串. 内存1G. 字符串长0-255字节(1) 主要解决思路(2) 算法及其复杂度分析百度2011研发工程师笔试卷1. 判断一个括号字符串是否匹配正确，如果括号有多种，怎么做？如（）正确，()错误。2. 百度Spider如何在不超过抓取限额的情况下使得抓取的网页价值之和最大，要求一个最佳抓取方案。请详细描述你的算法思路（可以用伪代码），并分析时间复杂度和空间复杂度。3. 仅用O(1)的空间，将整数数组按奇偶数分成2部分，数组左边是奇数、右边是偶数。（要求：给出完整代码，尽量高效，简洁）4. 给定两个数A、B（0，100000），求AB中最后三位数是多少。请简要描述你的思路。5. 微博上，每个用户可以发送一条消息，可以follow 另一个用户， 当用户发送消息时，所有follow 他的用户都能看见这条消息。如A follow B，则B 的消息，A 都能看见。实现一个微博客消息存储系统，可以使用多台机器来满足性能要求， 可以再海量的用户和消息下，快速的实现以下两种查询：a）给定一个用户，查询他发送的消息，按消息发送时间排序，新的消息在前。b）给定一个用户，查询他follow 的所有人的消息，按消息发送时间排序，新的消息在前.美团2013研发笔试卷1. 有ABCD四个人要在夜里过一座桥，他们通过这座桥分别需要耗时1、2、5、10分钟，现在只有一支手电，过桥时必须带有手电，并且同时最多只能两个人一起过桥。请问如何安排能够让四个人尽快都过桥。2. 25匹马赛跑，每次只能跑5匹马，最快能赛几次找出跑得最快的3匹马？赛跑不能计时，并假设每匹马的速度是恒定不变的。请给出答案并描述比赛过程。3. 在有团购之前，大家都是现场买门票，公园的门票是5元，某天售票处开门时没有准备零钱。假设一天来购票的依次有2N个人，其中有N个人有5元零钱，其他N个人只有10元面值的钱；假设每人只买一张票。请问任何人都不必为找零而等待的概率是多少？4. 有一个函数“int f(int n)”，请编写一段程序调试函数f(n)是否总是返回0，并添加必要的注视和说明。5. 用你熟悉的语言编写程序用两个栈（Stack）模拟队列（Queue）的先进先出操作，仅实现add、remove方法即可。1）请先描述思路； 2）编写完整代码实现，编程语言不限。6. 编写函数，获取两段字符串的最长公共子串的长度，例如： S1= GCCCTAGCCAGDE S2= GCGCCAGTGDE 这两个序列的最长公共子串是GCCAG，也就是说返回值。1）请先描述思路；2）编写完整代码实现，编程语言不限。7. （iOS开发选做）实现多线程都有哪几种方法？8. （Android开发选做）关于Activity的生命周期，下拉statusbar时，桌面Activity会触发哪几个生命周期？系统关机时，弹出关机Dialog之后，此时，桌面Activity会触发哪几个生命周期？9. （系统运维选做）有主机A、B、C通过eth0和同一个交换机相连，A的IP地址为192.168.1.2，子网掩码255.255.255.0，B的IP地址为192.168.2.2，子网掩码255.255.255.0，C的IP地址为192.168.4.2，子网掩码255.255.255.0。现希望A和B能够通信，A和C、B和C不能通信。1）假设能更改A和B的子网掩码，要如何设置A和B的子网掩码？ 2）如果不能更改子网掩码，需要在A和B做什么设置？ 3）A和B通信时，C是否能够通过sniffer截获A和B通信的报文，如果只能截获一部分报文，是哪一类报文？ 4）C可以仅通过sniffer得知A和B的IP地址和MAC地址吗？如果能，如何获得？美团2013湖南研发工程师笔试卷1. 一堆硬币，一个机器人，如果是反的就翻正，如果是正的就抛掷一次，无穷多次后，求正反的比例。2. 一个汽车公司的产品，甲厂占40%，乙厂占60%，甲的次品率是1%，乙的次品率是2%，现在抽出一件汽车时次品，问是甲生产的可能性？3. 一个栈的入栈序列是A,B,C,D,E,则栈的不可能的输出序列是( )A. EDCBAB. DECBAC. DCEABD. ABCDE4. 用两个栈模拟队列先进先出，模拟其add和romve功能，给出思路和代码。5. 一景区需要门票5元，售票员没有零钱，假设这一天会来2N个人，其中N个人会给5元钱，N个人给10元，问所有人都不需要等待的概率是多少？6. 给两个字符串，输出其最长共同字符串的长度：如S1: asdfghjqweryuiase S2: astyfrtfghjqwsa 其最长共同字符串为fghjqw 长度为6，给出代码。美团2012研发工程师笔试卷1. k链表翻转。给出一个链表和一个数k，比如链表123456，k=2，则翻转后214365，若k=3,翻转后321654，若k=4，翻转后432156，用程序实现。2. 有一个随机数发生器，以概率P产生0，概率(1-P)产生1，请问能否利用这个随机数发生器，构造出新的发生器，以1/2的概率产生0和1。请写明结论及推理过程。3. 4个足球队打小组单循环，计分方式：胜3分平1分负0分，如果计分相同，则净胜球多的队伍排名靠前，如果净胜球还一样，则进球多的球队排名靠前。小组前两名出线。问可能出线的最低分数是多少。请说明推理过程。备注：单循环赛是指所有参加比赛的队两两之间都比赛一次，最后按各队在全部比赛中的积分，