一亩三分地论坛

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

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

uber intern

[复制链接] |试试Instant~ |关注本帖
jobfinding 发表于 2016-4-5 08:45:46 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 实习@Uber - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
最近刚面完uber,面经回报地里。3月初才拿到面试机会(本来以为没有职位了)共三轮,具体面经如下,:

1. 第一轮电面:implement a hash map, key和value都是<int, int>

2. 第二轮是一维dp问题:在[0,M]的线段上,给定不同的点(x1, x2, ..., xn)以及对应的utility (r1, r2, ..., rn),需要选出subset of positions 来maximize sum of utility,同时满足下列条件:. From 1point 3acres bbs
(1) 不能选太靠近起点和终点的位置: 选择的点不能在 [0,s]以及[M-s, M]内。
(2) 任何两个位置之间距离不能小于d

3. 第三轮是manager面,问了两道leetcode原题,分别是permutation和wordbreak。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

多谢大家。

评分

3

查看全部评分

wtcupup 发表于 2016-4-5 09:13:42 | 显示全部楼层
第二题如果要return subsets里的每个点的话岂不是不能DP?
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-4-5 09:26:17 | 显示全部楼层
lz怎么拿面试的啊,现在uber还有坑吗,谢谢!
回复 支持 反对

使用道具 举报

 楼主| jobfinding 发表于 2016-4-5 10:08:25 | 显示全部楼层
wtcupup 发表于 2016-4-5 09:13
第二题如果要return subsets里的每个点的话岂不是不能DP?

有可能的,题目只需要返回optimal utility,不需要return subsets
回复 支持 反对

使用道具 举报

 楼主| jobfinding 发表于 2016-4-5 10:10:15 | 显示全部楼层
gjxwin 发表于 2016-4-5 09:26
lz怎么拿面试的啊,现在uber还有坑吗,谢谢!

是找朋友内推的,等了很长时间才拿到面试,估计是临时多了一个位置。。。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-4-5 10:33:08 | 显示全部楼层
jobfinding 发表于 2016-4-5 10:08
有可能的,题目只需要返回optimal utility,不需要return subsets

我懂了,其实这道题是leetcode house robber I的变形
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-4-5 11:18:16 | 显示全部楼层
这个点还能拿到面试太牛了
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-4-5 11:50:07 | 显示全部楼层
johnjavabean 发表于 2016-4-5 11:18. visit 1point3acres.com for more.
这个点还能拿到面试太牛了

层主找到实习了吗。。。
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-4-6 13:22:30 | 显示全部楼层
gjxwin 发表于 2016-4-5 11:50
层主找到实习了吗。。。

拿到了...图森科技...
回复 支持 反对

使用道具 举报

无可奈何花落去 发表于 2016-4-7 00:29:49 | 显示全部楼层
第二题能理解成maximum subarray只是找的起点和终点要e-s>d 并且e和s都在[S:M-S]中嘛。。求具体点的思路!
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-7 01:03:24 | 显示全部楼层
问下楼主第二题是只要返回最大和是吧?
回复 支持 反对

使用道具 举报

menderr 发表于 2016-4-7 01:14:18 | 显示全部楼层
第二题能再解释一下吗?楼主拿到offer了吗?
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-4-7 01:45:06 | 显示全部楼层
第一题楼主怎么设计hash函数的....直接定义一个长度然后取模?然后collision用链表存?
回复 支持 反对

使用道具 举报

 楼主| jobfinding 发表于 2016-4-7 13:35:37 | 显示全部楼层
johnjavabean 发表于 2016-4-7 01:45
第一题楼主怎么设计hash函数的....直接定义一个长度然后取模?然后collision用链表存?

是的,我当时就是这么写的。
回复 支持 反对

使用道具 举报

 楼主| jobfinding 发表于 2016-4-7 13:36:15 | 显示全部楼层
jy_121 发表于 2016-4-7 01:03
问下楼主第二题是只要返回最大和是吧?

对的 返回最大和就好。
回复 支持 反对

使用道具 举报

 楼主| jobfinding 发表于 2016-4-7 13:47:55 | 显示全部楼层
无可奈何花落去 发表于 2016-4-7 00:29
第二题能理解成maximum subarray只是找的起点和终点要e-s>d 并且e和s都在[S:M-S]中嘛。。求具体点的思路!

对的,就是找在[s:M-s]之间的subarry,使得utility最大,同时满足任意两点间的距离要大于d
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-7 14:35:07 | 显示全部楼层
jobfinding 发表于 2016-4-7 13:36
对的 返回最大和就好。

谢谢
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-4-7 15:03:21 | 显示全部楼层
jobfinding 发表于 2016-4-7 13:47. more info on 1point3acres.com
对的,就是找在[s:M-s]之间的subarry,使得utility最大,同时满足任意两点间的距离要大于d

这个时间复杂度应该是n*d的吧...
回复 支持 反对

使用道具 举报

unclemoe 发表于 2016-4-17 23:31:23 | 显示全部楼层
请问楼主收到最终结果了吗?或者有通知你需要等多久吗?
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-11 14:49:09 | 显示全部楼层
2. sort之后可以dp, 没想到不sort能dp的方法,也就是o(n)好像解决不了?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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