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

🐶 VO 想不太出来的一道题 请教各位

全局:

2021(10-12月) 码农类General 硕士 全职@google - 内推 - 在线笔试  | 😐 Neutral 😣 Hard | Fail | 在职跳槽

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

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

x
大家好,这道题是我朋友onsite的时候遇到的,代他发出来,想请教一下各位算法大佬有什么好的思路。

给两个logic expression,实现一个bool findOverlap(Expression ex1, Expression ex2)函数,判断两个expression是否有重叠部分。
Expression中包含OR,AND,括号的operator。
example:
exp1: foo > 1 AND bar < 3
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
onList(Operator op) 返回除去op后的sub expression list。

也可以随意assume一些library(比如Range,Overlap等)。关键是算法部分。

如果大家有好的想法欢迎讨论。

评分

参与人数 2大米 +7 收起 理由
地里的生活菌 + 6 给你点个赞!
分割冬季 + 1 赞一个

查看全部评分


上一篇:微软不招OPT不到一年的Candidate了?
下一篇:吴波店面
推荐
juyoujing 2021-10-12 15:05:24 | 只看该作者
全局:
如果只有一个变量的话,那一个expression可以转化成几个线段/射线,整个题目可以转化成求两组线段之间有没有overlap
两个变量的话,就是求两组矩形直接overlap
更多变量的话就是更高维度的overlap了。。
回复

使用道具 举报

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

使用道具 举报

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

使用道具 举报

全局:
这道onsite...可以的....
回复

使用道具 举报

🔗
daydream1 2021-10-12 12:33:56 | 只看该作者
全局:
暴力,根据Restriction枚举出所有可能的values,所有组合全部试一遍
回复

使用道具 举报

🔗
daydream1 2021-10-12 12:38:51 | 只看该作者
全局:
重叠指的是赋值以后,两个expressions的结果都是True吗?
回复

使用道具 举报

🔗
 楼主| samson1215 2021-10-12 13:04:29 来自APP | 只看该作者
全局:
daydream1 发表于 2021-10-11 21:38:51
重叠指的是赋值以后,两个expressions的结果都是True吗?
是的 针对某些赋值 两个expression都为true
回复

使用道具 举报

🔗
 楼主| samson1215 2021-10-13 02:25:10 | 只看该作者
全局:
daydream1 发表于 2021-10-11 21:33
暴力,根据Restriction枚举出所有可能的values,所有组合全部试一遍

确实是个思路,怎么枚举所有可能value呢?根据每个range的边界赋两边的值?
回复

使用道具 举报

🔗
 楼主| samson1215 2021-10-13 02:26:45 | 只看该作者
全局:
juyoujing 发表于 2021-10-12 00:05
如果只有一个变量的话,那一个expression可以转化成几个线段/射线,整个题目可以转化成求两组线段之间有没 ...

如果是简单的二维range求overlap,那是leetcode原题。但没法解决逻辑上的AND、OR吧
回复

使用道具 举报

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

使用道具 举报

🔗
 楼主| samson1215 2021-10-13 05:28:16 | 只看该作者
全局:
stupidtag 发表于 2021-10-12 14:19
他给你的input就是一个expression tree,可以转化成range吧。比如两边expression都是矩形,AND就是求矩形o ...

明白你的意思了,确实是个好思路。但是如果维度多了的话,好像就不容易解决了
回复

使用道具 举报

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

本版积分规则

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