《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4196|回复: 21
收起左侧

亚马逊OA, 01/15

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

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

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

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

x
刚刚写完亚马逊的 HackerRank的code challenge, 看了地里的资料,现在回馈地里。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
timeline是01/15号发的邀请,需要在7天内完成。
可能考虑到自己是在职找,所以只有一道算法题目,时间是75分钟。

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

函数的signature大概是这样的:
public static List<Movie> getNearest(Movie movie, int numSimilar)。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

举个栗子:
m0 <-->m1, similarity 2
mo <--> m2, similarity 3
m1 <--> m3, similarity 4
m2 <--> m5, similaity 5

如果要返回和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 1point 3acres bbs
踢出队列,加上这个新的。
-google 1point3acres
28号还要点面google。。。
接着写LeetCode去。。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

补充内容 (2016-1-21 16:14):
update: 应该返回 m5 (只有有一条路径从 m1到 m5, 并且 5是最大的) --> 应该返回 m5 (只要有一条路径从 m1到 m5, 并且 5是最大的)

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

评分

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?

-google 1point3acres举个栗子:
m0 <-->m1, similarity 2. 1point3acres.com/bbs
mo <--> m2, similarity 3 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
m1 <--> m3, similarity 4
m2 <--> m5, similaity 5.1point3acres缃

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

使用道具 举报

 楼主| guixi107 发表于 2016-1-27 08:22:42 | 显示全部楼层
pepero 发表于 2016-1-27 05:11
要返回mo最相似的movie, 那么应该返回 m5
. Waral 鍗氬鏈夋洿澶氭枃绔,没看明白, 为什么返回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
m0, m1 都是节点(vertex), 里面的值是它和源movie的similarity。

数据是这样给出的:

或者说:

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

dfs,或者bfs, 都可以。
用一个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. more info on 1point3acres.com
mo <--> m2, similarity 3
m1 <--> m3, similarity 4
m2 <--> m5, similaity 5
画图如下:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
m0 -- m1 -- m3
|
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 ...

接着用你的例子. Waral 鍗氬鏈夋洿澶氭枃绔,

假设 m0是源movie

m0(2.0) -- m1(3.0) -- m3(4.0).1point3acres缃
|
m2(3.0) - - m5(5.0). From 1point 3acres bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
如果找和m0最相似的movie, 那么返回m5
. 1point3acres.com/bbs
抽象的结果是: 返回所有和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)。
. more info on 1point3acres.com
传进来的第一个参数就是source movie对象
回复 支持 反对

使用道具 举报

pepero 发表于 2016-1-28 05:22:19 | 显示全部楼层
返回m5是因为m5的相似度5是最大的马?那如果k是2, 返回什么?
. more info on 1point3acres.com
如果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

每一个movie都有一个rating(看我给的movie的定义)。m0(2.0)里面的2.0没有意义,这也是为什么要求返回相似电影的时候要剔除souce movie.
回复 支持 反对

使用道具 举报

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

面完才能写啊

同样4:00 pst 面

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

使用道具 举报

qjx026 发表于 2016-1-30 10:55:49 | 显示全部楼层
真心看糊涂了。
求教楼主
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的相似度,不用再对相似度进行处理了。

m0(2) --- m2(3)
m2(3) --m5(5)

可以认为m5(5)中的5是和m0的相似度。
. Waral 鍗氬鏈夋洿澶氭枃绔,
不要想的太复杂了
回复 支持 反对

使用道具 举报

 楼主| guixi107 发表于 2016-1-31 05:07:07 | 显示全部楼层
firemanysome 发表于 2016-1-30 11:43
. visit 1point3acres.com for more.跪求源码。

这个我没有存源码啊。

最核心的code是这样的(通过了所有的测试):
. more info on 1point3acres.com
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();
        pq.offer(s);. 1point3acres.com/bbs
    }     
   }

   for(Movie m : s.similarMovies())
   {
        if(!visited.contains(m)). Waral 鍗氬鏈夋洿澶氭枃绔,
       {
           dfs(m, sourceMovieId, k, visited, pq);
      }
   }
}

当然写priorityqueue的时候要提供comparator
. more info on 1point3acres.com
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是这样的(通过了所有的测试):
.1point3acres缃
修改下:. Waral 鍗氬鏈夋洿澶氭枃绔,
    if(pq.size() > k && pq.peek().getRating() < s.getRating())
to:
    if(pq.size() == k && pq.peek().getRating() < s.getRating())
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-24 17:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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