请简要描述你的思路。
(这题我用方法比较笨,应该是做错了,唉XX2011校园招聘笔试题)
答:
定义A,B为unsignedint,共4个字节,(A&1)^(B&1)剩下两位分别与2和4
2.阅读一段代码,然后有四个小问题,代码和题都很简单基础。
a)C程序中的存储区分哪几个部分?
b)指出程序中几个变量所在的存储区。
c)使用new分配的内存如果分配失败会如何?
d)关于new/delete和malloc/free的区别。
3.判断一个括号字符串是否匹配正确,如果括号有多种,怎么做?
如(([]))正确,[[(()错误。
二、算法
1.XXSpider如何在不超过抓取限额的情况下使得抓取的网页价值之和最大,要求一个最佳抓取方案。
请详细描述你的算法思路(可以用伪代码),并分析时间复杂度和空间复杂度。
2.仅用O
(1)的空间,将整数数组按奇偶数分成2部分,数组左边是奇数、右边是偶数。
(要求:
给出完整代码,尽量高效,简洁)
三、系统设计题
微博上,每个用户可以发送一条消息,可以follow另一个用户,当用户发送消息时,所有follow他的用户都能看见这条消息。
如AfollowB,则B的消息,A都能看见。
实现一个微博客消息存储系统,可以使用多台机器来满足性能要求,可以再海量的用户和消息下,快速的实现以下两种查询:
a)给定一个用户,查询他发送的消息,按消息发送时间排序,新的消息在前。
b)给定一个用户,查询他follow的所有人的消息,按消息发送时间排序,新的消息在前。
2011年XX校园招聘技术类笔试真题
第一大题
1.定义栈的数据结构,添加一个min函数,找到栈的最小元素。
要求函数min、push、pop的时间复杂度为O
(1),请简要描述思路。
2.是一个读程序写结果,并判断函数功能。
同时要指出程序的隐患 程序太长了,记不住了。
3.分析线性表、二叉平衡树和哈希表存储数据时各自的优劣。
第二大题
1.一串首尾相连的珠子,共m颗。
每个珠子有自己的颜色,全部颜色共有n种 (n小于等于10),从中截取一段,要求包含所有不同的颜色,长度越短越好,如何截取。
详述算法思路,并分析时间和空间复杂度。
2.设计strnumcmp函数,比较字符串的大小。
功能为 a.当字符串中有数字时,以数字大小为准 b.对于只有其中一个字符串有数字的情况,仍然沿用strcmp方式。
第三大题
处理一个词搭配的词典,条件为
1) 字典中存在的项是两个词的搭配,例如:
字典中有“今天”和“晚上”两个词,那它们组成的搭配为“今天 晚上”和“晚上 今天”
2)词的集合很大,约为10万量级
3)一个词并不会和其它所有词搭配,通常只会和不超过1万个词搭配
4)对字典的使用读操作很多,通常为上千次请求,几乎没有写入操作。
请设计一个字典服务系统,当请求为两个词的搭配时,能快速返回搭配的相关信息,使用尽可能少的资源,并计算出需要使用的机器资源。
2012实习生校园招聘笔试题
1、给一个单词a,如果通过交换单词中字母的顺序可以得到另外的单词b,那么b是a的兄弟单词,比如的单词army和mary互为兄弟单词。
现在要给出一种解决方案,对于用户输入的单词,根据给定的字典找出输入单词有哪些兄弟单词。
请具体说明数据结构和查询流程,要求时间和空间效率尽可能地高。
字典树的典型应用
2、系统中维护了若干数据项,我们对数据项的分类可以分为三级,首先我们按照一级分类方法将数据项分为A、B、C......若干类别,每个一级分类方法产生的类别又可以按照二级分类方法分为a、b、c......若干子类别,同样,二级分类方法产生的类别又可以按照是三级分类方法分为i、ii、iii......若干子类别,每个三级分类方法产生的子类别中的数据项从1开始编号。
我们需要对每个数据项输出日志,日志的形式是key_value对,写入日志的时候,用户提供三级类别名称、数据项编号和日志的key,共五个key值,例如,write_log(A,a,i,1,key1),获取日志的时候,用户提供三级类别名称、数据项编号,共四个key值,返回对应的所有的key_value对,例如get_log(A,a,i,1,key1),
请描述一种数据结构来存储这些日志,并计算出写入日志和读出日志的时间复杂度。
3、C和C++中如何动态分配和释放内存?
他们的区别是什么?
malloc/free和new/delete的区别
4、数组al[0,mid-1]和al[mid,num-1]是各自有序的,对数组al[0,num-1]的两个子有序段进行merge,得到al[0,num-1]整体有序。
要求空间复杂度为O
(1)。
注:
al[i]元素是支持'<'运算符的。
5、线程和进程的区别及联系?
如何理解“线程安全”问题?
答案:
进程和线程都是由操作系统所体会的程序运行的基本单元,系统利用该基本单元实现系统对应用的并发性。
1、简而言之,一个程序至少有一个进程,一个进程至少有一个线程.
2、线程的划分尺度小于进程,使得多线程程序的并发性高。
3、另外,进程在执行过程中拥有独立的内存单元,而多个线程共享内存,从而极大地提高了程序的运行效率。
4、线程在执行过程中与进程还是有区别的。
每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。
但是线程不能够独立执行,必须依存在应用程序中,由应用程序提供多个线程执行控制。
5、从逻辑角度来看,多线程的意义在于一个应用程序中,有多个执行部分可以同时执行。
但操作系统并没有将多个线程看做多个独立的应用,来实现进程的调度和管理以及资源分配。
这就是进程和线程的重要区别。
算法与程序设计一、
网页爬虫在抓取网页时,从指定的URL站点入口开始爬取这个站点上的所有URL
link,抓取到下一级link对应的页面后,同样对页面上的link进行抓取从而完成深度遍历。
为简化问题,我们假设每个页面上至多只有一个link,如从
问:
对于爬虫分别从
请先描述相应的算法,再给出相应的代码实现。
(只需给出判断方法代码,无需爬虫代码)
两个单向链表的相交问题。
算法与程序设计二、
4、有一种结构如下图所示,它由层的嵌套组成,一个父层中只能包含垂直方向上或者是水平方向上并列的层,例如,层1可以包含2、3、4三个垂直方向上的层,层2可以包含5和6两个水平方向的层,在空层中可以包含数据节点,所谓的空层是指不包含子层的层,每个空层可以包含若干个数据节点,也可以一个都不包含。
在这种结构上面,我们从垂直方向上划一条线,我们约定每一个子层中我们只能经过一个数据节点,在这种情况下,每条线可以经过多个数据节点,也可以不经过任何数据节点,例如,线1经过了3、5、8三个数据节点,线2只经过了14个数据节点。
(1)给出函数,实现判断两个数据节点,是否可能同时被线划中,给出具体的代码。
(2)给出函数,输出所有一条线可以划中的数据节点序列,
可以给出伪代码实现。
思路:
(1)判断两个数所属的同一层次的相同矩形框的下一层次矩形框是水平排列的还是垂直排列的,垂直排列在能在一条线上,水平排列则不能。
(2)用回溯算法求出所有在一条直线上的字符串,用两字符串是否在同一直线上进行剪枝操作。
系统设计题
1、相信大家都使用过XX搜索框的suggestion功能,XX搜索框中的suggestion提示功能如何实现?
请给出实现思路和主要的数据结构、算法。
有什么优化思路可以使得时间和空间效率最高?
应用字典树来求前缀和TOP
K对热词进行统计排序
2、两个200G大小的文件A和B,AB文件里内容均为无序的一行一个正整数字(不超过2^63),请设计方案,输出两个文件中均出现过的数字,使用一台内存不超过16G、磁盘充足的机器。
方案中指明使用java编程时使用到的关键工具类,以及为什么?
2012XX招聘笔试题目
1,设计一个消息队列,要求实现以下的功能:
消息队列的初始化
消息队列的插入消息
消息队列的取消息(阻塞的方式)
消息队列消息的访问(非阻塞的方式)
使用信号量和mutex来实现
2,二叉树的深度优先遍历的非递归实现
3,cmwap和cmnet的区别,总技术的角度阐述。
4,设计一个内存管理系统,要求实现线程安全和内存泄露溢出管理,尽量与malloc/free的效率差不多
2013年校招笔试
一:
简答题(30)
1:
数据库以及线程发生死锁的原理及必要条件,如何避免死锁
答:
产生死锁的原因主要是:
(1)因为系统资源不足。
(2)进程运行推进的顺序不合适。
(3)资源分配不当等。
产生死锁的四个必要条件:
(1)互斥条件:
一个资源每次只能被一个进程使用。
(2)请求与保持条件:
一个进程因请求资源而阻塞时,对已获得的资源保持不放。
(3)不剥夺条件:
进程已获得的资源,在末使用完之前,不能强行剥夺。
(4)循环等待条件:
若干进程之间形成一种头尾相接的循环等待资源关系。
避免死锁:
死锁的预防是通过破坏产生条件来阻止死锁的产生,但这种方法破坏了系统的并行性和并发性。
死锁产生的前三个条件是死锁产生的必要条件,也就是说要产生死锁必须具备的条件,而不是存在这3个条件就一定产生死锁,那么只要在逻辑上回避了第四个条件就可以避免死锁。
避免死锁采用的是允许前三个条件存在,但通过合理的资源分配算法来确保永远不会形成环形等待的封闭进程链,从而避免死锁。
该方法支持多个进程的并行执行,为了避免死锁,系统动态的确定是否分配一个资源给请