📣 VIP通行证夏日特惠 限时立减$68
回复: 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 b
您好!
本帖隐藏的内容需要积分高于 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 | 只看该作者
全局:
samson1215 发表于 2021-10-17 14:15
思路很棒!感觉很接近了。请问如果是这样的表达式:那么map的内容长什么样呢?

哦,我没考虑变量之间的与或表达,只想了单变量区间的。
多变量因为相当于考虑多维问题,我考虑过kd tree但是那个只能读,不能增删改
我目前的思路:假设每个变量是一个维度,然后树的每层节点代表一维,指针代表对应的区间

你这个式子表示成

A:         [(1,inf), (inf,1)]
              |            |
B:       [(inf,1)]    [(1,inf)]
注意第一层的A是一个节点,两个区间分别对应B的两个节点。也就是A每多一个区间,就要多加一个B的节点,来表示A对应区间内B的有效范围。如过有C的话,B也同理。
两个树合并的时候,如果是或,只要把树里层数最高的节点接上就行。与会很复杂,要逐层merge。
这个复杂度会很高,因为最后一层的节点数是之前所有有效区间的累乘。

我感觉应该有专门的数据结构表示这种东西,我是不太清楚,有知道的求告知哈。

回复

使用道具 举报

推荐
pureklkl 2021-10-17 04:21:08 | 只看该作者
全局:
本帖最后由 pureklkl 于 2021-10-17 04:22 编辑

抛砖引玉:
首先求exp1,exp2有无重叠的部分其实就是求exp1 && exp2,把两个表达式放一起中间直接加个与,然后用开始evaluate expression tree
表达式的结果用map表示,key是变量名,value是list of interval。interval本身表示与,多个interval表示或,比如
(A>3)&&(A<6)表示成(3,6),
(A>3)||(A<6)表示成 [3,inf],[-inf,6]
然后计算与表达式就是经典的算interval intersect,或表达式就直接加进list,可选merge interval 化简。算与的时候检查一下是否重叠部分为空即可。
回复

使用道具 举报

全局:
这道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吧
回复

使用道具 举报

全局:
samson1215 发表于 2021-10-12 11:26:45
如果是简单的二维range求overlap,那是leetcode原题。但没法解决逻辑上的AND、OR吧
他给你的input就是一个expression tree,可以转化成range吧。比如两边expression都是矩形,AND就是求矩形overlap,OR就输出两个矩形
回复

使用道具 举报

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

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

使用道具 举报

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

本版积分规则

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