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


一亩三分地论坛

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

七月脸书

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

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

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

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

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| chrono98 发表于 2017-8-6 23:37:19 | 显示全部楼层
不好意思这几天太忙了一直没上.鐣欏璁哄潧-涓浜-涓夊垎鍦

关于那个follow up,当时就是还剩十几分钟,就仅仅和面试官描述了一下思路:

基本逻辑:
1. 巨大迷宫可以划分成格子存储,每块格子能放进单机memory
2. 从起点S用DFS找到格子上下左右边界上所有可达的点集X。对每一个点,记录位置和方向(方向是指接下来的探查方向,比如说点P在当前格子的左边界上,那么下次就应该继续向左边的格子探查;如果在角上,就要探查两个方向,比如向左和向上)
3. 对于点集X中的每一个没有处理过的点,按照探查方向继续用DFS找到相邻格子中上下左右边界上的可达点,并加入X
4. 最终会hit终点e的格子的边界,再看看从边界上的点能不能达到终点e

并行化:
.鐣欏璁哄潧-涓浜-涓夊垎鍦
1.所有的迷宫格子数据存在HDFS,
2.点集X可以用一台server存储,加个RPC存取API
3.分布式的worker的逻辑就是 a)从X取几个点 b)load 相应的迷宫格子 c)找到边界点集存进server

最后又提了下failure handling 什么的,面试官说和他想的差不多,应该算是混过去了
回复 支持 1 反对 0

使用道具 举报

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,抛砖引玉来啦.
分割矩阵:按照行的方式分割矩阵,然后每个子矩阵分别存到不同的机器。 ...
. From 1point 3acres bbs
嗯,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,抛砖引玉来啦..1point3acres缃
分割矩阵:按照行的方式分割矩阵,然后每个子矩阵分别存到不同的机器。 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
分割之后src点和target点之间会存在多个节点,每个中间节点需要保存什么状态呢?map主节点,然后reduce任何一个slave节点吗?
回复 支持 反对

使用道具 举报

daguanyuan 发表于 2017-8-4 04:50:33 | 显示全部楼层
mchzh 发表于 2017-8-4 02:41
分割之后src点和target点之间会存在多个节点,每个中间节点需要保存什么状态呢?map主节点,然后reduce任 ...

在slave上记录每个节点的状态
回复 支持 反对

使用道具 举报

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

使用道具 举报

mchzh 发表于 2017-8-4 06:45:40 | 显示全部楼层
daguanyuan 发表于 2017-8-4 04:50
在slave上记录每个节点的状态
. from: 1point3acres.com/bbs
就是说每一个节点都要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!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南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/

不知道按照这个链接的思路    去解第一问 的 follow up 的问题行不行?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-23 19:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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