一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 14446|回复: 48
收起左侧

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

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

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

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

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

x
看过这么多面经,大家或许会发现Google的面试并不是大部分来自leetcode原题,所有不是说你使劲刷leetcode,甚至能默写下来的程度就一定能拿到offer.. more info on 1point3acres.com
然后许多谷歌的面试题,是需要一点思维的,如果想出来,写代码并不是特别难。 其实这样比直接 让你默写 leetcode的valid number, regular expression会更有诚意一些。
比如说下面这道题,大家可以讨论一下。
游客,本帖隐藏的内容需要积分高于 133 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
. 鍥磋鎴戜滑@1point 3 acres
注意s的长度可以达到50,000



补充内容 (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):. more info on 1point3acres.com
return True. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
else:
return direction != up
-google 1point3acres
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.1point3acres缃
         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
这个题的关键是不是看机器人是否会回到起点,从而构成一个死循环呢
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我画了几张图,好像是如果执行完一个 ...

接近真相了。你能不能写写伪代码呢?
你还少了一个情况,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):. from: 1point3acres.com/bbs
  3.     self.d = 0
  4.     self.dname = ['north','east','south','west']. 鍥磋鎴戜滑@1point 3 acres
  5.     self.dx = [0,1,0,-1]
  6.     self.dy = [1,0,-1,0]
  7.     self.x = 0
  8.     self.y = 0. From 1point 3acres bbs
  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:
  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']. 1point 3acres 璁哄潧
  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
google的onsite难度吗?电面不会就这么难吧

这个题代码不难写。主要是思路。
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| Linzertorte 发表于 2015-8-13 07:57:39 | 显示全部楼层
jiebour 发表于 2015-8-13 07:51. more info on 1point3acres.com
楼主,你的问题到底是什么?保证机器人走出这个圆?还是走不出这个圆?
.1point3acres缃
走不出这 圆。打错了。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

如果不回到原点,就根据第一步的方向和最后一步方向判定就是了。
如果一样就不存在圆,如果不一样就存在圆。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

使用道具 举报

 楼主| 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
维持一个坐标记录最后离原点的位置。
. 鍥磋鎴戜滑@1point 3 acres
如果回到原点,显然存在圆

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-12-14 23:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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