Re: an old worn interview question

On Sep 17, 3:00 pm, user923005 <dcor...@xxxxxxxxx> wrote:
A typical problem is a database of workers and supervisors. All
employees are kept in a single table, where employees of supervisors
are identified with a 'works_for' field. I guess you can imagine how
easily loops can arise.

A proper algorithm will identify the loops and draw an org chart, with
defects spelled out in some way. You can even do the identification
phase purely in SQL if you use a temp table.

If your organizational chart is a tree, then why do you represent it
as a DAG? You can leverage nested sets, therefore automatically
enforcing tree constraint.

OK, even if you represent the tree as a graph, then you can just query
the number of connected components in the graph. A connected graph as
a graph that has a single connected component. Next, a connected graph
with N nodes and N-1 edges must be a tree. Thus, counting nodes and
edges together with transitive closure is a way to enforce tree
constraint.

And, finally, one of the "advanced" techniques that I recall from my
interview many years ago was initiating two pointer with different
speeds and watching when one pointer reaches the other. One may wonder
how this solution might be helpful in SQL world.

.

Relevant Pages

  • Re: Is There a Java Class for this Kind of Data Structure?
    ... I was looking into a tree because I thought that would be the easiest ... directed graph. ... and you iterate over the queue until it's empty (meaning ...
    (comp.lang.java.programmer)
  • Re: Two Steps Forward One Step Back Re: Newbie list traversal
    ... >> Why don't you build a graph from your list before generating the DOT ... In you case, it looks like you're considering LISTs to be the nodes, ... To take the example of your *linear* tree: ... you'll notice that the DOT file can be written ...
    (comp.lang.lisp)
  • Re: Relationship Tables...too many
    ... multiple pages, in my opinion, so you can isolate trees or tree groups ... any table to any other table in the relatinship graph. ... is to add even more table occurrences. ... The Contact anchor table might have related TOs of SalesOrder, ...
    (comp.databases.filemaker)
  • Re: Organizations with two or more Managers
    ... If your graph happens to be a tree, ... boyd would contrast that with the blitzkrieg and guderian's directive ... there are going to be mistakes. ...
    (microsoft.public.sqlserver.programming)
  • Re: Next Generation of Language
    ... |>> algorithms are graph based and have to search a tree. ... |>> graph algorithms are inherently unparallelizable. ... | over any number of cores (supposing one doesn't care about exact DFS ...
    (comp.lang.lisp)