Google Onsite 11.23

上周五hr通知说过了hc了，发一下面经攒攒人品！
第一轮
白人大叔
input:
G . . G
X . . .
. G . .
G是终点，.是可走的点，X是不可走的点
output:
求出每个可走的点到终点的最短距离（每一步可上／下／左／右一步）


我的做法是经典的BFS。先构造一个距离矩阵，所有G的点对应的是距离为0，其他点为MAX_INT。然后将G的点放入Queue中进行BFS，修改距离矩阵。

follow up:
如果每一步可走两步／三步怎么办？
如一步可走：左左，左上，右下，。。。
我说应该画出解空间树，然后DFS遍历解空间树，DFS的返回值是从该点出发最少需要几步到达一个G点。大叔说make sense。

第二轮
白人Geek小哥
input:
string stream
如 abckdeghs...

有一个se

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

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

方形。

关键在于四条边的关系。

一点感想：
Google onsite是我最紧张的一次onsite了。感觉中途代码写的不是bug free，不过面试官一直安慰我说他们看重的是思维。
觉得自己很幸运，遇到两个国人哥哥，真是非常谢谢他们！面试过程中可以感觉出来Google很看重思维的过程。整个过程中我都在和面试官不断的交流，每道题（除了第一轮）都拿出了2到3种方案，感觉他们对于这点还蛮满意的。






补充内容 (2015-12-10 00:50):
求大米啊～～

第二题：
给出四个点的坐标，判断这四个点能否构成一个正方形。

关键在于四条边的关系。
****************************************************************
我的想法是： 计算出任以 两点的距离，共6个， 然后对距离排序， 如果前4个距离相等，后2个距离相等，可以认为是正方形

欢迎拍砖

根据JohnsonMS 的思想写了下代码

1. public class Square {
   
2.         static class Point {
   
3.                 int x;
   
4.                 int y;
   
5.                 public Point(int x, int y) {
   
6.                         this.x = x;
   
7.                         this.y = y;
   
8.                 }
   
9.         }
   
10.         public boolean isSquare(Point[] points) {
    
11.                 if (points == null || points.length != 4) {
    
12.                         return false;
    
13.                 }
    
14.                 List<Integer> dis = new ArrayList<Integer>();
    
15.                 for (int i = 0; i < points.length - 1; i++) {
    
16.                         for (int j = i + 1; j < points.length; j++) {
    
17.                                 dis.add(getDis(points[i], points[j]));
    
18.                         }
    
19.                 }
    
20.                 Collections.sort(dis);
    
21.                 if (dis.get(0) != dis.get(1) || dis.get(1) != dis.get(2) || dis.get(2) != dis.get(3) || dis.get(4) != dis.get(5)) {
    
22.                         return false;
    
23.                 } else {
    
24.                         return true;
    
25.                 }
    
26.         }
    
27.         private int getDis(Point point1, Point point2) {
    
28.                 return (int) Math.sqrt((point1.x - point2.x) * (point1.x - point2.x) + (point1.y - point2.y) * (point1.y - point2.y));
    
29.         }
    
30.        
    
31.         public static void main(String[] args) {
    
32.                 Square s = new Square();
    
33.                 Point[] points = {new Point(1, 1), new Point(2, 0), new Point(0, 1), new Point(1, 0)};
    
34.                 System.out.println(s.isSquare(points));
    
35.         }
    
36. }
    

复制代码

pigmightfly 发表于 2016-1-19 18:28
只能走n步。
就是每个格子的步长不一样。
比如到A格子，步长是三步。在B格子，步长是两步。

楼主 按照你的描述 我的理解是：从一个格子，如果想走到其他周围四个格子的任意一个，需要走过的路程都是不同的，例如向左走一步需要2step，向上走一步需要3step等等。
如果我上述理解无误，那么我觉得可以通过Dijkstra方法解答。
BFS一般用于解决edge长度为1的最短路径问题，而Dijkstra用于解决一般性的edge非负的情况。
数据结构可以使用HashSet 和 indexed heap解决。复杂度是nlogn
楼主说的“空间树”的解法一般用来处理NP-hard问题，就是传说中的暴力解法。例如TSP问题，一般可以通过
此法解决。不过最短路径依然需要在空间树中通过BFS解决。例如经典的水桶倒水问题。优化一般用A*。

补充内容 (2016-1-20 09:43):
算法复杂度中的 n 指的是 矩阵中的 边或点 的数量。

LZ能再具体说一下“于是想到可以用两个map，第二个map是记录(s[i], t[i])这一对tuple的位置的。于是由第二个map可以找到将差异值减小2的解，由第一个map可以找到将差异值减小1的解。”
非常感谢！

ssross 发表于 2015-12-9 10:13
LZ能再具体说一下“于是想到可以用两个map，第二个map是记录(s, t)这一对tuple的位置的。于是由第二个map可 ...

map2 是这样的
(a,e): 0
(b,b): 1
(c,c): 2
..
那么每遍历到一个新的tuple，比如(e,a)，就查一下(a,e)是否已在map2中，如果是，那说明存在这个交换使得差异值减少2.

ssross 发表于 2015-12-9 10:13
LZ能再具体说一下“于是想到可以用两个map，第二个map是记录(s, t)这一对tuple的位置的。于是由第二个map可 ...

map1 还是记录source string的char的位置
a: 0
b: 1
...
那么遍历target string的时候，比如第一个元素e，只要发现map1中存在e并且index不同，那么说明至少有一种交换是可以将差异值减少1的。

谢谢楼主分享～请问怎么怎么判断四个点能否构成正方形哈？首先要四条边长度相等，然后再判断四个夹角是不是90度嚒？

xiaoniuona 发表于 2015-12-15 08:08
谢谢楼主分享～请问怎么怎么判断四个点能否构成正方形哈？首先要四条边长度相等，然后再判断四个夹角是不是 ...

单纯判断边的关系即可

randomusername 发表于 2015-12-15 08:21
楼主可以说说等待的流程嘛..
onsite到送hc等了多久呢
然后hc等了多久呢

我正好面试那周是感恩节，所以拖了一点时间。我从onsite到hc是等了两周，hc当天出的结果。

randomusername 发表于 2015-12-15 08:36
两周这么久...敢问楼主是怎么熬过的...(会不会像我一样每半小时看一次邮件呢）

我当时面完就知道结果不会出那么快（因为感恩节嘛），所以还好哈哈。。最后是要赶上我另一个offer的ddl，才和hr催了一下。你要是实在不安心，就问联系你的hr大概啥时候有结果吧