一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4339|回复: 8
收起左侧

LiveRamp OA面经总结帖

[复制链接] |试试Instant~ |关注本帖
Olivier12345 发表于 2015-2-25 15:51:07 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@LiveRamp - 网上海投 - 在线笔试 |Other

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

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

x
目前看得到的LiveRamp面经整理如下,希望能够帮助到将要面试的童鞋,包括我自己^_^帖子的时间都是2014下半年到2015年1、2月的,应该不会过期

// 感言及提醒
1. 首先澄清一点大家的错误认识,LiveRamp实际上最近还是一直在招人的, 否则我也不会拿到Offer。我问了其中一些人,他们说基本每天都有一个人去Onsite,所以就算去onsite拿到的比例还是很低的。现在的Engineering team大概35人,计划今年double。
Six-degree那题一定要好好准备,知道所有常见的解法及相互之间比较,时间复杂度和空间复杂度分析。

// OA
1. 电话面试之前要做一个OA,题目不是很难,大概有10道左右的关于时间复杂度和算法的选择题。然后就是那个著名的six-degree的问题,其实就是在无向图中找两个点之间的最短路径,不需要写代码,只要分析讨论一下各种不同的算法之间的优劣,然后说明自己想选择哪种算法就可以了。如果时间允许,尽量多讨论一些算法,BFS,Dijkstra, Bi-BFS等等。我选的是Bi-BFS。然后还有一个问题问为什么选择Liveramp, 随便写写就行了。glassdoor也有详细的OA的题目。

2. 关于OA,已经有太多的面经,我在这里就再稍微简单说下吧。就是基本的算法复杂度分析和那个six-degree的题。当时我做OA的时候也没太认真想six-degree的所有解法,就只写了DFS, BFS和Bi-directional BFS,然后选bi-BFS写了要用到的数据结构(两组):
首先是BFS需要的Queue. From 1point 3acres bbs
存距离的Map
为恢复路径存BFS路径上一个节点的信息Map. 1point 3acres 璁哄潧
上述数据结构需要两份,因为bi-BFS是双向的,而且需要step by step,每个BFS轮流走一步。
好多人觉得自己OA做的不错但还是被拒了。。我也不知道为什么 问了一些同学朋友感觉他们答的也不错。。所以到底判断标准是什么呢?
1小时候收到一面。
. more info on 1point3acres.com
3. 之前有传闻说他家换题了,但是我碰到的还是经典的那几道题。。。前面的真的太容易了,,就一道题比较tricky
个关于算法的时间复杂度问题。其中一个题是关于求pairs和的问题。就是给定一个array,长度为n, 则有n*(n – 1)/ 2个pairs。 先将每个pair里的两个数加起来,得到n*(n-1 )/2 个,然后将这些数加起来。得到一个总和。题目问的是求这个总和最快方法的复杂度是多少。这个题目比较贱。从题目的描述以为是O(n*n), 其实是O(n)。因为等于所有数加起来然后乘以(n-1)。。。
传闻中的六度空间还在(是不是因为我运气好,之前有几个人说等到最后也没碰到)。。然后我就bi-BFS。。。
后面的behavior看来是无所谓的,因为我没怎么答也通过了。。

// Phone Interview
1. 印度小哥面的 口音很纯
先介绍一下面试内容 说大概20分钟
然后讲了一下简历 他看我介绍的是big data的project 于是开始问 假设有1GB数据对 怎么储存 我说HashMap就可以了. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后问如果数据量达到1TB又怎么处理 我说用一个hashMap映射到10个Map
follow up假如数据量分布不均匀怎么办 我开始说可以在数据录入的时候跟踪用别的方法来record 面试官说这样太麻烦 后来我想不起来 说应该有一种数学分布可以解决这个问题 把数据平均化 小哥说确实有一种 然后说了半天没听懂
然后小哥问 那这个分布式系统需要一个master机器吗 我说需要。。(大概会跪在这儿) 他说其实不用 问我为什么 我说可以减少流量 他说防止failure 免得一个机器废掉都废掉了。。
最后我问了下公司大概有多少人 他说有34到35个engineer 在未来7个月会扩张一倍


2. 之后就是电面了。我第一轮电面就问了为什么投Liveramp, 然后就在详细地问six degree的问题。问了各种算法的时间空间复杂度,以及BFS和双向BFS算法具体是怎么实现的,算法运行完了之后如何找出具体的最短路径。然后又follow-up了一个问题,就是如果图太大了,储存空间不够,不能用BFS,应该怎么办? 这种情况就要用IDS算法,就是多次执行DFS,每次增加depth,直到找到最短路径。这种算法空间复杂度跟DFS一样,时间复杂度比BFS稍大,但是也没有大很多。我第一轮电面大概就20分钟就结束了。
然后当天就邮件约了第二轮电面。我看了一些其他的面经说第二轮电面会问一些概率题,然后就是继续问six-degree。可能我第一轮电面six-degree已经问的很透彻了,所以第二轮没有问six degree。上来还是先问为什么Liveramp, 接着问了那个著名的投篮概率问题。就是投篮3中2和8中5应该选哪个? 这个问题以前很多的面经都讲过了,大概就是如果投篮命中率比较高,选3种2,投篮命中率比较低的话就选8中5. 因为投篮次数越多,结果越接近数学期望,所以如果命中率是90%,应该尽量多投,这样避免意外。如果命中率只有10%,那应该选择3中2,因为投篮次数越少,结果越离散,只投3次因为运气意外赢的可能性比较大。接着问了一个涉及dsitributed file system的问题。开始就是问有一个file,里面包含很多访问者的ID,要统计总共有多少unique ID, 这个就扫一遍文件用hashset做就行了。接着问假如ID太多,储存空间不够,不能用hashset怎么办?这样就要先sort这个文件里的ID,然后扫一遍统计一下,不需要hashset了。接下来继续问如果给你一个machine上存着这个文件,另外再给你10个machine, 怎么构建一个分布式的系统能够最快速地算出总共有多少unique ID. 会不停地问你还能不能继续优化,目前你的方案有没有缺陷之类的。



3. 第一轮电面:我觉得在电面前应该先把公司网站上写的东西认真看下对公司和产品稍微优点了解,因为在两轮电面中我都被问到了。。聊天扯淡问简历差不多就10多分钟了。接下来又问到了six-degree,具体主要是问普通的BFS和双向BFS的区别,为什么双向的能够省时间和空间,省多少时间和空间。我基本也就是举了个worst case,双向BFS的空间及时间复杂度和普通BFS相比大概都是开根号的关系,如果这点没有想明白的同学一定要把这个问题想清楚,二面也问了这个。还有问了那个X, Y, 1, 2扑克牌的问题(一面数字,一面字母)。这题那个面试官给我描述的太混乱了。。为了搞清楚题意,我让他重复了好多好多遍,大概10分钟才弄明白题意。。然后知道题意后基本就几秒钟就知道怎么做了。做这道题前没太看面经,后来看了才知道好多人已经被面过这个了。我觉得最简单的题意的表述是这样的:现在给你一个statement: “X的背面一定是偶数“,上述扑克牌你至少要翻几次才能验证这个statement是对的还是错的。扑克牌两面的数字和字母对应关系可以是不一样的,例如可以同时有以下两张扑克牌: Y/2, Y/3。理解题意后就非常简单了,就翻X和1就行了,因为只有这两者有可能证否。1.5h收到二面。
第二面电面:
就开始同样是扯淡聊简历10多分钟。然后就是那个著名的投篮问题了。我被问到的是2/3和4/6的比较,貌似和大家经常被问到的5/8不太一样。我觉得看过面经的同学基本都知道这道题应该是分命中率讨论的。因为在两个数值差不太多的时候,样本空间的大小有很大的影响。投篮次数少(样本空间小)则有很大的不确定性,如果命中率不高果断选投篮次数少的。高的话就选投篮次数多的,因为当样本空间足够大的时候,进球数会基本靠近于命中率 * 投篮次数。 以上只是最基本的分析,对于不同的数字组合,可能分析上会略微有不同,不过总体思路就是这样。
之后又是six-degree,问的内容基本重复一面的。忘了在一面还是二面的时候问我有多少中解法的时候我还说了Dijkstra,然后就问我为什么不用这个。这题很明显所有边的权重是一样的,所以Dijkstra就退化成了BFS,所以二者是一样的,况且Dijkstra还要维持一个堆,时间复杂度更高。
接下来问了下说如果要你给别人介绍他们公司的产品,你会怎么介绍。这点是非常重要的,也是为什么我让大家提前去看他们公司产品资料的原因,如果看了还不太明白的话可以直接看最下面有一些”Case Study”. 1.5h收到onsite.鐣欏璁哄潧-涓浜-涓夊垎鍦



4. 之前做的OA 然后约的电面我没接到 他家HR连发两封邮件让重约 。。上来吐槽下那个逻辑题 四张纸 X Y 1 2 每张纸一面写数字一面写字母 问要翻几张纸才能确定X对面是不是偶
算法继续问六度 不过我刚说完BFS 他就很深入的要聊这个 最后他给了个图 把整个流程都要讲一遍 包括怎么存储路径
最后问问题 他名字叫Roshan 我就问了他玩不玩dota
这个公司不抱什么希望 下周factset onsite 求指点求人品
.1point3acres缃

// On site
1. 第一轮:一个Team Lead面的,他一个人就lead 3个team, 也是醉了。。不过每个team都挺小,就3-5人。聊天扯淡30多分钟,最后问了一道coding.
给定一个概念,叫做加密可替换,定义为两个单词间每个字母都能通过一套映射规则相互替换。为了大家理解举几个例子: aba和cdc,这两个就可以,因为映射关系可以为a-c, b-d。aba和cde这两个就不是加密可替换,因为不能同时a-c且a-e。
然后输入是Set输出格式是List>, 所有相互间加密可替换的单词组成一个group,就是一个List, 然后返回所有的group。同个group任意两个单词间都可以是不同的映射规则,只要保证任意两个可以通过某个映射规则替换成对方就行。
第二轮:
又是聊天聊了40分钟,然后让写个subset。。。为了装作没做过,假装想了一下,然后很快就写完了。
第三轮:
Decode Ways。。同上,假装想了一下,然后先随便用O(n)复杂度的DP写了。写完后写几个test case。然后说空间可以优化为O(1)。 接着问了一个很神奇的问题,做好几遍这个题都从没想过的。问我能不能给出一些答案的upper bound,不一定需要非常tight的upper bound。我最开始说了Fibonacci数列,然后说了快速计算Fibonacci数列第n个数的方法,这个答案面试官还是很满意的。然后又问有没其他的upper bound。我在很努力的想其他tricky的upper bound的同时顺便说下非常明显的upper bound是2^n,结果他说他就是要这个答案,给跪了。。害我想的非常复杂,以为有什么tricky的答案。。
第四轮:.鏈枃鍘熷垱鑷1point3acres璁哄潧
VP面的,同样聊天聊了40分钟,最后10多分钟先是问了level order traversal,不过给的tree不是Binary的,child使用一个list来存的。只需要print不需要返回。但是基本思路反正都一样,这个很快就写完了。follow up: 如果在Queue初始化的时候就要指定分配的内存空间的大小,要怎么给出一个尽量小的值但同时保证得到正确答案。然后就是各种复杂度分析。之后的一个follow up是,如果树的层数非常多,每个node的child也非常多,怎么解决。这个问题想了挺久,还说了各种奇奇怪怪的方法,包括用分布式的计算等等等。。结果说是只能用一台机器。结果是他给我提示了下说如果要输出第10层的所有node要怎么做。有了这个提示就很简单了,对于特定层用限定深度的DFS就行了,所以就逐层DFS就行了。

// 传说中的six degree from glassdoor
Six Degrees of Turkey Bacon You've always been intrigued with the Six Degrees of Kevin Bacon game. Let's say if two actors have been in the same movie we call them 'friends' and if two actors have not been in the same movie, we say they are not 'friends'. Now choose any two actors at random -- we want to calculate the number of degrees of separation and the path between them. How do you go about this problem? • Discuss your algorithm ideas. For each algorithm talk about the tradeoffs. • Choose which method you think is best for solving this problem and describe how it works. You may also want to talk about what data structures you would use to implement it.

祝各位好运吧!!
.鐣欏璁哄潧-涓浜-涓夊垎鍦



补充内容 (2015-3-26 07:11):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
话说现在的面试又有变化了,加上了word ladder II之类的。请大家多多搜集信息,这份帖子仅作参考!

评分

3

查看全部评分

aYao81296 发表于 2015-3-5 06:57:39 | 显示全部楼层
恭喜楼主,谢楼主总结……
回复 支持 反对

使用道具 举报

faye_roll 发表于 2015-3-25 11:13:18 | 显示全部楼层
LZ整理的好详细 给赞一个!!
回复 支持 反对

使用道具 举报

 楼主| Olivier12345 发表于 2015-3-26 07:11:00 | 显示全部楼层
faye_roll 发表于 2015-3-25 11:13. Waral 鍗氬鏈夋洿澶氭枃绔,
LZ整理的好详细 给赞一个!!

不过话说现在有些新面经已经出来了。这份帖子过期了吧。。
回复 支持 反对

使用道具 举报

faye_roll 发表于 2015-3-26 07:32:33 | 显示全部楼层
Olivier12345 发表于 2015-3-26 07:11. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
不过话说现在有些新面经已经出来了。这份帖子过期了吧。。

过期应该不至于吧。。整理的这么详细是得赞一下的。。我后天电面到时候就知道过期没了啦~~~
回复 支持 反对

使用道具 举报

 楼主| Olivier12345 发表于 2015-3-26 10:14:18 | 显示全部楼层
faye_roll 发表于 2015-3-26 07:32
.鐣欏璁哄潧-涓浜-涓夊垎鍦过期应该不至于吧。。整理的这么详细是得赞一下的。。我后天电面到时候就知道过期没了啦~~~

恩,好的,加油!!
回复 支持 反对

使用道具 举报

faye_roll 发表于 2015-3-26 11:42:14 | 显示全部楼层
Olivier12345 发表于 2015-3-26 10:14
恩,好的,加油!!

我现在才发现你是LZ 谢谢!!
回复 支持 反对

使用道具 举报

julia1006 发表于 2015-8-27 00:20:25 | 显示全部楼层
楼主总结的好全~~谢谢楼主~~~
回复 支持 反对

使用道具 举报

chenlei825 发表于 2015-9-25 02:09:43 | 显示全部楼层
谢谢楼主分享!!!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 23:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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