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

爱彼迎电面遇到较难题

🔗
匿名用户-TWOTM  2021-5-27 09:37:14 |倒序浏览

2021(4-6月) 码农类General 博士 全职@airbnb - 内推 - 技术电面  | | Other | 在职跳槽

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

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

x
上周面的。
题目如下:
输入正整数N,表示有N个灯泡排成一列,每个灯泡可以亮可以灭,初始假设全灭。
要求实现两个操作:
1. toggle(a, b), 0 <= a <= b <= N-1
表示将第a个
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
一定会出面经题。放上来提醒大家还是要尽量全面复习,像我虽然复习了线段树现场也写完了,但是忘记了lazy update仍然失败了,大家要引以为戒。


评分

参与人数 3大米 +10 收起 理由
ahenry015 + 1 给你点个赞!
匿名用户-C0IBX + 8
ND0406 + 1 赞一个

查看全部评分


上一篇:硬币基地店面(包含问题特殊要求)
下一篇:开花堡 店面 挂经
推荐
zhmingrui 2021-5-28 23:54:06 | 只看该作者
全局:
拍脑袋想Segment tree和Fenwick tree都超纲了。
可以用平衡树。一个记录起点,一个记录终点。插入log(n)复杂度。
在平衡树结点上维护大于或小于本结点的计数,就可以log(n)复杂度查询有多少段已经开始还没有结束。通过奇偶判断这个灯的状态。
不过平衡树当场基本写不出来,估计写个二叉树,解释下就可以了。
回复

使用道具 举报

地里匿名用户
推荐
匿名用户-YI5ZG  2021-8-27 03:47:47
ND0406 发表于 2021-5-30 06:39
你这个On是每个query都是On update O1
换句话说 query是N 就成了n平方了 肯定是不对的

能讲讲是lc 哪题吗? 怎么用BIT 实现的思路呢? 怎么做range update 在logN?
回复

使用道具 举报

推荐
hjp709394 2022-10-19 14:30:09 | 只看该作者
全局:
lazy tag的线段树感觉还是可以handle的,区间BIT我觉得就有点太取巧了。。。
回复

使用道具 举报

🔗
ND0406 2021-5-27 09:48:06 来自APP | 只看该作者
全局:
lc的原题吧…
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-TWOTM  2021-5-27 09:52:25

求题号?
回复

使用道具 举报

🔗
xueraijier 2021-5-27 12:11:43 | 只看该作者
本楼:
全局:
天啊
回复

使用道具 举报

全局:
扫描线可以做不?
回复

使用道具 举报

全局:
扫描线,起点+1,终点-1,然后重新扫一遍过去,遇到奇数是1偶数是0,On解决
回复

使用道具 举报

🔗
ND0406 2021-5-30 06:37:57 来自APP | 只看该作者
全局:
抱歉回复完了。
就是BIT的题。
每次update是 2个logn
求具体某个点的时候是一个logn
你等我给你找下类似的…这题我太有印象了…
回复

使用道具 举报

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

使用道具 举报

地里匿名用户
🔗
匿名用户-CGARI  2021-6-2 06:05:17
区间操作变成点操作然后使用树状数组的题。出这个题coding有点过分。

回复

使用道具 举报

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

本版积分规则

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