Re: an old worn interview question

Tegiri Nenashi <TegiriNenashi@xxxxxxxxx> writes:

"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 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?

In traversing a directory, it is useful to be able to detect a
directory loop (caused by symlinks). GNU grep, for example, does
this, as do several other GNU programs (see cycle-check.[ch] in
http://cvs.savannah.gnu.org/viewvc/gnulib/lib/?root=gnulib). I
don't know whether this falls under your qualifiers, but it's
what comes to mind.
--
Ben Pfaff
http://benpfaff.org
.

Relevant Pages

  • Re: Brian Kernighan, maybe Im not worthy, maybe Im scum
    ... and just hone in on the stuff related to programming and this newsroup] ... moron that was taken from optimization which does hoist when to do so ... compiler design and optimization, including my 1976 text in graduate ... loop in a language in which the designers messed up, ...
    (comp.programming)
  • Re: what does "serialization" mean?
    ... language programming and found that my productivity increased to the ... the use of an expression in the For loop is not only ... acceptable it's good style because it forces the reader to understand. ... If the reader doesn't understand the language he must get ...
    (comp.programming)
  • Re: what does "serialization" mean?
    ... the "how" of assembler languages to the "what" of functional and logic ... > As a general programming heuristic, ... For line is inside the loop and one's style should not perpetuate ... one problem is that the concept of "iterator" doesn't ...
    (comp.programming)
  • Re: [EGN] Hoisting Loop Invariants (Was: Re: [EGN] Numerical Accuracy)
    ... outdated language, for manual optimization. ... > such as moving loop invariants outside of loops is not unmaintainable. ... > code might be trivially faster (one of your favorite micro optimizations ... > used programming language on the planet. ...
    (comp.programming)
  • Re: Response to Karen and to Willem on recursive proofs
    ... > Could you give an example of a correctness proof involving recursion? ... // But since it can be seen by inspection of the loop termination condition ... // Recursion in programming is, of course, a subroutine calling itself. ...
    (comp.programming)