一亩三分地论坛

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

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

Google 最新Seattle电面

[复制链接] |试试Instant~ |关注本帖
sunjiawen2009 发表于 2016-4-22 03:53:43 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
上来聊了下debug中遇到的挑战和怎么解决的, 聊了10min。

第一题 atoi 只考虑正数,写了一些test case,没啥问题。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
第二题 没见过,有一个4-way stop的路口,4条lane, 给两个function getNextCar(), arriveCar(Car car, Lane lane),要求实现这两个方法。
就是生活中一个intersection有4个stop sign,然后看看哪条lane的车应该先走。理解完题只剩10min,写了一会儿发现好烦,最后没时间了,说了下思路,还有好多核心code没写。。
估计挂了。。。

评分

2

查看全部评分

Alice0701 发表于 2016-4-22 20:52:52 | 显示全部楼层
是因为楼主在职跳槽的原因吗 上来店面就这么难的感觉
回复 支持 反对

使用道具 举报

 楼主| sunjiawen2009 发表于 2016-4-23 00:45:22 | 显示全部楼层
Alice0701 发表于 2016-4-22 20:52
是因为楼主在职跳槽的原因吗 上来店面就这么难的感觉

我也想知道为什么。。。
回复 支持 反对

使用道具 举报

atlas1017 发表于 2016-4-23 01:42:17 | 显示全部楼层
楼主那个four way stop 的问题是只要考虑先到先走 还是也要考虑yield rule什么的 你说的复杂能具体说说吗 多谢!
回复 支持 反对

使用道具 举报

 楼主| sunjiawen2009 发表于 2016-4-23 01:45:18 | 显示全部楼层
atlas1017 发表于 2016-4-23 01:42
楼主那个four way stop 的问题是只要考虑先到先走 还是也要考虑yield rule什么的 你说的复杂能具体说说吗  ...

就这么想,如果4个lane都有车,那么不管哪个lane的哪辆车先来的,都要挨个走。就是说即使lane1的第二辆车比lane2的第一辆车来的早,也要先走lane2.
回复 支持 反对

使用道具 举报

menderr 发表于 2016-4-23 02:02:17 | 显示全部楼层
最后这个是oo design还是什么其他的问题?
回复 支持 反对

使用道具 举报

 楼主| sunjiawen2009 发表于 2016-4-23 02:06:40 | 显示全部楼层
menderr 发表于 2016-4-23 02:02
最后这个是oo design还是什么其他的问题?

算法加design吧,只剩15min出个这个也是醉了
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-4-23 02:11:18 | 显示全部楼层
sunjiawen2009 发表于 2016-4-23 01:45.1point3acres缃
就这么想,如果4个lane都有车,那么不管哪个lane的哪辆车先来的,都要挨个走。就是说即使lane1的第二辆车 ...

假设四个方向各只有一个道,如果所有车都是直行还好,就相当于round robin,东西向各走一辆,南北向再走一辆以此类推。

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴但是如果考虑到转向呢。。考虑上北下南,左西右东:
1. 如果南北向各有一辆车,其中两辆车都直行,或者其中一辆右转,是可以同时通过的。

2. 如果南北向,有一个车直行,另一个方向的车左转,就会出现冲突,左转的得让,但不能一直让:此时如果东西向也有车在等,(1)东西向车先到,让东西向车先走,再左转。(2)先让南北向左转的车,再放东西向。

是否需要考虑这些情况呢?
回复 支持 反对

使用道具 举报

 楼主| sunjiawen2009 发表于 2016-4-23 02:22:24 | 显示全部楼层
sheepmiemies 发表于 2016-4-23 02:11
假设四个方向各只有一个道,如果所有车都是直行还好,就相当于round robin,东西向各走一辆,南北向再走 ...

不需要考虑这些情况,就是直行,而且每次过一辆车,不考虑同向走两辆车。我已经在前面说了算法,写起来比较烦
回复 支持 反对

使用道具 举报

 楼主| sunjiawen2009 发表于 2016-4-23 02:27:01 | 显示全部楼层
sunjiawen2009 发表于 2016-4-23 02:22. Waral 鍗氬鏈夋洿澶氭枃绔,
不需要考虑这些情况,就是直行,而且每次过一辆车,不考虑同向走两辆车。我已经在前面说了算法,写起来比 ...

看来我在instant的回复都没有显示在这上面。。。
回复 支持 反对

使用道具 举报

atlas1017 发表于 2016-4-23 02:55:10 | 显示全部楼层
  1. public class fourWayStop {

  2.         private class Lane {
  3.                 public Queue<Car> queue;
  4.                 public Lane() {
  5.                         queue = new Queue<Car>();. from: 1point3acres.com/bbs
  6.                 }
  7.         }. 1point3acres.com/bbs

  8.         private Lane lane0;
  9.         private Lane lane1;
  10.         private Lane lane2;
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.         private Lane lane3;

  12.         private class Pair {
  13.                 public Lane lane;
  14.                 public Car car;
  15.         }

  16.         private Queue<Pair> ready;
  17. -google 1point3acres
  18.         public fourWayStop {. From 1point 3acres bbs
  19.                 lane0 = new Lane();
  20.                 lane1 = new Lane();
  21.                 lane2 = new Lane();
  22.                 lane3 = new Lane();

  23.                 ready = new Queue<car>();
  24.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  25.         public void arriveCar(Car oneCar, Lane oneLane) {
  26.                 if(oneLane.queue.isEmpty()) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  27.                         Pair onePair = new Pair();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.                         onePair.lane = oneLane;
  29.                         onePair.car = oneCar;

  30.                         ready.add(onePair);
  31.                 }. visit 1point3acres.com for more.
  32.                 oneLane.queue.add(oneCar);
  33.         }

  34.         public Car getNext() {-google 1point3acres
  35.                 if(ready.isEmpty())
  36.                         throw new NullPointerException();
  37.                 Pair onePair = ready.remove();
  38.                 Car oneCar = onePair.car;
  39.                 Lane oneLane = onePair.lane;

  40.                 oneLane.queue.remove();

  41.                 if(!oneLane.queue.isEmpty()) {
  42.                         Car firstCar = oneLane..queue.peek();
  43.                         . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  44.                         Pair firstPair = new Pair();
  45.                         firstPair.car = firstCar;
  46.                         firstPair.lane = oneLane;
  47.                         ready.add(firstPair);
  48.                 }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  49.                 return oneCar;
  50.         }
  51. }
复制代码


大概长这样? 欢迎指正!
. From 1point 3acres bbs
补充内容 (2016-4-23 02:57):.1point3acres缃
constructor 少写了个()  =。=

补充内容 (2016-4-23 02:57):
十五分钟真的写不出来啊= =
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-23 03:07:06 | 显示全部楼层
我怎么记得four way...对向可以同时走. more info on 1point3acres.com
这样的话就是个状态机啊.
回复 支持 反对

使用道具 举报

xdrealmadrid 发表于 2016-4-23 03:07:17 | 显示全部楼层
请问是FIFO的原则吗 如果是这样 直接弄个queue可行吗
回复 支持 反对

使用道具 举报

atlas1017 发表于 2016-4-23 03:12:07 | 显示全部楼层
ykwwind 发表于 2016-4-23 03:07
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴我怎么记得four way...对向可以同时走
这样的话就是个状态机啊.

这个算是follow up吧 所以对向可以走的意思是 看最先到stop sign的车的对面是不是刚好有车在等 如果有的话就可以沾光一起走?
回复 支持 反对

使用道具 举报

 楼主| sunjiawen2009 发表于 2016-4-23 04:12:36 | 显示全部楼层
atlas1017 发表于 2016-4-23 02:55.鏈枃鍘熷垱鑷1point3acres璁哄潧
大概长这样? 欢迎指正!.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-4-23 02:57):
. from: 1point3acres.com/bbs
你这么写应该是对的。我刚写完arriveCar就没时间了。。估计挂了。。
回复 支持 反对

使用道具 举报

atlas1017 发表于 2016-4-23 04:57:12 | 显示全部楼层
sunjiawen2009 发表于 2016-4-23 04:12.1point3acres缃
你这么写应该是对的。我刚写完arriveCar就没时间了。。估计挂了。。

.1point3acres缃时间确实紧张 我15分钟也写不完 anyway多谢分享祝好运!
回复 支持 反对

使用道具 举报

Effiel 发表于 2016-4-24 11:46:00 | 显示全部楼层
atlas1017 发表于 2016-4-23 02:55
大概长这样? 欢迎指正!
. from: 1point3acres.com/bbs
补充内容 (2016-4-23 02:57):
. 1point3acres.com/bbs
这个应该不全面,每个到应该有一个timestamp, 纪录排到第一个的时间(到达或排到), 然后比四个道的时间
回复 支持 反对

使用道具 举报

atlas1017 发表于 2016-4-24 12:42:41 | 显示全部楼层
Effiel 发表于 2016-4-24 11:46
这个应该不全面,每个到应该有一个timestamp, 纪录排到第一个的时间(到达或排到), 然后比四个道的时 ...

我的理解是 绝对的timestamp是不必要的 相对的timestamp就是放进ready queue的先后顺序 可否给个反例一定需要你那样的stamp?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 04:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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