Zenefits数据库设计面试题
Database Design 题目
zenefits有很多个部门，是层级结构，比如R&D这个部门下有 software department 部门，而 software department 部门下又有 backend 和 frontend 等等。其中每个部门里有主管，有员工。
请设计数据库表结构来表示这个关系。
学员面试解答
楼主设计了两个Table， 一个表示 department， 一个表示 stuff 其中 department table 中存了 这个部门的上级部门的id，以及子部门 id list， 这样比如下面表示的 R&D 部门没有上级部门，但是有下级部门：software department，然后 software department 的上级是 R&D， 子部门是 frontend、backend
Department Table departmentID, department name, manager id, emloyees, parent id, childrent id ---- 1, R&D, manager_id(123), employee_id_list(124,125), null, children_id_list(2, 3, 4 ...) 2, software department, , (), parent_id(1), children_id_list(3, 4, 5)
3, front end 4, back end
Staff Table id, name, department id, ...
然后面试官问如果这个结构要查 RD 所有部门下的员工怎么办。
楼主这个结构只能先把 RD 下面的所有 department id 遍历出来，然后拿着这个 list 去 stuff table 中找了，貌似不太好啊...
不知道大家有什么想法。
解题思路点拨
系统设计班张无忌老师：
需要考虑的要素包括：
Organization table ID, Name, Level, Father,
Staff Table ID Name, OrganizationID
如果简单来做，可以只记录一个staff所在的最底层的.OrganizationID。此时看似检索一个大的organization可能需要点时间，但是复杂度其实并不会很高，因为公司人数最多几万人，而且我们如果还建立了索引的话，会更快。
如果想加速的话，可以记录一个staff的OrganizationLevels，例如1.2.3，这样检索的时候就很快了
优化解答参考
感觉自己面试的时候答得不好。谢谢张老师点拨。后来又搜了些资料，发现 mongodb 有篇文章给的比较全面：http://docs.mongodb.org/master/tutorial/model-tree-structures/
总共是五种表示法：
1. 在每个部门中记录子部门的信息
2. 在每个部门中记录父部门的信息
3. 在2的基础上，每个部门中除了 parent，还存储一个 array 结构的 ancestors, 记录所有的祖先
4. 和3类似，但是ancestor不用数组结构，而是使用一个string，记录从顶级部门到当前部门的path
5. 用 nested sets, 给每个部门加上两个字段：left 和 right，分别为中序遍历时的先后到达的序列号。
几个方法各有优劣吧。
1 和 2 比较简单，获取当前 父/子节点非常快，但是要获取一个部门下的所有部门，需要多查询。 3 查询节点下所有子部门只需一个查询即可搞定，比如查Programming下的部门，ancestors 字段中有 Programming 即是，缺点嘛，就是添删了节点后，需要更新该节点的所有子节点，复杂度比较高。另外ancestors字段这里是array类型的，mongodb没问题，不过mysql估计就不支持了。 4 和3类似，只是将ancestors字段打平为一个string结构，这样mysql就能支持了，不过查找时需要正则表达式，感觉效率会略有影响。 5 这个方法挺巧妙的，更具体的可以参考：http://qinxuye.me/article/storing-hierachical-data-in-database/ 优点是查询一个部门的所有子节点会非常快，缺点也是增删会比较复杂。
更多实战面试题
更多讨论和面经，请移步九章官网“问答”专区，或点击“阅读原文”。
简介
九章算法,帮助更多中国人找到好工作!
九章算法，团队成员均为硅谷和国内顶尖IT企业工程师。提供算法培训、面试咨询、求职内推。
目前培训的程序员遍布中国、美国、加拿大、澳大利亚、英国、新加坡等12个国家和地区。
目前开设课程有九章算法班、系统设计班、BAT国内班、九章算法强化班。更有Java / ios / C++等即将开课。
更多详情，登录www.jiuzhang.com，或致信info@ninechapter.com.
【Zenefits数据库设计面试题】相关文章：
数据库面试题及答案05-31
数据库常见面试题01-27
Oracle数据库DBA经典面试题02-11
2016年最新数据库面试题02-14
java设计模式面试题06-01
数据库设计论文致谢词04-11
HR如何设计面试题目02-23
iOS开发、设计面试题汇总08-24
数据库课程教学设计心得范文03-31