谷歌 电面面经

楼主投的是 iOS Engineer， 下午投，晚上就收到HR邮件约电话

HR还让我选面试iOS的东西还是 general algorithm，我选了后者。

题目是  给一个字符串 OOXOOXOOYXOOY  返回最短的X Y距离
第一次电面就是谷歌的，缺乏经验，一上来紧张先用 brute force

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

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

，我打电话很多都没听明白，让人家重复了很多次。最后不仅给我面试，还说谢谢我让她知道自己以后说话应该慢一点。

有用的话加个大米，谢谢！

贴一个代码

1. def min_dist(input):
   
2.     last_pos = {'X':-1,'Y':-1}
   
3.     ans = float('inf')
   
4.     for i in range(len(input)):
   
5.         c= input[i]
   
6.         if c in ['X','Y']:
   
7.             last_pos[c]=i
   
8.         if last_pos['X']!=-1 and last_pos['Y']!=-1:
   
9.             ans  = min(ans,abs(last_pos['X']-last_pos['Y']))
   
10.     return ans if ans < float('inf') else -1
    
11. 
    
12. assert min_dist('XOOOOY')==5
    
13. assert min_dist('XOOXOOX')==-1
    
14. assert min_dist('XOYOXOOOY')==2

复制代码

可以这样做吗 从左往右扫描 记录 lastX 和 lastly, 然后碰到x就算和lastY 的距离 碰到y就算lastX的距离 循环完保存最小的

Sliding Window 就能解决了

祝楼主好运！
又见到一个面google mobile  :)

话说为啥你没选iOS的问题呢？
要是给我选的话我巴不得选ios

evissoup 发表于 2019-4-3 06:13
祝楼主好运！
又见到一个面google mobile  :)

谢谢，可能mobile最近缺人吧

求O(N) 解法啊

这个我想出来的方法
找XY：
先用两个指针，一个往右走找第一个 X 一个从右往左走找第一个 Y
找到后 再用一个指针Z，从  X 出发往右走，，碰到  Y 就更新 globalMin  碰到X，就把左边那个X 换成现在这个，然后再用Z往右走直到碰到最后面那个 Y
然后同样方法找YX

two pointer 一个lastx，一个lasto。lc上记得有原题的，手机码字，不方便查…

kkchenk 发表于 2019-4-3 11:00
可以这样做吗 从左往右扫描 记录 lastX 和 lastly, 然后碰到x就算和lastY 的距离 碰到y就算lastX的距离 循 ...

你这个方法应该是最简单优雅的
可惜我没想出来

kkchenk 发表于 2019-4-3 11:00
可以这样做吗 从左往右扫描 记录 lastX 和 lastly, 然后碰到x就算和lastY 的距离 碰到y就算lastX的距离 循 ...

你这个方法应该是最简单优雅的
可惜我没想出来