巨婴OA跪经

Job Hunting Interview
, , , , , ,
1

经历了一天准备全部OA题 https://leetcode.com/discuss/interview-question/398023/Microsoft-Online-Assessment-Questions
心想着至少中一题吧，结果一题都没中，还碰到巨恶心的类型（可能是DP和Binary Search）。

60分钟3题，只做了一题。。今年又和微软无缘了。

  1. 尒一

  2. 给你一个integer array （假设可以负数），和一个startIndex,

    写个function确认能不能到达终点，终点的值为0。

    如果你所在位置为i, 你能move left OR right by nums [ i ].

    我相信这是旧题，不知道什么时候地里见过，可是没有看过正确答案。

    和Frog Jump差不多，但是难很多。区别在于F.J是从index = 0开始，第一次跳为1格，终点index >=nums.size().

  3. 给你一个sorted array， 和一个integer n表示numbers of buckets，

    写一个function把这个sorted array 分解成n个sub array，

    使得每个sub array 的总和（weights） 差不多相同。 （approximately equals）

EX: [1,2,3,4,5], result = [[5], [4,1],[3,2]] 有点像咬零药药，不过做法肯定不一样。

2

2和3我都没见过原题，可能LC刷得还不够，只刷了400多
第二个应该是快慢指针的题型，结果就是看看在到达最后一个值之前有没有circle或者走进死了胡同。但是我怀疑楼主的描述有点小问题，应该是负数只能往左走，正数只能往右走，否则就没有正负数的必要性了，而且就无法快慢指针了。
循环中就考虑两点，是否走进了死胡同，就是没路走了，也就是 (i+num[i] < 0 || i +num[i] > num.Length), 或者出现了circle 也就是两个执政 fast == slow了。就停止循环返回false，在停止循环之前如果num[fast] == 0就返回true.
最后一题我能想到的解法不知道是不是正确，因为对这个approximately equals拿不准。新建一个class，里面两个property, sum 和 list。基于这个class建立一个priority queue，排序的顺序就是sum的大小。从大到小遍历那个数组，如果pq.Count() < n就根据当前数字新建一个class加进去，否则就把当前数字加到pq的最小的里面。我不知道该怎么证明，但自己试了几个test case，好像都对…

第二题的确没有注明有负数，但是由于题目只说了an array of integers,所以假设有负数也是没问题的，虽然没什么用。原题是这样：

You’re given an array of integers, such as arr = [3,4,2,3,0,3,1,2,1], and a start index.
When your’re at an index i, you can move left or right by arr. Your task is to figure out if you can reach value 0.

第三题的话我当时只想起以前好像做过类似的题目，可是忘了怎么做了。你这个做法应该是正确的，用sum来做比较，建一个min heap.做法有点像散气散。

3

如果是这样那就BFS，用一个bool visited来记录那些已经查过了的visit过的点，如果在queue变成空之前到达了最后一个点，返回true。否则就是false。

我觉得基础思路是一个memory cache存visited的数据，然后recursion。由于每个node都有两种走法（左和右），所以能走到的路径是多种并且会重复的。一旦array变得很大的情况下，我不知道BFS会不会TLE，但其实真正的思路都是一样，那就是memorization + DP。只是要我在60分钟/2 = 30分钟内解出来的实在难（第一题一分钟不用），所以真心运气不好。昨晚15个·小时的准备一题都没用上，果然运气和实力都很重要啊

4

这题只要加入visited去重，memoried search记忆化搜索, 怎么做都是o(n)的时间复杂度，dfs, bfs都可以，要是这都TLE, 我想不出有什么小于o(n)的解法。
这题真心不难，我觉得你over think了，是不是上来就往复杂的dp上走了

看来我是overthink了，坏习惯。。不过当时的确怂了，犹豫就会败北没毛病

5

这题只要加入visited去重，memoried search记忆化搜索, 怎么做都是o(n)的时间复杂度，dfs, bfs都可以，要 …

感谢你的帮忙，我最后自己重做一遍，不知道有没有了什么edge cases

第二题我改了一下我Jump Frog的代码，例如memorization + DFS做 (真希望有人能检查一下代码）。
第三题用你的思路写的，让我回忆起了以前真的做过。