一亩三分地论坛

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

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

2.23刚出炉的面经

[复制链接] |试试Instant~ |关注本帖
antonioxzxy 发表于 2016-2-24 12:04:35 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Amazon - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
1点的面试,1.06才打过来,我都准备发邮件问了。。面试官应该是美国人,标准的美语。. From 1point 3acres bbs
上来说咱们先聊聊数据结构,然后再coding
问了 什么是BST树,HashTable 和 LinkedList的区别
然后就是coding,coding是考的杨辉三角.1point3acres缃
      1
    1  1
  1  2  1
1  3  3  1
...

说给你一个坐标(row, col)让你得到坐标对应点的值
比如(0,0)指的是第0行的1,(3,2)指的是第3行第二个3
然后说我们开始吧. more info on 1point3acres.com


楼主之前没做过这题,只能当场想,coding出来一个O(row^2)的方法,就是用List<ArrayList>存每一行. Waral 鍗氬鏈夋洿澶氭枃绔,
的数再通过上一行得到下一行。然后说跑个test case 吧,跑了发现不对,又改了5分钟,然后对了,此时已经过去了25分钟左右,
然后面试官就一直问我能不能优化。楼主本来用的空间复杂度也是O(row^2),所以我说空间复杂度还是可以优化成O(row),因为每一行只需要上一行的信息
然而面试官就是不放过我,问我怎么优化时间,真心蒙了,当场实在想不出来,考官就给了我提示(提示现在已经忘记了。。),然后也依然无用,他最后就
说就这样吧,此时已经是1.36分,他说再问个题也没时间了,就问我有没有要问的,楼主就知道要跪了,问了下亚马逊实习都做点什么。。就挂了结束1.41


已经不指望offer了,希望拒信要来的话早点来,别让楼主还心存幻想. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-3-8 06:48):
已拒

评分

1

查看全部评分

spwahaha 发表于 2016-2-24 12:30:48 | 显示全部楼层
优化时间空间应该是每一行都只计算前col 的树就行行了吧,因为要得到(row, col), 只需要每行前col个元素就可以,
回复 支持 反对

使用道具 举报

 楼主| antonioxzxy 发表于 2016-2-24 12:33:12 | 显示全部楼层
spwahaha 发表于 2016-2-24 12:30
优化时间空间应该是每一行都只计算前col 的树就行行了吧,因为要得到(row, col), 只需要每行前col个元素 ...

你要是每行运行到row列,光这行就已经是O(n)复杂度了
回复 支持 反对

使用道具 举报

weihu816 发表于 2016-2-24 13:18:03 | 显示全部楼层
1 + j * (i – j) ???
回复 支持 反对

使用道具 举报

weihu816 发表于 2016-2-24 13:20:58 | 显示全部楼层
weihu816 发表于 2016-2-24 13:18.1point3acres缃
1 + j * (i – j) ???

错了。。
回复 支持 反对

使用道具 举报

Yogurt_Gakki 发表于 2016-2-24 13:42:37 | 显示全部楼层
这个应该是直接算排列组合就行吧,Cij
回复 支持 反对

使用道具 举报

 楼主| antonioxzxy 发表于 2016-2-24 14:00:41 | 显示全部楼层
Yogurt_Gakki 发表于 2016-2-24 13:42
这个应该是直接算排列组合就行吧,Cij

楼主当时没想到可以这样
回复 支持 反对

使用道具 举报

yyboyz 发表于 2016-2-24 14:07:52 | 显示全部楼层
我觉得他想要应该是一个DFS
. more info on 1point3acres.com
假如给你(3,2)
你应该从(3,2) 推出两个parents应该是(2,1)和(2,2). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
继续回溯,直到边界条件: 如果碰到某行两边 则返回1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

这样时间复杂度等于 O(h) h是三角高度. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

头像被屏蔽
wangjm15 发表于 2016-2-25 04:55:23 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 05:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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