Google Singapore 電面

Google SG phone interview
date: 2019/June/11

Problem 1 get distance between X Y:

The string composed of X Y O, please return the closest distance between any pair of X and Y
e.g.
YOOOOOXOOOXOY

X: 10
Y: 12
→ Output = 12 - 10 = 2

interviewer agree with this solution

1. 
   
2.     def get_dist(str):
   
3.         min_dist = float('inf')
   
4.         is_X = None
   
5.         last_index = None
   
6.         for index, char in enumerate(str):
   
7.             if char == "X":
   
8.                 if is_X is None:
   
9.                     is_X = True
   
10.                     last_index = index
    
11.                 # if last seen valid character is Y
    
12.                 if is_X = False:
    
13.                     dist = index - last_index
    
14.                     min_dist = min(min_dist, dist)
    
15.                     is_X = True
    
16.                     last_index = index
    
17.                 # if last seen valid cahracter is X
    
18.                 if is_X = True:
    
19.                     last_index = index
    
20.             if char == "Y":
    
21.                 if is_X is None:
    
22.                     is_X = False
    
23.                     last_index = index
    
24.                 # if last seen valid character is X
    
25.                 if is_X = True:
    
26.                     dist = index - last_index
    
27.                     min_dist = min(min_dist, dist)
    
28.                     is_X = False
    
29.                     last_index = index
    
30.                # if last seen valid cahracter is Y
    
31.                 if is_X = False:
    
32.                     last_index = index
    
33.         return min_dist

复制代码

Problem 2: get min distance between X Y 2D version

description:

2d array with 3 types of characters: X Y and O, get the shortest distance between any pair of X and Y
OOOOXX
XOOOOO
OOYYOO

Output = 3

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

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

求大米！十分感謝！
八月要去onsite
                           
                  
                  
                  

Problem 2 的一个O(m*n)的思路，用BFS：
先取得所有X，Y坐标
对存储的X做BFS，检查相邻的格子，如果有Y就返回当前步数，如果有O就标记为X并加入下一次BFS的列表
对Y重复上一个步骤
这样每个格子都最多走过一次，得到O(m*n)
在XY数量都很多的时候(lz解法的worst case)效率高