《百姓网公开笔试题:查询条件的子集判断》的一份 PHP 答卷
我的答卷在 http://soulogic.com/subset_test/subset_test.tar.gz
演示地址为 http://soulogic.com/subset_test/
碰到这道题时才意识到自己的见识浅薄,非等到这种题出来才能明白,高等数学对于程序员而言是多么重要。其中最难最关键的部分是在留言里看到了 qmigh 的解释才搞定的。
这道题分三部分:把查询语句转成数组结构,然后把层级混乱的条件最终分解成 以 OR 关联的 AND 合集(也就是 qmigh 所解释的),以及按规则来读取并判断两个数组。在我的代码里,Class TreeStore 负责前两步,Class SetCheck 负责后一步。
由于我完全说不出任何术语,只能把数组的转换过程列一下了。
原始语句
a = 1 AND (b = 1 OR (c = 1 AND (e > 1 OR f = 1)))
第一步,循环用正则,从最里面的括号开始,分解出每一级。这样每一级里面都没括号了
Array
(
[1] => e > 1 OR f = 1
[2] => c = 1 AND _1
[3] => b = 1 OR _2
[4] => a = 1 AND _3
)
按照 AND OR 的优先级进一步分解
Array
(
[AND] => Array
(
[0] => a = 1
[1] => Array
(
[OR] => Array
(
[0] => b = 1
[1] => Array
(
[AND] => Array
(
[0] => c = 1
[1] => Array
(
[OR] => Array
(
[0] => e > 1
[1] => f = 1
)
)
)
)
)
)
)
)
将上述数组最终分解成 OR 下的一堆 AND
Array
(
[OR] => Array
(
[0] => Array
(
[AND] => Array
(
[0] => a = 1
[1] => b = 1
)
)
[1] => Array
(
[AND] => Array
(
[0] => a = 1
[1] => c = 1
[2] => e > 1
)
)
[2] => Array
(
[AND] => Array
(
[0] => a = 1
[1] => c = 1
[2] => f = 1
)
)
)
)
其实就是按 qmigh 说的,做一下转换,把最开始的表达式转换为
(a = 1 AND b = 1) OR (a = 1 AND c = 1 AND e > 1) OR (a = 1 AND c = 1 AND f = 1)
如果只有一个表达式,可以理解为只有一个元素的 AND
如果
(a > 3) AND (b < 4)
可以用数组表示为
array(
[0] => a > 3
[1] => b < 4
)
那么
a > 3
可以用数组表示为
array(
[0] => a > 3
)
OR 也同理
用来判断时的数组样子,也就是 Class TreeStore 的最终输出
Array
(
[0] => Array
(
[a] => Array
(
[=] => Array
(
[1] => 1
)
)
[b] => Array
(
[=] => Array
(
[1] => 1
)
)
)
[1] => Array
(
[a] => Array
(
[=] => Array
(
[1] => 1
)
)
[c] => Array
(
[=] => Array
(
[1] => 1
)
)
[e] => Array
(
[>] => 1
)
)
[2] => Array
(
[a] => Array
(
[=] => Array
(
[1] => 1
)
)
[c] => Array
(
[=] => Array
(
[1] => 1
)
)
[f] => Array
(
[=] => Array
(
[1] => 1
)
)
)
)
至于判断,应该不算难,按照上面的数组挨个字段判断就可以了。以及判断父集合是否有子集合没有的字段,如果有,那肯定不是子集关系了。
写完之后一直没把握到底做的对不对,要是有类似 ACID 2 或者 Man or boy test 那样的东西就好了。如果能有人告诉我有什么复杂条件是我的代码判断不了的,实在感激不尽(当然,用 10MB 长的条件语句搞溢出不算……)
看了看 其他人的答案,“从离散数学到编译原理”,这标题总结得不错,核心也就是这两个问题吧。我用正则来把“编译”那部分绕过去了,但从执行效率上讲是很蠢的。
看来大家都知道画蛇添足的故事,所以都只做了满足要求(“为了简单起见,只需要实现最简单的AND, OR逻辑操作,大于,等于,小于三种比较操作就好”)的最小实现。
如果能有 PHP 同好的题解能相互学习学习那是最好了,其他语言的看不懂 -_-
原来还自诩为程序员,被这道题臊的不行,我现在的定义是,没法独自实现一个 C Compiler 的人充其量也不过是 coding fans。
给自己定下了三年目标:学离散数学、学微积分、学《SICP》
建议继续学习:
- 腾讯-1亿个数据取前1万大的整数-题解答 (阅读:9026)
- 谷歌(Google)2011年校园招聘笔试题 (阅读:8890)
- 你是那10%可以实现二分查找算法的程序员吗? (阅读:6494)
- 15道使用频率极高的基础算法题 (阅读:5580)
- 新浪微博笔试题:找出共有2个以上标签的用户对 (阅读:4952)
- 有道实习生笔试总结 (阅读:4528)
- 2014网易前端开发笔试题笔记 (阅读:3920)
- 百姓网公开笔试题:查询条件的子集判断 (阅读:2566)
- mysql数据库查询优化 (阅读:2535)
- 百姓网公开笔试题结果展示 (阅读:2303)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:Platinum 来源: Soulogic
- 标签: 子集 查询 笔试
- 发布时间:2010-05-11 14:55:02
- [66] Go Reflect 性能
- [66] Oracle MTS模式下 进程地址与会话信
- [65] 如何拿下简短的域名
- [59] IOS安全–浅谈关于IOS加固的几种方法
- [59] android 开发入门
- [59] 图书馆的世界纪录
- [58] 【社会化设计】自我(self)部分――欢迎区
- [53] 视觉调整-设计师 vs. 逻辑
- [47] 界面设计速成
- [47] 读书笔记-壹百度:百度十年千倍的29条法则