首页 > > 我们仍未知道那天所遇到的面试题的答案

我们仍未知道那天所遇到的面试题的答案

2015年1月28日 发表评论 阅读评论

好吧,两个月,终于把论文送审了,唉,盲审什么的最讨厌了!!回过头来也发现了,一月还没写过博文,所以随便搞一篇应付一下好了。。嗯,交了论文的人,生活就是这么颓废!!

毛驴作为老板的助教,某天在思考第二天要不要去监考的人生大事,然后我脑海中发生了以下思考经历:

啊,说起来,我上一次监考好像还是作为课代表的时候吧。
=>学生作为监考官是不是有种翻身做主人的感觉?
=>说起来我搞不好几年内也会变成面试官呢~
=>啊咧?面试官,我能胜任么?
=>话说问些什么题好呢?
=>然后开始各种脑洞。。
=>要不整理一篇校招面试遇到的题目的总集吧,拿自己当年被问的题来问别人好像挺微妙的。。
=>于是,我终于把这篇博文扯到正题这里来了。。。


所以,下文中95%是今年校招中我遇到的可以公开(也许)的面试题,剩余小部分是有印象的笔试题。。但愿可以帮到来年校招的少年们。。

至于你问我为什么记得这么多的话,其实题目来源于以下几个部分,第一个自然就是我印象深刻的面试题,第二就是有些面试过后我会在回去的公交车上拿出小本子记录一下一些不确定的面试题以便回去考证,第三就是找工作期间和一些人聊了QQ,互相讨论过一些面试题,直接翻聊天记录得到。还有就是电话面试的录音。。

以下带有手写符号的表示面试中需要当场在纸上写出代码的,否则就是口头描述算法。另外面试题目其实很多都在网上可以找到,而且描述比我文中好很多倍,但是一题一题去找太麻烦了,我还是用我自己的话来描述吧。。如有不清晰的说明还望提出。。就酱~


算法

0x00手写给定字符串,找出第一个出现一次的字符。

0x01手写图的DFS和BFS算法,都不许用递归

0x02手写给定一个字符串数组,根据其第一个出现的数字来排序,比如asd123zc,w1,dsdsadad10,第一个出现的数字分别是123,1,10,所以排序结果是w1,dsdsadad10,asd123zc。

0x03NDA大法封印大法

0x04NDA大法封印大法

0x05NDA大法封印大法

0x06NDA大法封印大法

0x07手写字符串中单词位置翻转,比如把"the sky is blue"变成"blue is sky the"。(leetcode链接)。

0x08手写从一个数组中,找出单调递增的最长子序列(LIS问题)。

0x09:提取C语言中所有注释【设计状态机即可】。

0x0A手写比如有字符串“11122333388888881”,可以统计字数三个一,两个2,四个3等等,所以变成3122437811(其中每一个都用uchar来表示)

0x0B:上一题中,如果有不少字符串是12345678,这样“压缩”反而增大存储空间(变成1112131415161718),如何在基本思想不变情况下优化上述压缩算法】。

0x0C手写给定(x,y),表示一个点在原点,另一个对角点在(x,y)的矩形,其中x,y大于0,给定这样一堆矩形,求覆盖总面积。

0x0D手写给定一个数字n表示有n个石头,还有一个数组x[1,2,3...m],双方轮流从n个石头里面拿走一定数目的石头,拿走的数目必须出现在数组x[i]中,判断先拿是否必胜。『我居然傻乎乎地写了个α-β剪枝的代码。。』

0x0E手写定义一种操作可以交换一个数某个节点的左右子树,给定两棵树,判断可否通过有限次数的操作将其变成完全一样。

0x0F手写给定一个字符串和一个字符串数组,通过加空格的方式返回该字符串所有可能组成的句子。比如s = "catsanddog”,dict = ["cat", "cats", "and", "sand", "dog”],那么返回 ["cats and dog", "cat sand dog"].(Leetcode

0x10:类似魔兽争霸这种游戏,给定一个矩形作为全地图,划定一些区域为不可达的区域,给两个点,判断两个点是否联通。

0x11:上一问中,如何给出最短路径?不太需要考虑计算机中的实现,比如圆形区域就是完美的圆,切线可精确求解的那种。。『不是网易游戏的面试题。。』

0x12:计算平面上n个矩形的覆盖总面积。【可以先不考虑三个以上矩形叠在一个地方那种情况】

0x13:为了找出某个程序中运行时间最长的函数来进行优化,可以利用勾子在每个函数开始运行和结束运行都分别打印一条日志,比如开始的话打印fun1 00:10:03 BEGIN,结束的话打印fun2 00:14:12 END,找出运行时间最大的10个函数。【注意考虑子函数调用递归

0x14手写移除一个英文字符串中多余的空格,也就是大于等于两个以上的空格变成一个。

0x15:有一个邮件系统会记录所有收发邮件的ip地址,按时间顺序存下来,假设给定规则,一秒内发送次数超过k1,或者一分钟内发送次数超过k2,或者一个小时内超过k3的ip直接拉黑,如何实现实时检测系统,最后计算算法所需内存大小约为多少。『当年鹅厂实习的时候那边的导师给我讲过类似的问题,直接秒~』

0x16手写两个数组,每个数组的元素都是一个闭区间,每个数组内的所有元素区间两两不重叠,合并两个数组的所有区间。(基本类似leetcode上的这道题这道题,但是麻烦一点)『面试的时候这道题尼马写了我半天,最后居然一遍过!开心死』

0x17手写带权二叉树最长路径,权值可以为负

0x18手写排序数组中找出全部和为k的两个数组合。『老题。。』

0x19手写二叉查找树转链表。(leetcode

0x1A:判断一个点在不在多边形里面,至少两种方法。『多亏当年自娱自乐写某个引擎的时候研究过这个。。』

0x1B:上30层楼梯,每次可以上一层或两层,其中10和20层不允许踩,有多少种走法。『最关键的两个字说出来,这道题直接pass~』

0x1C:如何优化快排,优化主要是指优化最坏情况。

0x1D手写实现大整数加法。『自然不用说,正数负数都要,一小时内完成』

0x1E手写有一个函数,1/3概率返回1,2/3概率返回0,利用它们写一个函数,1/2概率返回1,1/2概率返回0。

0x1F:如何放大一张图片?

0x20手写倒置链表。

0x21:给定n个点,没有两个点x轴的值相同,连接任意两个点得到一条直线,找出直线斜率最大的两个点。『我觉得某次面试能过就是因为当场想出这道题来。。』

0x22:给四个排好序的数组,合并成一个排序数组。(要求代码要具有很好的可拓展性高效!比如随时可以合并100个数组)

0x23手写给定一个字符串,长度为n,再给四个整数,0<=a1<a2<a3<4<n,将字符串中索引为a1-a2的部分和a3-a4的部分交换。

0x24手写写出一个字符串算式的计算器,包含加减乘除括号。『只给20分钟简直要死。。』

0x25:海量数据中找出第k大的数。


基础知识

0x00:智能指针实现原理

0x01:阐述python垃圾回收机制

0x02手写vector的push_back()函数。(使用template,重点关注赋值应该怎么实现)

0x03:malloc和new的区别,如何实现,工作原理是什么?

0x04:new一个int和new一个int数组,有什么区别?

0x05:delete的时候加不加中括号有什么区别?

0x06:new一个类和类的数组,delete加不加中括号有什么区别?

0x07:delete基本类型数组和自定义类型数组的区别?

0x08:一个进程中不断new或者malloc,会在什么区出现什么问题?

0x09:如何防止一个类被复制?

0x0A:如何实现一个类,实例只允许在堆上进行构造?

0x0B:全局变量,局部变量,局部静态变量分别存储在什么地方?

0x0C:哪些排序算法是稳定的,如何判断其是不是稳定的。

0x0D:const跟指针结合有几种情况?

0x0E:const的实现原理?

0x0F:C++中如何调用C的代码?

0x10:string是怎么实现的,用起来有什么技巧?(面试官让我回去好好多读书。。)

0x11:重载和重写的区别,其分别的实现原理。

0x12:虚函数的实现原理。

0x13:多继承下的虚函数表排列。

0x14:构造函数可以是虚函数么?析构函数可以是虚函数么?如果有,作用是什么?

0x15:程序调试断点是如何实现的?

0x16:函数调用栈空间大约多大?

0x17:根据以下现象判断程序出错原因有哪些:

  • 100000次循环的数值计算,监视中间变量,总是在5万多次左右时结果开始出错,次数随机,有时5万多,有时6万多,程序没崩溃
  • 运行中没响应,CPU占用率100%
  • 运行中崩溃,提示堆栈溢出
  • 运行崩溃,报segmentfault
  • 提示内存非法访问,gdb查看函数调用堆栈,发现堆栈错乱

0x18:放掉100k个数据的vector的所有内存用什么函数。『面试官说函数不偏,只不过我平时不这么用所以不知道,然后另一场面试问了另一个面试官这个问题,被告知结果后,尼马我觉得还是挺偏的。。』

0x19:如何判断程序内存泄露,要给出多种检测方案。

0x1A:拷贝构造函数申明怎么写,这种题长着一脸就是问你A(const A a)为什么错的样子。。

0x1B:要求某一个函数执行完之后,全局变量g1的值一定要变成0,而这个函数可能中间某个for循环就return掉,或者中间抛出异常直接跳出这个函数了,要如何实现?

0x1C:STL的vector大小从0动态增长到n需要多少次内存重新分配。

0x1D:实现宏#define middle(a,b,c)『我一开始抖机灵写a+b+c-max(a,max(b,c))-min(a,min(b,c))然后一直被追问有哪些隐含问题,结果最后只答出可能溢出这个可能。。』

0x1E:用goto重写for(i=0;i< =n;i++){dosmth();}


数据结构

0x00:如何提高链表随机读取速度?

0x01:设计数据结构存储课程信息,每个课程包含多个章节,每个章节包含多个小节等。。

0x02:如何从海量数据中查找某一个数据在不在,并计算每次查找平均磁盘读取次数。

0x03:设计一个堆栈,可以o(1)时间实现入栈,出栈,返回最小值,返回最大值。『烂大街的题目』

0x04:设计一个堆栈,可以0(1)时间实现返回最小值,返回最大值,返回中位数,但是入栈出栈可以慢一点,一点,点。。。【算法最坏情况不能比平均情况差太多,换言之,要稳定】

0x05:说明STL中vector,map,set的实现。

0x06:不用数据结构课程中讲到的解决哈希冲突的方法,还有什么办法?


数学

0x00:甲乙丙丁四个人比赛,允许排名并列,有多少种结果?【Vespaの补充提问:如果有n个人,如何通过变成快速计算】

0x01伪码9宫格解锁密码长度为9,总共有多少种密码?

0x02:证明根号3是无理数。

0x03:x轴正半轴上n个点,y轴正半轴上m个点,两两连接x轴和y轴上的点,最多可以得到多少个交点?【面试时要给出化简后的结果】

0x04:一杯一升的水和一升的酒,从水中取出10%加入酒中,搅匀,然后酒中取出10%加入水中,搅匀,请问水中的酒的含量和酒中的水的含量哪个高?(最好不要做任何计算来解释)

0x05:x1+x2+x3+x4=30,x1>=2,x2>=0,x3>=-5,x4>=8,有几种整数解?『纳尼?你问我怎么记得这么清楚?电话面试我当然会录音啦~』

0x06:能不能在边长为2的正三角形内部放5个点,使得两两距离大于1?其实这是一道证明题。。

0x07:有一运煤车,最多装1千吨煤,每走一公里消耗一吨煤,起点有三千吨煤,运到一千公里处,最多剩多少吨煤?『以前专门研究过最多能走多远的问题,结果在三个面试官“注目”下,最后还是没算对。。』

0x08:1到1370有多少个数字1?(Vespaの补充提问:如何写程序快速计算出来?)

0x09:a,b,c,d,e依次入栈出栈,有多少种出栈顺序?(Vespaの补充提问:如何写程序快速计算出来n个数的情况?)

0x0A:一天24小时分针和时针重叠多少次?

0x0B:彩票35选6中4的概率是多少?

0x0C:最小二乘法的意义和用处,并推导。

0x0D:抛三个色子,你押一个数,出现一个赔一倍,两个配两倍,三个赔三倍,一个都没出现庄家胜,分析公平性。

0x0E:一个大医院每天100个小孩出生,小医院每天50个出生,请问哪个医院每天生出男孩超过60%的概率大一些。

0x0F:计算0.99^100『如果你问精确到多少位说明你思路还不对』


0x00:有一个文件,200多k,计算过其md5的值,并记录在本地。然后将文件传到ftp上,因为某些原因,本地文件备份丢了,从ftp上下载下来,发现下下来的文件md5的值和之前记录的值不一样,然后面试官问我遇到这种情况我会怎么做来试图恢复这个文件,我说的每一种手段她都会告诉我结果如何,看我能不能恢复出这个文件来。嗯,很有趣的一种面试方式,很像文字冒险解密啊有木有?『有兴趣的读者可以在评论里面给方案,我来模拟面试官告诉你方案的结果23333』

0x01:如果让你来设计一个云笔记,客户端和云端你会分别怎么设计,提出一些简单功能并解释怎么实现【重点讲如何实现云同步】,然后假设给你一堆码农,你会怎么安排他们实现这个东西。

0x02:一定数量服务器,如何设计存储视频方案,使得负载均衡,而且要能实时应对每天很多视频上传的需求,还有一些类似《中国好声音》这种点击量超大的。『我还吐槽了一句,好声音这节目我一集都没看过。。』

0x03:两个机器人,在一维直线上两个点(整数坐标),给两个机器人烧完全一样的程序,程序操作只包含左移n,右移n,判断自己是否在对方的起点,判断自己是否在自己的起点,然后目标是保证两个机器人一定要相遇。(程序请注意整数范围不要溢出)

0x04:列举C++和Python你所知道的所有不一样的地方。

0x05:线性时不变系统中,可以接受多个输入参数,不同输入得到不同的输出,如何快速确定任意一个输入,计算出输出结果?

0x06:一个人工作七天,报酬是每天一个金环,其中雇主有七个金环,但是都扣在一起了,请问如何断开最少的金环可以保证每天都可以拿到相应的报酬?『我总觉得面试官问我这个问题有种瞧不起我的感觉。。』

0x07:1000瓶试管里面装着足够量的液体,其中一瓶是毒药,可以拿小白鼠来试毒,一滴即可致命,毒发需要半小时,尽可能短时间内用尽可能少小白鼠找出毒药。


评论回复贴代码还请贴gist的链接。。多说这个逗逼评论框会把中括号内的英文给变成表情符号。。

人生仅有的一次校招,我本想为它写三篇博文的,这篇是第二篇。。虽然第三篇已经写了80%了。。但是不怎么想发。。算了,看心情吧。。

噢,另外,下面这段话是惯例,我懒得删,此文还望不要转出去。。。
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓


【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

分类: 标签: , , , ,
  • 发现了数学0x03有一个很方便的方法,y轴上的两个点和x轴上的两个点最多能够构成一个在第一象限的交点,那么最多就有n*(n-1)/2 * m*(m-1)/2个在第一象限内的交点了。至于存在性应该比较容易就能够想到了。

    • 嗯,就是C(n,2)C(m,2)

      • 一个矩形的对角线确定一个交点,只要求有多少个矩形就行了,所以C(n, 2) * C(m, 2)

  • Yu

    >> 如何提高链表随机读取速度? 构造一个辅助索引树算作弊么?>> 不用数据结构课程中讲到的解决哈希冲突的方法,还有什么办法?我知道三种,1,2是保存key,1. hash,发现碰撞,移到下一个2. hash,发现碰撞,链表挂后面去blz还做过一种,key的空间非常大,是unsigned long类型的,然后每个key可以生成3个val.它们碰撞的几率微乎其微.课本至少1,2都讲了...3可以充当答案么?> 二叉查找树转链表。(leetcode)先序,中序,后序或者层次遍历?

    • 1,肯定是要一些辅助结构来提高的,我当时直接说跳表。2,其实当时他问的就是不要用1和2,还有什么办法,我也是跟他讲双哈希函数。3,反正就是前三个的某一个,我忘了。。

      • Yu

        哦...leetcode里面瞄了眼,中序感觉这里有些看起来基本教科书上都能找到答案,但有些.... 比如>> const的实现原理? 我印象中它的声明只对编译器有效,编译优化的时候可以做一些更好的优化.到了机器码没啥特别的吧...还是说在编译中怎么处理本变量使其readonly? 额..基本没想过这个问题...

        • 基础知识里面都是教科书上的,但是好多一问才反应过来平时没思考过。。只是单纯地在用。。

  • Yu

    算法0x00 https://gist.github.com/yujing5b5d/e54bf54231b0587cd190这样算过么?怎样算"手写"呢?我感觉我写hello world不编译下都没法一次过.这次第一次写的时候是 string 的 s.length() 写成了 s.length... 果然scala写多了好的没学好丢三落四的倒是学得蛮快...

    • 过不过你自行测试吧。。你没玩过leetcode么?就是没有任何ide,白板写代码,不许调试。面试中就是一张白纸给你。不过一般写接口就可以了,需要给面试官一行一行讲代码。。外企有些需要上机,这种就需要自己把main,头文件和测试案例写好。。

      • Yu

        leetcode给返回结果,而且我一般是自己vi开个简单的文件先编译下试试看结果再paste上去的...似乎不正规的样子...

        • lc上的题目主要就是给大家练习面试手写代码用的,如果你还用编译的话,那么平时写代码就没区别了。。

  • Yu

    杂: 0x00 重新下载一遍,比较md5...若发现第二次下载和第一次下载一样,说明线上的不是正确的文件,放弃治疗......(我是不是放弃太快了?)0x01 以文件为单位计算revision,最多记录15次的revision,每个revision都有个commitid,这个commtid可以parse出时间点,保存最早的纪录和15次的commit,然后同步的时候选择一个比较新的作为base,寻找比较旧的commit.旧的应该是新的的某个历史commit.然后传输commit更新...总之思路就是github+mongodb的replica同步.0x02 一个master,若干slave,LRU什么的不知道可以不(没做过这类东西,我脑补的...)0x03 两个同时启动么?那就是不断左右移动,每次距离+i...仔细想了想实现感觉有点麻爪...0x04 C++是编译型语言,自己控制内存,强类型, template很好用, lambda之类的要11才能有....想了下,好多东西貌似都可以变通的实现两个0x05? 金环那个表示看不懂....

    • 0x00:和第一次下载不一样,但是md5还是错的。0x01:我瞎讲了一堆,我也不是很清楚。。0x02:我也是瞎讲的。。0x03:是同时启动,但是你这样存储距离的那个变量最后会溢出,我专门提醒了。。手滑。。金环网上的说法是这样的,你看说清楚了么?=>假如你在某司上班7天,老板给的报酬是7个金环,但是七个金环是一条相连的金环,你只能解开一环且每上班一天就要拿走一环,不能多拿也不能少拿,不然你就得不到报酬,请问如何拿到你的报酬?

      • Yu

        0x03 我注意了,但溢出的问题解决并不困难.1. 高精度2. 两个整型表示简单说就是: 向左移65535, 没找到...,向右移65535(pre),再向右移i ... 这样子.我想过调用 "判断自己是否在对方的起点,判断自己是否在自己的起点"两个API,但是没想好怎么用比较好....金环那个.....是说拿第三环,截取后得到2,1,4三段,然后各种拼...?这不是脑筋急转弯么.....

        • 0x03:你这样子,只要两个机器人起点足够远,你还是会溢出的啊。。嗯,所以我觉得面试官问这个有点囧。。感觉小学生就会做的。。

          • Yu

            高精度的值域理论上是无限的...虽然命令只能是"向左右移动int类型",但是我可以执行"向左/右移动int类型高精度b次,前b-1次移动65535格,最后一次移动int类型i格"...所以溢出什么的并不是问题.不过很好奇标准答案...

            • 同时以某一个速度向一个方向移动,其中一个可以检测到是否是对方的起点,然后n倍速度赶上去

              • Yu

                赞..有道理

                • 我那一场面试感觉就这道题答对了。。

  • Yu

    又..算法0x14和0x07实现基本一模一样...

  • =w=每次看完评论就花了半天2333最近忙的快死了哭晕

    • 评论其实就Yu一个人在刷。。忙比闲好,闲到快哭死才是真的要哭晕了。。

  • EnguangZ

    同学,你面试的是什么企业?题目怎么专业。感觉我面试的都是一些日常问题。

  • EnguangZ

    同学,你面试的是什么企业?题目怎么专业。感觉我面试的都是一些日常问题。

    • 见前篇博文为部分面试公司。技术岗问这些问题不很正常么?

  • lv

    除了数学题能大部分搞定……其他呵呵了

    • 你就不是干这行的,好好干你老本行去。。

  • 心如止水

  • pmx

    那个10万次循环中间变量出错是什么原因?最近C#碰到个循环到6000次左右就开始出错……