一亩三分地论坛

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

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

Uber 电面(求大米)

[复制链接] |试试Instant~ |关注本帖
he2004365 发表于 2015-6-17 10:11:43 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Uber - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
   上上周突然收到Uber的电面通知,之前招人内推的终于有结果了。但是上地理看了下面经,心如死灰啊。即使电面过了,onsite铁定过不了, 什么设计excel这种东西,听都没听说过。 然后看了看电面的面经,感觉也不简单(主要还是自己太渣),本人东部公立学校小硕一枚,去年开始才接触程序这个玩意。到今年leetcode刷了一遍多点,感觉自己好渣。然后果不其然,这次电面就被虐了。进入正题:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   电面的是个国人大叔,第一次约到周四,结果被放鸽子,重新安排到周二,接到电话先让介绍下自己,巴拉巴拉说了一下,他就说:恩,好, 然后开始慢慢问些technique的问题,问了问什么是array啊, 和arraylist的区别啊, 心想国人大叔就是好,这是要放水的节奏啊,心中窃喜。然后楼主犯二逼的事情就来了,当问到tree和graph的区别,楼主很二的说了句:traverse data的时候performance不一样(太尼玛想抽自己了,明明是在问概念)。然后国人大叔估计很无奈的说:这个不是最主要的,还有没有? 脑子突然短路,说了句:tree有root,graph没有。面试官:恩,还有么?就想不起来了,啊啊啊啊啊啊啊~
  国人大叔,没问project, 没问简历,就是聊天,最后最了一道题。估计最后挂在这道题上了。 题目: 一个二维数组,m * n, 给一个起点,给一个终点,让把从起点到终点的元素加起来,返回加合(心中窃喜,太简单了)。就说用for循环就行,讲了下最naive的方法,两层循环。 写完,问有没有优化,心中有窃喜,把sprial matrix的方法讲了下,以为通过了,谁知面试官说了句:恩,这个不是我想要的,而且感觉复杂度没变。啊啊啊啊啊,难道是我刷题刷错了,这可是我刷得不多的几道题之一啊。这时时间快到了,让我问问题,我就问了优化到底怎么优化,面试官说了什么从四个角那开始,要先pre-process啊,巴拉巴拉, 不懂啥意思(还是自己太渣)。就挂了。不出意外,两天后收到邮件说挂了。哎,感觉国人大叔还是挺好的,没咋为难我,还是自己基础和题刷得不够。继续刷题吧。. Waral 鍗氬鏈夋洿澶氭枃绔,

PS: 求人品,求大米。全程拿英文对话,中国人和中国人用英文,你们懂的,沟通也不是很顺畅。所以,挂的毫无悬念。

评分

3

查看全部评分

sqzqkd 发表于 2015-8-5 01:48:06 | 显示全部楼层
这是个dp题啊,好多公司都问到了。patpat楼主,我看地里面经的时候也觉得基本要放弃这家的面试了。system design的题都好难。。。哎
回复 支持 1 反对 0

使用道具 举报

chwcrazy 发表于 2015-7-21 07:56:17 | 显示全部楼层
可是预处理的复杂度也一样啊, 预处理后的优点就是,剩下的所有解(eg. A-D, M-N, X-Y etc.)都是O(1)了

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

houqingniao 发表于 2015-6-17 12:39:36 | 显示全部楼层
这个题应该好多公司都出过的。。。需要预处理一下

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

adiggo 发表于 2015-6-17 13:37:46 | 显示全部楼层
houqingniao 发表于 2015-6-17 12:39
这个题应该好多公司都出过的。。。需要预处理一下
.鏈枃鍘熷垱鑷1point3acres璁哄潧
能具体讲讲么。 没太懂
回复 支持 反对

使用道具 举报

xiaoxi99cs 发表于 2015-6-17 15:19:52 | 显示全部楼层
楼主能不能说清楚点啊, 加和 啥意思啊   . 1point 3acres 璁哄潧
-google 1point3acres
1 2 3
4 5 6 . From 1point 3acres bbs
7 8 9
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
他想要什么啊, 是每个数字和之前所有数字的和 的和么?   比方说求从第一个到最后一个的和,
1   3   6 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
10 15 21
28  36 47   是这个数组再求和?

回复 支持 反对

使用道具 举报

billyli8866 发表于 2015-6-17 15:32:47 | 显示全部楼层
求问楼主怎么加和呀?和sprial matrix有什么关系?
回复 支持 反对

使用道具 举报

KOoshebe 发表于 2015-6-17 16:47:01 | 显示全部楼层
pat~pat~楼主
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-6-17 23:43:19 | 显示全部楼层
xiaoxi99cs 发表于 2015-6-17 15:19. more info on 1point3acres.com
楼主能不能说清楚点啊, 加和 啥意思啊   

1 2 3

不是,就是从起点是1,终点是9,那就从返回从1加到9的和。
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-6-17 23:43:57 | 显示全部楼层
houqingniao 发表于 2015-6-17 12:39
这个题应该好多公司都出过的。。。需要预处理一下

大神,怎么预处理?
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-6-17 23:45:39 | 显示全部楼层
billyli8866 发表于 2015-6-17 15:32.1point3acres缃
求问楼主怎么加和呀?和sprial matrix有什么关系?

我当时想的就是按照sprial matrix的scan的方式,来做。从左上到右上,再从右上到右下那样,但是好像想错了,复杂度好像没有优化。
回复 支持 反对

使用道具 举报

billyli8866 发表于 2015-6-18 04:48:02 | 显示全部楼层
houqingniao 发表于 2015-6-17 12:39
这个题应该好多公司都出过的。。。需要预处理一下
. 1point3acres.com/bbs
怎么预处理呀?
回复 支持 反对

使用道具 举报

adiggo 发表于 2015-6-18 07:35:00 | 显示全部楼层
回复 支持 反对

使用道具 举报

adiggo 发表于 2015-6-18 07:35:07 | 显示全部楼层
he2004365 发表于 2015-6-17 23:45
我当时想的就是按照sprial matrix的scan的方式,来做。从左上到右上,再从右上到右下那样,但是好像想错 ...
. 1point3acres.com/bbs
http://www.ardendertat.com/2011/ ... -matrix-region-sum/
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-6-19 14:03:41 | 显示全部楼层
就是把所有的以左上角和右下角为顶点的矩形的和先求出来
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-22 09:14:45 | 显示全部楼层
he2004365 发表于 2015-6-17 23:43
不是,就是从起点是1,终点是9,那就从返回从1加到9的和。

什么? 1到9的和?
1+2+3+4+。。。。+9?
逗我呢?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-22 09:18:57 | 显示全部楼层
大哥!
楼主你这描述坑爹啊!. 1point3acres.com/bbs
人家意思是先预处理,然后给你任意一个左上角和右下角,你能很快给人返回这个矩形内元素的sum!
回复 支持 反对

使用道具 举报

rogerdai 发表于 2015-7-22 10:10:50 | 显示全部楼层
jiebour 发表于 2015-7-22 09:18
大哥!. 1point3acres.com/bbs
楼主你这描述坑爹啊!
人家意思是先预处理,然后给你任意一个左上角和右下角,你能很快给人返回这 ...

原来是这个意思,那就是sub matrix的sum,的确要预处理一下
回复 支持 反对

使用道具 举报

 楼主| he2004365 发表于 2015-7-22 11:04:57 | 显示全部楼层
jiebour 发表于 2015-7-22 09:14
什么? 1到9的和?
1+2+3+4+。。。。+9?. 1point3acres.com/bbs
逗我呢?

我知道啊,楼上那个哥们给我的例子,让我解释下。我就随便说了一个起点一个终点啊。当然不是楼上说的就一个3 * 3的矩阵。肯定是随便一个大小的矩阵,才需要预处理。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-22 12:36:06 | 显示全部楼层
楼主不该说spiral matrix的。spiral matrix只是加和的顺序变得fancy了一点,实质上和你说的naive二重循环没有区别。面试官听到你把spiral matrix称作优化的话,可能会认为你在时间复杂度分析这件事上概念不是太清楚。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 17:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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