May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 11406|回复: 46
收起左侧

[找工就业] 由一道真题看如何准备Google面试

[复制链接] |试试Instant~ |关注本帖
Linzertorte 发表于 2015-8-13 05:06:49 | 显示全部楼层 |阅读模式

2014(1-3月)-[11]CS硕士+fresh grad 无实习/全职 - 内推| 码农类全职@Googlefresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
看过这么多面经,大家或许会发现Google的面试并不是大部分来自leetcode原题,所有不是说你使劲刷leetcode,甚至能默写下来的程度就一定能拿到offer.. from: 1point3acres.com/bbs
然后许多谷歌的面试题,是需要一点思维的,如果想出来,写代码并不是特别难。 其实这样比直接 让你默写 leetcode的valid number, regular expression会更有诚意一些。
比如说下面这道题,大家可以讨论一下。

有一个机器人在二维平面上,开始在(0,0)点,头向北,-google 1point3acres
机器人只接受三个指令,G,L,R. G向前走一步, L 左转90度, R右转90度。
现在给定一个命令序列s,机器人一直重复执行这个序列。. visit 1point3acres.com for more.
问能不能在平面上画一个圆,保证机器人会走出这个圆,圆的半径不需要是整数.

输入s,一个String,代表命令序列.
如果存在这么一个圆,返回”YES”,否则返回”NO”. 1point3acres.com/bbs

例1 s=“GGGR”, 机器人一直在围着一个正方形轨迹走.
返回YES.

例2 s=“GGRGGL”, 机器人向着东北方向走向无穷远
返回NO

注意s的长度可以达到50,000.鐣欏璁哄潧-涓浜-涓夊垎鍦



补充内容 (2015-8-13 07:57):
是走不出这个圆。打错了

评分

3

查看全部评分

本帖被以下淘专辑推荐:

snklee 发表于 2015-8-13 15:35:10 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
We only need to look at diraction the robot facing and position is will be at the end of one sequence execution.. 鍥磋鎴戜滑@1point 3 acres
Let's assume position is (x,y), direction is in {up, down, right, left}.
Original direction is up.
. visit 1point3acres.com for more.
if (x,y) == (0,0):
return True.鏈枃鍘熷垱鑷1point3acres璁哄潧
else:
return direction != up

proof for else conditional branch:
Let's consider it in two canses:
* direction is down
    - in this case, at the end of second sequence execution, robot will come back to original point, facing up. Thus it'll only be doing such back and forth
* direction is one of {left, right}
   - let's assume it is right. The result will also apply because left and right case are symmetrical.
     end of execution
         round 1: position(x                  ,y),                   direction right
         round 2: position(x  +y            , y  -x),             direction down. 鍥磋鎴戜滑@1point 3 acres
         round 3: position(x  +y  -x       , y  -x  -y),       direction left
         round 4: position(x  + y  -x  - y, y  -x  -y  +x), direction up, AKA position(0,0) direction up, the same as original.. From 1point 3acres bbs
.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 5 反对 0

使用道具 举报

Thaib 发表于 2015-8-13 06:02:55 | 显示全部楼层
关注一亩三分地微博:
Warald
这个题的关键是不是看机器人是否会回到起点,从而构成一个死循环呢

我画了几张图,好像是如果执行完一个序列导致机器人的朝向和起点朝向相同,就会导致它永远沿着一个方向前进而不会回来
. 1point 3acres 璁哄潧但如过朝向不同,就会在执行几次序列后回到起点, 然后重复相同的图案前进
回复 支持 2 反对 0

使用道具 举报

liv073 发表于 2015-8-13 11:42:59 | 显示全部楼层
initDirection = UP 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
distanceMoved = getDistance(s)//how far it moved from start point
if(distanceMoved == 0)//still at start point
    return true
else. 1point 3acres 璁哄潧
    afterDirection = getDirectionAfterMove(s)//the direction it faces after the move
    return !(afterDirection == initDirection)
回复 支持 2 反对 0

使用道具 举报

ChrisGates23 发表于 2015-8-13 05:45:42 | 显示全部楼层
无限的执行序列那行走轨迹应该一定要求两点: 1)行走轨迹有周期的,2)起始点和终止点一定是重合的。只要满足这两点就一定可以花这么一个圆。如果是这样,那这两点应当分别处理,先看是否有overlap的点,然后看是否有两个overlap的点之前的路径是相同的
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 05:47:27 | 显示全部楼层
ChrisGates23 发表于 2015-8-13 05:45
无限的执行序列那行走轨迹应该一定要求两点: 1)行走轨迹有周期的,2)起始点和终止点一定是重合的。只要 ...

具体的算法是什么?有伪代码吗
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 06:20:08 | 显示全部楼层
Thaib 发表于 2015-8-13 06:02
这个题的关键是不是看机器人是否会回到起点,从而构成一个死循环呢

我画了几张图,好像是如果执行完一个 ...

接近真相了。你能不能写写伪代码呢?
你还少了一个情况,corner case.
回复 支持 反对

使用道具 举报

windream1991 发表于 2015-8-13 06:28:03 | 显示全部楼层
Linzertorte 发表于 2015-8-13 06:20
接近真相了。你能不能写写伪代码呢?
你还少了一个情况,corner case.

corner case应该是回到原点吧
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 07:02:25 | 显示全部楼层
写了个个逼真的机器人。大家用来测试下自己的猜想。  只要改那个cmd变量就行了。能看到机器人最后走到了哪
  1. class Robot:
  2.   def __init__(self):
  3.     self.d = 0
  4.     self.dname = ['north','east','south','west']. 1point3acres.com/bbs
  5.     self.dx = [0,1,0,-1]
  6.     self.dy = [1,0,-1,0]
  7.     self.x = 0
  8.     self.y = 0. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.     self.f = {'L':{'dx':0,'dy':0,'dd':3},
  10.               'R':{'dx':0,'dy':0,'dd':1},. visit 1point3acres.com for more.
  11.               'G':{'dx':1,'dy':1,'dd':0}}
  12.   def accept(self,instr):
  13.     if instr not in self.f:
  14.       raise Exception("Invalid instruction!")
  15.     else:
  16.       v = self.f[instr]
  17.       self.d = (self.d+v['dd']) % 4
  18.       self.x = self.x + self.dx[self.d]*v['dx']
  19.       self.y = self.y + self.dy[self.d]*v['dy']
  20.     return self
  21.   def __repr__(self):
  22.     return 'Robot at (%d,%d)'%(self.x,self.y)+'facing '+self.dname[self.d].鐣欏璁哄潧-涓浜-涓夊垎鍦

  23. cmd = "GGRGGLGGGGGRR"*4
  24. robot = Robot()
  25. reduce(lambda x,y: x.accept(y) , list(cmd), robot)
  26. print robot
复制代码
回复 支持 反对

使用道具 举报

xuyirio 发表于 2015-8-13 07:03:03 | 显示全部楼层
我怎么觉得最近在哪儿见过这题呢。。。
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 07:26:27 | 显示全部楼层
xuyirio 发表于 2015-8-13 07:03
我怎么觉得最近在哪儿见过这题呢。。。

是啊是啊。最近的新题
回复 支持 反对

使用道具 举报

天空无语 发表于 2015-8-13 07:41:46 | 显示全部楼层
google的onsite难度吗?电面不会就这么难吧
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 07:47:33 | 显示全部楼层
天空无语 发表于 2015-8-13 07:41
. 鍥磋鎴戜滑@1point 3 acresgoogle的onsite难度吗?电面不会就这么难吧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这个题代码不难写。主要是思路。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-13 07:51:39 | 显示全部楼层
楼主,你的问题到底是什么?保证机器人走出这个圆?还是走不出这个圆?
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 07:57:39 | 显示全部楼层
jiebour 发表于 2015-8-13 07:51
楼主,你的问题到底是什么?保证机器人走出这个圆?还是走不出这个圆?

走不出这 圆。打错了。
回复 支持 反对

使用道具 举报

f1371342385 发表于 2015-8-13 12:31:02 | 显示全部楼层
我感觉这一题可以这么考虑,因为每次不是左转90度,就是右转90度,那么对于来说,如果回来的话,肯定会转90度,那么,我们就看看,在四次之内,离原点的值是不是一直增加,如果是那么在转过了4次之后还是一直远离的话,那么肯定不行的,如果是,那么应该走不出
回复 支持 反对

使用道具 举报

danchou 发表于 2015-8-13 12:55:40 | 显示全部楼层
f1371342385 发表于 2015-8-13 12:31
我感觉这一题可以这么考虑,因为每次不是左转90度,就是右转90度,那么对于来说,如果回来的话,肯定会转90 ...

我也这么觉得,如果不能回来的话,结束时刻的方向应该跟开始时候的方向相同。因为不相同的话,感觉怎么转都能转回来。这样就简化成分析字符串里R和L的问题了。有同学能举个反例吗??

补充内容 (2015-8-13 12:56):
然后有个corner case就是一次就回到原点的情况。
回复 支持 反对

使用道具 举报

z928czzc 发表于 2015-8-13 12:56:35 | 显示全部楼层
维持一个坐标记录最后离原点的位置。

如果回到原点,显然存在圆

如果不回到原点,就根据第一步的方向和最后一步方向判定就是了。
如果一样就不存在圆,如果不一样就存在圆。

上面逻辑可能存在问题,但是大抵也就这样了。大不了四象限的四个方向枚举一下。
核心是不用care中间是怎么走的。
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 13:28:39 | 显示全部楼层
f1371342385 发表于 2015-8-13 12:31
我感觉这一题可以这么考虑,因为每次不是左转90度,就是右转90度,那么对于来说,如果回来的话,肯定会转90 ...

赞啊。 不过走一次转180的情况也是有的。
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 13:29:16 | 显示全部楼层
z928czzc 发表于 2015-8-13 12:56
维持一个坐标记录最后离原点的位置。

如果回到原点,显然存在圆

如果需要20分钟之内写出代码来,能不能行?自己能证明正确性吗
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 13:30:24 | 显示全部楼层
z928czzc 发表于 2015-8-13 12:56
维持一个坐标记录最后离原点的位置。

如果回到原点,显然存在圆

你这个逻辑是正确的。但是下面想复杂了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-5-29 05:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表