谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 16995|回复: 50
收起左侧

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

  [复制链接] |试试Instant~ |关注本帖
我的人缘0
Linzertorte 发表于 2015-8-13 05:06:49 | 显示全部楼层 |阅读模式
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】

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

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

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

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

注意s的长度可以达到50,000
. 1point3acres


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

评分

参与人数 3大米 +53 收起 理由
mmliu + 3 感谢分享!
vancexu + 10 interesting question
whdawn + 40

查看全部评分


上一篇:求问dealersocket这个公司
下一篇:想用OPT找在加州的实习,unpaid 也行,希望各位大大提供些机会

本帖被以下淘专辑推荐:

我的人缘0
snklee 发表于 2015-8-13 15:35:10 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
We only need to look at diraction the robot facing and position is will be at the end of one sequence execution.-google 1point3acres
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. more info on 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..本文原创自1point3acres论坛
     end of execution
         round 1: position(x                  ,y),                   direction right. 1point 3acres 论坛
         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

使用道具 举报

我的人缘0
Thaib 发表于 2015-8-13 06:02:55 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这个题的关键是不是看机器人是否会回到起点,从而构成一个死循环呢

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

使用道具 举报

我的人缘0
liv073 发表于 2015-8-13 11:42:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
initDirection = UP
distanceMoved = getDistance(s)//how far it moved from start point
if(distanceMoved == 0)//still at start point. more info on 1point3acres
    return true
else
    afterDirection = getDirectionAfterMove(s)//the direction it faces after the move
    return !(afterDirection == initDirection)
回复 支持 2 反对 0

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2015-8-13 05:47:27 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
ChrisGates23 发表于 2015-8-13 05:45. Waral 博客有更多文章,
无限的执行序列那行走轨迹应该一定要求两点: 1)行走轨迹有周期的,2)起始点和终止点一定是重合的。只要 ...
. Waral 博客有更多文章,
具体的算法是什么?有伪代码吗
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2015-8-13 06:20:08 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
Thaib 发表于 2015-8-13 06:02
这个题的关键是不是看机器人是否会回到起点,从而构成一个死循环呢

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

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

使用道具 举报

我的人缘0
windream1991 发表于 2015-8-13 06:28:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
Linzertorte 发表于 2015-8-13 06:20.留学论坛-一亩-三分地
接近真相了。你能不能写写伪代码呢?
你还少了一个情况,corner case.

corner case应该是回到原点吧
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2015-8-13 07:02:25 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
写了个个逼真的机器人。大家用来测试下自己的猜想。  只要改那个cmd变量就行了。能看到机器人最后走到了哪
  1. class Robot:
  2.   def __init__(self):
  3.     self.d = 0
  4.     self.dname = ['north','east','south','west']
  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:
    .1point3acres网
  16.       v = self.f[instr]
  17.       self.d = (self.d+v['dd']) % 4. Waral 博客有更多文章,
  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
复制代码
回复 支持 反对

使用道具 举报

我的人缘0
xuyirio 发表于 2015-8-13 07:03:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我怎么觉得最近在哪儿见过这题呢。。。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2015-8-13 07:26:27 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
xuyirio 发表于 2015-8-13 07:03
我怎么觉得最近在哪儿见过这题呢。。。
来源一亩.三分地论坛.
是啊是啊。最近的新题
回复 支持 反对

使用道具 举报

我的人缘0
天空无语 发表于 2015-8-13 07:41:46 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
google的onsite难度吗?电面不会就这么难吧
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2015-8-13 07:47:33 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
天空无语 发表于 2015-8-13 07:41
google的onsite难度吗?电面不会就这么难吧

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

使用道具 举报

我的人缘0
jiebour 发表于 2015-8-13 07:51:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主,你的问题到底是什么?保证机器人走出这个圆?还是走不出这个圆?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2015-8-13 07:57:39 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
jiebour 发表于 2015-8-13 07:51
楼主,你的问题到底是什么?保证机器人走出这个圆?还是走不出这个圆?

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

使用道具 举报

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

使用道具 举报

我的人缘0
danchou 发表于 2015-8-13 12:55:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
f1371342385 发表于 2015-8-13 12:31
我感觉这一题可以这么考虑,因为每次不是左转90度,就是右转90度,那么对于来说,如果回来的话,肯定会转90 ...

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

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

使用道具 举报

我的人缘0
z928czzc 发表于 2015-8-13 12:56:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
维持一个坐标记录最后离原点的位置。

如果回到原点,显然存在圆
. 1point 3acres 论坛
如果不回到原点,就根据第一步的方向和最后一步方向判定就是了。.本文原创自1point3acres论坛
如果一样就不存在圆,如果不一样就存在圆。. Waral 博客有更多文章,
. 牛人云集,一亩三分地
上面逻辑可能存在问题,但是大抵也就这样了。大不了四象限的四个方向枚举一下。
核心是不用care中间是怎么走的。. more info on 1point3acres
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2015-8-13 13:28:39 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
f1371342385 发表于 2015-8-13 12:31
我感觉这一题可以这么考虑,因为每次不是左转90度,就是右转90度,那么对于来说,如果回来的话,肯定会转90 ...

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

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2015-8-13 13:29:16 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
z928czzc 发表于 2015-8-13 12:56
维持一个坐标记录最后离原点的位置。

如果回到原点,显然存在圆
.1point3acres网
如果需要20分钟之内写出代码来,能不能行?自己能证明正确性吗
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| Linzertorte 发表于 2015-8-13 13:30:24 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
z928czzc 发表于 2015-8-13 12:56
维持一个坐标记录最后离原点的位置。.1point3acres网

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

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

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-6-23 18:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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