微软北京Azure面经

shinn_qy 发表于 2020-1-1 15:43
拿到offer了吗

已经拿到了~

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

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

楼主，除了做题还问了其他的了吗?

crystal0309 发表于 2020/01/14 12:56:26
楼主，除了做题还问了其他的了吗?

项目上的事情

猜想二面的问题似乎可以O(n^2)

1. 做横向/纵向 每一行列的前缀和
2. 要求最大的正方形，所以在每一行做纵向的滑动窗口（或者每一列做横向滑动窗口），窗口宽度就是正方形边长。每一次滑动导致的扩大和缩小的框住的数字和都可以用前缀和来O(1)得出，滑动 O(n)， 枚举每一行O(n)。综上乘起来得到O(n^2)

楼主，面试完了多久发offer?

crystal0309 发表于 2020-2-8 16:47
楼主，面试完了多久发offer?

还挺快的，比阿里快多了

stkevintan 发表于 2020-2-11 13:14
还挺快的，比阿里快多了

比阿里快似乎适用于几乎所有互联网公司