一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 7038|回复: 46
收起左侧

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

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

有一个机器人在二维平面上,开始在(0,0)点,头向北,
机器人只接受三个指令,G,L,R. G向前走一步, L 左转90度, R右转90度。
现在给定一个命令序列s,机器人一直重复执行这个序列。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
问能不能在平面上画一个圆,保证机器人会走出这个圆,圆的半径不需要是整数.

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

例1 s=“GGGR”, 机器人一直在围着一个正方形轨迹走.
返回YES. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

例2 s=“GGRGGL”, 机器人向着东北方向走向无穷远
返回NO
. 鍥磋鎴戜滑@1point 3 acres
注意s的长度可以达到50,000


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

评分

3

查看全部评分

本帖被以下淘专辑推荐:

snklee 发表于 2015-8-13 15:35:10 | 显示全部楼层
We only need to look at diraction the robot facing and position is will be at the end of one sequence execution.
Let's assume position is (x,y), direction is in {up, down, right, left}.
Original direction is up.
.鐣欏璁哄潧-涓浜-涓夊垎鍦
if (x,y) == (0,0):
return True
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
         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.

回复 支持 5 反对 0

使用道具 举报

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

我画了几张图,好像是如果执行完一个序列导致机器人的朝向和起点朝向相同,就会导致它永远沿着一个方向前进而不会回来
但如过朝向不同,就会在执行几次序列后回到起点, 然后重复相同的图案前进
回复 支持 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
    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
这个题的关键是不是看机器人是否会回到起点,从而构成一个死循环呢. more info on 1point3acres.com

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

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

使用道具 举报

windream1991 发表于 2015-8-13 06:28:03 | 显示全部楼层
Linzertorte 发表于 2015-8-13 06:20
接近真相了。你能不能写写伪代码呢?
你还少了一个情况,corner case.
. from: 1point3acres.com/bbs
corner case应该是回到原点吧
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 07:02:25 | 显示全部楼层
写了个个逼真的机器人。大家用来测试下自己的猜想。  只要改那个cmd变量就行了。能看到机器人最后走到了哪
  1. class Robot:. 鍥磋鎴戜滑@1point 3 acres
  2.   def __init__(self):
  3.     self.d = 0
  4.     self.dname = ['north','east','south','west']. from: 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},
  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:. 1point 3acres 璁哄潧
  16.       v = self.f[instr]. Waral 鍗氬鏈夋洿澶氭枃绔,
  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. from: 1point3acres.com/bbs
复制代码
回复 支持 反对

使用道具 举报

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
google的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的问题了。有同学能举个反例吗??.1point3acres缃

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

使用道具 举报

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

如果回到原点,显然存在圆.鐣欏璁哄潧-涓浜-涓夊垎鍦

如果不回到原点,就根据第一步的方向和最后一步方向判定就是了。. Waral 鍗氬鏈夋洿澶氭枃绔,
如果一样就不存在圆,如果不一样就存在圆。

上面逻辑可能存在问题,但是大抵也就这样了。大不了四象限的四个方向枚举一下。
核心是不用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
维持一个坐标记录最后离原点的位置。.1point3acres缃

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

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

使用道具 举报

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

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

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

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

custom counter

GMT+8, 2016-12-9 00:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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