Google 四月初上门

四月初的阳谷面试

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

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

补充内容 (2019-4-5 01:09):
第一轮补充：老鼠先走，双方轮流，每次步数走<=各自的maxStep。老鼠从猫身上过没关系。
第五轮补充：Follow up：如果是除去较大的%m和较小的%n求平均值呢

只身回马枪 发表于 2019-4-15 23:37
所以，楼主采用的方法是，BFS的时候，人为的加入一个“边界”？（比如，然后，判断当前点向下一层扩散时 ...

是的，我是这个意思。我觉得这样应该是没问题的。一个不严格的证明：
假设在无限大平面内存在一条从起始S到终点D的路径path。
    如果这条路径根本不需要进入外面加这个框，我们定义的BFS显然可以找到这条路径；
    否则的话对于该路径path，从两头S和D分别出发，一定分别有第一次进入我们定义的外框的点A和B，那么很容易证明仅利用外框我们就可以找到从A到B的马步跳法。从而我们找到了一条在我们自定义边界内的路径path1，而且这条path1一定可以被我们的BFS找到。Over

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

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

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

最近第二次看到猫抓老鼠了，让我好慌啊，感觉楼主的题都偏难

其实第一轮如果输入是二维矩阵感觉比较像妻疤玖，但是多了障碍物，这题是看鼠（人）到终点的距离有没有比猫（鬼）到终点的距离近，加了障碍物是不是改BFS就行了？还是我的直觉想法是错的？

第五题，双pq?

感觉每一轮都是hard……

第三轮简化后简单了不少，只需要two pointer了吧。

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

第五轮是面筋，我看一般用heap来做，但是java和python的heap的remove的操作一个是O（n）一个压根没实现（虽然有所谓的lazy delete但是很麻烦）。楼主是如何实现的呢？

补充内容 (2019-4-4 21:20):
这题似乎不需要remove操作，面经里面是length=k的滑动窗口。

kaipeng21 发表于 2019/04/04 12:39:03
其实第一轮如果输入是二维矩阵感觉比较像妻疤玖，但是多了障碍物，这题是看鼠（人）到终点的距离有没有比猫（鬼）到终点的距离近，加了障碍物是不是改BFS就行了？还是我的直觉想法是错的？

如果是同时走，感觉和你说的更像一点。否则好像更像楼主说的那题

umialpha 发表于 2019-4-4 16:15
第三轮简化后简单了不少，只需要two pointer了吧。

试着写了下。

1. String shortestSuperstring(String a, String b){
   
2.         String r1 = getSuperString(a,b);
   
3.         String r2 = getSuperString (b,a);
   
4.         if (r1.length()<r2.length()) return r1;
   
5.         return r2;
   
6.     }
   
7. 
   
8.     private String getSuperString(String a, String b) {
   
9.         for (int i = 0;i<a.length();i++){
   
10.             String s= a.substring(i);
    
11.             if (b.startsWith(s)){
    
12.                 return a.substring(0,i)+b;
    
13.             }
    
14.         }
    
15.         return a+b;
    
16.     }

复制代码