狗家onsite - MTV

刚刚面完出来,回想一下面试的题目感觉都不是很难,但是做题的时候都有各种卡住之类的,感觉有点凉。出来发个面经希望可以攒点人品求过!!!!!

在MTV面的四轮onsite。

第一面:白人小哥高频面经题,给一个坐标系,只能往右, 右下和右上走。问从(0,0)走到(w,0) 然后走过的高度小于等于给定的范围h,一共有多少valid path。跟面经里那个从左上角走到右上角差不多。
问了时间和空间复杂度,还问了时间复杂度可不可以优化,最多可以优化到什么样。问到这里我就蒙了,后来开始瞎猜,好像意思是说有一些确定不能visit到的点就不用考虑了吧。如果h特别大的话,时间可以算短到到1/2w^2这样?

followup1:给一堆点,要求找到所有经过从(0,0)到(w,0)并且经过这些点的路径数量
followup2:给一个高度min_h,要求找到所有会碰到min_h的路径数量

followup3:给一堆高度,要求在走的时候按顺序访问这些高度的路径数量

看过这个面经,也想过,但是最后一问到自己讲的时候还是有点糊涂应该怎么做。最后小哥也一副有点糊涂的样子,所以。。。。。。难受!

第二面:白人小哥
应该也是面经题吧?给一个binary tree作为棋盘。游戏设定是两个玩家,一人选一个点,然后开始按顺序占点,每次可以占自己已经占了的点相邻的点。已知root和对手选的点,找出任意一个能够保证自己胜利的点,如果没有这样的点就返回None。

三种情况分类讨论,然后比较subtree size和剩下的node 的个数。

followup:现在你是第一个玩家,返回一个点可以确保你的胜利。如果没有这样的点,一样返回None。

一开始做followup的时候,就直接用第一问的function做了,然后问到时间复杂度的时候就说O(n^2), 这里n是tree size。小哥问能不能再优化,想半天,其实可以把subtree size存起来,就不用每次去找了。感觉中间这个沉默是真的有点久了。。。不知道会怎么样。

午饭:国人小姐姐
小姐姐人很好,上来就跟我说只是带你吃午饭,不会计入feedback的所以放轻松

第三面:国人小哥
大概是面的最惨的一轮。上来先问简历,然后问了几个简单的问题。什么thread vs process啊。deadlock你知道不?咋预防deadlock你知道不?

给了一个class,replacement,里面有start_idx, before,和after。主要想要实现的是text replacement。然后让写一个function,input是一串这样的replacement和一个string,让返回一个更新完的string。

就从后往前sort一下然后replace就好了。

followup:你的replacement可能是invalid的,这种情况怎么办?那就check每个相邻的replacement有没有overlap呗?
问了时间复杂度之类的,感觉自己答的不是很好TAT。因为楼主写的是循环的时候立即更新string,所以时间复杂度比较高。然后就问了有没有什么办法可以进行优化,其实我大概知道他是什么意思,但是我就是想不出来可以怎么搞,瞎说了一个可以把东西存再map里面最后再合并呀。最后告诉我可以用linkedlist【我为什么没有想到TAT

其实很简单的题我觉得这个哥哥是真的给我放水了,但是其实表现还是不是很好。可能上午遇到两道面经,下午上来就是没见过的题目有点慌了。

第四面:白人小哥
问简历。然后就问题目,说给一个array里面有好多数字,然后有一个function可以检查这些数字是不是dirty。想要的返回是一个array里面没有这些dirty number。
. From 1point 3acres bbs
返回的array要按照原来的顺序,并且希望时间复杂度是O(n)
从左向右扫,存一个dirty number的index,然后遇到不是dirty的就和他swap,然后更新index+1,这样所有不是dirty的就会在前面,是的就会在后面。然后从后往前pop掉所有想要被删掉的数字就可以了。

还问了unit test话有些什么testcase
总之四面的题目都不是很难,但是都有卡壳的情况,面试官也给了很多hint才做出来这些题目。准备moveon了。。。感觉自己还是水平不够。

如果知道对方的node, 那么3个选择, node->left , node->right, parent, 选其中tree size 最大的
如果不知道对方Node, 那么任选一个Node会导致三个结果: node->left, node->right, parent, 对方会贪心选择最大那个branch, 我方的选择要保证对方选择的是parent, 并且 left + right > parent, 就赢了。

感觉这个题目可以双指针头尾扫描。
i 如果指向的dirty number, j 寻找第一个正常数字然后交换
i == j 结束

请问第二轮follow up怎么选点才能确保胜利呢?

谢谢楼主分享

感谢分享!

请问楼主,最后一题中如果一个dirty number后面连续有m个dirty number,怎么处理呢,如果把它们index都记下来和下面出现的第一个non dirty number换位置这个操作不是O(1)吧,那如何保证整体上的运行时间是O(n)呢

不一定啊,onsite看的是交流。有hint能做出来就很好的啊。

占领树的那题没什么思路,能不能求楼主说说

但是这样不能保证array是原来的顺序啊,比如1,2,3,4,5里面如果只有2是dirty number,这样换完了之后就变成1,5,3,4了,desired return应该是1,3,4,5