聊聊在私立文理读cs的两年感受

一亩三分地论坛

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

亚马逊OA, 01/15

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

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

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

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

x
刚刚写完亚马逊的 HackerRank的code challenge, 看了地里的资料,现在回馈地里。
-google 1point3acres
timeline是01/15号发的邀请,需要在7天内完成。
可能考虑到自己是在职找,所以只有一道算法题目,时间是75分钟。

题目如下:
假设有个Movie类,
public class Movie
{
   int movieId;. 一亩-三分-地,独家发布
   float rating;
   List<Movie> similarMovies
还有其他的getters
}
现在要求找到 k个和movie最相似 的movies。
.1point3acres网
函数的signature大概是这样的:
public static List<Movie> getNearest(Movie movie, int numSimilar)。

举个栗子:
m0 <-->m1, similarity 2
mo <--> m2, similarity 3. From 1point 3acres bbs
m1 <--> m3, similarity 4
m2 <--> m5, similaity 5

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

可以的一个做法是 dfs + min-Heap(PriorityQueue), 我们一直做dfs, 每次碰到一个新的movie,如果现在queue的size比 k小的话,直接加到queue里面; 如果新movie的rating比queue top movie的rating高的话, 把顶部movie. visit 1point3acres for more.
踢出队列,加上这个新的。

28号还要点面google。。。. 1point 3acres 论坛
接着写LeetCode去。。。


补充内容 (2016-1-21 16:13):
求给米,求给米,求给米

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

举个栗子:
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. visit 1point3acres for more.
要返回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
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?
你说的栗子:. 1point 3acres 论坛
m0 <-->m1, similarity 2
mo <--> m2, similarity 3
m1 <--> m3, similarity 4
m2 <--> m5, similaity 5. visit 1point3acres for more.
画图如下:
m0 -- m1 -- m3. 围观我们@1point 3 acres
|
m2 - - m5

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

(m0, 2)
(m1, 4)
然后m0和m1直接有一个edge。. more info on 1point3acres
来源一亩.三分地论坛.
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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

店面还有3小时 就要开始啦。。。. visit 1point3acres for more.
. 1point3acres
面完才能写啊
回复 支持 反对

使用道具 举报

 楼主| 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
.留学论坛-一亩-三分地
抽象的结果是: 返回所有和source movie(上面的例子里, 就是m0) 相连的movie里面, 相似度最高的k个; 如果相连的movie的数目不够k个,那么返回所有相连的movie。
回复 支持 反对

使用道具 举报

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

假设 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, 返回什么?. visit 1point3acres for more.

如果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
. from: 1point3acres
直接取5,后面的数字就是和source movie的相似度,不用再对相似度进行处理了。

. 围观我们@1point 3 acresm0(2) --- m2(3)
m2(3) --m5(5)

可以认为m5(5)中的5是和m0的相似度。.留学论坛-一亩-三分地

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

使用道具 举报

 楼主| guixi107 发表于 2016-1-31 05:07:07 | 显示全部楼层
firemanysome 发表于 2016-1-30 11:43.本文原创自1point3acres论坛
跪求源码。

这个我没有存源码啊。

最核心的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){. Waral 博客有更多文章,
            pq.offer(s);. more info on 1point3acres
     }

    if(pq.size() > k && pq.peek().getRating() < s.getRating())
    {
        pq.poll();
        pq.offer(s);
    }     . 一亩-三分-地,独家发布
   } 来源一亩.三分地论坛.

   for(Movie m : s.similarMovies())
   {
        if(!visited.contains(m)). 1point3acres
       {
           dfs(m, sourceMovieId, k, visited, pq);
      }
   }
}

当然写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里面去。. 1point3acres

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

使用道具 举报

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())
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-21 09:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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