微软实习面经

很久前写的面经了，整理桌面发现了，发出来备份下

微软STCA 实习 一面 

自我介绍

项目询问

写题：（1）不用long long，如何判断两种int类型的数是否会溢出？

                        按正负分类讨论

            （2）二叉搜索树，如果有两个节点位置对调了，如何调整？

                        中序遍历 + 记录节点位置 + 遍历后值交换

反问：由于我投了好多实习，面试官告诉我是她同事推给她的，我就以为是之前的MSRA呢？其实人家是我之前投的STCA，我以为没回消息，就简历被筛掉了，巨尴尬。。

微软STCA 二面 

75 min

讲之前的科研，没想到这块讲了半个小时，写了两个两年前的课设凑版面，结果被追着问。。。

LRU，经典中的经典，很快写出来了，有一点点小问题，不过面试官说没事儿，OK了

此时，已经50分钟了，面试官说，来我们再做一道题

现在有个爬虫从网站上爬下来一堆商品的title和类别，有些类别是空，该如何分类？我讲了讲怎么构建feature，但是面试官不满意，因为我这样必须知道当前所有的类别，真不会了。。。

此时，已经60分钟了，面试官说，来我们再做一道题

给你很多个数，可能几十个G这样大的数据，该怎么找到最大的K个，我说维护一个小根堆。面试官不满意，让详细讲讲整个过程，如果当前值比堆顶大，替换堆顶，然后自上向下调整堆，仍然保持小根堆的状态，维护堆是log k，遍历数据是O(n)，总共是O(nlogk)。嗯，ok了

此时，已经接近70分钟了，面试官说，来我们再做一道题

如果现在有一万条线，每条线上有100个点数据，数据都是double 类型，如何让相似的线能聚类？此时我已经很懵了，内心os: 我投的不是开发岗么？想了好久，把毕设要用的dbscan算法讲上去了，面试官让详细讲解算法的思路，我：。。。。面试官问，应该用什么距离，能让线性聚类，大二学的那点东西早都还给老师了呜呜呜，我编了一个明式距离，面试官不是很满意俺的算法功底。

此时，已经75分钟了，面试官说，来我们在做一道题

我：emmm，面试官看了看表，奥，到时间了，你有啥想问的么？

我说，我投的不是开发么？面试官说，组内不分开发和算法，一块面了，我哭死，一点没复习

我暗示他啥时候能有结果？孩子还有别的实习要推进，面试官摊了摊手，这是leader的事儿，他只负责汇报面试情况，他也不知道，早知道俺就不问了。。。

总结：

数据结构的编程算法都答上来了，没想到面试官问了很多机器学习的问题和模型，事先没有准备，有些失策了，还是一面的姐姐温柔点，还给思路提示