Google 四月初上门

第五轮代码。

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

xiangwangtong6 发表于 2019/04/04 19:20:43


试着写了下。
[mw_shl_code=java,true]String shortestSuperstring(String a, String b){
        String r1 ...

你这个核心方法复杂度还是O（n**n）你用两个指针一个从a的头，一个从b的尾开始遍历。可以复杂度降为o（n）

补充内容 (2019-4-4 21:22):
手误是O(n*n)

第一轮补充：老鼠先走，双方轮流，每次步数走<=各自的maxStep。老鼠从猫身上过没关系。

kaipeng21 发表于 2019-4-4 12:39
其实第一轮如果输入是二维矩阵感觉比较像妻疤玖，但是多了障碍物，这题是看鼠（人）到终点的距离有没有比猫 ...

我还是按照猫鼠那题的思路做的，只能每轮BFS一下了

umialpha 发表于 2019-4-4 16:16
第二轮 无限大棋盘，楼主用A*算法了么？如果没有用，bfs的时候是怎么样定义行走的规则呢？

首先不带障碍的BFS肯定没问题，因为马理论是可以到达棋盘的任何位置的。至于带障碍的follow up没让写code，根据个人实际经验：如果能到达那么马走最少步数可能走过的位置应该是在【包含起点，所有障碍，和终点的最小矩阵的若干倍以内的矩形里面】。所以我觉得BFS的时候加个边界好了，比如长宽都 * 3（如果长宽都很小可以设个最小界限，比如起码搜索20 * 20之类的）。

xiangwangtong6 发表于 2019-4-4 19:20
试着写了下。
[mw_shl_code=java,true]String shortestSuperstring(String a, String b){
        Stri ...

是不是有个corner case需要考虑下：String a = "abcdefg", String b = "cde"

umialpha 发表于 2019-4-4 21:01
你这个核心方法复杂度还是O（n**n）你用两个指针一个从a的头，一个从b的尾开始遍历。可以复杂度降为o（n ...

请问一个从头一个从尾不是反着的吗，要match的部分都得正着来，还是我没理解意思？

感觉现在SVL的面试难度不只高了一点点... 另外周五面试会不会比较好？几个哥们是周五onsite的 题目都不难...我这周二面的 直接要设计一个多线程系统...

楼主面的level4/5？  

umialpha 发表于 2019-4-4 21:01
你这个核心方法复杂度还是O（n**n）你用两个指针一个从a的头，一个从b的尾开始遍历。可以复杂度降为o（n ...

= =没想到你的方法是什么...能详细说下么0 0
这里想了想要做到O(N)似乎要用后缀数组+LCP然后单调扫一遍解决...
不错过onsite写O(N)后缀数组= =....有点难