Help: A challenging interview question - about data structure

[xie tuo]

During the interview I was asked a question:

Suppose a human resource department has to manage, say, 30,000 employees. The relationship we care about is only supervising and supervised. From this relationship, we can define a tree structure.


According to this image, we could say 1 supervise 2 and 3, 2 supervise 4, 5 and 6.

Since this is a big tree, we have to put it into a database.

The question: how to design your table, so that:
1) given an employee X, we could quickly find X's supervisor;
2) given an employee X, we could quickly find all X's sibling (the same level manager)
3) given an employee X, we could quickly find all X's supervisors, that is the path from the root to X.

Here is my answer:
-------------------------------------------------------------------
My table structure is like the following:

ID Hierarchy
1.1.
2.1.2.
3.1.3.
4.1.2.4.
5.1.2.5.
6.1.2.6.
7.1.3.7.
8.1.2.6.8.

Hierarchy = (Hierarchy of Parent) + this.ID + �.�
The point is to save each node�s hierarchy information in the table.

Thus, to get P�s children: find all nodes that has hierarchy starts with (Hierarchy of P).

To get all sibling of N: get N�s parent�s hierarchy H first, then find all nodes whose hierarchy starts with H.

To get the path of a node N: N�s hierarchy is N�s path.
--------------------------------------------------------------------------

The comment from the interviewer towards my answer:

Not efficient, cannot handle addition and removal of nodes efficiently. Say, I want to reorganize my company, and get rid of the middle management that is redundant. Therefore, direct reports of those that are laid off have to report to a new manager.

The interviewer said there definitly should be another well-known optimized solution to this question, and give me several hours to figure it out, no matter I ask somebody or google it. So I come here. Wish somebody can help me!

By the way, during the interview process, he gave me a hint: map the tree node to element of an array. I do not know if this hint is useful or misleading.

Thanks!

[David Harkness]

Well, the non-optimized standard normalized form for this would be the following table structure.

table emp
(
  emp_id
  super_id
  name
  ...
)

The super_id holds the ID of the employee's supervisor.

Finding X's supervisor is a single query:

select s.* 
from emp e, emp s
where e.emp_id = X
  and e.super_id = s.emp_id

Finding X's siblings is also a single query:

select s.* 
from emp e, emp s
where e.emp_id = X
  and e.super_id = s.super_id

Note that this also returns employee X but could be changed slightly to omit X.

Getting the chain of command above an employee is where this breaks down. You need to do a separate query to obtain each supervisor up the chain. Oracle has a special type of operation to perform this exact logic, but I've never used it.

The hint the interviewer gave tells me nothing new. All tables can be viewed as an array with each row being an element in the array. Maybe it will mean something to some other Rancher.

[Julia Reynolds]

Xie,

I think by saying "Node" the interviewer was giving you a clue to
talk about the LinkedList data structure in Java. Here is a good
explanation:

http://www.javacoffeebreak.com/books/extracts/javanotesv3/c11/s2.html

Julia

[Srinivasa Raghavan]

Hi we faced the same situation in our last project.

David when we design the Db as

  
table emp(  emp_id  super_id  name  ...)

We faced lots of problems since the employee Id & his / her supervisors id are in the same table. As a example wehn an employee gets transferred from one location or one center to other it was difficult to handle.

So we designed a table structure like the one below.


table USER_TYPE_REF ( USER_TYPE, MANAGER_TYPE );

The above tabl eis like a reference table holding the the possible user types like programmer, Manager, CTO etc .. Manager_type holds the immediate supervisor type. This way makes things configurable.

table USER_DET ( Name,Addr,UserType, other personal stuff );

The above table holds the user personal stuff.

table USER_Allocation_Det ( EmpNo, DeptNo, ProjectNo, fromDate,ToDate some other allocation details );

The above is the key table that holds the current & the past allocation status. This table can be used to get the Employees working under a supervisor. This table will have entries for both supervisor & normal employees so by using the usrtype & MgrType Employees working under a supervisor can be found. i.e Use a Join and get the datas from the above tables.

[Venkatraman Kandaswamy]

How about this ??

2 tables

Table 1 : Employee table ( empid, name, desig,depth )
Table 2 : Relations table ( manager_empid1, unluckysoul_empid2 )

1) given an employee X, we could quickly find X's supervisor;

trivial.

2) given an employee X, we could quickly find all X's sibling (the same level manager)

use depth to find all the managers at that manager's depth

3) given an employee X, we could quickly find all X's supervisors, that is the path from the root to X.

i dont think its possible to write a query to accomplish this - even with nested queries - need the support of a high level language to iterate.

The advantage of this solution - want to remove all middle level managers of depth n ? In relations table find all the managers with depth n, get the corresponding unlucky souls and update them with this manager's manager. Then delete all instances of this manager in relations table.

Good luck on your interview !!
[ February 22, 2005: Message edited by: Venkatraman Kandaswamy ]

[David Harkness]

Srinivasa and Venkatraman, that's all very good, but remember that this was a very specific interview question about modeling a tree structure that can support three queries. It assumed a one-to-many relationship between supervisor and employee, didn't need configurable employee types, and definitely said nothing about tracking historical values.

Can you think of other ways to solve the interview question? Your ideas would be great for a real application, but sometimes it's helpful to perform design under constraints to flex your modeling muscles.

Keep in mind that it can be quite difficult to design interview questions that cover real-world scenarios and yet allow the interviewee to answer in under five hours.

[David Yen]

When interviewees are permitted to go home, ask anybody any question, search on the Internet for answers, read any books they want; questions are supposed to be real-life problems. Interviewees may not find out the optimal solution; but if they show they know how to approach a problem when they get stuck, they are considered to be fairly good candidates. I believe it is more realistic to evaluate candidates by giving them all freedom they want and all resources available. Besides, I like creative interviews.

There are plenty of resources online on this topic. One good article is http://www.dbazine.com/tropashko4.shtml, which you may obtain by using "trees in sql" as search words.

Just to add that the hint was misunderstood. Perhaps I had not been too clear during the interview.

Just took the comma out from the URL... Thanks, Ernest.

[ EJFH: Fixed URL ]

[ February 23, 2005: Message edited by: David Yen ]

[ February 23, 2005: Message edited by: Ernest Friedman-Hill ]
[ February 23, 2005: Message edited by: David Yen ]

[Ilja Preuss]

Originally posted by David Yen:
One good article is http://www.dbazine.com/tropashko4.shtml

Cool article, thanks!

[David Harkness]

Originally posted by David Yen:
When interviewees are permitted to go home, ask anybody any question, search on the Internet for answers, read any books they want; questions are supposed to be real-life problems.

Agreed, but it was my impression that this question was asked, answered, and evaluated all in one sitting.

Just to add that the hint was misunderstood. Perhaps I had not been too clear during the interview.

Am I misreading this, or were you the person who interviewed Xie?

[Srinivasa Raghavan]

Am I misreading this, or were you the person who interviewed Xie?

[Ilja Preuss]

Originally posted by Srinivasa Raghavan:
Am I misreading this, or were you the person who interviewed Xie?

What are you confused about?

[David Yen]

David Harkness and Srinivasa Raghavan, I strongly believe that you are reading it correctly. I was the one who gave Xie this problem.

This problem will be deprecated from my problem library, as I realize that there are so many resources online on this topic today, compared to what was available two years ago. It was a very interesting problem.

The ability to figure out good keywords is indeed and still an art. We need to turn it into science one day.
[ February 24, 2005: Message edited by: David Yen ]

[Ilja Preuss]

Originally posted by David Yen:
I was the one who gave Xie this problem.

Welcome at the Ranch!

The ability to figure out good keywords is indeed and still an art. We need to turn it into science one day.

Isn't science an art, too?

[Srinivasa Raghavan]

So David Yen ,
Can you exactly tell me what answer you expect for this type of question.

[David Yen]

It all depends. Difficulty of the problem, background of the candidates, nature and function of the position open, just to name a few. In general, a complete solution would be ideal. Otherwise, I wish to see some flexibility and creativity in his approach to the problem. And, usually, I ask much more than one question. That's as much as I can tell. Can't let out too much of my secret sauce...