狗家油管上门面经

很有用的信息！

ulim 发表于 2018-8-18 13:32
还是不太明白为什么linear time。比如我现在要看B，发现第一个pos不行，也许第二个行，或者第某个可以。 ...

的确是，之前有一种Worst Case没有想到，照这样的话只能nlogm, 不知道有没有更好的解法可以做到Linear。

用'ABC'的sub-sequence来组成 'CBA', 求问这题用KMP怎么解呢?貌似kmp是整substring的, 想不太明白. 感谢

szyyn95 发表于 2018-8-17 11:21
**** 本内容被作者隐藏 ****
顺便，楼主的面经很用心，点赞

@szyyn95, 第四轮, "面试官是不是想问最少用多少个拼出来呢，那就和地里一个店面题很像" 请问你还记得是哪个帖子吗? 谢谢!

atlantic7200 发表于 2018-8-20 17:26
@szyyn95, 第四轮, "面试官是不是想问最少用多少个拼出来呢，那就和地里一个店面题很像" 请问你还记得是 ...

自己搜一下，谷歌的店面题，至少有二十条讨论我记得，就是八月份的，那么多积分呢不用白不用

szyyn95 发表于 2018-8-20 21:27
自己搜一下，谷歌的店面题，至少有二十条讨论我记得，就是八月份的，那么多积分呢不用白不用

感谢提示, 是不是这篇, 这篇的楼主最后过了, 貌似这题面试官只要求O(m*n) http://www.1point3acres.com/bbs/thread-437474-1-1. html

补充内容 (2018-8-21 01:11):
http://www.1point3acres.com/bbs/thread-437474-1-1.html

补充内容 (2018-8-21 01:56):
再補充一下, 應該用類似szyyn95提出的這個做法就可以了.
http://www.1point3acres.com/bbs/ ... p;page=3#pid4380320

补充内容 (2018-8-21 06:41):
刚才又想了一下, szyyn95的做法好像也是O(m*n, m = len(A), n = len(B)). pop掉那些已经小于当前index的值+更新queue的worst case还是O(m*n) ; eg: A="CCCCCC"对上B="ABCA", 那对每个'C'都要O(n)的时间去reset

atlantic7200 发表于 2018-8-21 01:04
感谢提示, 是不是这篇, 这篇的楼主最后过了, 貌似这题面试官只要求O(m*n) http://www.1point3acres.com/b ...

我在那个贴子里提到的那个pop list in dict的做法其实是错的，原因在于如果你只检查每个list的最后一个（下一个被pop的val），会遇到一个edge case:假设现在a在dict里的list是[7,3]，现在的index是6，实际上list里的7是可以的，但是由于3并没有被pop掉，导致你误认为需要再来开始一个新的String。

canoee 发表于 2018-8-17 11:59
MTV zszszs

对于选择去 Mt View 还是去 San Bruno 面， 楼主有什么推荐吗？