谈谈面试官在面试coding题目时的考察终点与心理活动, 求大米

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3031|回复: 23
收起左侧

七月脸书

[复制链接] |试试Instant~ |关注本帖
我的人缘0
chrono98 发表于 2017-8-2 15:09:34 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩

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

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

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

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

评分

参与人数 2大米 +21 收起 理由
pomme2016 + 1 感谢分享!
hurricane_e + 20 感谢分享!

查看全部评分


上一篇:巨硬728 hiring event
下一篇:applovin 昂赛特

本帖被以下淘专辑推荐:

我的人缘0
 楼主| chrono98 发表于 2017-8-6 23:37:19 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
不好意思这几天太忙了一直没上

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

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

1.所有的迷宫格子数据存在HDFS,
2.点集X可以用一台server存储,加个RPC存取API
3.分布式的worker的逻辑就是 a)从X取几个点 b)load 相应的迷宫格子 c)找到边界点集存进server

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

使用道具 举报

我的人缘0
f1371342385 发表于 2017-8-2 15:21:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (48)
 
 
12% (7)  踩
LZ基本都是原题呀,求问第一题的follow up是如何回答的? :)
回复

使用道具 举报

我的人缘0
mythal 发表于 2017-8-2 15:23:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
同样问follow up是怎么回答的
回复

使用道具 举报

我的人缘0
chris612ku 发表于 2017-8-2 17:45:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (15)
 
 
0% (0)  踩
同問第一題followup,謝謝樓主
回复

使用道具 举报

我的人缘0
say543 发表于 2017-8-3 14:53:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (32)
 
 
15% (6)  踩
两个list of int ranges, 求加在一起以后的ranges(重合的range合并组成一个新的range) 这题是扫一遍就行了吗?
回复

使用道具 举报

我的人缘0
say543 发表于 2017-8-3 14:54:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (32)
 
 
15% (6)  踩
Followup:如果矩阵超大需要机群存放,如何设计一个并行算法找到AB间的路径 也想知道follow up 怎解...
回复

使用道具 举报

我的人缘0
shuoshuo 发表于 2017-8-3 23:35:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (10)
 
 
0% (0)  踩
求大神解答
Mobile Apps Category (English)728x90
回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
bearicc 发表于 2017-8-4 02:09:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (30)
 
 
6% (2)  踩
daguanyuan 发表于 2017-8-4 01:29
第一问的follow up,抛砖引玉来啦.
分割矩阵:按照行的方式分割矩阵,然后每个子矩阵分别存到不同的机器。 ...

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

使用道具 举报

我的人缘0
bearicc 发表于 2017-8-4 02:13:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (30)
 
 
6% (2)  踩
3b 就是 621 task scheduler 么 ?
回复

使用道具 举报

我的人缘0
mchzh 发表于 2017-8-4 02:41:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (66)
 
 
7% (5)  踩
daguanyuan 发表于 2017-8-4 01:29
第一问的follow up,抛砖引玉来啦.
分割矩阵:按照行的方式分割矩阵,然后每个子矩阵分别存到不同的机器。 ...

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

使用道具 举报

我的人缘0
yikehongxin 发表于 2017-8-4 04:50:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (232)
 
 
8% (22)  踩
mchzh 发表于 2017-8-4 02:41
分割之后src点和target点之间会存在多个节点,每个中间节点需要保存什么状态呢?map主节点,然后reduce任 ...

在slave上记录每个节点的状态
回复

使用道具 举报

我的人缘0
mchzh 发表于 2017-8-4 06:39:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (66)
 
 
7% (5)  踩
第4题出现的概率很高,这个是有几个什么样的解法?
回复

使用道具 举报

我的人缘0
mchzh 发表于 2017-8-4 06:45:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (66)
 
 
7% (5)  踩
daguanyuan 发表于 2017-8-4 04:50
在slave上记录每个节点的状态

就是说每一个节点都要map一次,reduce一次?然后这个节点的输入是下一个节点的输出?这样怎么样保证并行呢?多谢!
回复

使用道具 举报

我的人缘0
flgt2014 发表于 2017-8-4 09:10:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (34)
 
 
0% (0)  踩
楼主这题能否举个例子? “两个list of int ranges, 求加在一起以后的ranges(重合的range合并组成一个新的range)”
回复

使用道具 举报

我的人缘0
bearicc 发表于 2017-8-4 09:25:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (30)
 
 
6% (2)  踩
mchzh 发表于 2017-8-4 06:39
第4题出现的概率很高,这个是有几个什么样的解法?

priority_queue O(nlogk), quickselect O(n), 如果需要返回结果有序, n + klogk
回复

使用道具 举报

我的人缘0
bearicc 发表于 2017-8-4 09:27:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (30)
 
 
6% (2)  踩
flgt2014 发表于 2017-8-4 09:10.留学论坛-一亩-三分地
楼主这题能否举个例子? “两个list of int ranges, 求加在一起以后的ranges(重合的range合并组成一个新的 ...

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

使用道具 举报

我的人缘0
porkbelly 发表于 2017-8-4 12:20:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

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

使用道具 举报

我的人缘0
porkbelly 发表于 2017-8-4 12:22:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
http://www.geeksforgeeks.org/design-data-structures-for-a-very-large-social-network-like-facebook-or-linkedln/

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

使用道具 举报

我的人缘0
yikehongxin 发表于 2017-8-5 01:11:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (232)
 
 
8% (22)  踩
mchzh 发表于 2017-8-4 06:45
就是说每一个节点都要map一次,reduce一次?然后这个节点的输入是下一个节点的输出?这样怎么样保证并行 ...

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

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-7-23 21:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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