推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1886|回复: 23
收起左侧

七月脸书

[复制链接] |试试Instant~ |关注本帖
chrono98 发表于 2017-8-2 15:09:34 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Facebook - Other - Onsite |Other在职跳槽

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

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

x
老题不少
1. MxN 01矩阵迷宫,看有没有 路徑从A点到B点。 Followup:如果矩阵超大需要机群存放,如何设计一个并行算法找到AB间的路径
2. 设计instagram
3. 两个list of int ranges, 求加在一起以后的ranges(重合的range合并组成一个新的range); 求单线程处理一个序列task的最短时间,序列中的同一类task有cooldown time
4. 求点集中离给定点最近的K个点

评分

2

查看全部评分

本帖被以下淘专辑推荐:

f1371342385 发表于 2017-8-2 15:21:46 | 显示全部楼层
LZ基本都是原题呀,求问第一题的follow up是如何回答的? :)
回复 支持 反对

使用道具 举报

mythal 发表于 2017-8-2 15:23:09 | 显示全部楼层
同样问follow up是怎么回答的
回复 支持 反对

使用道具 举报

chris612ku 发表于 2017-8-2 17:45:08 | 显示全部楼层
同問第一題followup,謝謝樓主
回复 支持 反对

使用道具 举报

say543 发表于 2017-8-3 14:53:56 | 显示全部楼层
两个list of int ranges, 求加在一起以后的ranges(重合的range合并组成一个新的range) 这题是扫一遍就行了吗?
回复 支持 反对

使用道具 举报

say543 发表于 2017-8-3 14:54:39 | 显示全部楼层
Followup:如果矩阵超大需要机群存放,如何设计一个并行算法找到AB间的路径 也想知道follow up 怎解...
回复 支持 反对

使用道具 举报

shuoshuo 发表于 2017-8-3 23:35:40 | 显示全部楼层
求大神解答
回复 支持 反对

使用道具 举报

daguanyuan 发表于 2017-8-4 01:29:15 | 显示全部楼层
第一问的follow up,抛砖引玉来啦.
分割矩阵:按照行的方式分割矩阵,然后每个子矩阵分别存到不同的机器。
逻辑算法:先广搜索。
具体算法(将先广搜索运用到分布式集群上):采用类似Map-Reduce的方式
Map:master根据节点所在的具体机器的位置发送请求,如:告诉我A节点可达的所有点;
Reduce:slave返回本次请求的结果至master.
这样的方式来模拟先广搜索,来最后找到路径。

别的实在想不到了,有错误的地方请指教。
回复 支持 反对

使用道具 举报

bearicc 发表于 2017-8-4 02:09:59 | 显示全部楼层
daguanyuan 发表于 2017-8-4 01:29
第一问的follow up,抛砖引玉来啦.
分割矩阵:按照行的方式分割矩阵,然后每个子矩阵分别存到不同的机器。 ...

嗯,slave 告诉 master 新的可到的点,master 告诉有这些点的slave 继续处理。应该可行。这样是一开始只处理两个seed。如果能更多nodes同时一起处理感觉会更好。
回复 支持 反对

使用道具 举报

bearicc 发表于 2017-8-4 02:13:52 | 显示全部楼层
3b 就是 621 task scheduler 么 ?
回复 支持 反对

使用道具 举报

mchzh 发表于 2017-8-4 02:41:20 | 显示全部楼层
daguanyuan 发表于 2017-8-4 01:29. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第一问的follow up,抛砖引玉来啦.
分割矩阵:按照行的方式分割矩阵,然后每个子矩阵分别存到不同的机器。 ...

分割之后src点和target点之间会存在多个节点,每个中间节点需要保存什么状态呢?map主节点,然后reduce任何一个slave节点吗?
回复 支持 反对

使用道具 举报

daguanyuan 发表于 2017-8-4 04:50:33 | 显示全部楼层
mchzh 发表于 2017-8-4 02:41
. visit 1point3acres.com for more.分割之后src点和target点之间会存在多个节点,每个中间节点需要保存什么状态呢?map主节点,然后reduce任 ...
. from: 1point3acres.com/bbs
在slave上记录每个节点的状态
回复 支持 反对

使用道具 举报

mchzh 发表于 2017-8-4 06:39:09 | 显示全部楼层
第4题出现的概率很高,这个是有几个什么样的解法?
回复 支持 反对

使用道具 举报

mchzh 发表于 2017-8-4 06:45:40 | 显示全部楼层
daguanyuan 发表于 2017-8-4 04:50
在slave上记录每个节点的状态
. Waral 鍗氬鏈夋洿澶氭枃绔,
就是说每一个节点都要map一次,reduce一次?然后这个节点的输入是下一个节点的输出?这样怎么样保证并行呢?多谢!
回复 支持 反对

使用道具 举报

flgt2014 发表于 2017-8-4 09:10:40 | 显示全部楼层
楼主这题能否举个例子? “两个list of int ranges, 求加在一起以后的ranges(重合的range合并组成一个新的range)”
回复 支持 反对

使用道具 举报

bearicc 发表于 2017-8-4 09:25:05 | 显示全部楼层
mchzh 发表于 2017-8-4 06:39
第4题出现的概率很高,这个是有几个什么样的解法?

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴priority_queue O(nlogk), quickselect O(n), 如果需要返回结果有序, n + klogk
回复 支持 反对

使用道具 举报

bearicc 发表于 2017-8-4 09:27:14 | 显示全部楼层
flgt2014 发表于 2017-8-4 09:10
楼主这题能否举个例子? “两个list of int ranges, 求加在一起以后的ranges(重合的range合并组成一个新的 ...

感觉应该是LC57,将输入改为两个list.  两个list 排序, two pointer merge.
回复 支持 反对

使用道具 举报

porkbelly 发表于 2017-8-4 12:20:52 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!. Waral 鍗氬鏈夋洿澶氭枃绔,

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南facebook how to find friends
回复 支持 反对

使用道具 举报

porkbelly 发表于 2017-8-4 12:22:22 | 显示全部楼层
http://www.geeksforgeeks.org/design-data-structures-for-a-very-large-social-network-like-facebook-or-linkedln/
. from: 1point3acres.com/bbs
不知道按照这个链接的思路    去解第一问 的 follow up 的问题行不行?
回复 支持 反对

使用道具 举报

daguanyuan 发表于 2017-8-5 01:11:13 | 显示全部楼层
mchzh 发表于 2017-8-4 06:45. From 1point 3acres bbs
就是说每一个节点都要map一次,reduce一次?然后这个节点的输入是下一个节点的输出?这样怎么样保证并行 ...

slave上记录的是在slave上的节点状态:该节点有没被访问过。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-22 10:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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