|
本帖最后由 大壮哥哥 于 2013-4-27 22:34 编辑 3月18号微软中国科学技术大学苏州研究院宣讲会；3月23号压哨网申投简历；4月4号接到笔试通知；4月6号参加微软笔试；4月12号接到微软面试通知；4月25号下午参加了微软长达两个多小时的线上面试，这一路走来，感觉命运之神待我不薄~ 其实一直不敢声张自己通过了笔试。因为真的压力好大，什么都不会，之前数据结构都没学过，一个月之前甚至都没写过一个链表结构。得知通过笔试之后恶补数据结构和算法啊。 言归正传，下面我简单说一下今天（25号）下午的面试情况。面试时间3:30~5:30,两轮，一轮一小时左右。3:20就打开他发来的开会软件Lync2010,说实话有点小紧张。大概3:35分左右，第一位面试官加入到会议中，简单打了招呼。他先让我做了一下简单的自我介绍，我又简单说了我的项目，把我最拿手的项目说了一下。我自由发挥，说我学到了什么，遇到了什么问题，怎么解决的。他问到我这个项目（单片机驱动的机器人小车）具体都有那些函数，都完成了什么功能 。我都一一回答了。关于项目他还问了，我是怎样测试的，功能是怎么优化的之类。我就说首先要保证完成要求，然后再进行测试和修改。我就结合这个项目，谈到外部环境对测试的影响，代码的优化等项目涉及到的具体问题。然后他问我了不了解设计模式，这个真心不知道、不懂、不了解啊，如实说不懂、不了解。又问进程同步是什么？我不懂啊！为了避免尴尬，我说我了解一点多线程，两者有什么区别吗？他说有点相似，转而又问我进程同步具体用到哪些地方。真心不知道。   然后就是具体编代码的环节了。好紧张啊啊啊~他把问题简单说了一下。说是有一些Ip地址访问服务器，设计一种数据结构存储这些Ip的相关信息，通过查询这些信息判断Ip是不是非法攻击（假设一个Ip在1秒内访问服务器10次以上就认为是非法攻击）。其实当时他没说这么详细，我是一点一点套出来的。他不断提示我比如怎样怎样等等。刚开始我没有理解题意，就定义一个结构体存储Ip号，Ip的访问时间，Ip的访问次数。然后 【每秒访问次数=访问次数/访问时间】 判断其是否大于10，来确定是否是非法攻击。他提示我要动态添加Ip信息。我就顿时明白什么意思了 typedef struct IpInfo { char a[20];//存储Ip号 float time;//存储Ip访问是的绝对时间 struct IpInfo *next; }IpInfo; 他问我怎么判断是否是恶意攻击。当时想的是向前查找9个链表结点中有该Ip号的 time,看其和当前结点time差值是否大于1秒。大于1s就不是非法攻击，反之，是非法攻击。由于还需要向前查找，单链表不行，我便说用双向链表。他提示我说你的这些Ip的相关信息是否都要一直保存下去，才发现自己忽略了一些过期的Ipinfo结点应该删除，然后就向他说明怎样怎样删除，此处不细说了~到此大概已经进行了1个小时左右了。之后，他便说他的问题问完了，我有什么问题问他。我问他假如我能加如微软具体干些什么活？他说各部门的工作不一样，比如bing怎样怎样，他的部门office怎样怎样。我就跟他闲扯，说近期正在用bing，每天看到那个优美的主页很舒服之类的。还说到我们学校Windows 8 能免费使用云云，只是自己电脑装了好多软件没舍得重装Windows 8，一直没机会体验office 2013。然后他建议我去装虚拟机体验一下office 2013。到此，第一轮面试便愉快地结束了~ 我去上了个厕所,又回到了电脑前。过了一会，另一位面试官也进入了“会议室”。简单打过招呼之后，便开始面试。他也是先让我做了自我介绍。我便简单介绍我本科学校，现在学校，以及做过的项目。这次我不仅把我本科的项目说了，又说了一下现在的工程实践。工程实践我们做的是Adroid应用，涉及到服务器搭建、爬虫、和Android app访问图片。我把原理简单说了一下，并特别提到搭建服务器时原本打算用LAMP架构，后来采用的WAMP架构，即Windows环境下Apache+Mysql+PHP。然后提到编写一个爬虫把爬取的图片存到服务器，图片名称及存储路径存到数据库，然后Android app通过数据库中的图片名称和存储路径访问服务器中的图片云云。。。然后他借题发挥问我一个类似爬虫的问题，我的心顿时凉了半截，爬虫原理我不懂啊！不过还好他说不用你回答具体原理，只需要你说出用什么数据结构解决这个问题。问题是这样的：一个网页有许多链接，一个链接下又有很多链接，。。。。。这其中的链接有可能有环（经过几个链接后又回到初始网页），有可能回到自身（比如回首页），这些链接中有些是坏的（404 NOT Found），用什么数据结构遍历所有链接去除坏的链接？刚开始我是一点思路没有，但也不能没话说不是。我就说要是没有环，用树就可以解决了。。。他说对，现在的问题就集中在怎样解决环的问题。然后又提示说我：你看结点被遍历过了以后怎样能在下次遍历的时候发现他是被遍历过的。我就提出在树的结构体里再增加一个域，作为标志位。他不太满意，说如果链接很多（大数据量）不合适之类。他说你想想还有什么数据结构，我又提到图，但是图我不会啊，那个太复杂了，看大话数据结构时跳过去了。他说图太复杂，再想想。再想，我去，那不就剩散列表（Hash 表）了。我弱弱地说散列表，他说恩对了。其实颇担心他细问散列表，看书时也跳过了。他没接着问，我松了一口气。。。又到了紧张的编代码环节。他介绍说有一二叉排序树（BST），写一个函数求其镜像，即：原先结点数据的从小到大的顺序是左中右，现在让其变成右中左。他给出了函数名和参数表：void Mirror(Node *pRoot) 我迅速打出 void Mirror(Node *pRoot) { } 他问我拿到这个问题我的首先想到怎么办，我当时被面的已经有点懵了，就说先中序遍历，将结点数据存入数组，然后倒置数组，再中序插入。他很不满意，说如果我给你5分钟时间，你能完成这个思路的代码吗？我感觉到这不是他想要的答案。这时我想到了递归，在小健和郝同学的帮助下（这个有作弊嫌疑啊，嘿嘿~），完成了程序的初始版本 void Mirror(Node *pRoot) { if (pRoot == NULL) { return ; } if(pRoot->pLeft==NULL&&pRoot->pRight==NULL) return ; Node *tmp = pRoot->pLeft; pRoot->pLeft = pRoot->pRight; pRoot->pRight = tmp; Mirror(pRoot->pLeft); Mirror(pRoot->pRight); } 他看了代码问第二个if判断有必要吗，我感觉还是有必要的，毕竟他避免了无谓的交换啊，左右两个子树都是NULL时候不必交换。我说我感觉有必要啊。他说去掉以后代码就精简了许多，不就是交换了两个空指针嘛。原来他是从代码精简角度来说的，赶紧认错（呵呵），我说，是啊，对对云云~他又问我时间复杂度，这个应该是遍历每个结点（n个），我说是O(n)。他又问我空间复杂度，这个我想了一会，说是O(1)。其实我不明白怎么还有空间复杂度啊，嘿嘿，蒙的。他不耐烦地说怎么是1呢，难道递归的时候的压栈出栈你都不考虑，顿时明白了，空间复杂度就是整个过程中栈中元素的最大个数。条件反射地说O(n)。他又问为什么是n？他的语气表明好像还是不对。我又仔细看了一下代码，每次递归只有当根结点为空的时候才返回，这时候才出栈。最坏情况下就是到二叉树的最底层才为空，压栈次数为二叉树的高度，空间复杂度应该是O(logn)。我告诉他这个结果的时候，他那边不说话了。我心想：这是要闹哪样啊，这就不理我了啊（嘿嘿）。就给他打字，问他还在不。一会有反应了。说Sorry，他机器重启了云云。我说没事，我打字问我，空间复杂度是多少（还挺敬业），我打字O(logn)，他打字“嗯，对了”。他："面试时间也差不多了，要不就先到这里吧!" 我:"嗯，好的，谢谢！" 他：”有什么事情，HR会联系你的，感谢你的参与！再见“ 我：”好的，再见！“ 就这样第二轮也结束了~此时已经17：45了。我长长的吸了一口气。 我突然感觉到面试就像在打DOTA，现在我们面试就是在打野升级、刷钱、混经验，等到装备起来了，就可以大展神威了。但是，我不知道自己是不是后期的Hero。至少，我感觉我刚才打了Roshan,而且被虐的很惨~ 这个面经写了三天，不是想不起来面试细节（历历在目啊），是实在都是泪啊，被虐了一下午，写一遍等于再被虐一遍啊。以至于写写停停，总算告一段落，写完了。 致谢：卡总（大神，卡总的大话数据结构是我数据结构第一本书，帮我大忙了） 郝同学（大神，曾经我的上百行代码调不通，他加了一行就通了） 小健（大神，我想健哥不介意我这样叫他的，每次我问他问题他都比较耐心的帮我解答） |
[招聘|实习·全职·内推] 微软面经
大壮哥哥
· 发布于 2013-04-27 22:34
· 3285 次阅读
转载文章时务必注明原作者及原始链接，并注明「发表于 软院网 RuanYuan.Net 」，并不得对作品进行修改。
| 很给力，很有用。 |
辛苦乐！
顶贴！！！ 
| 大壮牛b呀，学习学习！ |
