一亩三分地论坛

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

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

亚马逊OA, 01/15

[复制链接] |试试Instant~ |关注本帖
guixi107 发表于 2016-1-21 16:10:32 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Amazon - 猎头 - HR筛选 |Other在职跳槽

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

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

x
刚刚写完亚马逊的 HackerRank的code challenge, 看了地里的资料,现在回馈地里。

timeline是01/15号发的邀请,需要在7天内完成。.鏈枃鍘熷垱鑷1point3acres璁哄潧
可能考虑到自己是在职找,所以只有一道算法题目,时间是75分钟。-google 1point3acres

题目如下:
假设有个Movie类,
public class Movie
{
   int movieId;
   float rating;. 鍥磋鎴戜滑@1point 3 acres
   List<Movie> similarMovies
还有其他的getters
}
现在要求找到 k个和movie最相似 的movies。

函数的signature大概是这样的:
public static List<Movie> getNearest(Movie movie, int numSimilar)。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
举个栗子:.1point3acres缃
m0 <-->m1, similarity 2
mo <--> m2, similarity 3
m1 <--> m3, similarity 4
m2 <--> m5, similaity 5.1point3acres缃

如果要返回和mo最相似的movie, 那么应该返回 m5 (只有有一条路径从 m1到 m5, 并且 5是最大的); 如果返回3个最相似的就返回 m2, m3, m5(顺序不重要); 如果需要返回10个,但是相似的只有9个,那么就返回9个。
source movie本身不能在返回结果里面。

可以的一个做法是 dfs + min-Heap(PriorityQueue), 我们一直做dfs, 每次碰到一个新的movie,如果现在queue的size比 k小的话,直接加到queue里面; 如果新movie的rating比queue top movie的rating高的话, 把顶部movie
踢出队列,加上这个新的。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. from: 1point3acres.com/bbs
28号还要点面google。。。
接着写LeetCode去。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

. From 1point 3acres bbs
补充内容 (2016-1-21 16:13):
求给米,求给米,求给米

补充内容 (2016-1-21 16:14):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
update: 应该返回 m5 (只有有一条路径从 m1到 m5, 并且 5是最大的) --> 应该返回 m5 (只要有一条路径从 m1到 m5, 并且 5是最大的).鏈枃鍘熷垱鑷1point3acres璁哄潧

(好像没法修改已经发表的东西,神奇的网站设计)

评分

2

查看全部评分

本帖被以下淘专辑推荐:

pepero 发表于 2016-1-28 06:27:20 | 显示全部楼层
恩,搞明白了。如果k是3,那有两组(m5,m3,m2) ,(m5,m3,m1),返回哪组都行吧。.鐣欏璁哄潧-涓浜-涓夊垎鍦

顺祝店面顺利。
回复 支持 1 反对 0

使用道具 举报

 楼主| guixi107 发表于 2016-1-21 16:11:33 | 显示全部楼层
update: 应该返回 m5 (只有有一条路径从 m1到 m5, 并且 5是最大的) --> 应该返回 m5 (只要有一条路径从 m1到 m5, 并且 5是最大的)
回复 支持 反对

使用道具 举报

pepero 发表于 2016-1-27 05:11:24 | 显示全部楼层
要返回mo最相似的movie, 那么应该返回 m5
没看明白, 为什么返回m5?.1point3acres缃

举个栗子:
鏉ユ簮涓浜.涓夊垎鍦拌鍧. m0 <-->m1, similarity 2
mo <--> m2, similarity 3
m1 <--> m3, similarity 4
m2 <--> m5, similaity 5 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

你这个例子里有m0, m1, m2, m3, m5, 相当于节点吗?similarity相当于edge的权重?
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-27 08:22:42 | 显示全部楼层
pepero 发表于 2016-1-27 05:11
要返回mo最相似的movie, 那么应该返回 m5
没看明白, 为什么返回m5?

m0, m1 都是节点(vertex), 里面的值是它和源movie的similarity。

数据是这样给出的:
(m0, 2)
(m1, 4)
然后m0和m1直接有一个edge。

我当时的处理是访问到m1的时候,看到4,那么我把4理解为m1和源movie直接的相似度。
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-27 08:26:50 | 显示全部楼层
guixi107 发表于 2016-1-27 08:22. 1point 3acres 璁哄潧
m0, m1 都是节点(vertex), 里面的值是它和源movie的similarity。
.1point3acres缃
数据是这样给出的:

或者说:

抽象的结果是: 返回所有和source movie相连的movie里面, 相似度最高的k个; 如果相连的movie的数目不够k个,那么返回所有相连的movie。

dfs,或者bfs, 都可以。.鏈枃鍘熷垱鑷1point3acres璁哄潧
用一个priorityqueue来选择k个。

有没有讲明白?
回复 支持 反对

使用道具 举报

kiviljc 发表于 2016-1-27 22:58:52 | 显示全部楼层
兄弟,,给个店面面经吧
回复 支持 反对

使用道具 举报

pepero 发表于 2016-1-28 05:02:57 | 显示全部楼层
小弟真没看懂, 怎么除了m0, m1, ..., m5 还有源movie? 什么是源movie?
你说的栗子:
m0 <-->m1, similarity 2
mo <--> m2, similarity 3
m1 <--> m3, similarity 4
. visit 1point3acres.com for more.m2 <--> m5, similaity 5
画图如下:
m0 -- m1 -- m3-google 1point3acres
|. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
m2 - - m5

没搞明白这几个节点是什么关系。
还有rating是干什么用的?

(m0, 2)
(m1, 4)
然后m0和m1直接有一个edge。

回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-28 05:09:14 | 显示全部楼层
kiviljc 发表于 2016-1-27 22:58
兄弟,,给个店面面经吧

店面还有3小时 就要开始啦。。。

面完才能写啊
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-28 05:12:00 | 显示全部楼层
pepero 发表于 2016-1-28 05:02
小弟真没看懂, 怎么除了m0, m1, ..., m5 还有源movie? 什么是源movie?
你说的栗子:
m0 m1, similarity ...

接着用你的例子

假设 m0是源movie

m0(2.0) -- m1(3.0) -- m3(4.0)
|
m2(3.0) - - m5(5.0)

如果找和m0最相似的movie, 那么返回m5. 鍥磋鎴戜滑@1point 3 acres

抽象的结果是: 返回所有和source movie(上面的例子里, 就是m0) 相连的movie里面, 相似度最高的k个; 如果相连的movie的数目不够k个,那么返回所有相连的movie。
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-28 05:14:09 | 显示全部楼层
guixi107 发表于 2016-1-28 05:12
接着用你的例子

假设 m0是源movie

函数的signature大概是这样的:
public static List<Movie> getNearest(Movie movie, int numSimilar)。.鐣欏璁哄潧-涓浜-涓夊垎鍦

传进来的第一个参数就是source movie对象
回复 支持 反对

使用道具 举报

pepero 发表于 2016-1-28 05:22:19 | 显示全部楼层
返回m5是因为m5的相似度5是最大的马?那如果k是2, 返回什么?

如果m0是源movie, m0(2.0) 中的2.0代表什么?
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-28 05:42:19 | 显示全部楼层
pepero 发表于 2016-1-28 05:22
返回m5是因为m5的相似度5是最大的马?那如果k是2, 返回什么?

如果m0是源movie, m0(2.0) 中的2.0代表什 ...

k ==2, 返回 m3和m5.1point3acres缃
.鏈枃鍘熷垱鑷1point3acres璁哄潧
每一个movie都有一个rating(看我给的movie的定义)。m0(2.0)里面的2.0没有意义,这也是为什么要求返回相似电影的时候要剔除souce movie.
回复 支持 反对

使用道具 举报

kiviljc 发表于 2016-1-28 05:49:21 | 显示全部楼层
guixi107 发表于 2016-1-28 05:09
店面还有3小时 就要开始啦。。。. more info on 1point3acres.com

面完才能写啊

同样4:00 pst 面

补充内容 (2016-1-28 05:49):
good luck for both of us
回复 支持 反对

使用道具 举报

qjx026 发表于 2016-1-30 10:55:49 | 显示全部楼层
真心看糊涂了。
求教楼主. more info on 1point3acres.com
mo <--> m2, similarity 3
m2 <--> m5, similarity 5
说明m0 和m2相连, m2和m5再连。中间隔着一个m2呢, 相似度是要衰减的.
楼主的意思 m0和m5的相似度应该是多少? 3+ 5 = 8?还是直接取5?
感觉完全不make sense.
回复 支持 反对

使用道具 举报

firemanysome 发表于 2016-1-30 11:43:16 | 显示全部楼层
跪求源码。 alex.liuwe@gmail.com
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-31 04:56:51 | 显示全部楼层
qjx026 发表于 2016-1-30 10:55
真心看糊涂了。
求教楼主
mo  m2, similarity 3

直接取5,后面的数字就是和source movie的相似度,不用再对相似度进行处理了。
. visit 1point3acres.com for more.
m0(2) --- m2(3)
m2(3) --m5(5)

可以认为m5(5)中的5是和m0的相似度。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

不要想的太复杂了
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-31 05:07:07 | 显示全部楼层

这个我没有存源码啊。

最核心的code是这样的(通过了所有的测试): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

private void dfs(Movie s, int sourceMovieId, int k, Set<Movie>visited, PriorityQueue<Movie> pq)
{
   visited.add(s);
   if(s.id != sourceMovieId)
   {
      if(pq.size() < k){
            pq.offer(s);
     }

    if(pq.size() > k && pq.peek().getRating() < s.getRating())
    {
        pq.poll();. more info on 1point3acres.com
        pq.offer(s);
    }     
   }
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   for(Movie m : s.similarMovies()). 鍥磋鎴戜滑@1point 3 acres
   {. visit 1point3acres.com for more.
        if(!visited.contains(m))
       {
           dfs(m, sourceMovieId, k, visited, pq);
      }
   }
}
. Waral 鍗氬鏈夋洿澶氭枃绔,
当然写priorityqueue的时候要提供comparator

PriorityQueue<Movie> pq = new PriorityQueue(k, new Comparator<Movie>(){
   public int compare(Movie m0, Movie m1)
   { return m0.getRating() - m1.getRating();}
});

最后的结果是把pq里面的东西放到list里面去。

有没有问题?
回复 支持 反对

使用道具 举报

qjx026 发表于 2016-1-31 12:34:50 | 显示全部楼层
guixi107 发表于 2016-1-31 04:56. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
直接取5,后面的数字就是和source movie的相似度,不用再对相似度进行处理了。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
m0(2) --- m2(3)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
嗯, 懂了。 谢谢楼主。
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-31 12:37:05 | 显示全部楼层
guixi107 发表于 2016-1-31 05:07
这个我没有存源码啊。

最核心的code是这样的(通过了所有的测试):

修改下:
    if(pq.size() > k && pq.peek().getRating() < s.getRating())
to:
    if(pq.size() == k && pq.peek().getRating() < s.getRating())
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 17:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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