一亩三分地论坛

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

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

LiveRamp第一轮店面

[复制链接] |试试Instant~ |关注本帖
miraclebingo 发表于 2015-4-11 02:51:49 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@LiveRamp - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
LiveRamp他们家广发OA,lz也是看到论坛上很多人发帖才知道这家公司,于是去投了一发,马上收到OA,关于OA的面经论坛上很多人都有,可以搜一下,最关键还是six degree那题,写得越多越详细越好。很多人说他们家广发面试是为了广告效应,也有人拿他们家的面试练手,也看到有人拿到他们家offer的,所以无论如何,好好准备下总是没错的,尤其对lz这种马上毕业还没offer的苦逼。。

刚刚结束了第一轮店面,本来看面经以为会继续问six degree的题,所以充分准备了各种解法的回答。然后看面经大家都被问why liveramp,所以也好好准备了下回答,结果过程完全不是预料的这样的。。上来先叫我介绍自己最得意的project,然后就问了一道题:find the kth largest element in an array 这道题面经里也看到过,我先说了可以sort,但是要nlogn,不好。然后说可以维护一个大小是k的min heap,然后iterate这个array,那大哥接着问如果第一数就是最大的数,放在了top,其他数不就进不来了?我说前k个数拿来initialize min heap,从k+1开始遍历,他说make sense。我以为这样就完了,结果他问还有没有更好的方法,我其实就准备到这里,没想到居然还嫌不够好。然后我说可以用类似quick sort的思路,选一个pivot,找到比它小的放array的left part,完了看看总共有多少数比pivot小,如果k比它小,再go into left part,然后做同样的事。接着问这个方法的average time complexity是多少?然后这个我就不会算了。。。followup问我这个算法和quick sort有什么区别,quick sort为什么是nlogn。。差不多时间就到了让我问了几个问题这样。。。

.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉min heap之后回答质量就降得太快像龙卷风了,目测悲剧,毕竟startup面试感觉有一点答得不好就会被thank you,更何况像他家这样广发OA,然后OA所有人都一样,网上还有答案的。。

不知道有没有人能说下这题有没有更好的解法呢?或者用quick sort的思路big O怎么算?

最后穷人求一点大米,感觉还要在这里水好久
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

补充内容 (2015-4-13 03:21):
周日收到邮件,果然悲剧了

评分

3

查看全部评分

JoeQi 发表于 2015-4-11 03:15:01 | 显示全部楼层
如果楼主在接下来的一两个小时内没收到约二面的通知,就有可能悲剧。

不过楼主答得很好啊。
回复 支持 反对

使用道具 举报

stevenlordiam 发表于 2015-4-11 04:01:03 | 显示全部楼层
请问面试形式怎么样的?skype+google doc么?下周三电面 还只是收到了个预约时间的链接  HR也没有说电话或者skype什么的
回复 支持 反对

使用道具 举报

 楼主| miraclebingo 发表于 2015-4-11 04:47:34 | 显示全部楼层
JoeQi 发表于 2015-4-11 03:15
如果楼主在接下来的一两个小时内没收到约二面的通知,就有可能悲剧。

不过楼主答得很好啊。

多谢!不过已经过了两个小时了,错过黄金时间了。。。
回复 支持 反对

使用道具 举报

 楼主| miraclebingo 发表于 2015-4-11 04:48:31 | 显示全部楼层
stevenlordiam 发表于 2015-4-11 04:01
请问面试形式怎么样的?skype+google doc么?下周三电面 还只是收到了个预约时间的链接  HR也没有说电话或 ...

他们家一面就是电话,也不用写代码,就说思路,问复杂度之类的问题
回复 支持 反对

使用道具 举报

stevenlordiam 发表于 2015-4-11 06:56:31 | 显示全部楼层
miraclebingo 发表于 2015-4-11 04:48
.鏈枃鍘熷垱鑷1point3acres璁哄潧他们家一面就是电话,也不用写代码,就说思路,问复杂度之类的问题

好的 谢谢啦
回复 支持 反对

使用道具 举报

 楼主| miraclebingo 发表于 2015-4-11 07:00:56 | 显示全部楼层

祝好运~字数字数字数
回复 支持 反对

使用道具 举报

chm34 发表于 2015-4-11 10:14:07 | 显示全部楼层
个人觉得quicksort的思路的average complextiy是O(N),因为第一次分割所花时间为n, 第二次大概为n/2,第三次大概为n/4,一共大概有logn次,所以是(1+1/2+1/4+...)*n=2n.  主要是pivot的可能性太多无法保证abs(pivot-k)的值每次都是上次(right-left)的一半,不过这也只能这样假设了。
回复 支持 反对

使用道具 举报

 楼主| miraclebingo 发表于 2015-4-12 13:11:32 | 显示全部楼层
chm34 发表于 2015-4-11 10:14
个人觉得quicksort的思路的average complextiy是O(N),因为第一次分割所花时间为n, 第二次大概为n/2,第三 ...

好有道理!那人就问我的average time complexity,应该是这样的
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-4-13 01:20:17 | 显示全部楼层
我感觉考官最后的时候是希望你向 Selection Algorithm 的方向来回答,时间复杂度 O(n + klogk),如果只找 top k 的话,那么O(klogk) 部分可以省略,直接就是 O(n)
回复 支持 反对

使用道具 举报

 楼主| miraclebingo 发表于 2015-4-13 03:21:19 | 显示全部楼层
干.什么 发表于 2015-4-13 01:20 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我感觉考官最后的时候是希望你向 Selection Algorithm 的方向来回答,时间复杂度 O(n + klogk),如果只找 t ...

嗯,应该是这样的
回复 支持 反对

使用道具 举报

zn88358800 发表于 2015-7-24 23:42:20 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 07:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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