San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2908|回复: 17
收起左侧

Amazon电面,experienced职位

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

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

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

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

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

第二题我最后几步做错了。
Amazon面试的电话有问题。电话一顿一顿的,经常一句话好几个单词miss掉,听不清对方说什么。对方只好把问题打字给我。搞得我高度紧张,怕对方认为我听不懂。

昨天网上状态变成Not Selected。今天收到拒信。. 留学申请论坛-一亩三分地
. Waral 博客有更多文章,

评分

2

查看全部评分

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

使用道具 举报

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

使用道具 举报

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

谢谢支持。

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

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

<obj1, [0,1]>. 一亩-三分-地,独家发布
<obj2, [1,1]>
<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).
我不知道为什么要用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
第二题是不是可以hashmap + doubly linked list
楼主一定可以找到更好的!
. more info on 1point3acres
我想了一下,用hashmap+double linked list,似乎没有那么方便。。这个数据结构里面,链表和hashmap都应该存一个node的数据结构而不仅仅是obj把?

不知道是不是想乱了,麻烦指正一下~
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

我被吓到了,突然好多人问。。。。。. 围观我们@1point 3 acres
两个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)).本文原创自1point3acres论坛
而每次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
谢谢支持。-google 1point3acres

面试之前我没见过第二题。
.本文原创自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))
而每次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 来源一亩.三分地论坛.
这样,插入的话:
先看是不是第一次出现,如果是,就放到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,如果没有的话,就跳过。
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-4-9 04:33:55 | 显示全部楼层
liberwang 发表于 2015-4-9 04:15
一个Hashmap就够了吧?
.1point3acres网
恩恩,对!!!!!!!
谢谢楼主!!!!!!!
回复 支持 反对

使用道具 举报

 楼主| 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

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 . more info on 1point3acres
        create a new linked list node
        put object[i] address into node's attribute.本文原创自1point3acres论坛
        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

楼主,我觉得这个题目既然说了是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
我面试也是这样想的,但面试官说为了简单,就定义一个数组传进来。他并不在意输入输出形式,在意你的算法。 ...
. 围观我们@1point 3 acres
说的对!确实要问清楚,一个数组传进来其实也是一样的
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-26 04:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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