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

大家好，这道题是我朋友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等）。关键是算法部分。

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

如果只有一个变量的话，那一个expression可以转化成几个线段/射线，整个题目可以转化成求两组线段之间有没有overlap
两个变量的话，就是求两组矩形直接overlap
更多变量的话就是更高维度的overlap了。。

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。
这个复杂度会很高，因为最后一层的节点数是之前所有有效区间的累乘。

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

抛砖引玉：
首先求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...可以的....

暴力，根据Restriction枚举出所有可能的values，所有组合全部试一遍

重叠指的是赋值以后，两个expressions的结果都是True吗？

daydream1 发表于 2021-10-11 21:38:51
重叠指的是赋值以后，两个expressions的结果都是True吗？

是的 针对某些赋值 两个expression都为true

daydream1 发表于 2021-10-11 21:33
暴力，根据Restriction枚举出所有可能的values，所有组合全部试一遍

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

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就输出两个矩形

stupidtag 发表于 2021-10-12 14:19
他给你的input就是一个expression tree，可以转化成range吧。比如两边expression都是矩形，AND就是求矩形o ...

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