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

微软09/12/2019新鲜店面

全局:

2019(7-9月) 码农类General 硕士 全职@microsoft - 内推 - 技术电面  | | WaitList | 在职跳槽

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

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

x
硬度人。给一棵BST和一个range,要
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies


求大米!

评分

参与人数 5大米 +18 收起 理由
cindémon + 1 赞一个
紫衣云梦小怪兽 + 10
financeFree + 3 很有用的信息!
滚动的西瓜 + 3 很有用的信息!
tommyjiang + 1 很有用的信息!

查看全部评分


上一篇:2020 GS Hirevue 面经
下一篇:Akuna 18年OA以及一些面经onsite整理
推荐
yeehaah 2019-9-13 23:08:04 | 只看该作者
全局:
celiax2y5 发表于 2019-9-13 17:51
bst 用inorder traversal写到一个vector里面,每次看这个vector里在这个range的数?

同意。 表示因为是sorted, 后面可以用binary search来查找range index, 左右index相减加一就是答案
回复

使用道具 举报

推荐
zichen.wang 2019-9-14 05:00:15 | 只看该作者
全局:
这是splay的基本操作,把比左端点小的第一个结点旋转到根,把比右端点大的第一个结点旋转到根的右儿子,然后根的右儿子的左子树的 size 就是答案,如果树是平衡的,复杂度就是 O(log N)
回复

使用道具 举报

推荐
 楼主| xm2yz 2019-9-15 01:14:29 | 只看该作者
全局:
jjjjjia11 发表于 2019-9-13 14:57
你有什么思路?我想的是用hash_map存下来比一个range小的有多少个数字,query的时候直接return?

这个恐怕不好做,range边界不一定是节点中数值
回复

使用道具 举报

🔗
jjjjjia11 2019-9-13 14:57:29 | 只看该作者
全局:
你有什么思路?我想的是用hash_map存下来比一个range小的有多少个数字,query的时候直接return?
回复

使用道具 举报

🔗
celiax2y5 2019-9-13 17:51:51 | 只看该作者
全局:
bst 用inorder traversal写到一个vector里面,每次看这个vector里在这个range的数?
回复

使用道具 举报

全局:
jjjjjia11 发表于 2019/09/13 14:57:29
你有什么思路?我想的是用hash_map存下来比一个range小的有多少个数字,query的时候直接return?

可以每个节点存比他小的节点的个数 然后一个range就按照左右两端去个查询一次 两者相减得到range里的数
回复

使用道具 举报

全局:
For follow up: 为何不建一个segment tree存range
回复

使用道具 举报

🔗
tommyjiang 2019-9-14 00:04:55 | 只看该作者
本楼:
全局:
感谢分享!
回复

使用道具 举报

🔗
逸何 2019-9-14 02:34:05 | 只看该作者
全局:
请问楼主是内推new grad吗?
回复

使用道具 举报

🔗
cuisine 2019-9-14 05:39:36 | 只看该作者
全局:
所以followup是怎么解决的呢?
回复

使用道具 举报

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

本版积分规则

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