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...

有一个search list［google, ok, doit

您好！
本帖隐藏的内容需要积分高于 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. }
    

复制代码

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

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

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

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

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

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

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

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

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

单纯判断边的关系即可

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

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

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

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