面经1

第一轮：

topological sort。我写了上百遍了（DFS wik版本），但是华人大叔没太看懂为什么有两个visited set，所以解释了好久。

第二轮：

int[][]矩阵，求是否满足性质：左上角到右下角的斜线上的值都要相等。比如(0,1)(1,2),(2,3)这些要相等。 小伙伴告诉过我这题，所以我知道follow up是矩阵很大，每次只能读一行怎么办，所以我一开始就写了两行两行比较的算法，面试小哥有点蒙蒙，依然也给了这个follow up，秒了。然后还剩二十多分钟，小哥就给了第二个follow up：现在一行都太大没法读进来，但是可以允许算法不是100%准确的。然后我也不知道为什么灵光闪现，想起来大四的时候跟实验室同学聊天知道的一个压缩矩阵保持feature的方法，然后给出了：每次取出matrix的一小块，算一个signiture（比如乘一个vector就能压缩到一维向量），然后整个矩阵就可以压缩，保持一定的feature，最后用前面的算法做，有False positive，但是满足性质的matrix一定是返回True的。小哥说每次读一小块太昂贵了（因为有不同行，从disk的一个条带上读的话跨越太多）， 只能一行一行读，每次读一小点。我说那就能读多少读多少（比如读N），signiture简单乘上一个固定的vector（大小N）压缩成一个int就好了，这样整个大矩阵也可以每行一点一点压缩（每行压缩的时候要有offset，因为是斜着比较的），如果压缩一次不够的话，还可以递归压缩，直到内存足够读入一行为止。最后小哥让我写代码，写完表示非常非常非常满意。

第三轮：

LC394，剩十分钟follow up是反过来encode，求最短encode（跟我说前面那个是warm up，这才是真题）。懵逼，给了个贪心+memory的算法（代码非常乱），也不知道能不能得到最优解。没做出来。。。最后结束的时候她说这题很难很难，让我don't worry，用DP做（分析题目的时候我试了一下，她没有hint所以我没继续下去），然后我才想到用dp[k][i][j]做应该可以。。。但也没时间写了。。

第四轮：

这题真是前所未见的，白人面试官，带一个非常可爱的华裔小帅哥shadow。题目：double[][]矩阵，值表示高度，所以是一个3D的地图。现在无限远处平行光射入（任何角度），求矩阵上那些点被遮盖住了。 懵逼。开始各种分析，我以为是设计题，就3D阴影建模。正要开始写class的时候，然后得到hint：从每个cell看向太阳方向，所以想到现在2D上，对一条光路ax+by=0，求哪些cell相交（这个挺难算的，在hint和反复的question下，我最后给出了三条平行线算计算相交cell，面试官表示肯定）。然后跟面试官negotiate得到只需要考虑中心点被覆盖，同时相交cell之间的距离就近似成中心点的距离（因为要计算tanA*distance(p1,p2)得到高度）。。。。总之到最后是给出了一个算法，写了一点点中间步骤的代码，但是整个代码是没写的。结束的时候考官问我感觉怎么样，我说没有想到是这种数学题，他说我们希望看到你分析这个题然后写成代码的整个过程，我说可惜我还是没写完代码呀，他点点头说嗯（我就觉得完蛋了）。最后朋友圈大神说这是计算机图形学最后几章的问题，什么z buff scan算法。。。。

总结：

好的就这样，等待HR反馈。。。。我个人觉得已经发挥我所有实力了，但感觉依然有风险。。第三轮followup不好，第四轮只分析出来算法没写出代码。.