LiveRamp 准备

作者 QIFAN 日期 2017-04-23
LiveRamp 准备

已挂


OA

两道 coding ,地里的题目一道都没有出现。作文题常规,解释上一道题 + why excited in LiveRamp 。

第一题

小红有很多糖,什么种类的都有,小明也想要。本着分享的原则,小红要给小明一半。小红只有一个要求,尝到尽可能种类多的糖,就是说希望自己剩下的糖的种类能尽可能的多。要求时间空间复杂度都是 $O(N)$ 。假设糖总数为偶数。

先生成一个 candyMap 记录所有糖果的个数。然后遍历 candyMap ,假设每种糖都只剩下一颗,其他都给掉,当给出去的糖果是 half ,那就退出遍历。退出遍历后看给出去的糖果是不是 half ,如果是那 candyMap 的大小就是结果。如果给出去的糖果数量还小于 half ,那 candyMap 的大小减去差值就是结果。

时间 $O(N)$ ,空间 $O(N)$

第二题

每个旅行社都有固定的行程,第一天到第 N 天的行程都已经安排好了。这些行程可能会包含重复的景点,小黑的时间很宝贵,他想要在尽可能少的时间里把旅行社所有能逛的经典都逛完。比如说给定行程:

A[0] = 1
A[1] = 4
A[2] = 2
A[3] = 4
A[4] = 3
A[5] = 1

A[0] = 1 表示第 0 天去逛景点 1 。这个行程一共要 6 天包含景点 1, 2, 3, 4。按照小黑的要求,如果从第 2 天开始第 5 天结束,他也能逛完所有的景点。所以最短时间为 4 。

先遍历一遍得知一共可能的景点数 N,然后建立一个 map 开始记录已逛的景点与次数。开始旅程,记下旅程开始日 start = 0 。每当进入新的一天,
a) 将景点加入 map ,
b) 查看当前 start 是否存在于 map 且值大于 1 ,如果是,则说明第一天不逛也可以逛到那天的景点,start++ ,map 中 start 对应的值减一。重复 b 步骤直到 start 的对应值为 1 ,说明只有在开始日逛了这个景点。
c) 当 map.size() == N 说明当前已经逛了所有的景点,记下使用的天数并在下次 map.size() == N 时的天数比较
d) 行程遍历结束后,返回最小使用天数。

后来想了一个优化就是不用多遍历一遍去拿总景点数,只要修改 c 步骤条件使之记下更多景点数时的天数。

时间复杂度 $O(N)$ ,空间复杂度 $O(N)$ 。

电面

一个在 LiveRamp 工作了四年的 engineer ,听他自己说管着好几个 team 。

上来先唠嗑,问你有什么觉得特别重要的事情,general 层面。
然后聊一聊最自豪的项目,没有细问(大概是没什么兴趣吧)
接着抛出一个实际问题:每次用户点击都会生成一条 log 记录,包括 timestamp,user agent 信息,ip 等等,没有 user id ,这些 log 都存在本地文件,问给一个文件,如何判断 unique user 数量。一开始我以为是有 user id 的,当成了一个 hashmap 问题,应该是从这里开始就跪了。其实这个就是 LiveRamp 自己干的事情,把网上的 log 归类,map 到线下的用户。这个主要的问题应该是 how to define a unique user 。我花了十分钟讲了怎么快速弄 map 然后才被打断说意思理解错了,自己的表达能力实在欠缺。接着面试官转换了方向,说如果把一个 browser 当成 user id ,应该怎么知道 unique user 数量,这不是就回到了我刚开始想的那样?所以在这二十分钟里我也挺懵的。
最后问问题,想着铁定跪了,就聊天问他们为啥发了这么多 OA 但是拿到 offer 的人这么少,惊讶的是 LiveRamp 其实规模挺小的,但每个月竟然有上千个 application 。面试官也说他们也十分不喜欢花这么多时间面试但是好多是无效的(然后我也是其中的一个无效面试),但是更希望公司能够 grow steady ,同时暗暗黑了一下 uber 。然后又问他 LiveRamp 到底的业务是怎么样的,用例子说就是你在超市买了一个苹果,结果隔天可以收到推销苹果的邮件,叫做 data connecting ,还是很有趣的,没有进行下一步也很遗憾。