一亩三分地论坛

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

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

Amazon电面,experienced职位

[复制链接] |试试Instant~ |关注本帖
liberwang 发表于 2015-4-8 23:51:54 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 本科 全职@Amazon - 网上海投 - 技术电面 |Fail在职跳槽

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

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

x
我4月6号电面Amazon。第一题是2Sum。第二题是
Q: Write a program that identifies the first occurring unique object in a stream of objects at any time.
Sample input stream: obj1 obj2 obj3 obj2 obj2 obj1 obj4 obj3 obj6
Result: obj4
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二题我最后几步做错了。
Amazon面试的电话有问题。电话一顿一顿的,经常一句话好几个单词miss掉,听不清对方说什么。对方只好把问题打字给我。搞得我高度紧张,怕对方认为我听不懂。

昨天网上状态变成Not Selected。今天收到拒信。

评分

2

查看全部评分

Arthur2012 发表于 2015-4-9 01:44:07 | 显示全部楼层
第二题是不是可以hashmap + doubly linked list. From 1point 3acres bbs
楼主一定可以找到更好的!
回复 支持 反对

使用道具 举报

头像被屏蔽
mstc123 发表于 2015-4-9 03:10:05 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

 楼主| liberwang 发表于 2015-4-9 03:19:56 | 显示全部楼层
Arthur2012 发表于 2015-4-9 01:44. visit 1point3acres.com for more.
第二题是不是可以hashmap + doubly linked list
楼主一定可以找到更好的!

谢谢支持。

面试之前我没见过第二题。. 1point3acres.com/bbs
之后,有人也告诉我要用hashmap+doubly linked list
我个人觉得用hashmap/hashtable 就足够了。不需要linkedlist.

先扫一遍传进来的Stream,记下<key, value>, key就是Obj的地址,value可以是个Obj,里面有index 和 counter。
如:

<obj1, [0,1]>
<obj2, [1,1]>. From 1point 3acres bbs
<obj3, [2,1]>
<obj2, [1,2]>
<obj2, [1,3]>
<obj1, [0,2]>
<obj4, [6,1]>
<obj3, [2,2]>
<obj6, [8,1]>

返回时,再扫一遍hashmap/hashtable, 找到counter为1,index值最小的那个。这是O(n).. 鍥磋鎴戜滑@1point 3 acres
我不知道为什么要用linkedlist. 维护linkedlist的代码挺麻烦的。

个人想法,请指正。 谢谢。
回复 支持 反对

使用道具 举报

 楼主| liberwang 发表于 2015-4-9 03:32:55 | 显示全部楼层
mstc123 发表于 2015-4-9 03:10
这不是LRU cache解法吗?能详细说说怎么应用到第二个题目吗?

您这么一说,我觉得和LRU真的很想。

我也前实现LRU就是用一个Index的变量,放在Memory Page里的。当evict的时候,总是把最小的Index值给踢出来。当时我们是用Avl Tree存储的Page。
回复 支持 反对

使用道具 举报

苏DsL 发表于 2015-4-9 03:54:27 | 显示全部楼层
liberwang 发表于 2015-4-9 03:19
谢谢支持。

面试之前我没见过第二题。

同意楼主,感觉lru那个解法,反而不是很适合这个题目
回复 支持 反对

使用道具 举报

苏DsL 发表于 2015-4-9 03:55:53 | 显示全部楼层
Arthur2012 发表于 2015-4-9 01:44-google 1point3acres
第二题是不是可以hashmap + doubly linked list
楼主一定可以找到更好的!

我想了一下,用hashmap+double linked list,似乎没有那么方便。。这个数据结构里面,链表和hashmap都应该存一个node的数据结构而不仅仅是obj把?
. visit 1point3acres.com for more.
不知道是不是想乱了,麻烦指正一下~
回复 支持 反对

使用道具 举报

 楼主| liberwang 发表于 2015-4-9 04:01:48 | 显示全部楼层
我当时没想到LRU,只是想用O(n)实现。如果出题者的意图是double linkedlist ,那我就知道我失败的原因了。
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-4-9 04:10:27 | 显示全部楼层
mstc123 发表于 2015-4-9 03:10
这不是LRU cache解法吗?能详细说说怎么应用到第二个题目吗?

我被吓到了,突然好多人问。。。。。
两个hashmap:
1. 一个<object, int> 存object出现的次数
2. 另一个<object, list<Node>::iterator> 存到目前为止只出现了一次的object在doubly linked list的位置,
一个doubly linked list: 存只出现了一次的object
这样,插入的话:
先看是不是第一次出现,如果是,就放到doubly linked list的末尾,并插入到两个hashmap中
如果不是,更新第一个hashmap,然后通过第二个hashmap把这个object从doubly linked list中除去(因为是双向链表,所以删除的操作平摊下来是O(1)). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
而每次find first occurring unique object in a stream of objects at any time,就可以直接取doubly linked list的第一个object。
所以,新来一个,和实时取结果的时间都是平摊的O(1)
回复 支持 反对

使用道具 举报

 楼主| liberwang 发表于 2015-4-9 04:10:32 | 显示全部楼层
苏DsL 发表于 2015-4-9 03:55
我想了一下,用hashmap+double linked list,似乎没有那么方便。。这个数据结构里面,链表和hashmap都应 ...

hashmap的Value应该存的是LinkedList的指针。当找到Key的时候,如果Value不是Null,就把那个Node删掉,Value制成Null,如果是Null的话,说明已经重复过了,就跳过。应该是这样吧。
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-4-9 04:11:42 | 显示全部楼层
liberwang 发表于 2015-4-9 03:19
谢谢支持。

面试之前我没见过第二题。
.1point3acres缃
我被吓到了,突然好多人问。。。。。
两个hashmap:
1. 一个<object, int> 存object出现的次数
2. 另一个<object, list<Node>::iterator> 存到目前为止只出现了一次的object在doubly linked list的位置,
一个doubly linked list: 存只出现了一次的object
这样,插入的话:
先看是不是第一次出现,如果是,就放到doubly linked list的末尾,并插入到两个hashmap中
如果不是,更新第一个hashmap,然后通过第二个hashmap把这个object从doubly linked list中除去(因为是双向链表,所以删除的操作平摊下来是O(1))-google 1point3acres
而每次find first occurring unique object in a stream of objects at any time,就可以直接取doubly linked list的第一个object。
所以,新来一个,和实时取结果的时间都是平摊的O(1)
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-4-9 04:11:57 | 显示全部楼层
苏DsL 发表于 2015-4-9 03:55
我想了一下,用hashmap+double linked list,似乎没有那么方便。。这个数据结构里面,链表和hashmap都应 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我被吓到了,突然好多人问。。。。。
两个hashmap:
1. 一个<object, int> 存object出现的次数
2. 另一个<object, list<Node>::iterator> 存到目前为止只出现了一次的object在doubly linked list的位置,. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
一个doubly linked list: 存只出现了一次的object
这样,插入的话:. 鍥磋鎴戜滑@1point 3 acres
先看是不是第一次出现,如果是,就放到doubly linked list的末尾,并插入到两个hashmap中
如果不是,更新第一个hashmap,然后通过第二个hashmap把这个object从doubly linked list中除去(因为是双向链表,所以删除的操作平摊下来是O(1))
而每次find first occurring unique object in a stream of objects at any time,就可以直接取doubly linked list的第一个object。
所以,新来一个,和实时取结果的时间都是平摊的O(1)
回复 支持 反对

使用道具 举报

 楼主| liberwang 发表于 2015-4-9 04:15:18 | 显示全部楼层
Arthur2012 发表于 2015-4-9 04:10. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我被吓到了,突然好多人问。。。。。
两个hashmap:
1. 一个 存object出现的次数

一个Hashmap就够了吧?

<obj address, linked list node address>

如果linked list node address 有的话,就直接删,置成Null,如果没有的话,就跳过。.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-4-9 04:33:55 | 显示全部楼层
liberwang 发表于 2015-4-9 04:15
一个Hashmap就够了吧?

恩恩,对!!!!!!! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢谢楼主!!!!!!!
回复 支持 反对

使用道具 举报

 楼主| liberwang 发表于 2015-4-9 04:50:17 | 显示全部楼层
谢谢大家的讨论。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
================================
set a head pointer of double linked list
set a tail pointer of double linked list
set a hashmap/hashtable
. Waral 鍗氬鏈夋洿澶氭枃绔,
for i: 0 to lenght of input stream list -1
     if find object[i] as key in hashtable
        if value is not null
            delete linked list node by value
            set value to null
     else
        create a new linked list node
        put object[i] address into node's attribute
        put new node into tail
        put <object[j], node's address> into hashtable


return object[x] address from head of double linked list
回复 支持 反对

使用道具 举报

xieqilu1989 发表于 2015-4-9 07:03:56 | 显示全部楼层
liberwang 发表于 2015-4-9 04:50
谢谢大家的讨论。
================================
set a head pointer of double linked list
-google 1point3acres
楼主,我觉得这个题目既然说了是stream而且要在任何时候找到第一个出现的unique的object, 那么接受的输入应该是每次接受一个object, 然后任何时候call返回函数的时候都能得到结果。就是stream是一个一个存进来的,不是一下存一个list.
回复 支持 反对

使用道具 举报

 楼主| liberwang 发表于 2015-4-9 07:42:46 | 显示全部楼层
我面试也是这样想的,但面试官说为了简单,就定义一个数组传进来。他并不在意输入输出形式,在意你的算法。
面试的问清楚输入输出定义就可以了,这并不是重点。
回复 支持 反对

使用道具 举报

xieqilu1989 发表于 2015-4-9 10:57:59 | 显示全部楼层
liberwang 发表于 2015-4-9 07:42
我面试也是这样想的,但面试官说为了简单,就定义一个数组传进来。他并不在意输入输出形式,在意你的算法。 ...

说的对!确实要问清楚,一个数组传进来其实也是一样的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 00:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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