微软2022暑期实习挂经

算法菜鸡一枚，头贴冲ms，记录一下面试过程

批次：提前批，学校群里看到消息立马就投了，很期待wlb

12月中旬投的简历，1.4提前批截止后立马收到邮件回复，1.17，18两天都安排了面试。提前批截止日看到hr说如果提前批技术岗没过，正式批也不能投了，很慌

1.17第一次面试，女面试官人很好，自我介绍完后直接开始问算法，没有发给我链接用白板写，直接口述，题目为，1000瓶水有一瓶有读，给你10只老鼠，最多多少次能找出有毒的那瓶。参考leetcode 458 有毒的小猪。这一看要降低时间复杂度，就类似归并+二分的结合，在6次左右能完全找出来。ok，然后开始进阶了，问，如果老鼠的毒性一周后才发作，怎么在一周后给出结果。这，我懵了，然后进行了两轮提示，位运算=>2^10与1000的关系。内心os，这不是妥妥的log(n）时间复杂度的二分嘛。思考无果，可能时间快到了，又提示想想看把老鼠用0和1表示，忽然想到10只老鼠可以用排列组合，可能就有1000种方式，然后用亦或确定。说了思路，面试官说差不多，但是叫我再考虑一下，最后一轮提示，考虑一下把1000瓶水编号。芜湖，恍然大悟，其实就是把10只老鼠当成10个bit，把1000瓶水中二进制为1的给对应的老鼠喝，死了的就是那个编号了。唉，怪自己格局太小，一直在考虑如何减少搜索的范围，没有想到把1000瓶水都喝一边。只能说位运算yyds。若有后续，将继续更新

1.18二面。说实话，面之前已经感觉凉了，同一批次的好几个同学一面完就收到了lead round的面试邮件，可是我还没收到。二面面试官上来先问了一些八股文，让我介绍项目。问了异步式编程、数据库事务、数据一致性、数据库索引、死锁、进程线程等问题，408都考完两年了，都忘的差不多，只能根据自己的理解描述一下，总共问了快20min吧。后来给了一个字典树的题，给你一个n，按字典顺序输出。对于算法菜鸡来说都忘了字典树是什么东西了，面试官提示了一下，然后开始思考。刚开始想用优先级队列，忽然发现不对。字典树字典树，当然用树啊，那就递归用二叉树吧，写了个dfs算法，由于电脑里没有编译器，所以写完后就让自己debug了，勉强算过关。刚刚看到了原题leetcode 386 字典序排树

感觉我的ms面试之行应该到此结束了，体验不错，面试官都很好，只不过我给学校丢人了，自己复习的还是不够。正式批也没机会了，想去的话只能秋招再碰碰运气吧。