This week's book giveaway is in the Java 8 forum.
We're giving away four copies of Java 8 in Action and have Raoul-Gabriel Urma, Mario Fusco, and Alan Mycroft on-line!
See this thread for details.
The moose likes Java in General and the fly likes Help: A challenging interview question - about data structure Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Help: A challenging interview question - about data structure" Watch "Help: A challenging interview question - about data structure" New topic
Author

Help: A challenging interview question - about data structure

xie tuo
Greenhorn

Joined: Jan 07, 2005
Posts: 10
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
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
Well, the non-optimized standard normalized form for this would be the following table structure.The super_id holds the ID of the employee's supervisor.

Finding X's supervisor is a single query:Finding X's siblings is also a single query: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
Ranch Hand

Joined: May 31, 2001
Posts: 123
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
Ranch Hand

Joined: Sep 28, 2004
Posts: 1228
Hi we faced the same situation in our last project.

David when we design the Db as


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.


Thanks & regards, Srini
MCP, SCJP-1.4, NCFM (Financial Markets), Oracle 9i - SQL ( 1Z0-007 ), ITIL Certified
Venkatraman Kandaswamy
Ranch Hand

Joined: Jul 07, 2004
Posts: 120
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 ]

--Venkatraman<br />SCJP 1.4<br /><a href="http://kvrlogs.blogspot.com" target="_blank" rel="nofollow">blog</a>
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
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
Greenhorn

Joined: Feb 23, 2005
Posts: 3
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
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Originally posted by David Yen:
One good article is http://www.dbazine.com/tropashko4.shtml


Cool article, thanks!


The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
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
Ranch Hand

Joined: Sep 28, 2004
Posts: 1228
Am I misreading this, or were you the person who interviewed Xie?
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Originally posted by Srinivasa Raghavan:
Am I misreading this, or were you the person who interviewed Xie?


What are you confused about?
David Yen
Greenhorn

Joined: Feb 23, 2005
Posts: 3
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
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
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
Ranch Hand

Joined: Sep 28, 2004
Posts: 1228
So David Yen ,
Can you exactly tell me what answer you expect for this type of question.
David Yen
Greenhorn

Joined: Feb 23, 2005
Posts: 3
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...
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Help: A challenging interview question - about data structure
 
Similar Threads
parsing a graph
Algorithm to find Nodes having largest distance in Binary tree.
Find Binary Tree Height with O(n/2)
Searching a JTree
XML Notes -II