2012年欧姆定律中考题集.doc

以下是整理自8月下旬至10月份内的各大公司的笔试面试三十题（注：所有题目基本上全部为软件开发方向，题目来源：网络收集），相信一定能给正在参加各种校招的诸多朋友多少帮助，学习参考或借鉴九月十月百度人搜，阿里巴巴，腾讯华为小米搜狗笔/面试五十题9月11日， 京东：谈谈你对面向对象编程的认识1 8月20日，金山面试，题目如下：数据库1中存放着a类数据，数据库2中存放着以天为单位划分的表30张（比如table_20110909,table_20110910,table_20110911）,总共是一个月的数据表1中的a类数据中有一个字段userid来唯一判别用户身份，表2中的30张表（每张表结构相同）也有一个字段userid来唯一识别用户身份如何判定a类数据库的多少用户在数据库2中出现过？百度实习笔试题（2012.5.6）简答题1一个单词单词字母交换，可得另一个单词，如army->mary，成为兄弟单词提供一个单词，在字典中找到它的兄弟描述数据结构和查询过程评点：同去年9月份的一道题，见此文第3题：简答题2线程和进程区别和联系什么是“线程安全”简答题3C和C++怎样分配和释放内存，区别是什么算法题1一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空，这两种情形都定义为null。

这样构成一个单链表给两条这样单链表，判断里面是否存在同样的urlurl以亿级计，资源不足以hash算法题2数组al[0,mid-1] 和 al[mid,num-1]，都分别有序将其merge成有序数组al[0,num-1]，要求空间复杂度O(1)系统设计题百度搜索框的suggestion,比如输入北京，搜索框下面会以北京为前缀，展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词如何设计使得空间和时间复杂度尽量低评点：老题，直接上Trie树+Hash，Trie树的介绍见：从Trie树（字典树）谈到后缀树2 人搜笔试3 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.编程题：一棵树的节点定义格式如下：struct Node{Node* parent;Node* firstChild; // 孩子节点Node* sibling; // 兄弟节点}要求非递归遍历该树思路：采用队列存储，来遍历节点。

5. 算法题：有N个节点，每两个节点相邻，每个节点只与2个节点相邻，因此，N个顶点有N-1条边每一条边上都有权值wi，定义节点i到节点i+1的边为wi求：不相邻的权值和最大的边的集合4 人搜面试，所投职位：搜索研发工程师：面试题回忆1、删除字符串开始及末尾的空白符，并且把数组中间的多个空格（如果有）符转化为1个2、求数组（元素可为正数、负数、0）的最大子序列和3、链表相邻元素翻转，如a->b->c->d->e->f-g，翻转后变为：b->a->d->c->f->e->g4、链表克隆链表的结构为：typedef struct list {int data; //数据字段list *middle; //指向链表中某任意位置元素(可指向自己)的指针list *next;//指向链表下一元素} list;5、100万条数据的数据库查询速度优化问题，解决关键点是：根据主表元素特点，把主表拆分并新建副表，并且利用存储过程保证主副表的数据一致性不用写代码）6、求正整数n所有可能的和式的组合（如；4=1+1+1+1、1+1+2、1+3、2+1+1、2+2）5 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模型6 网易有道二面：判断一个数字序列是BST后序遍历的结果，现场写代码7 8月30日，网易有道面试题var tt = 'aa';function test(){alert(tt);var tt = 'dd';alert(tt);}test();8 8月31日，百度面试题：不使用随机数的洗牌算法，9 9月6日，阿里笔试题：平面上有很多点，点与点之间有可能有连线，求这个图里环的数目10 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的情形排除出去9月8日，腾讯面试题：假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配， 比如：abcda和adabc,由于出现的字符个数都是相同，只是顺序不同， 所以这两个字符串是匹配的要求高效！又是跟上述第3题中简单题一的兄弟节点类似的一道题，我想，你们能想到的，11 阿里云，搜索引擎中5亿个url怎么高效存储；11 一道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){ ...}点评：healer_kx：补齐代码，最好是简洁的，别用库你可以写你的辅助函数，宏定义，代码风格也很重要ri_aje：struct rect 11 { 11 // axis alignment assumed 11 // bottom left is (x[0],y[0]), top right is (x[1],y[1]) 11 double x [2]; 11 double y [2]; 11 }; 1111 template T const& min (T const& x, T const& y) { return x T const& max (T const& x, T const& y) { return x>y ? x : y; } 1111 // return type changed to handle non-integer rects 11 double area (rect const& a, rect const& b) 11 { 11 // perfectly adjacent rects are considered having an intersection of 0 area 11 double const dx = min(a.x[1],b.x[1]) - max(a.x[0],b.x[0]); 11 double const dy = min(a.y[1],b.y[1]) - max(a.y[0],b.y[0]); 11 return dx>=0&&dy>=0 ? dx*dy : -1; 11 } 12 下面是一个简短的证明。

对于平行于坐标轴的矩形 r，假设其左下角点坐标为 (rx0,ry0)，右上角点坐标为 (rx1,ry1)，那么由 r 定义的无限有界点集为：{(x,y)|x in [rx0,rx1] && y in [ry0,ry1]}根据交集的定义，则任意二维点 (x,y) 在矩形 a,b 的交集内等价于{(x,y)|(x,y) in a 并且 (x,y) in b} <==>{(x,y)|x in [ax0,ax1] && x in [bx0,bx1] 并且 y in [ay0,ay1] && y in [by0,by1]} <==>{(x,y)|x in [max(ax0,bx0),min(ax1,bx1)] 并且 y in [max(ay0,by0),min(ay1,by1)]}因此，交集矩形的边长分别为 min(ax1,bx1)-max(ax0,bx0) 和 min(ay1,by1)-max(ay0,by0)注意当交集为空时(a,b 不相交)，则经此法计算出来的交集边长为负值，此事实可用于验证 a,b 的相交性鉴于笛卡尔积各个维度上的不相关性，此方法可扩展到任意有限维线性空间，比如，三维空间中平行于坐标轴的长方体的交集体积可以用类似的方法计算。

13 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，编号为。