一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

码农求职神器Triplebyte
不用海投
内推多家公司面试

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 856|回复: 9
收起左侧

狗家昂赛面经

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (20)
 
 
0% (0)    👎

2019(7-9月) 码农类General 硕士 全职@Google - 猎头 - Onsite  | WaitList | 在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
很紧凑的schedule,一共5轮,4轮技术+1轮Behavioral question

游客,本帖隐藏的内容需要积分高于 180 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

评分

参与人数 6大米 +35 收起 理由
blakesen + 2 给你点个赞!
pudding0129 + 1 赞一个
清道神君 + 25
zorrowei + 3 很有用的信息!
dovedove + 1 赞一个
uestchx1 + 3 很有用的信息!

查看全部评分


上一篇:sam's club technology oa
下一篇:雨林OA
我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (94)
 
 
2% (2)    👎
感谢分享面经!第一轮那个流数据的统计百分位查询好难呀!想了好久,没什么好思路。不知道该题,有哪些假设或已知条件?楼主如何解答的?
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (12)
 
 
0% (0)    👎
zorrowei 发表于 2019/08/20 07:16:12
感谢分享面经!第一轮那个流数据的统计百分位查询好难呀!想了好久,没什么好思路。不知道该题,有哪些假设或已知条件?楼主如何解答的?

感觉上是实现一个数据结构 既有linkedlist的任意插入功能又有array的任意访问的功能 这样插入复杂度是log n percentile是n
回复

使用道具 举报

我的人缘0
zorrowei 2019-8-20 12:30:27 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (94)
 
 
2% (2)    👎
kkchenk 发表于 2019-8-20 09:51
感觉上是实现一个数据结构 既有linkedlist的任意插入功能又有array的任意访问的功能 这样插入复杂度是log ...

这个是流数据,不能全存下来吧?或者流数据通过I/O写入日志,然后二分查找找到对应查询值的最接近的元素,再来判断百分位数?如果这样的话,那么写日志无法达到排序的效果。。。。
回复

使用道具 举报

我的人缘0
jobsjobs 2019-8-20 15:45:17 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (8)
 
 
0% (0)    👎
本帖最后由 jobsjobs 于 2019-8-20 15:47 编辑
zorrowei 发表于 2019-8-20 12:30
这个是流数据,不能全存下来吧?或者流数据通过I/O写入日志,然后二分查找找到对应查询值的最接近的元素 ...

请问你说的数据流I/O日志是什么意思?

我觉得这个题使用一个“平衡二叉搜索树”,每个节点上存储 val 和 n。
n表示这个分支上存储的数字的个数。insert和query都是log(N)

搜索的percentage的时候
if percentage < ( p.left.n / p.n ):
    p = p.left
else:
    p = p.right
插入的时候注意更新所有parent的n=n+1





回复

使用道具 举报

我的人缘0
zorrowei 2019-8-20 22:39:56 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (94)
 
 
2% (2)    👎
jobsjobs 发表于 2019-8-20 15:45
请问你说的数据流I/O日志是什么意思?

我觉得这个题使用一个“平衡二叉搜索树”,每个节点上存储 val  ...

对于单机能够存下来的小数据流,用平衡二叉查找树是个不错的办法,插入和查询都是对数时间复杂度。我开始的假设是:问题规模是分布式的,数据量超级大,以致于单机无法存下来数据流。可能这是本轮的扩展问题。在放🐕搜了下,确实有在流数据里求百分位统计参数的算法,当然这些算法会有小的误差。
回复

使用道具 举报

我的人缘0
zorrowei 2019-8-20 22:41:41 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (94)
 
 
2% (2)    👎
kkchenk 发表于 2019-8-20 09:51
感觉上是实现一个数据结构 既有linkedlist的任意插入功能又有array的任意访问的功能 这样插入复杂度是log ...

对于单机能够存下来的小数据流,平衡二叉查找树是个好的数据结构来解决这个问题。插入和查询都是对数时间复杂度。
回复

使用道具 举报

我的人缘0
Wyf2222 2019-8-21 03:03:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (27)
 
 
3% (1)    👎
zorrowei 发表于 2019-8-20 22:41
对于单机能够存下来的小数据流,平衡二叉查找树是个好的数据结构来解决这个问题。插入和查询都是对数时间 ...

请教一下具体是哪种实现的平衡bst呢 ?
因为如果是一般的AVL tree的话, 只能保证左右高度差,并不能准确知道node数目差,所以查找的复杂度还是降不下来把
回复

使用道具 举报

我的人缘0
workworkhard 2019-8-22 14:25:53 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
求问楼主有几年工作经验呀 感觉题目都不是很简单呀
回复

使用道具 举报

我的人缘0
shzhj 2019-8-23 07:13:26 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (44)
 
 
2% (1)    👎
第一题如果input都是price的话,虽然是float我们只要精度到0.01就够了吧
然后price的话可能有个range (比如¥0 - ¥1000000)
这样的话内存里开一个 100 * range size的array就可以count所有的price了
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

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

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

手机版||一亩三分地

GMT+8, 2019-9-18 07:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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