曾记否,去年的10月份也同此刻一样,是找工作的高峰期,本博客便是最初由整理微软等公司面试题而发展而来的。如今,又即将迈入求职高峰期--10月份,而本人也正在找下一份工作中,所以,也不免关注了网上和我个人建的算法群Algorithms1-12群内朋友发布和讨论的最新面试题。特此整理,以飨诸位。至于答案,望诸位共同讨论与思考。
好久没有好好享受思考了。ok,任何人有任何意见或问题,欢迎不吝指导:
某服务器流量统计器,每天有1000亿的访问记录数据,包括时间、url、ip。设计系统实现记录数据的
保存、管理、查询。要求能实现一下功能:
(1)计算在某一时间段(精确到分)时间内的,某url的所有访问量。
(2)计算在某一时间段(精确到分)时间内的,某ip的所有访问量。
假设某个网站每天有超过10亿次的页面访问量,出于安全考虑,网站会记录访问客户端访问的ip地址和对应的时间,如果现在已经记录了1000亿条数据,想统计一个指定时间段内的区域ip地址访问量,那么这些数据应该按照何种方式来组织,才能尽快满足上面的统计需求呢,
设计完方案后,并指出该方案的优缺点,比如在什么情况下,可能会非常慢?(参考答案:用B+树来组织,非叶子节点存储(某个时间点,页面访问量),叶子节点是访问的IP地址。这个方案的优点是查询某个时间段内的IP访问量很快,但是要统计某个IP的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。或者可以建立二级索引,分别是时间和地点来建立索引。)
腾讯1.服务器内存1G,有一个2G的文件,里面每行存着一个QQ号(5-10位数),怎么最快找出出现过最多次的QQ号。(此题与稍后下文的第14题重复,思路参考请见下文第14题)。
腾讯2.如何求根号2的值,并且按照我的需要列出指定小数位,比如根号2是1.141 我要列出1位小数就是1.1 2位就是1.14, 1000位就是1.141...... 等。。
给定一个字符串的集合,格式如:{aaa bbb ccc}, {bbb ddd},{eee fff},{ggg},{ddd hhh}要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应输出{aaa bbb ccc ddd hhh},{eee fff}, {ggg}。
创新工场面试题:abcde五人打渔,打完睡觉,a先醒来,扔掉1条鱼,把剩下的分成5分,拿一份走了;b再醒来,也扔掉1条,把剩下的分成5份,拿一份走了;然后cde都按上面的方法取鱼。问他们一共打了多少条鱼,写程序和算法实现。提示:共打了多少条鱼的结果有很多。但求最少打的鱼的结果是3121条鱼(应该找这5个人问问,用什么工具打了这么多条鱼)。(http://blog.csdn.net/nokiaguy/article/details/6800209)。
ok,这13道题加上此前本博客陆陆续续整理的微软面试187题:重启开源,分享无限--诚邀你加入微软面试187题的解题中,至此,本博客内已经整理了整整200道面试题。
以下是后续整理的最新面试题,不断更新中(2011.09.26).....
14、腾讯最新面试题:服务器内存1G,有一个2G的文件,里面每行存着一个QQ号(5-10位数),怎么最快找出出现过最多次的QQ号。
以下是个人所建第Algorithms_12群内朋友的聊天记录:
首先你要注意到,数据存在服务器,存储不了(内存存不了),要想办法统计每一个qq出现的次数。
比如,因为内存是1g,首先 你用hash 的方法,把qq分配到10个(这个数字可以变动,比较)文件(在硬盘中)。
相同的qq肯定在同一个文件中,然后对每一个文件,只要保证每一个文件少于1g的内存,统计每个qq的次数,可以使用hash_map(qq, qq_count)实现。然后,记录每个文件的最大访问次数的qq,最后,从10个文件中找出一个最大,即为所有的最大。更多读者可以参见此文:海量数据处理面试题集锦与Bit-map详解 。那若面试官问有没有更高效率的解法之类的?这时,你可以优化一下,但是这个速度很快,hash函数,速度很快,他肯定会问,你如何设计,用bitmap也行。15、百度今天的笔试题:在一维坐标轴上有n个区间段,求重合区间最长的两个区间段。
16、华为社招现场面试1:请使用代码计算1234567891011121314151617181920*2019181716151413121110987654321 。
华为面试2:1分2分5分的硬币,组成1角,共有多少种组合。
17、百度笔试题:
一、系统有很多任务,任务之间有依赖,比如B依赖于A,则A执行完后B才能执行
(1)不考虑系统并行性,设计一个函数(Task *Ptask,int Task_num)不考虑并行度,最快的方法完成所有任务。
(2)考虑并行度,怎么设计
typedef struct{
int ID;
int * child;
int child_num;
}Task;
提供的函数:
bool doTask(int taskID);无阻塞的运行一个任务;
int waitTask(int timeout);返回运行完成的任务id,如果没有则返回-1;
bool killTask(int taskID);杀死进程二、必答题(各种const)
1、解释下面ptr含义和不同
double* ptr = &value;
//ptr是一个指向double类型的指针,ptr的值可以改变,ptr所指向的value的值也可以改变
const double* ptr = &value
//ptr是一个指向const double类型的指针,ptr的值可以改变,ptr所指向的value的值不可以改变
double* const ptr=&value
//ptr是一个指向double类型的指针,ptr的值不可以改变,ptr所指向的value的值可以改变
const double* const ptr=&value
//ptr是一个指向const double类型的指针,ptr的值不可以改变,ptr所指向的value的值也不可以改变2、去掉const属性,例: const double value = 0.0f; double* ptr = NULL;怎么才能让ptr指向value?
强制类型转换,去掉const属性,如ptr = <const_cast double *>(&value);18、如果用一个循环数组q[0..m-1]表示队列时,该队列只有一个队列头指针front,不设队列尾指针rear,求这个队列中从队列投到队列尾的元素个数(包含队列头、队列尾)(华赛面试题、腾讯笔试题)。
19、昨晚淘宝笔试题:
1. 设计相应的数据结构和算法,尽量高效的统计一片英文文章(总单词数目)里出现的所有英文单词,按照在文章中首次出现的顺序打印输出该单词和它的出现次数。
2、有一棵树(树上结点为字符串或者整数),请写代码将树的结构和数据写到一个文件中,并能通过读取该文件恢复树结构 。
20、13个球一个天平,现知道只有一个和其它的重量不同,问怎样称才能用三次就找到那个球?(http://zhidao.baidu.com/question/66024735.html
)。21、搜狗笔试题:一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素,即a[0]变为a[1]到a[n-1]的积,a[1]变为a[0]和a[2]到a[n-1]的积,...,a[n-1]为a[0]到a[n-2]的积(就是除掉当前元素,其他所有元素的积)。
程序要求:
要求具有线性复杂度。
不能使用除法运算符。思路:left[i]存储a[i]之前的乘积,right[i]存储a[i]之后的乘积,那么a[i]=left[i]*right[i] 。
不过,left的计算从左往右扫的时候得出,right是从右往左扫得出。因为就是当中某个元素的 左边所有元素与右边所有元素的乘积,就这么简单。所以计算a[i]=left[i]*right[i]时,直接出结果。
22、腾讯高水平复试题:
1.有不同的手机终端,如iphone,安卓,Symbian,不同的终端处理不一样,设计一种服务器和算法实现对不同的终端的处理。
2.设计一种内存管理算法。
3.A向B发邮件,B收到后读取并发送收到,但是中间可能丢失了该邮件,怎么设计一种最节省的方法,来处理丢失问题。
4.设计一种算法求出算法复杂度 。
23、人人笔试1:一个人上台阶可以一次上1个,2个,或者3个,问这个人上n层的台阶,总共有几种走法?人人笔试2:在人人好友里,A和B是好友,B和C是好友,如果A 和C不是好友,那么C是A的二度好友,在一个有10万人的数据库里,如何在时间0(n)里,找到某个人的十度好友。24、淘宝算法面试题:两个用户之间可能互相认识,也可能是单向的认识,用什么数据结构来表示?如果一个用户不认识别人,而且别人也不认识他,那么他就是无效节点,如何找出这些无效节点?自定义数据接口并实现之,要求尽可能节约内存和空间复杂度。25、淘宝笔试题:对于一颗完全二叉树,要求给所有节点加上一个pNext指针,指向同一层的相邻节点;如果当前节点已经是该层的最后一个节点,则将pNext指针指向NULL;给出程序实现,并分析时间复杂度和空间复杂度。26、腾讯面试题:给你5个球,每个球被抽到的可能性为30、50、20、40、10,设计一个随机算法,该算法的输出结果为本次执行的结果。输出A,B,C,D,E即可。27、搜狐笔试题:给定一个实数数组,按序排列(从小到大),从数组从找出若干个数,使得这若干个数的和与M最为接近,描述一个算法,并给出算法的复杂度。28、苹果面试题:write a function that will trigger a prefetch address abort exception。29、阿里巴巴研究院(2009):
1. 有无序的实数列V[N],要求求里面大小相邻的实数的差的最大值,关键是要求线性空间和线性时间2. 25匹赛马,5个跑道,也就是说每次有5匹马可以同时比赛。问最少比赛多少次可以知道跑得最快的5匹马3. 有一个函数int getNum(),每运行一次可以从一个数组V[N]里面取出一个数,N未知,当数取完的时候,函数返回NULL。现在要求写一个函数int get(),这个函数运行一次可以从V[N]里随机取出一个数,而这个数必须是符合1/N平均分布的,也就是说V[N]里面任意一个数都有1/N的机会被取出,要求空间复杂度为O(1)
30、微软面试题:Given a head pointer pointing to a linked list ,please write a function that sort the list
in increasing order. You are not allowed to use temporary array or memory copy
struct
{
int data;
struct S_Node *next;
}Node;
Node * sort_link_list_increasing_order (Node *pheader):
更新至2011.09.30....
当即早已进入10月份,十一过后,招聘,笔试,面试,求职渐趋火热。而在这一系列过程背后浮出的各大IT公司的笔试/面试题则蕴含着诸多思想与设计,细细把玩,思考一番亦能有不少收获。
上个月,本博客着重整理九月腾讯,创新工场,淘宝等公司最新面试十三题,此次重点整理百度,阿里巴巴,迅雷和搜索等公司最新的面试题。同上篇一样,答案望诸君共同讨论之,个人亦在慢慢思考解答。多谢。
如果你没看过, 也至少听说<人月神话> (The Mythical Man-month) 这本在软件工程领域很有影响的书. 当你在微软学术搜索中输入 “manmonth” 这个词的时候, 你会意外地碰到下面这个错误:
经过几次试验之后, 你发现必须要输入 “man-month” 才能得到希望的结果。 这不就是只差一个 ‘-’ 符号么? 为什么这个搜索引擎不能做得聪明一些, 给一些提示 (Query Suggestion)? 或者自动把用户想搜的结果展现出来 (Query Alteration)? 我们在输入比较长的英文单词的时候, 也难免会敲错一两个字母, 网站应该帮助用户, 而不是冷冰冰地拒绝用户啊。
微软的学术搜索 (Microsoft Academic Search) 索引了超过 3千万的文献, 2 千万的人名, 怎么能以比较小的代价, 对经常出现的输入错误提供提示? 或直接显示相关结果, 避免用户反复尝试输入的烦恼?
你可能会说, 这很难吧, 但是另一家搜索引擎似乎轻易地解决了这个问题 (谷歌,读者可以一试)。 所以, 还是有办法的。
这个题目要求你:
1) 试验不同的输入, 反推出目前微软的学术搜索是如何实现搜索建议 (Query Suggestion)的。
2) 提出自己的改进建议, 并论证这个解决方案在千万级数据规模上能达到 “足够好” 的时间 (speed) 和空间 (memory usage)效率。
3) 估计这事需要几个 人·月 (man-month) 才能做完? (备注:顺便给邹欣老师传个话,如果应届毕业生可以能做好上述全部三个题目,便可直接找他。http://www.cnblogs.com/xinz/archive/2011/10/10/2205232.html)。
tencent2012笔试题附加题
问题描述: 例如手机朋友网有n个服务器,为了方便用户的访问会在服务器上缓存数据,因此用户每次访问的时候最好能保持同一台服务器。
已有的做法是根据ServerIPIndex[QQNUM%n]得到请求的服务器,这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了,那么n就变为了n-1,那么ServerIPIndex[QQNUM%n]与ServerIPIndex[QQNUM%(n-1)]基本上都不一样了,所以大多数用户的请求都会转到其他服务器,这样会发生大量访问错误。
问: 如何改进或者换一种方法,使得:
(1)一台服务器死掉后,不会造成大面积的访问错误,
(2)原有的访问基本还是停留在同一台服务器上;
(3)尽量考虑负载均衡。(思路:往分布式一致哈希算法方面考虑。关于此算法,可参见此文:http://blog.csdn.net/21aspnet/article/details/5780831)
腾讯面试题:A.txt和B.txt两个文件,A.txt有1亿个QQ号 , B.txt 100W个QQ号, 用代码实现交、并、差。
说出下面的运行结果
#include <iostream>
using namespace std;
class A
{
public:
virtual void Fun(int number = 10)
{
std::cout << "A::Fun with number " << number<<endl;
}
};
class B: public A
{
public:
virtual void Fun(int number = 20)
{
std::cout << "B::Fun with number " << number<<endl;
}
};
int main()
{
B b;
A &a = b;
a.Fun();
return 0;
} //虚函数动态绑定=>B,非A,缺省实参是编译时候确定的=>10,非20 。
今晚阿里云笔试:有101根电线 每根的一头在楼底 另一端在楼顶 有一个灯泡 一个电池 无数根很短的电线 怎么样在楼上一次在楼下去一次将电线的对应关系弄清楚。
淘宝:
在现代web服务系统的设计中,为了减轻源站的压力,通常采用分布式缓存技术,其原理如下图所示,前端的分配器将针对不同内容的用户请求分配给不同的缓存服务器向用户提供服务。
分配器
/ | \
缓存 缓存 . ..缓存
服务器1 服务器2 ...服务器n
1)请问如何设置分配策略,可以保证充分利用每个缓存服务器的存储空间(每个内容只在一个缓存服务器有副本)
2)当部分缓存服务器故障,或是因为系统扩容,导致缓存服务器的数量动态减少或增加时,你的分配策略是否可以保证较小的缓存文件重分配的开销,如果不能,如何改进?
3)当各个缓存服务器的存储空间存在差异时(如有4个缓存服务器,存储空间比为4:9:15:7),如何改进你的策略,按照如上的比例将内容调度到缓存服务器?(思路:往memcached或者一致性hash算法方面考虑,但具体情况,具体分析。)
腾讯:50个台阶,一次可一阶或两阶,共有几种走法(老掉牙的题了,详见微软面试100题2010版)。
有两个float型的数,一个为fmax,另一个为fmin,还有一个整数n,如果 (fmax - fmin)/n ,不能整除,怎么改变fmax,fmin,使改变后可以整除n 。
2011.10.11最新百度电面:
1、动态链接库与静态链接库的区别
2、指针与引用的区别
3、进程与线程的区别
4、函数调用入栈出栈的过程
4、c++对象模型与虚表
5、海量数据处理,以及如何解决Hash冲突等问题
6、系统设计,概率算法
今天腾讯面试:
一个大小为N的数组,里面是N个整数,怎样去除重复,
要求时间复杂度为O(n),空间复杂度为O(1).
一个长度为10000的字符串,写一个算法,找出最长的重复子串,如abczzacbca,结果是bc(思路:后缀树/数组的典型应用,@well:就是求后缀数组的height[]的最大值
)。
更多面试题,参见横空出世,席卷Csdn--评微软等数据结构+算法面试100题 (在此文中,集结了本博客已经整理的236道面试题)。
此些面试题看多了,自然会发现题目类型可能会千变万化,但解决问题的思路却只有那么几种。再者,写代码的时候,很多的细节需要务必注意,如返回值,函数参数的检查,特殊情况的处理等等,这是一个代码规范性的问题。在结文之前,有三事须说明:
ok,日后一有最新的面试题,再整理,有任何问题,欢迎在本文评论下指出或来信指导(zhoulei0907@yahoo.cn),谢谢。July、2011.10.09。http://blog.csdn.net/v_july_v/article/details/6855788
联系客服