Archive

Archive for the ‘Algorithms’ Category

Top 10 Traits of a Rockstar Software Engineer

March 25, 2009 Leave a comment

I came across this excellent post on ReadWriteWeb about 10 traits of a Rockstar Software Engineer and I could not agree more. In 10 traits every thing about a software engineer is sufficed. It is a true analysis of what a software engineer must equip of. The traits are,

  1. Loves To Code
  2. Gets Things Done
  3. Continuously Refactors Code
  4. Uses Design Patterns
  5. Writes Tests
  6. Leverages Existing Code
  7. Focuses on Usability
  8. Writes Maintainable Code
  9. Can Code in Any Language
  10. Knows Basic Computer Science

Read them, analyze them and if you are a software engineer find how many you have from these. For more details read the complete post with description of each trait at here.

Find the complexity of code.

October 29, 2008 16 comments

I came across measuring complexity of a piece of code, which is really tricky one. Following is the code,

void function( int n)
{
while(n > 1)
n = sqrt (n); // assume sqrt returns square root of any number and ignore the complexity of square root
}

If any one wants to try this do try 🙂 and post your answers.

Just Another Programming Puzzle (Finding one non repeating element in list of pairs)

March 12, 2008 15 comments

So here is a programming question once again,

Consider a list of unsorted positive numbers in which each number has a pair except one of the number, the problem is to find that number in minimum complexity with O(1) extra space. The complexity in this case should not be more than O(n).

For instance, in the list {5,7,4,9,5,7,4} the answer should be 9. I will post my solution in the comments some time later.

Try your coding skills !

January 14, 2008 12 comments

Here is a small C/C++ code snippet,

int n = 20;

for( int i = 0; i < n ; i—) // i minus minus(in case of typo)

printf(“Hello World!”) ;

First try to find the answer to this program. It will obviously be an infinite loop or memory over flow or …

The question is to make this snippet work and print the “Hello World!” 20 times correctly as if the statement i— would have been i++.

The restriction however is to change only one ASCII character in this code. This means you can change, replace, move, introduce only one character to this program and the program still remains a valid C/C++ code.

There are three possible ways I know to do this. May be there are more. If you find two then you are good, if three you are brilliant and if more than extraordinary 😉

Have happy time solving this.

Measuring Complexity of an Executable!

December 31, 2007 4 comments

For the time being, I have an interesting question to share rather ask 🙂

When ever we do the Asymptotic Analysis, we are given the source code or algorithm of a problem and we measure the run time complexity in terms of Big O, Big Omega etc…by doing the line to line analysis of the code.

Now the question is, lets say we are given an executable containing the code of a given problem (lets assume a sorting or searching algorithm), now how will we find the complexity of the executable i.e the asymptotic complexity? means is it taking linear, quadratic or exponential time etc…

Do try to think on this, it’s small but interesting question..

Difference between two strings – Levenshtein Algorithm

September 22, 2006 4 comments

So now after a long time, I am going to write about an algorithm which I recently read, and found it very useful.

This algorithm is about, how different two strings are, and how many minimum operations are required to convert smaller string in length to larger (if their lengths are different). If the two string are of equal length then the number of charcaters that differ in two strings is the difference of strings. For example, in ‘computer’ and ‘computes’ the difference is 1 and in ‘test’ and ‘goat’ the difference is 3. Such distance is called as Hamming distance or edit distance simply put.

However if the strings are different in length then we use Levenshtein Algorithm or edit distance. Which works as follows.

For the two strings s1(cat) and s2(cots) of lengths m(3) and n(4), make an array of n*m and fill the each cell in 0th row with it’s corresponding column number and each cell in 0th column with it’s corresponding row number so our array ‘D’ will look like,

0 1 2 3

1

2

3

4

After this we compute a value in ‘temp’ which is 0 if s1[i] = s1[j] and 1 otherwise. And then find the minimum of D[i-1][j] + 1, D[i][j-1] +1 and D[i-1][j-1] + cost and assign it to D[i][j], where ‘i’ and ‘j’ are indeces while we compute. When we fill this array the last value in D[n][m] will give you the minimum number of moves required to convert str1(smaller) into str2(larger).

Here D[i-1][j] + 1, tell us if it is selected that we have to insert value in str1, if we select D[i][j-1] + 1 then we have to delete from str2 and if D[i-1][j-1] + cost is selected then we have to substitue in str1.

This is an interesting algorithm to try and then code, and is useful to find closest matches for a string and then can be used in many applications.

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.