2013年校园招聘:IT公司笔试题精选

  • 9月11日, 京东:
    谈谈你对面向对象编程的认识
  • 8月20日,金山面试,题目如下:
    数据库1中存放着a类数据,数据库2中存放着以天为单位划分的表30张(比如table_20110909,table_20110910,table_20110911),总共是一个月的数据。表1中的a类数据中有一个字段userid来唯一判别用户身份,表2中的30张表(每张表结构相同)也有一个字段userid来唯一识别用户身份。如何判定a类数据库的多少用户在数据库2中出现过?
    来源:http://topic.csdn.net/u/20120820/23/C6B16CCF-EE15-47C0-9B15-77497291F2B9.html
  • 百度实习笔试题(2012.5.6)
    1、一个单词单词字母交换,可得另一个单词,如army->mary,成为兄弟单词。提供一个单词,在字典中找到它的兄弟。描述数据结构和查询过程。评点同去年9月份的一道题,见此文第3题:http://blog.csdn.net/v_july_v/article/details/6803368
    2、线程和进程区别和联系。什么是“线程安全”
    3、C和C++怎样分配和释放内存,区别是什么
    4、算法题1
    一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空,这两种情形都定义为null。这样构成一个单链表。给两条这样单链表,判断里面是否存在同样的url。url以亿级计,资源不足以hash。
    5、算法题2
    数组al[0,mid-1] 和 al[mid,num-1],都分别有序。将其merge成有序数组al[0,num-1],要求空间复杂度O(1)
    6、系统设计题
    百度搜索框的suggestion,比如输入“北京”,搜索框下面会以北京为前缀,展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词,输入“结构之”,会提示“结构之法”,“结构之法 算法之道”等搜索词。
    请问,如何设计此系统,使得空间和时间复杂度尽量低。评点老题,直接上Trie树「Trie树的介绍见:从Trie树(字典树)谈到后缀树」+TOP Khashmap+堆,hashmap+堆 统计出如10个近似的热词,也就是说,只存与关键词近似的比如10个热词? or  Double-array trie tree同时,StackOverflow上也有两个讨论帖子:http://stackoverflow.com/questions/2901831/algorithm-for-autocompletehttp://stackoverflow.com/questions/1783652/what-is-the-best-autocomplete-suggest-algorithm-datastructure-c-c。此外,这里有一篇关于“拼写错误检查”问题的介绍,或许对你有所启示:http://blog.afterthedeadline.com/2010/01/29/how-i-trie-to-make-spelling-suggestions/

  • 人搜笔试
    1. 快排每次以第一个作为主元,问时间复杂度是多少?(O(N*logN))
    2. T(N) = N + T(N/2)+T(2N), 问T(N)的时间复杂度是多少? 点评:O(N*logN) or O(N)?
    3. 从(0,1)中平均随机出几次才能使得和超过1?(e)
    4.编程题:
    一棵树的节点定义格式如下:
    [cpp]
    struct Node{
    Node* parent;
    Node* firstChild; // 孩子节点
    Node* sibling; // 兄弟节点
    }
    [/cpp]

    要求非递归遍历该树。
    思路:采用队列存储,来遍历节点。
    5. 算法题:
    有N个节点,每两个节点相邻,每个节点只与2个节点相邻,因此,N个顶点有N-1条边。每一条边上都有权值wi,定义节点i到节点i+1的边为wi。
    求:不相邻的权值和最大的边的集合。

  • 人搜面试,所投职位:搜索研发工程师:面试题回忆
    1、删除字符串开始及末尾的空白符,并且把数组中间的多个空格(如果有)符转化为1个。
    2、求数组(元素可为正数、负数、0)的最大子序列和。
    3、链表相邻元素翻转,如a->b->c->d->e->f-g,翻转后变为:b->a->d->c->f->e->g
    4、链表克隆。链表的结构为:
    [cpp]
    typedef struct list {
    int data; //数据字段
    list *middle; //指向链表中某任意位置元素(可指向自己)的指针
    list *next;//指向链表下一元素
    } list;
    [/cpp]

    5、100万条数据的数据库查询速度优化问题,解决关键点是:根据主表元素特点,把主表拆分并新建副表,并且利用存储过程保证主副表的数据一致性。(不用写代码)
    6、求正整数n所有可能的和式的组合(如;4=1+1+1+1、1+1+2、1+3、2+1+1、2+2)。点评:这里有一参考答案:http://blog.csdn.net/wumuzi520/article/details/8046350
    7、求旋转数组的最小元素(把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1)
    8、找出两个单链表里交叉的第一个元素
    9、字符串移动(字符串为*号和26个字母的任意组合,把*号都移动到最左侧,把字母移到最右侧并保持相对顺序不变),要求时间和空间复杂度最小
    10、时间复杂度为O(1),怎么找出一个栈里的最大元素
    11、线程、进程区别
    12、static在C和C++里各代表什么含义
    13、const在C/C++里什么意思
    14、常用linux命令
    15、解释Select/Poll模型

  • 8月30日,网易有道面试题
    [cpp]
    var tt = ‘aa’;
    function test()
    {
    alert(tt);
    var tt = ‘dd’;
    alert(tt);
    }
    test();
    [/cpp]
  • 9月6日,阿里笔试题:平面上有很多点,点与点之间有可能有连线,求这个图里环的数目。
  • 9月7日,一道华为上机题:
    题目描述: 选秀节目打分,分为专家评委和大众评委,score[] 数组里面存储每个评委打的分数,judge_type[] 里存储与 score[] 数组对应的评委类别,judge_type == 1,表示专家评委,judge_type == 2,表示大众评委,n表示评委总数。打分规则如下:专家评委和大众评委的分数先分别取一个平均分(平均分取整),然后,总分 = 专家评委平均分 * 0.6 + 大众评委 * 0.4,总分取整。如果没有大众评委,则 总分 = 专家评委平均分,总分取整。函数最终返回选手得分。
    函数接口 int cal_score(int score[], int judge_type[], int n)
    上机题目需要将函数验证,但是题目中默认专家评委的个数不能为零,但是如何将这种专家数目为0的情形排除出去。
    来源:http://topic.csdn.net/u/20120907/15/c30eead8-9e49-41c2-bd11-c277030ad17a.html
  • 9月8日,腾讯面试题:
    假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,
    比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,
    所以这两个字符串是匹配的。要求高效!
    又是跟上述第3题中简单题一的兄弟节点类似的一道题,我想,你们能想到的,这篇blog里:http://blog.csdn.net/v_JULY_v/article/details/6347454都已经有了。
  • 阿里云,搜索引擎中5亿个url怎么高效存储;
  • 一道C++笔试题,求矩形交集的面积:
    在一个平面坐标系上,有两个矩形,它们的边分别平行于X和Y轴。
    其中,矩形A已知, ax1(左边), ax2(右边), ay1(top的纵坐标), ay2(bottom纵坐标). 矩形B,类似,就是 bx1, bx2, by1, by2。这些值都是整数就OK了。
    要求是,如果矩形没有交集,返回-1, 有交集,返回交集的面积。
    int area(rect const& a, rect const& b)
    {

    }来源:http://topic.csdn.net/u/20120913/18/bc669d60-b70a-4008-be65-7c342789b925.html
  • 2012年创新工场校园招聘最后一道笔试题:工场很忙
    创新工场每年会组织同学与项目的双选会,假设现在有M个项目,编号从1到M,另有N名同学,编号从1到N,每名同学能选择最多三个、最少一个感兴趣的项目。选定之后,HR会安排项目负责人和相应感兴趣的同学一对一面谈,每次面谈持续半小时。由于大家平时都很忙,所以咱们要尽量节约时间,请你按照以下的条件设计算法,帮助HR安排面试。
    1)同学很忙。项目负责人一次只能与一名同学面谈,而同学会在自己第一个面试开始时达到工场,最后一个面试结束后离开工场,如果参加一个项目组的面试后不能立即参加下一个项目组的面试,就必须在工场等待。所以请尽可能让同学的面试集中在某一时间段,减少同学在工场等待的时间。
    2)项目负责人很忙。众所周知,创业团队的负责人会有很多事情要做,所以他们希望能够将自己参与的面试集中在某一段时间内,请在保证1)的情况下,使得项目负责人等待的时间最少。
    3)HR很忙。从第一轮面试开始以后,所有HR都必须等到最后一轮面试结束,所以需要在保证1)和2)的同时,也能尽快解放掉所有的HR,即让第一轮面试到最后一轮面试之间持续的时间最短。
    输入(以文件方式输入,文件名为iw,例如iw.in):
    第1行…第n行:同学的编号 项目的编号
    样例(数据间用空格隔开,两个0表示输入结束):
    1 1
    1 2
    1 3
    2 1
    3 1
    3 2
    0 0
    表示M=3,N=3,编号为1的同学选择了项目1,2和3,编号为2的同学选择了项目1,编号为3的同学选了项目1和2
    输出(以文件方式输出,文件名为iw,例如iw.out):
    第1行:编号为1的项目依次面试新同学的编号序列
    第2行:编号为2的项目依次面试新同学的编号序列

    第n行:编号为n的项目依次面试新同学的编号序列
    样例(数据间用空格隔开,0表示没有面试):
    1 3 2
    3 1 0
    0 0 1
    表示编号为1的项目在第一轮面试编号为1的同学,第二轮面试编号为3的同学,第三轮面试编号为2的同学
    编号为2的项目在第一轮面试编号为3的同学,第二轮面试编号为1的同学,第二轮不用面试
    编号为3的项目在第一轮和第二轮都不用面试,第三轮面试编号为1的同学
    链接:http://t.qq.com/p/t/108332110988802
  • 4**9 的笔试题,比较简单:
    1.求链表的倒数第二个节点
    2.有一个整数数组,求数组中第二大的数
  • 阿里巴巴二道题
    第一道:
    对于给定的整数集合S,求出最大的d,使得a+b+c=d。a,b,c,d互不相同,且都属于S。集合的元素个数小于等于2000个,元素的取值范围在[-2^28,2^28 – 1],假定可用内存空间为100MB,硬盘使用空间无限大,试分析时间和空间复杂度,找出最快的解决方法。
    点评:
    @绿色夹克衫:两两相加转为多项式乘法,比如(1 2 4 6) + (2 3 4 5) => (x + x^2 + x^4 + x^6)*(x^2 + x^3 + x^4 + x^5) 。更多思路请见这http://www.51nod.com/answer/index.html#!answerId=569
    阿里巴巴第二道(研发类)
    笔试题1,原题大致描述有一大批数据,百万级别的。数据项内容是:用户ID、科目ABC各自的成绩。其中用户ID为0~1000万之间,且是连续的,可以唯一标识一条记录。科目ABC成绩均在0~100之间。有两块磁盘,空间大小均为512M,内存空间64M。
    1) 为实现快速查询某用户ID对应的各科成绩,问磁盘文件及内存该如何组织;
    2) 改变题目条件,ID为0~10亿之间,且不连续。问磁盘文件及内存该如何组织;
    3) 在问题2的基础上,增加一个需求。在查询各科成绩的同时,获取该用户的排名,问磁盘文件及内存该如何组织。
    笔试题2:代码实现计算字符串的相似度。
    点评:和计算两字符串的最长公共子序列相似。
    设Ai为字符串A(a1a2a3 … am)的前i个字符(即为a1,a2,a3 … ai)
    设Bj为字符串B(b1b2b3 … bn)的前j个字符(即为b1,b2,b3 … bj)
    设 L(i , j)为使两个字符串和Ai和Bj相等的最小操作次数。
    当ai等于bj时 显然L(i, j)=L(i-1, j-1)
    当ai不等于bj时
    若将它们修改为相等,则对两个字符串至少还要操作L(i-1, j-1)次
    若删除ai或在Bj后添加ai,则对两个字符串至少还要操作L(i-1, j)次
    若删除bj或在Ai后添加bj,则对两个字符串至少还要操作L(i, j-1)次
    此时L(i, j)=min( L(i-1, j-1), L(i-1, j), L(i, j-1) )  + 1
    显然,L(i, 0)=i,L(0, j)=j, 再利用上述的递推公式,可以直接计算出L(i, j)值。具体代码请见这:http://blog.csdn.net/flyinghearts/article/details/5605996
  • 9月14日,小米笔试,给一个浮点数序列,取最大乘积子序列的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积子序列为3,0.5,8。
    点评:
    解法一、
    或许,读者初看此题,自然会想到最大乘积子序列问题类似于最大子数组和问题:http://blog.csdn.net/v_JULY_v/article/details/6444021,然实则具体处理起来诸多不同,为什么呢,因为乘积子序列中有正有负也还可能有0。
    既如此,我们可以把问题简化成这样:数组中找一个子序列,使得它的乘积最大;同时找一个子序列,使得它的乘积最小(负数的情况)。因为虽然我们只要一个最大积,但由于负数的存在,我们同时找这两个乘积做起来反而方便。也就是说,不但记录最大乘积,也要记录最小乘积。So,
    我们让maxCurrent表示当前最大乘积的candidate,
    minCurrent反之,表示当前最小乘积的candidate。
    (用candidate这个词是因为只是可能成为新一轮的最大/最小乘积),
    而maxProduct则记录到目前为止所有最大乘积candidates的最大值。
    由于空集的乘积定义为1,在搜索数组前,maxCurrent,minCurrent,maxProduct都赋为1。
    假设在任何时刻你已经有了maxCurrent和minCurrent这两个最大/最小乘积的candidates,新读入数组的元素x(i)后,新的最大乘积candidate只可能是maxCurrent或者minCurrent与x(i)的乘积中的较大者,如果x(i)<0导致maxCurrent<minCurrent,需要交换这两个candidates的值。
    当任何时候maxCurrent<1,由于1(空集)是比maxCurrent更好的candidate,所以更新maxCurrent为1,类似的可以更新minCurrent。任何时候maxCurrent如果比最好的maxProduct大,更新maxProduct。
    变种
    此外,此题还有另外的一个变种形式,即给
    定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合中乘积最大的一组,并写出算法的时间复杂度。
    我们可以把所有可能的(N-1)个数的组合找出来,分别计算它们的乘积,并比较大小。由于总共有N个(N-1)个数的组合,总的时间复杂度为O(N2),显然这不是最好的解法。
    OK,以下解答来自编程之美

发表评论

电子邮件地址不会被公开。 必填项已用*标注