回复: 12
跳转到指定楼层
上一主题 下一主题
收起左侧

分享一道狗家VO的算法题

全局:

2022(4-6月) 码农类General 硕士 全职@google - 内推 - Onsite  | 🙁 Negative 😣 Hard | Fail | 在职跳槽

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

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

x
上个月面的狗家的VO,有一轮coding没答好所以挂了,不确定这道题刷题网有没有。在此分享一下。


要求是设计一个data structure,需要支持两种操作:
1. insert。就是插入一个integer
2. get
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
x*2这个等式中,如果x不是中位数而是比如10%的percentile怎么办。其实就是bucket sort完之后改一个参数而已。

评分

参与人数 7大米 +11 收起 理由
yuhanqiu + 1 很有用的信息!
bc2615 + 1 给你点个赞!
匿名用户-1K21Z + 5
onerhao + 1 赞一个
AthenaJJ1bZcu + 1 很有用的信息!

查看全部评分


上一篇:亚麻30分钟vo迷惑求教
下一篇:空气床挂经
推荐
 楼主| 狮子对长 2022-7-27 05:17:54 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

评分

参与人数 7大米 +12 收起 理由
bc2615 + 1 给你点个赞!
匿名用户-1K21Z + 5
onerhao + 1 赞一个
14417335 + 1 给你点个赞!
joepass + 1 有用!

查看全部评分

回复

使用道具 举报

全局:
狮子对长 发表于 2022-07-27 20:58:09
2^7和2^8之间的任意一个数都可以。
楼主 还有个问题 如果没有存x的值 如何确定x<=y<=2x? 我们只知道Logx logx+1的值 也就是相邻的两个桶号
回复

使用道具 举报

地里匿名用户
推荐
匿名用户-HQ4PG  2022-8-29 06:37:52
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

🔗
Tristan 2022-7-27 02:12:22 | 只看该作者
全局:
所以意思是用两个heap来找中位数,然后一个sorted list来找log2(median)的后一位,这么理解吗?10%的percentile直接在list里面按size大小去get?那heap岂不是没用了?还是说sorted list直接拿中点就可以得到median?
回复

使用道具 举报

🔗
neverlate 2022-7-27 04:46:13 | 只看该作者
全局:
我的理解:
维护一个list,insert new element之后,再random返回一个中间位置以后的数字?
insert o(n), get o(1)
follow up的insert一样,get先bs到x和x^2的位置,然后rnd取一个数字返回?
回复

使用道具 举报

🔗
joepass 2022-7-27 12:22:10 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

🔗
sillyron 2022-7-27 22:10:21 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

🔗
 楼主| 狮子对长 2022-7-28 11:58:09 | 只看该作者
全局:
joepass 发表于 2022-7-26 21:22
给楼主加米了!请问楼主,这样的话是否就不需要存原来插入的数x了,只需要记录每个bucket的统计数目。那 ...

2^7和2^8之间的任意一个数都可以。
回复

使用道具 举报

全局:
感谢分享

这个思路跟binary indexed tree一样的. 复杂度其实也一样,只不过这里n跟bit里的n定义不一样

数据大小有限制的话,均匀分桶也能解.
回复

使用道具 举报

全局:
onerhao 发表于 2022-07-28 01:38:38
感谢分享

这个思路跟binary indexed tree一样的. 复杂度其实也一样,只不过这里n跟bit里的n定义不一样
如果和indexed tree类似 insert和get就都做不到O(1)了吧?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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