微软北京Azure面经

微软Azure CosmosDb Fullstack岗，开了一个月leetcode会员，刷了两周题就直接上了

电面：
两道题，第一道是leetcode原题： Product of Array Except Self，比较简单，关键举testcase的时候举出0这种case就行了。
第二道是求N个数组中从前往后第一个重复的数相关的，没回答好，一度以为要挂掉，结果还是约了onsite

onsite：
一面问了两题：
1. leetcode原题： https://leetcode-cn.com/problems/course-schedule/ 直接暴力拓扑排序即可
2. 在一堆左右括号中找出最长合法的子串长度，不能用栈。 使用类似栈的思想过了，后面面试官说还可以用dp，然后想了想也想出来了

二面
一开始给了一个问题然后想找一个更难的（Orz），然而我第一题就做了好久差点没写完
1. 在一堆数字矩阵里找一个最大的正方形，使它围住的所有数字和不大于某个固定的threhold。 这题一开始觉得是dp，可是后面没想到比较高效率的方法，最后只写了一个O(n^3)的暴力，面试官说还有一个O(n^2lgn)的解法

三面
一上来什么都不问就直接出题。
1. 第一问：求一堆文本文件里面出现频率最高的前k个单词：这个很简单，维护一个最小堆即可，leetcode类似题目： https://leetcode-cn.com/problems ... uan-su-by-leetcode/
2. 第二问：如果两个文件都足够大，以至于一次只能读取一个文件该怎么办
3. 第三问：如果是有1000台计算机，每台计算机上有1000个足够大的文件该怎么办
以前没接触过类似的场景，直接被问蒙逼，不过后面还是在面试官提醒之下慢慢想到了一种最简单的Hash Count算法

四面： 一个很好的面试官，没有问算法
五面：大boss是外国人，跟他英语尬聊了半个小时就走了

.
补充内容 (2019-12-25 16:05):
Orz，初来乍到， 求求大家给点米

yanjinbin 发表于 2019-12-25 00:31
大佬好强 以前竞赛 acm noip搞过的吧  

补充内容 (2019-12-25 11:46):

acm都是5年前的事情了，而且acm我也是蒟蒻吊车尾

yanjinbin 发表于 2019-12-28 01:58
-baidu 1point3acres没看懂 题目意思  跟归并排序有什么关系呢   能在说说么  没看懂

sorry，忘记说数据流都是有序的了。举个例子，两个数据流：
1，2，3，4，5，6，7
0，3，6，9....
这两个数据流，重复出现的数字有： 3，6，第一次出现的是3
做法就是把所有数据流归并成一个数据流，比如说0， 1，2，3，3，4....如果一个数字重复的次数等于数据流的个数，那么就代表这个数在所有数据流中都出现过。

二面那题用二分查找正方形长度，用前缀和算出对应正方形的结果就是O(N^2logN)，最佳方案是O(N^2)，算一遍前缀和，再用行列遍历时，如果当前行列数均超过当前最大长度maxLen，直接计算maxLen+1，这个方法的正确性可以用反证法得到。

其实我很想吐槽我店面的时候面试官，让算无序数组两数之和绝对值的最小值（其实就是2sum的变种），我给出双指针解法后居然不知道是对的然后让我用二分写出来……

楼主二面那道是https://leetcode.com/problems/ma...eshold/description/这个吗

补充内容 (2019-12-23 15:40):
LC 1292

aranne 发表于 2019-12-24 07:39
楼主二面那道是https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-eq ...

对的，用前缀和暴力搞的，当时也想过二分查找，但是没写

大佬好强 以前竞赛 acm noip搞过的吧  

补充内容 (2019-12-25 11:46):
https://www.youtube.com/watch?v=SImXsBQQCEE   

补充内容 (2019-12-25 11:47):
1292

非常感谢楼主分享，电面第二道是求N个数组中从前往后第一个重复的数相关的，可以详细说下题目吗？没太看懂。

crystal0309 发表于 2019-12-25 16:47
非常感谢楼主分享，电面第二道是求N个数组中从前往后第一个重复的数相关的，可以详细说下题目吗？没太看懂 ...

与函数式编程相关的，就是给你N个数据流（可能是无穷的）,然后找到所有数据流中同时出现的第一个数。不知道你明白不，直接用mergesort思想做就可以了。

stkevintan 发表于 2019-12-25 17:01
与函数式编程相关的，就是给你N个数据流（可能是无穷的）,然后找到所有数据流中同时出现的第一个数。不知 ...

没看懂 题目意思  跟归并排序有什么关系呢   能在说说么  没看懂

拿到offer了吗