Re: an old worn interview question

On Sep 17, 3:09 pm, Tegiri Nenashi <TegiriNena...@xxxxxxxxx> wrote:
"given a graph of pointers, can you find a loop there"

I must admit that during 20 or so years of programming I never came
across any practical program that required finding a loop in the
directed graph.

I have had to do it many times.

I suspect that finding a loop is really a part of
bigger task such as finding transitive closure of a graph. And the
tricks of finding a single loop provide no insight how to solve bigger
problem. So, any counter examples of an interesting problem, or an
algorithm that requires finding a single loop in the graph?

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.


.

Relevant Pages

  • Re: an old worn interview question
    ... I suppose Oracle could implement this in a cheesy fashion: ... the size of the graph, ... I doubt hierarchical query loop detection is possible. ...
    (comp.programming)
  • Re: efficiently accumulating values
    ... (defun find-words (graph) ... "Given GRAPH find all possible words." ... do (loop as word in (get-words graph i j) ...
    (comp.lang.lisp)
  • Re: efficiently accumulating values
    ... Here is the lisp I wrote when I fisrt came with my questions. ... (loop as line = (read-line stream nil nil) ... (defun find-words (graph) ... "Given GRAPH find all possible words." ...
    (comp.lang.lisp)
  • Re: efficiently accumulating values
    ... do (loop as j from 0 to (1- n) ... (setf result gotten-words)) ... NCONCING accumulation clause: ... "Given GRAPH find all possible words." ...
    (comp.lang.lisp)
  • Re: an old worn interview question
    ... across any practical program that required finding a loop in the ... bigger task such as finding transitive closure of a graph. ...
    (comp.programming)