Archive for July, 2006

Finding or detecting a loop/cycle in Link List.

July 27, 2006 1 comment

One of famous questions asked in programming technical interviews is “Finding a loop in a linear linked list”. Apparently this problem is easy, but if one has interest in Algorithms and Complexity Theory this is a very interesting problem also related to number theory.

The most famous method to solve this problem is to use Floyd’s algorithm to find cycle in lists also known as “The Hare and the Tortoise Algorithm”, intersting :). If a list has a cycle in it, it can be detected using this algorithm. This algorithm can also be used to find cycles in “Pseudo-Random Sequences”. The algorithm to find the cycle in linked list is as follows.

Take two pointers pointing to head. Now advance one pointer to one node and other pointer to two nodes each time while iterating. This is the simple algorithm, and that’s it. If the first pointer enters the loop (cycle part of algorithm) it is guaranteed that the second pointer will be at some node in the loop at the same time when other pointer is pointing to same node. The result may come out by some iteration, but it’s assured. That’s because one pointer is iterating each node in loop and other is iterating alternating nodes, so at first or second iteration while in the loop it will catch the first pointer at same node. This is indeed a very good find. I tried this with moving the second pointer to three nodes at one time and it worked also though I had to iterate many times. By using this approach we can also find the number of nodes in the loop which is an interesting thing to try.


Managed C++ – C++/CLI

July 25, 2006 1 comment

I am working on an interesting image processing and recognition project here in my office and it is a very wonderful work experience. Out of many things I have learnt, the most valuable thing is experience with Managed C++ (C++ for CLI). I have to write some core functionality classes and wrapper dll’s on calling Viisage SDK’s APIs which are written in native C++. To include these header files along with source code I had no other choice than to choose Visual C++.NET. In start I faced a lot of problems in dealing with managed and unmanaged code, conversion of native types to MS.NET types and vice versa and other issues of native C++. With time, extensive effort and lot of search now I am at ease with doing any thing in Managed C++ that I can do in C#. I will be writing some most valuable APIs that were no less than a blessing for me used in conversion of native to managed, managed to unmanaged code and other issues of handling .NET things in C++ the C++ way.

P.S: Having power of native C++ and Microsoft.NET in same language is beautiful.

My Google Interviews.

July 6, 2006 3 comments

In March and April 2006 I had good fortune to talk with Google Inc.’s folks and gave them phone interviews. I will soon write the synopsis of interviews as I have been planning to do so from a long time. I actually talked with a recruiter, had one pre-phone interview screen and 2 phone screens from USA and India. So I will write my experience with Google soon. Stay tuned.

Categories: Computer Science, General