一亩三分地论坛

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

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

Zenefits 实习电面 二面面经

[复制链接] |试试Instant~ |关注本帖
laonawuli 发表于 2015-3-31 14:03:30 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Zenefits - Other - 技术电面 |Other其他

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

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

x
    // 给一个n * n的二维数组,例如:
    // [[0, 1, 0]].鐣欏璁哄潧-涓浜-涓夊垎鍦
    // [[0, 2, 0]]. 鍥磋鎴戜滑@1point 3 acres
    // [[0, 1, 0]]. 1point3acres.com/bbs

    // 2是一面墙,表示此路不通。
    // 0表示小孩儿。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    // 1表示警察叔叔。
    // 求小孩儿到离他最近的那个警察叔叔的距离。
    // 如果最终小孩儿碰不到警察叔叔,则距离为-1。
    // 注:墙到警察叔叔的距离无论如何都是-1,警察叔叔到自己的距离是0。

    // Running case 1:
    // [[0, 1, 0]]
    // [[0, 2, 0]]. 1point 3acres 璁哄潧
    // [[0, 1, 0]]
    // Result:
    // [[1, 0, 1]]
    // [[2, -1, 2]]
    // [[1, 0, 1]]

    // Running case 2:
    // [[0, 2, 0]]
    // [[0, 2, 0]]
    // [[0, 2, 1]]
    // Result:
    // [[-1, -1, 2]]
    // [[-1, -1, 1]]
    // [[-1, -1, 0]]

    // Running case 3:
    // [[1, 0, 0]]
    // [[0, 0, 0]]
    // [[0, 0, 1]]
    // Result:
    // [[0, 1, 2]]
    // [[1, 2, 1]]
    // [[2, 1, 0]]

就考了一题。我的解法是对每一个警察叔叔做BFS,然后更新周围的点到警察叔叔的距离。



补充内容 (2015-4-2 11:21):
2015年04月01日20:20:09
.鏈枃鍘熷垱鑷1point3acres璁哄潧收到HR邮件,说是过几天给我打电话聊聊激动人心的事情。估计是Offer了...不然拒信也能令人激动人心的话,也太狗血了...

评分

7

查看全部评分

gbbbb 发表于 2015-4-2 18:14:05 | 显示全部楼层
newtt 发表于 2015-4-2 16:24
楼主想问 如果警察都一起先入列,那后来在遍历的时候,他们的同一个邻居可能多次入列,这个冲突是怎么处 ...

只有第一次的时候入列,后面都不会更优了。
回复 支持 1 反对 0

使用道具 举报

wnyforever 发表于 2015-4-1 23:07:50 | 显示全部楼层
gbbbb 发表于 2015-4-1 13:51
不可解,或者说那不叫DP

是可以的。从左上到右下,然后再从右下到左上。
这道题在其中一个面试中遇到过。面试官要求让用dp去解。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

yuxrose 发表于 2015-3-31 14:10:04 | 显示全部楼层
这题题目叫啥啊lz,在hackerrank上能找到吗?
回复 支持 反对

使用道具 举报

gbbbb 发表于 2015-4-1 00:19:13 | 显示全部楼层
所有警察都一起扔到队列里做一遍BFS就可以了,复杂度N^2
回复 支持 反对

使用道具 举报

 楼主| laonawuli 发表于 2015-4-1 00:54:40 | 显示全部楼层
gbbbb 发表于 2015-4-1 00:19
所有警察都一起扔到队列里做一遍BFS就可以了,复杂度N^2

我最后就是这么搞的
回复 支持 反对

使用道具 举报

 楼主| laonawuli 发表于 2015-4-1 01:03:07 | 显示全部楼层
gbbbb 发表于 2015-4-1 00:19
所有警察都一起扔到队列里做一遍BFS就可以了,复杂度N^2
. From 1point 3acres bbs
当时想法都跟面试官说完了,但是最后没敲完,最后让我发email给他。
回复 支持 反对

使用道具 举报

wnyforever 发表于 2015-4-1 05:54:38 | 显示全部楼层
这题用dp可解
回复 支持 反对

使用道具 举报

gbbbb 发表于 2015-4-1 13:51:11 | 显示全部楼层

不可解,或者说那不叫DP
回复 支持 反对

使用道具 举报

sijiyuren 发表于 2015-4-2 05:24:13 | 显示全部楼层
楼主请问面试时间是多久啊?
回复 支持 反对

使用道具 举报

 楼主| laonawuli 发表于 2015-4-2 11:19:54 | 显示全部楼层
sijiyuren 发表于 2015-4-2 05:24
楼主请问面试时间是多久啊?
. more info on 1point3acres.com
1个小时。
回复 支持 反对

使用道具 举报

newtt 发表于 2015-4-2 16:22:38 | 显示全部楼层
gbbbb 发表于 2015-4-1 00:19
所有警察都一起扔到队列里做一遍BFS就可以了,复杂度N^2
. 1point 3acres 璁哄潧
有个问题啊,如果一起全放到队列的话,那么在遍历的时候,同一个节点可能会多次作为入列这个怎么处理呢?
回复 支持 反对

使用道具 举报

newtt 发表于 2015-4-2 16:24:18 | 显示全部楼层
laonawuli 发表于 2015-4-1 00:54
我最后就是这么搞的
.1point3acres缃
楼主想问 如果警察都一起先入列,那后来在遍历的时候,他们的同一个邻居可能多次入列,这个冲突是怎么处理的?
回复 支持 反对

使用道具 举报

gbbbb 发表于 2015-4-2 18:20:33 | 显示全部楼层
wnyforever 发表于 2015-4-1 23:07
是可以的。从左上到右下,然后再从右下到左上。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这道题在其中一个面试中遇到过。面试官要求让用dp去解。


                               
登录/注册后可看大图

如图所示的情况怎么解决?图有点意识流,只有中间是1,黑色路径上的都是0,其它都是墙。

回复 支持 反对

使用道具 举报

 楼主| laonawuli 发表于 2015-4-2 23:19:34 | 显示全部楼层
newtt 发表于 2015-4-2 16:24
楼主想问 如果警察都一起先入列,那后来在遍历的时候,他们的同一个邻居可能多次入列,这个冲突是怎么处 ...

先写一个N^2的循环套循环,在最里面的循环里检查是不是警察,如果是警察,就把警察当作BFS的起点,警察四周的点就是临近的点(相当于四叉树)。然后碰到小孩儿,就更新小孩的距离(用Math.min更新小的那个值)。
代码:http://collabedit.com/dytjf
回复 支持 反对

使用道具 举报

 楼主| laonawuli 发表于 2015-4-4 00:28:40 | 显示全部楼层
gbbbb 发表于 2015-4-2 18:20
如图所示的情况怎么解决?图有点意识流,只有中间是1,黑色路径上的都是0,其它都是墙。

BFS搞定啊。看我上一个回复的代码。
回复 支持 反对

使用道具 举报

gbbbb 发表于 2015-4-4 03:16:34 | 显示全部楼层
laonawuli 发表于 2015-4-4 00:28
BFS搞定啊。看我上一个回复的代码。

我在问你DP怎么做?你不是说DP可解么
回复 支持 反对

使用道具 举报

 楼主| laonawuli 发表于 2015-4-4 03:45:31 | 显示全部楼层
gbbbb 发表于 2015-4-4 03:16. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我在问你DP怎么做?你不是说DP可解么

我是楼主,我没说DP可解。你看错人了。
回复 支持 反对

使用道具 举报

liujunlovecs 发表于 2015-4-6 13:31:19 | 显示全部楼层
我现在是15FALL的CE@UCSC,加州就申了这一个,现在比较倾向于这个学校。但是不知道CE转CS是否方便。或者能不能选很多CS的课程。
官网上面有一句“at least half of the credits from the graduate-level courses must be computer engineering graduate courses. ”这句话的意思是不是说必须有一半的课要选择CE专业下开设的?. from: 1point3acres.com/bbs
如果楼主有意愿的话,能不能加个好友方便交流?
回复 支持 反对

使用道具 举报

 楼主| laonawuli 发表于 2015-4-6 13:33:39 来自手机 | 显示全部楼层
liujunlovecs 发表于 2015-4-5 21:31
我现在是15FALL的CE@UCSC,加州就申了这一个,现在比较倾向于这个学校。但是不知道CE转CS是否方便。或者能 ...
. 1point 3acres 璁哄潧
微信就是我论坛帐号
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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