一亩三分地论坛

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

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

Amazon面经 要跪的节奏

[复制链接] |试试Instant~ |关注本帖
玛奇朵肉丝 发表于 2015-3-20 06:05:03 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 实习@Amazon - 网上海投 - 技术电面 |Other

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

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

x
刚面完,面试官是Adrian。一上来很奇怪先让我问问题,然后chalengest part of project,说了有二十分钟。。说完之后就做题。
题目名字我忘记了,是一个game,给一个二维数组,找到里面所有的单词。例子如下:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

c a t a
d u b k
e x b l
t o a b

单词有 cat, but, to 等等等等。只要是相邻的就行。
一开始理解错意思了,以为单纯的顺着一个方向找就行了,写了一半面试官说我理解错意思了,路径不一定是一条直线。
楼主终于反应过来要用dfs,但是前面耽误时间太多,没时间写代码了,就只是说了下思路  肯定必挂无疑。。
第一次面写代码的面试,太紧张了,好好准备下一场面试吧。
move on.. 1point 3acres 璁哄潧
shawlin 发表于 2015-3-20 06:34:01 | 显示全部楼层
感觉想leetcode word search
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-3-20 09:35:54 | 显示全部楼层
how to know it's a word? Is there a dictionary?
回复 支持 反对

使用道具 举报

 楼主| 玛奇朵肉丝 发表于 2015-3-20 09:50:32 | 显示全部楼层
seabiscuit119 发表于 2015-3-20 09:35
how to know it's a word? Is there a dictionary?

是的~~~有思路吗
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-3-20 09:54:00 | 显示全部楼层

like this? https://leetcode.com/problems/word-search/     change the 4-flood-fill to 8-flood-fill?
回复 支持 反对

使用道具 举报

liuzonyuan 发表于 2015-3-20 10:32:18 | 显示全部楼层
I think it's similar to the word search problem. Maintan a string and for each recursion, find out if the dictionary contains that string. If so, add the string to the result. Then if i, j meets the boundary then return.
回复 支持 反对

使用道具 举报

carter13466 发表于 2015-3-20 10:57:58 | 显示全部楼层
我和lz的题差不多,在面试官提示下才最终写出来
. From 1point 3acres bbs
补充内容 (2015-3-20 10:58):
估计也是要跪的节奏
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-3-21 23:06:43 | 显示全部楼层
seabiscuit119 发表于 2015-3-20 09:54
like this? https://leetcode.com/problems/word-search/     change the 4-flood-fill to 8-flood-fill?
. 1point 3acres 璁哄潧
感觉用 dfs 不能求出最优解,word search 问题是只需要横着和竖着就可以判断是否存在字典中的单词。这个题中给的矩阵,but 这个单词是需要斜着走(diagonally)才能得到的结果,也就是八个方向都可以走,这个有点像 android 开锁的那个问题,最好是用一个 trie 来存储所有单词。

我没去过 A 家 onsite,但是感觉他家总会考一个 trie 的问题(不知道是不是用来刷人的)
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-3-22 00:45:59 | 显示全部楼层
干.什么 发表于 2015-3-21 23:06
感觉用 dfs 不能求出最优解,word search 问题是只需要横着和竖着就可以判断是否存在字典中的单词。这个 ...

Maybe the trie implementation is a little hard for intern position..
回复 支持 反对

使用道具 举报

Luciferre 发表于 2015-3-22 03:32:58 | 显示全部楼层
干.什么 发表于 2015-3-21 23:06
感觉用 dfs 不能求出最优解,word search 问题是只需要横着和竖着就可以判断是否存在字典中的单词。这个 ...

word search基础上加上四个角不行么
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-3-22 04:07:28 | 显示全部楼层
seabiscuit119 发表于 2015-3-22 00:45
Maybe the trie implementation is a little hard for intern position..
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
是,只是看到过类似的面经里面提到过最好用 trie 来实现,但是也不知道是不是真的有人在面试的过程中被要求在白板上写个 trie,我自己数了一下,word search II,非空非注视差不多要40行,感觉面试的时候不太现实能完整写对了,所以觉得如果提出用 backtracking 考官不满意,是不是之前没发挥好?
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-3-22 04:50:44 | 显示全部楼层
Luciferre 发表于 2015-3-22 03:32
word search基础上加上四个角不行么

LZ 没有说清楚,我感觉题目是要求返回所有单词,而不是返回 true / false ,应该给一个dictionary,更像 word search II
回复 支持 反对

使用道具 举报

Luciferre 发表于 2015-3-22 07:28:00 | 显示全部楼层
干.什么 发表于 2015-3-22 04:50
LZ 没有说清楚,我感觉题目是要求返回所有单词,而不是返回 true / false ,应该给一个dictionary,更像  ...

嗯,不过那也可以是dfs然后判断是否在字典里出现过,收集结果就行了
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-3-22 09:54:10 | 显示全部楼层
Luciferre 发表于 2015-3-22 07:28
嗯,不过那也可以是dfs然后判断是否在字典里出现过,收集结果就行了

有一个问题,就是如果输入参数有一个字典,比如
  1. public List<String> search(char[][] boardList<String> dict)
复制代码
那么按照 DFS 的方法,至少要有三重循环:
  1. for (Sting word : list) {
  2.     for (int i = 0; i < board.length; i++) {
  3.         for (int j = 0; j < board[0].length; j++) {
  4.         dfs(...);
  5.         }
  6.     }
  7. }
复制代码
这个时间复杂度是多少?
回复 支持 反对

使用道具 举报

Luciferre 发表于 2015-3-22 10:51:41 | 显示全部楼层
干.什么 发表于 2015-3-22 09:54. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
有一个问题,就是如果输入参数有一个字典,比如那么按照 DFS 的方法,至少要有三重循环:这个时间复杂度是 ...

k*m^2*n^2 ? k是字典长度,m,n是board的长宽。。。我看过的其他面经是Dictionary会给一个是否在dictionary里的一个函数,直接调用就行
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 19:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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