一亩三分地论坛

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

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

Quora面经-已挂

[复制链接] |试试Instant~ |关注本帖
桃子湖no.1霸 发表于 2016-3-9 12:39:30 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 实习@Quora - 网上海投 - 技术电面 Onsite |Fail其他

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

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

x
面之前发现地里基本没看到Quora的面经。。。可能他家招人真的很少吧(比较公司也就150人左右)因为已经是一个月前面的。。记得已经不是太清楚了。。请见谅. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

电面:
1. Construct Binary Tree from Preorder and Inorder Traversal
2. Merge k Sorted Lists. 鍥磋鎴戜滑@1point 3 acres
都是原题

On site:
一面: 是他家一个自创的面试类型,他们自己叫Practical Interview。。。就是上机实操一个project。。然后改bug,加功能什么的。。
我面的是 elasticsearch
二面:
1. find element in rotated array的变种,输入的数组不保证最右边一定小于最左边
e.g. 6,7,9,1,4,8
2. 一个lc原题。。具体忘了。。
三面:设计题 . 鍥磋鎴戜滑@1point 3 acres
实现一个系统,维护最近一个小时输入数据的平均值

评分

1

查看全部评分

starcroce 发表于 2016-5-10 03:46:34 | 显示全部楼层
handsomecool 发表于 2016-5-10 01:27
lc原题不用pop所以我觉得比较容易,堆里面pop某个值没那么简单吧? logN能pop任意一个node?

不用从堆里pop,只是记录下要pop在哪个堆里,然后更新相应堆的大小和median的偏移量
比如当前最大堆是1,3,5,最小堆是6,8,10。。。这个时候push 4 pop 1,我们知道这个都是发生在最大堆的,所以median不会变,只不过最大堆变成了1,3,4,5,最小堆是6,8,10
但是如果push 7 pop 1,两个堆就会变成1,3,5和6,7,8,10,这时候就需要把6放到最大堆,两个就变成了1,3,5,6和7,8,10
每次有新的push / pop,我们只要知道median是变大一步还是变小一步就好了。。。缺点是时间长了以后堆会很大,这样更新堆的操作会变慢,可能需要定时根据queue来重建两个堆。。。
回复 支持 1 反对 0

使用道具 举报

笑靥嫣然 发表于 2016-5-7 01:47:42 | 显示全部楼层
楼主,可以具体说说那个rotated array么...你给的那个例子不是sorted array的rotate啊
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-9 11:04:23 | 显示全部楼层
最近一小时的平均值是不是就一个普通的queue,记下sum,每次时间更新的时候就从queue的前面减去过时的就好了. 鍥磋鎴戜滑@1point 3 acres
要是median就麻烦了
回复 支持 反对

使用道具 举报

starcroce 发表于 2016-5-9 14:04:50 | 显示全部楼层
handsomecool 发表于 2016-5-9 11:04
最近一小时的平均值是不是就一个普通的queue,记下sum,每次时间更新的时候就从queue的前面减去过时的就好 ...

median的话我能想到的就是类似lc find median from stream,然后用一个queue来确定要pop什么数,同时根据这个数是在当前的最大堆还是最小堆里,决定新的median应该是变大还是变小,这样的话每次取median就还是logn的时间
回复 支持 反对

使用道具 举报

starcroce 发表于 2016-5-9 14:06:40 | 显示全部楼层
笑靥嫣然 发表于 2016-5-7 01:47
楼主,可以具体说说那个rotated array么...你给的那个例子不是sorted array的rotate啊
. more info on 1point3acres.com
感觉按照LZ的例子,这道题只能暴力一个个找了?
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-10 01:27:02 | 显示全部楼层
starcroce 发表于 2016-5-9 14:04
median的话我能想到的就是类似lc find median from stream,然后用一个queue来确定要pop什么数,同时根据 ...

lc原题不用pop所以我觉得比较容易,堆里面pop某个值没那么简单吧? logN能pop任意一个node?
回复 支持 反对

使用道具 举报

笑靥嫣然 发表于 2016-5-10 06:12:39 | 显示全部楼层
starcroce 发表于 2016-5-9 14:06
感觉按照LZ的例子,这道题只能暴力一个个找了?

想了好久....感觉好像只能暴力找....感觉不会到logn
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-5-10 10:28:49 | 显示全部楼层
starcroce 发表于 2016-5-10 03:46. 1point3acres.com/bbs
不用从堆里pop,只是记录下要pop在哪个堆里,然后更新相应堆的大小和median的偏移量. Waral 鍗氬鏈夋洿澶氭枃绔,
比如当前最大堆是1 ...

恩,麻烦点还是可以做的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 13:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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