📣 独立日限时特惠: VIP通行证立减$68
回复: 23
跳转到指定楼层
上一主题 下一主题
收起左侧

狗家VO 挂筋

🔗
匿名用户-V2ZUE  2021-2-24 08:58:02 |倒序浏览

2021(1-3月) 码农类General 硕士 全职@google - 猎头 - Onsite  | | Fail | 在职跳槽

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

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

x
面了下狗家,挂了,三轮coding,面筋题我就不说了,地里都有
有一轮遇到了一个没有见过的题目,想了半天还不知道怎么做,大家可以讨论一下。
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
我除了想出了暴力,枚举每个数字的奇偶,想不起其他的办法,而且这种range如何保存,用什么数据结构呢?

评分

参与人数 3大米 +7 收起 理由
yesyzq + 2 很有用的信息!
fififi1323 + 1 给你点个赞!
匿名用户-WAMM4 + 4

查看全部评分


上一篇:胡萝卜MLE面试
下一篇:雨林NG一轮VO面筋(附timeline)
全局:
不知道楼上的都在说啥 把每个前缀和看成一个节点 然后做并查集就好啦

评分

参与人数 3大米 +5 收起 理由
Rieman + 2 给你点个赞!
yulian + 2 给你点个赞!
雨雨人 + 1 赞一个

查看全部评分

回复

使用道具 举报

全局:
楼上说的对 , prefix sum 感觉可以做
回复

使用道具 举报

全局:
Rieman 发表于 2021-3-3 10:01
可以請層主再多說明一下如何使用並查集嗎? 感謝

这个题其实不告诉你每个数或者prefix_sum[i]的奇偶
而每一条 i, j, 奇/偶,
其实告诉你的是prefix_sum[i]之间的相对关系
比如sum(a[i]..a[j]) = 奇数,
其实告诉你的是 prefix_sum[j] - prefix_sum[i-1] = 奇数, which means prefix_sum[j] 和prefix_sum[i-1]不是同奇偶的
所以根据这个就可以每次把prefix_sum[j], prefix_sum[i-1]对应的node放到相同/不同的set里去了(或者产生矛盾)

评分

参与人数 2大米 +4 收起 理由
CSholic + 2 给你点个赞!
Rieman + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
dorisH 2021-2-24 09:06:09 | 只看该作者
全局:
分不够看不了隐藏内容,但是如果是求range sum可以用prefix sum或者segment tree/binary indexed tree?
回复

使用道具 举报

🔗
yulian 2021-2-24 11:05:42 | 只看该作者
全局:
if 2-8 odd  then 9-10 odd
if 2-8 even then 9-10 even
if 9-10 even then 11 odd
if 9-10 odd then 11 even

2-8 odd, 9-10 odd, 11 even => 2-11 is even
or
2-8 even, 9-10 even, 11 odd => 2-11 is odd

所以2-11奇数 偶数都可能啊。


回复

使用道具 举报

🔗
匿名的 2021-2-24 11:35:47 | 只看该作者
全局:
xtt2016 发表于 2021-2-24 10:54
楼上说的对 , prefix sum 感觉可以做

这题不知道N个数字是什么 没法prefix sum吧 而且题目描述有问题 2-11为什么返回false。
回复

使用道具 举报

🔗
clairefig 2021-2-24 11:44:56 | 只看该作者
全局:
如果9 是 1,10 是2, 11 是2, 2是1, 其他数字都是0。这个是符合这三个条件的,楼主你这描述有点迷糊啊。
回复

使用道具 举报

🔗
匿名的 2021-2-24 11:48:13 | 只看该作者
全局:
本帖最后由 匿名的 于 2021-2-24 11:50 编辑

memo[j] 存 i+ (i+1) +...j 的奇偶

如果来了个(a ,b, 奇偶性)对于所有k,memo[a][k],
if k == b return
if k > b, recursive call (b, k)
if k <b, recursive call(k, b)
(回退的时候记得更新memo)
这样一直循环下去应该是可以的 空间O(N^2) 时间最坏N^2 * M M是query个数(这个不是很确定)
回复

使用道具 举报

🔗
fatalme 2021-2-24 13:10:42 | 只看该作者
全局:
本帖最后由 fatalme 于 2021-2-24 13:19 编辑

解方程,高斯消除法解同余方程,最多O(N^3)x9 - x1 = 0
x11 - x9 = 1
x11 - x1 = 0
回复

使用道具 举报

🔗
wx6807 2021-2-24 13:11:19 | 只看该作者
全局:
prefix 奇偶 instead of sum, 可以更简单;
遇到偶数,prefix sum的奇偶性不变,遇到基数,prefix sum的奇偶行就改变。
0 = 1, isEven, false; accumulative/prefix sum isEven, false;
1  = 2, true; false * true = false;
2 = 3, false; false * false = true;
3 = 4, true; true * true = true;

range 1 - 3,  accumulative isEven at 3 -  accumulative isEven at 0 = true - false = false;
return isEven = false, 是奇数
回复

使用道具 举报

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

本版积分规则

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