UDN-企业互联网技术人气社区

板块导航

浏览  : 1172
回复  : 2

[面试经历] 微软第二轮面试三道算法题目详解[转]

[复制链接]
Monologue。的头像 楼主
发表于 2015-9-15 18:26:11 | 显示全部楼层 |阅读模式
上题目之前先叨叨点废话。
       
       
               
       
       
                这个月被腾讯微软两家公司折腾的死去活来,笔试一家一次,一共两次。面试一共十轮,腾讯广州研发部四轮,腾讯全国统一校招三轮,微软三轮,结果还算顺利,两家都拿到了offer,最后决定去北京中关村的微软,因为北京离家近,而且死党们暑假也在北京。
       
       
               
       
       
                本来想写写这个月的辛酸转为欣慰的感慨,后来想想还是算了,因为很多优秀的同学可能RP没有攒够,结果没有拿到自己理想的offer。我一“小人”,在“得志”之后,大发成功感言,无异于在人家伤口上撒盐。此片日志我只想起到雪中送炭的作用,因为后面还有IBM百度等大公司的实习招聘。我也希望我晒得这些东西能对那些一时失手的童鞋带来些帮助。招聘这个过程偶然因素很多,笔试侥幸过了还有第一轮面试,第一轮侥幸过了,还有第二轮,第二轮侥幸过了还有第三轮。其中只要有一个环节出了差错就game
    over 了。所以千万不要拿一次面试失败就否定了你自己的实力。
       
       
               
       
       
                废话不多说了,我把我三次面试的详细题目包括我的解答晒一晒,也许比什么面试感想更有用一些。
       
       
               
       
       
                提前说明一下,很多题目是没有标准答案的,我之后也懒得查资料做进一步分析。我只能把我当时的回答大概回忆着描述一下,仅作为参考,如果有bug的话,还望高手留言指教。还有,由于该贴得照顾到对计算机掌握程度不同的童鞋,所以每一点我都力求描述的详细一些,大牛觉得啰嗦请直接忽视。
       
       
               
       
       
                总述:
       
       
               
       
       
                微软面试,每一轮至少一个小时,一对一PK。几乎不问你项目什么的,因为他们觉得你带来的项目肯定是自己在下面已经准备好了,考不出实力,于是,他们一般是上来就拿题目让你分析。这一点相对于腾讯面试要蛋疼一些,而且,现场写代码是肯定会有的重要环节。经历了三轮面试,感觉微软的面试很有规律,他只会出两类题目,一类是算法数据结构的题目,一类是工程题目。总体感觉,尤其是因为微软的面试时间是在腾讯刚刚结束不久,相比之下,每次面完微软都有一种意犹未尽,荡气回肠的感觉,因为在面试官的点播和提示之下,你解决了很多新颖的问题,但是用到的东西却是你曾经在课本上学到的,或者在竞赛比赛实践生活中掌握的知识。而不像腾讯,展示了两个曾经开发的手机软件,不到二十分钟就把我轰出去了,最后居然还给了我offer。
       
       
               
       
       
                (先说第二轮吧,因为第一轮面试,一个小时就考了一道工程题,描述起来比较蛋疼)
       
       
               
       
       
                第二轮面试 第一道题目:
       
       
               
       
       
                题目描述:现在让你在普通的计算器(位数最多12位)上增加一个功能button,点击这个button之后能进行数字显示模式的切换,即能显示我们汉语对数字表达的习惯。比如计算器最初显示“零”,你按“1”这个按键之后,屏幕显示的是“一”,继续按”9”这个键,显示的是”十九”,继续按“0”这个键,显示的是“一百九十”…
    …而且,还要增加两个功能button,“退格键”和“清空键”。继续按退格键,显示的是“十九”,继续按“清空建”,显示的是“零”。
       
       
               
       
       
                分析:
       
       
               
       
       
                这道题实际上是一道工程题。
       
       
               
       
       
                首先第一步也是最容易想到的一步就是先建立映射数组,即开辟一个数组用来保存“零,一,二,三,四,九”,以将单个数字快速转化为汉子。
       
       
               
       
       
                然后再建立一个映射数组用来保存单位,这里有个大陷阱,等会儿再说,我先按照错着来,这个数组保存从小到大的单位“十,百,千,万,十万,百万,,,亿,十亿,百亿,,,”
       
       
               
       
       
                做完映射这一步,你可以用一个数试一试,比如“931”转化为中文表达为“九百三十一”的过程为:将一个数从左往右扫描,9映射为“九”正确,该数字在百位,映射为“百”,继续,你最终能得到“九”“百”“三”“十”“一”,拼起来“九百三十一”,哇,正确!
       
       
               
       
       
                如果仅做到此步,你就向面试官描述了你的答案,那么就很危险了。。。
       
       
               
       
       
                最明显的一个错误是你没有增加对于“0”的处理。
       
       
               
       
       
                比如“901”转换为“九百零一”而不是“九百零十一”,所以,有零的位置并不输出“单位”。
       
       
               
       
       
                比如“1001”转换为“一千零一”而不是“一千零零一”,所以,连续0的地方只输出一个零。
       
       
               
       
       
                比如“1010”转换为“一千零一十”而不是“一千零一十零”,所以,0在最后的时候不作为输出。
       
       
               
       
       
                关于零的处理我当时就说了这三步处理,我看他的表情没有任何异常,我就没再考虑是否还有遗漏情形。
       
       
               
       
       
                然后他问我OK了吗?我半信半疑的点了点头。。。
       
       
               
       
       
                然后他写了一个数,让我用我刚才描述的算法翻译一下“1230123”。正确表达是“一百二十三 万 零一百二十三”,而我的算法翻译得到结果却是“一百万 二十万 三万
      零一百二十三”。。。我勒个去!!!当场SB了。不过没关系,如果能及时想办法解决掉,反而能衬托出你灵活处理问题的能力。我自己又测试了一个比较大的数之后,发现问题就出现在单位数组的设置上,就是刚才提到的那个“大陷阱”。“十万”“百万”“十亿”“百亿”等等,这些是“复合单位”,跟十,百,千,万,亿,这几个单位不同。
       
       
               
       
       
                意识到这一点,我给他说了新的算法思路,对于一个数,首先分成几段,从右到左,每四位一段,比如“123
      0123”就会被分为两段,第一段“0123”和第二段“123”然后写一个子函数专门处理四位数以下的翻译工作,0123翻译为“零一百二十三”,处于第一段,不用加单位。然后123会被翻译为一百二十三
    ,由于处于第二段,所以加上单位“万”(当然,如果处于第三段,加上单位“亿”)。两段拼起来得到最终答案“一百二十三万零一百二十三”。
       
       
               
       
       
                说到此,他点了点头,然后让我代码实现,一阵子奋笔疾书,搞定。他检查了一遍,一时没挑出大毛病,就问我,这个问题你解决完整了吗?
       
       
               
       
       
                我有点疑惑,难道还有神马特殊情形我没想到?
       
       
               
       
       
                他看我一脸疑惑就在纸上给我画了一个框架图,他说,解决一个问题,要善于将大的问题拆分成数个小的问题,你只解决了一个最关键的子问题,你回想一下我刚才给你提的要求。
       
       
               
       
       
                原来,我遗漏了解决“输入问题”。汗。。。
       
       
               
       
       
                他没让我说思路,直接让我写了代码。
       
       
               
       
       
                注意,如果代码写成:
       
       
               
       
       
                Int num;
       
       
               
       
       
                num = input();
       
       
               
       
       
                mPrint(num);
       
       
               
       
       
                那就over了。。。
       
       
               
       
       
                考虑到平时我们使用的计算器的实际情形,正确输入代码如下:
       
       
               
       
       
                int num = 0;//当前需要显示的数
       
       
               
       
       
                       int key_val;//每次按键的键值
       
       
               
       
       
                       while(key_val = input()){//每次得到一个按键
       
       
               
       
       
                              if(key_val == KEY_BACKSPACE){//如果案件为退格键
       
       
               
       
       
                                     num/=10;
       
       
               
       
       
                                     mPrint(num);//mPrint()函数就是刚才讨论过的那个翻译函数
       
       
               
       
       
                                     continue;
       
       
               
       
       
                              }
       
       
               
       
       
                              else if(key_val == KEY_CLEAR){ //如果按键为清除键
       
       
               
       
       
                                     num = 0;
       
       
               
       
       
                                     mPrint(num);
       
       
               
       
       
                                     continue;
       
       
               
       
       
                              }
       
       
               
       
       
                              else if(key_val == KEY_DIGIT){//如果为数字按键 0 -9
       
       
               
       
       
                                     num*=10;
       
       
               
       
       
                                     num+=key_val;
       
       
               
       
       
                                     mPrint(num);
       
       
               
       
       
                                     continue;
       
       
               
       
       
                              }
       
       
               
       
       
                              else{
       
       
               
       
       
                                     //...计算器上的其他按键。
       
       
               
       
       
                              }
       
       
               
       
       
                写完代码之后,他问我,你觉得加上这个功能会对整个系统带来什么新的问题吗?
       
       
               
       
       
                像这种问题一般都属于开放性的,想到什么就说什么,别怕错。
       
       
               
       
       
                我想了一下,说了一个关于“显示”的问题,就是汉字表达一个数,和数字表达一个数的不同之处,比如:11111 和10001 都占五位,而翻译为汉字表达之后,在显示上占得字长相差很多。想到这点主要是因为最近做的一个开发在处理View框架下对字符串排版的时候很是头疼。
       
       
               
       
       
                截至到此,这道题目就搞定了,题目不难,不涉及到高深技术,但是时间卡的很紧,当时这道题目的交流时间从头到尾进行了二十五分钟左右,包括最初问题描述,到中间的交流,算法描述,外加两段代码的书写。所以,每段代码的书写要控制在五分钟左右。注意,是在纸上写,不是电脑上,很不习惯,一定要提前练习一下。还有一点要注意,与核心算法无关的代码可以用伪代码实现。比如key_val
    = input();
    input()这个函数,并不需要实现,这么写仅仅代表,计算器内部有一个函数机制能检测你按了那个键,然后返回你一个值就可以了。
       
       
               
       
       
                第二轮面试 第二道题目
       
       
               
       
       
                题目描述:给你一个数组,让你返回一个值,这个值在该数组中占得个数,超过数组总的个数的一半以上。比如一个数组有10个数[2, 14 , 2
    , 3 , 4 , 2 , 2 , 2 , 2 , 14
    ]。这个数组中数字2一共出现6次,那么就返回数字2。为了简化问题,可以认为,对于给定的数组,这个数一定存在。
       
       
               
       
       
                解答:
       
       
               
       
       
                当然最简单的方法就是,将数组排个序,然后返回数组中间位置那个数,比如上面那个数组排序之后为[2,2,2,2,2,2
    ,3,4,14,14],中间的数为2,所以返回2.。
       
       
               
       
       
                由于排序的最快时间复杂度事O(nlogn)所以,上面解法的算法复杂度是nlogn。
       
       
               
       
       
                当然,微软既然拿这道题目考你,肯定不是靠你个简单排序。肯定会有O(n)的解决方法的。
       
       
               
       
       
                算法很简单,既然他让我找的数值在这儿数组里面占得个数超过总数的一半,那么如果我每次同时去掉两个不同的数,那么剩下的数组里面,那个值的个数仍然占到一半以上。
       
       
               
       
       
                最后剩下的一堆相同的数肯定就是那个值了。
       
       
               
       
       
                算法跟他说完之后,他说,算法没问题,但是如何实现呢,也就是说,如果通过一次线性扫描,删掉俩俩不同的数呢? 然后让我把实现代码写出来。
       
       
               
       
       
                在实现上用到一个“虚拟栈”的技巧,这个方法很典型,幸亏过去接触过,否则在那么短的时间内很难写出高效的实现代码。
       
       
               
       
       
                “虚拟栈”就是说,不需要真正开辟空间,我只是申请两个变量,一个记录栈顶的数值,一个记录此时栈里面当前元素个数。
       
       
               
       
       
                这样,为了解决上面的问题,用“栈”的那套语言来描述就是:
       
       
               
       
       
                从头到尾扫描原数组,每取出一个数x,进行如下操作。
       
       
               
       
       
                首先如果栈为空,那么就把当前值x  压入栈;
       
       
               
       
       
                如果栈不为空,就拿当前值x  跟栈顶元素top 比较:
       
       
               
       
       
                如果x 等于 top ,那么把x压入栈;
       
       
               
       
       
                如果x不等于top,那么把top弹出栈。
       
       
               
       
       
                数组扫描完毕之后,栈顶元素值top即为需要找到的数。时间复杂度O(n)。
       
       
               
       
       
                当然你会注意到,在栈动态变化的过程中,你会发现,栈中的元素如果数量大于1,必然是一堆相同的元素。所以根本没有必要开辟栈空间,这就用到刚才提到的“虚拟栈”,只需要记录栈顶元素值,和栈中元素的数量即可。可以将“运行时空间复杂度“由O(n)降到O(1)。
       
       
               
       
       
                代码我就不贴了。
       
       
               
       
       
                第二轮面试 第三道题目:
       
       
               
       
       
                题目描述:这道题目挺有意思,他问我你知道”外部排序”吗?
      我一脸茫然,我说,我只知道快排,归并排序,希尔排序等等。。。他打断我,你说的都是”内部排序”。他说到这里,我瞬间想起来,我们那个英文版本的数据结构书,好像在讲内部排序的时候的前一章节有提过外部排序。不过由于不是考试内容,所以我当时就没看。。。他说,没事,不知道没关系,我给你描述一个问题场景,你就把他当成一个新问题来处理就行了(微软面试官好贴心,感动)。
       
       
               
       
       
                他说,现在我要进行排序,不过需要排序的数据很大,有1000G那么大,但是我的机器内存只有2G大小,所以每次只能把2G的数据从文件中传入内存,然后用一个“内部排序“算法在内存排好序后,再将这有序数据,载入一个2G大小的文件。然后再载入第二个2G数据。。。循环500遍之后,我现在得到500个文件,每个文件2G,文件内部是有序的,然后我再比较这500个文件的第一个数,最小的肯定就是这1000G数据的最小的。那么之后的过程你肯能想到了,就是不断将这500个2G
    数据进行一个归并,最终就能得到这1000G的有序数据文件了。
       
       
               
       
       
                举个例子,比如我要排序10个数,但是我的内存一次只能装下5个数,所以最初的10个数我只能放到文件里面(文件时外存,只要硬盘或磁盘够大,想多大就多大)。内部排序肯定是得需要将数据载入内存中才可以进行的。
       
       
               
       
       
                这10个数是[ 2 ,3,1,7,9 ,6, 8,4 ,5 ,0 ]。
       
       
               
       
       
                第一次载入前五个数2,3,1,7,9.  排好序后是:1,2,3,7,9  然后导入一个只存五个数的文件中。
       
       
               
       
       
                第二次载入后五个数6,8,4,5,0   排好序后是:0,4,5,6,8,然后倒入一个只存五个数的文件中。
       
       
               
       
       
                之后在归并两个有序数列
       
       
               
       
       
                第一个有序子数列的头位1,第二个为0,因为0然后在进行第二次比较,1和4进行比较。。。
       
       
               
       
       
                重复进行最终得到一个有序数列的文件,里面存着,0,1,2,3,,,7,8,9
       
       
               
       
       
                问题是:在这个过程中,你能想到哪些优化?
       
       
               
       
       
                (擦,,,背景描述了半天,问题就一句话。。。当时我也很无语。。。)  
       
       
               
       
       
                解答:
       
       
               
       
       
                想了大概一分钟,除了增设一个缓冲buffer,加速从文件到内存的转储之外,我脑子里面一片空空。。。而且我想到的那个缓冲buffer所得到的回复是“假设这个优化系统已经帮你优化了”
    。。。无语。。。
       
       
               
       
       
                他看我眉头紧锁,然后给我做了一个提示:假设我现在把文件中的2G数据载入内存这个过程定义为”L”,把内存中的排序过程定义为”S”
    ,把排序好的 2G数据再转储到另一个文件这个过程定义为”T”…
       
       
               
       
       
                他还没说完,瞬间反应过来了!“用流水线并行实现“,然后我把流水线那个图画了出来,就是在计算机组成原理那本书中经常出现的“流水线图”。图画好后,他点点头,我也长嘘一口气。。。
       
       
               
       
       
                然后他问我,用流水线技术之后为什么会加速整个过程。
       
       
               
       
       
                当然这个问题就很容易了,过去得把一组2G数据的三个过程全部处理完之后,才能进行下一个2G数据的处理,现在就可以三个过程并行着进行了。当时我也忘了,加速比怎么计算了,所以就没提这个东西。。。
       
       
               
       
       
                他接着问,做了这个并行处理之后,会出现什么问题?
       
       
               
       
       
                。。。MD,又是一个恶心问题,其实我清楚,问题不难,但是“找问题”好讨厌啊。。。
       
       
               
       
       
                想了一下,我说,在“S”这个过程,也就是内部排序的这个环节最好不要用“快速排序”,因为快速排序是不稳定的排序,所以在流水线那个图中会出现不均匀的时间块,影响整体性能。
       
       
               
       
       
                他想了一下,点点头。问,还有吗?给你个提示吧,你想想加了这个优化之后,某个资源会不会出问题?
       
       
               
       
       
                我想了想,“资源”,计算机的资源没几样啊,CPU,内存。。。再一次,瞬间恍然大明白,是内存出的问题,因为,如果并行进行的话,打个比方,比如现在同时处理的过程是,第一个2G数据的“T”阶段(因为第一个2G数据,比较早的进入流水线,所以之前的两个阶段已经处理完毕),第二个2G数据的“S”阶段,第三个2G数据的“L”阶段,那么这三个阶段是都需要把数据放到内存中的,所以一共得需要6G内存,但是目前计算机的实际内存只有2G啊!!!
       
       
               
       
       
                解决方法很简单,将内存平均分为三份,分别用于处理三个阶段的数据。
       
       
               
       
       
                这样带来的影响是,现在一次就不能处理2G数据了,只能处理2/3G的数据,流水线会加长。
       
       
               
       
       
                他看这块处理的差不多了,就继续提示,你看看在最后的归并上有什么优化?
       
       
               
       
       
                最后的归并就是不断在一组有序数列中找最小值,还用刚才那个例子,最后不是得到500个2G有序数列吗,但是扫描每个文件头,找最小值,最差情形要比较500次,平均复杂度是O(n),n为最后得到的有序数组的个数,此例子为500。
       
       
               
       
       
                他既然问有没有什么优化?那么必然是存在logn的算法了。一提logn和最小值,那没的说,必须是“堆”啊!!!
       
       
               
       
       
                然后我给他说了一下具体实现细节
       
       
               
       
       
                就是维护一个大小为n的“最小堆”,每次返回堆顶元素,就为当前所有文件头数值的那个最小值。然后根据刚才弹出的那个最小值是属于哪个文件的,然后再将那个文件此时的头文件所指向的数,插入到最小堆中,文件指针自动后移。插入过程为logn复杂度,但是每次返回最小值的复杂度为O(1),运行时空间复杂度为O(n)。
    OK,搞定。
       
       
                 
       
       
                由于已经一个小时了,这道题目 他就没有让我写代码。幸运,堆那个上移,下移操作好长时间没有写过了。。。
       
       
               
       
       
                第二面结束。
       

发表于 2015-9-15 19:30:56 | 显示全部楼层

大神!!
使用道具 举报

回复

发表于 2015-9-15 22:13:27 | 显示全部楼层

好厉害,真正的大神啊
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部