设计公司网站建设模板图,世界购物网站排名,免费咨询医生的软件,集艾设计公司官网九月腾讯#xff0c;创新工场#xff0c;淘宝等公司最新面试三十题
引言 曾记否#xff0c;去年的10月份也同此刻一样#xff0c;是找工作的高峰期#xff0c;本博客便是最初由整理微软等公司面试题而发展而来的。如今#xff0c;又即将迈入求职高峰期--10月份#… 九月腾讯创新工场淘宝等公司最新面试三十题
引言 曾记否去年的10月份也同此刻一样是找工作的高峰期本博客便是最初由整理微软等公司面试题而发展而来的。如今又即将迈入求职高峰期--10月份而本人也正在找下一份工作中所以也不免关注了网上和我个人建的算法群Algorithms1-12群内朋友发布和讨论的最新面试题。特此整理以飨诸位。至于答案望诸位共同讨论与思考。
最新面试十三题 好久没有好好享受思考了。ok任何人有任何意见或问题欢迎不吝指导
五只猴子分桃。半夜第一只猴子先起来它把桃分成了相等的五堆多出一只。于是它吃掉了一个拿走了一堆 第二只猴子起来一看只有四堆桃。于是把四堆合在一起分成相等的五堆又多出一个。于是它也吃掉了一个拿走了一堆.....其他几只猴子也都是 这样分的。问这堆桃至少有多少个朋友说这是小学奥数题。 参考答案先给这堆桃子加上4个,设此时共有X个桃子,最后剩下a个桃子.这样: 第一只猴子分完后还剩:(1-1/5)X(4/5)X; 第二只猴子分完后还剩:(1-1/5)2X; 第三只猴子分完后还剩:(1-1/5)3X; 第四只猴子分完后还剩:(1-1/5)4X; 第五只猴子分完后还剩:(1-1/5)5X(1024/3125)X; 得:a(1024/3125)X; 要使a为整数,X最小取3125. 减去加上的4个,所以,这堆桃子最少有3121个。已知有个rand7()的函数返回1到7随机自然数让利用这个rand7()构造rand10() 随机1~10。 参考答案这题主要考的是对概率的理解。程序关键是要算出rand101到10十个数字出现的考虑都为10%.根据排列组合连续算两次rand7出现的组合数是7*749这49种组合每一种出现考虑是相同的。怎么从49平均概率的转换为1到10呢方法是 1.rand7执行两次出来的数为a1.a2. 2.如果a1*7a240,b(a1*7a2)/101,如果a1*7*a240,重复第一步。参考代码如下所示 int rand7() { return rand()%71; } int rand10() { int a71,a72,a10; do { a71 rand7()-1; a72 rand7()-1; a10 a71 *7 a72; } while (a10 40); return (a71*7a72)/41; } 如果两个字符串的字符一样但是顺序不一样被认为是兄弟字符串问如何在迅速匹配兄弟字符串如bad和adb就是兄弟字符串。要求设计一个DNS的Cache结构要求能够满足每秒5000以上的查询满足IP数据的快速插入查询的速度要快。一个未排序整数数组有正负数重新排列使负数排在正数前面并且要求不改变原来的正负数之间相对顺序 比如 input: 1,7,-5,9,-12,15 ans: -5,-12,1,7,9,15 要求时间复杂度O(N),空间O(1) 。此题一直没看到令我满意的答案一般达不到题目所要求的时间复杂度O(N),空间O(1)且保证原来正负数之间的相对位置不变。淘宝面试题有一个一亿节点的树现在已知两个点找这两个点的共同的祖先。海量数据分布在100台电脑中想个办法高效统计出这批数据的TOP10。此题请参考本博客内其它文章。 某服务器流量统计器每天有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。我们有很多瓶无色的液体其中有一瓶是毒药其它都是蒸馏水实验的小白鼠喝了以后会在5分钟后死亡而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠请问一下我们用这五只小白鼠5分钟的时间能够检测多少瓶液体的成分 淘宝2012笔试研发类http://topic.csdn.net/u/20110922/10/e4f3641a-1f31-4d35-80da-7268605d2d51.html一参考答案。 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 。 华为面试21分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 ptrvalue //ptr是一个指向double类型的指针ptr的值不可以改变ptr所指向的value的值可以改变 const double* const ptrvalue //ptr是一个指向const double类型的指针ptr的值不可以改变ptr所指向的value的值也不可以改变2、去掉const属性例 const double value 0.0f; double* ptr NULL;怎么才能让ptr指向value 强制类型转换去掉const属性如ptr const_cast double *(value); http://topic.csdn.net/u/20110925/16/e6248e53-1145-4815-8d24-9c9019d24bd8.html?seed1665205011r75709169#r_75709169 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的二度好友在一个有万人的数据库里如何在时间里找到某个人的十度好友。 24、淘宝算法面试题两个用户之间可能互相认识也可能是单向的认识用什么数据结构来表示如果一个用户不认识别人而且别人也不认识他那么他就是无效节点如何找出这些无效节点自定义数据接口并实现之要求尽可能节约内存和空间复杂度。 25、淘宝笔试题对于一颗完全二叉树要求给所有节点加上一个pNext指针指向同一层的相邻节点如果当前节点已经是该层的最后一个节点则将pNext指针指向NULL给出程序实现并分析时间复杂度和空间复杂度。 26、腾讯面试题给你5个球每个球被抽到的可能性为30、50、20、40、10设计一个随机算法该算法的输出结果为本次执行的结果。输出ABCDE即可。 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的机会被取出要求空间复杂度为O1 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.... 如果各位对上面的题目有好的思路或者还有好的面试题分享欢迎添加到本文评论下或者发至我的邮箱zhoulei0709yahoo.cn。谢谢大家。July、2011.09.30。
