## Top 10 Traits of a Rockstar Software Engineer

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,

- Loves To Code
- Gets Things Done
- Continuously Refactors Code
- Uses Design Patterns
- Writes Tests
- Leverages Existing Code
- Focuses on Usability
- Writes Maintainable Code
- Can Code in Any Language
- 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.

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.

## World’s Largest Semantic Web announced – Web 3.0 Insight

Cognition Technologies a Semantic Web company (wow Aleem Khan just think a ‘Semantic Web’ company – for those of you who don’t know Semantic Web was our final year project) is announcing the largest Semantic Map of English language. In simple words, they will be “enabling” search engines to understand what we have typed in the search box and retrieve contextually correct results.

The company is also going to fulfill one of my ambitions (to build a Semantic Web – Web 3.0 based search engine). So this is going to be advent of Web 3.0 hopefully.

References: ReadWriteWb.com on Cognition Technologies

To view Semantic Web already in action check out: Cognitive Wikipedia

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

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 !

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.

## C Traps and Pitfalls !

I still believe that C was/is my oldest and first love :). And when I read this paper C Traps and Pitfalls By: Andrew Koenig of AT&T Bell Laboratories, this love was even consolidated ;). Specially the function call (*(void(*)())0)(); really made me believe that, “C makes it easy to shoot yourself in the foot. C++ makes it harder, but when you do, it blows your whole leg”.

For the curious readers the hint is enough that this is the function call to a function whose address is stored at 0(zero) location, rest of the details can be read in the beautiful article that I mentioned earlier.

## How to check which control has caused Post Back !

My this post will be how to get the control that caused the Post back in ASP.NET code behind. I got this help from this page, all my courtesies to this guy :).

We will have to access the __EVENTTARGET element of the form. If any one has ever seen a client side HTML source of server side HTML code he/she must be familiar with __EVENTTARGET. A hidden tag is added to the form named __EVENTTARGET after a postback. This hidden input is set to the name of the control that was clicked in the __doPostBack JavaScript function(causing postback) and then the form is submitted. We can access this hidden input from our code-behind as it is submitted with the form and can be found in the Params or Form collections. This is how we get the control that caused a postback. Once we have the name you can get a reference to the control via FindControl and use it as needed.

string ctrlname = page.Request.Params.Get(“__EVENTTARGET”);

if (ctrlname != null && ctrlname != string.Empty)

{

return this.Page.FindControl(ctrlname);

}

The only problem of this method is if post back is caused by a button control. This is because a button is rendered as an input type=”submit” tag, and this causes the form to submit only, so a post back is not occured. Thus button will be added to the form collection of the page. So we can get this very control by a little bit of programming logic. So the code will be some like follows.

public static Control GetPostBackControl(Page page)

{

Control control = null;

string ctrlname = page.Request.Params.Get(“__EVENTTARGET”);

if (ctrlname != null && ctrlname != string.Empty)

{

control = page.FindControl(ctrlname);

}

else

{

foreach (string ctl in page.Request.Form)

{

Control c = page.FindControl(ctl);

if (c is System.Web.UI.WebControls.Button)

{

control = c;

break;

}

}

}

return control;

}

This method takes a parameter which is a reference to the Page, it then uses that to look for the control that caused the postback. You can easily use this as follows:

Control c = PageUtility.GetPostBackControl(this.Page);

if (c != null)

{

//…

}

## Difference between two strings – Levenshtein Algorithm

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.

## Interop – Managed C++ and C#

I mentioned about writing some basic stuff for Managed C++ so here I am writing it.

I had to send C# strings to Managed C++ dll(class library). In MC++ the managed reference is represented by ‘^’, in MC++ function’s prototype will be;

String^ foo(String ^ pInputString);

and call from C# will be normal like, Console.WriteLine(foo(str));

for sending array of strings;

void foo(array<String ^>^ pInputAStrings); // yeah looks weird

for sending a string as reference;

void foo(String ^ % pInputRString);

Similarly XmlDocument xdoc = new XmlDocument(); in C# is equivalent to

XmlDocument ^ xdoc = gcnew XmlDocument(); when we initiliaze with ‘gcnew’ the garbage collector will run even if we have enabled mixed types option in Managed C++ in .NET 2005.

The magical API that helped me through out is,

Marshal.Copy Method (IntPtr, Byte[], Int32, Int32) which have a total of 16 overloads and is in,

**Namespace:** System.Runtime.InteropServices

**Assembly:** mscorlib (in mscorlib.dll)

So using this method I convert a Base 64 Encoded string in bytes to native char * as follows.

array<Byte> ^ byteConvertedFromBase64 = nullptr;

String ^ string64bit = String::Empty;

byteConvertedFromBase64 = Convert::FromBase64String( string64bit );

char * bData = 0;

bData = new char[length];

Marshal::Copy(byteConvertedFromBase64, 0, IntPtr(bData), length);

It is a magical API which always worked when ever I needed to convert types from native char * to strings and vice versa and with other types.

Besides that I had to suppress the security checks that are incurred when calling native dlls from managed code, to save performance losses using PInvoke or COM Interop. This is done by SuppressUnmanagedCodeSecurityAttribute Class and applying /CLRUNMANAGEDCODECHECK in the linker settings. You can view MSDN for specific details.

## The Coding King – Coding Master # 2

In July 2006, I took part in an online programming competition conducted by MSN Search team and recruiting people. Fortunately, I have won it. The contest is named as “Coding Master 2″ for 2006. You can view a brief biography and a photograph of mine at “The Coding Master results”.

Haroon

## Finding or detecting a loop/cycle in Link List.

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.

## Great books for Programming Courses !

I just came across this book "Computer Systems: A Programmer's Perspective". I had my Introduction to Programming course back in Spring 2001, and this book has reminded of those wonderful days :). What a splendid book. A must read for any one who has joined any Computer Science major course and a good reference book for all the programmers, instead it contains most of the things every programmer should know. Written by CMU Professor's, it's one of the coolest book to come across. This is the best book to start after a simple programming course, that can teach you a Computer System along with how programming is done successfully on it.

Another good book taught in MIT for those taking Introduction to Programming course is "Structure and Interpretation of Computer Programs". It is an introduction to Computer Programming book taught in MIT and it take's LISP as it's default language. One of the de-facto standard text on the subject (I wish all Universities raise the standard of programming courses to this book's level). The tag on my blogs "Dedicated to the spirit that dwells in Computer Programs" is also a modification of some text in this book. I hope one enjoy reading these 2 great books.

Haroon

## An interesting small programming puzzle.

Abubakar Sultan who was my senior at NetSol and the best Microsoft.NET programmer I have seen so far in Pakistani industry, has made this programming question and asked many to solve this.

For any given n(positive integer only), you have to print integers from 1 to n and then print from n-1 to 1 using only a loop without any explicit if-else or ternary operators and not using any other memory location except loop variable.

Example: if n = 7 then out put should be 1 2 3 4 5 6 7 6 5 4 3 2 1

He claimed no one have been able to solve this in first try. However I solved this problem and come up with the follwoing solution. I am pasting the C++ source to print the same.

int n = 7 ; // set any integer value here

for( int i = 1; i <= (2* n) ; i++)

cout << (( i <=n) * i) + ((i > n) * (i – ( i – n ) * 2));

This is really an interesting programming puzzle and I enjoyed working on it.

Haroon

## Coin Denomination Problem !

I was asked to solve the coin denomination problem in an Interview. The problem statement is: Given an amount of money, and some coins that are used in some country ( which will definitely include at-least 1 coin of worth 1), you have to find the minimum number of coins which will be used to convert the amount of money in coins. I came up with 3 solutions ( greedy algorithm which is trivial ), recursive which is tough but costly and finally a Dynamic Programming solution. I coded the algorithm in C# which is pasted below, this code will print the minimum number of coins that will be used, but the not exactly those coins which are being used in the solution, for that very purpose we have to store some addictional information, but doing that is not that much of a tough task, so enjoy the C# code

//***************** this is portion of code

int money = 9; // set any amount of money here

int [] maxcoins = new int [money + 1];

int [] coins = { 1 , 4 , 5}; // set any values here

for( int i=0; i < maxcoins.Length; i++)

maxcoins[i] = 10000; //this value should infact be very large

maxcoins[0] = 0;

for(int i = 1; i <= money; i++)

{

for( int j=0 ; j < coins.Length; j++)

{

if( i >= coins[i])

if( (maxcoins[i - coins[j]] + 1) < maxcoins[i])

maxcoins[i] = maxcoins[ i - coins[j]] + 1;

}

}

Console.WriteLine( maxcoins[money + 1]);

I will explain the logic later. ;)

Haroon

## Ouroborous Snake !

Once I made a programming problem set for In-House programming contest and gave this problem , at my University taken from ACM. The problem statement is:

Ouroboros is a mythical snake from ancient Egypt. It has its tail in its mouth and continously devoursitself. The Ouroboros numbers are binary numbers of 2* ^{n} *bits that have the property of “generating” the whole set of numbers from 0 to 2

^{n}-1. The generation works as follows: given an Ouroboros number, we place its 2

*bits wrapped in a circle. Then, we can take 2*

^{n}*groups of*

^{n}*n*bits starting each time with the next bit in the circle. Such circles are called

*Ouroboros circles*for the number

*n*. We will work only with the smallest Ouroboros number for each

*n*.

Example: for *n *= 2, there are only four Ouroboros numbers. These are 0011, 0110, 1100 and 1001. In this case, the smallest one is 0011. Here is the Ouroboros circle for 0011:

The table describes the function *o*(*n,k*) which calculates the *k*-th number in the Ouroboros circle of the smallest Ouroboros number of size *n*. This function is what your program should compute.

**Input**

The input consists of several test cases. For each test case, there will be a line containing two integers *n *and *k *(1 <= *n <= *8; 0 < *k <* 2* ^{n}*). The end of the input file is indicated by a line containing two zeros. Do not process that line.

**Output**

For each test case, output o(n ,k) on a line by itself.** **

**Sample Input
**2 0

2 1

3 7

4 14

0 0

**Sample Output
**0

1

4

12

I recently solved this problem in my office. This costed me an exciting half an hour to solve it and code it perfectly. The real problem I faced is as soon as the size of n grows ( in terms of powers of 2), the computaion becomes too much and hence slow and solution comes too late. But the interesting part is the algorithm. Any ways interested people can solve this and I am sure this will interest them.

I, Haroon

## Finding Longest Common Subsequence !

Well I will be getting some what techie. in this post , i recently tried and solved the Longest Common Subsequence problem once again , which is a really hard problem to solve(if you have not heard it before or never tried it).

Well, consider the text string S = 'i am a computer programmer' and another text string T = "a crammer" now this is contained in the string S , read the letters in capital in S, 'i Am a Computer pRogrAMMER', now this is the problem of finding any substring of T in S at any place in any form and the one which is the longest.

I solved this problem in a programming competition by generating all the subsets of strings S and T and finding the longest in subset strings of S. But the code was too complex and the complexity was 2^N for subsets and log(n) for search even the code was iterative. However thanks to Dynamic Programming that this problem can be solved in O( M * N ) worst case time complexity, where M = length of string S and N = Length of string T

the dynamic programming algorithm or pseduocode is;

int FindMaxLengthSubstring( S, T )

{

// make a 2 D array say MaxLen of size M * N for logical thinking

for ( int i = 0; i < Len(S); i++)

{

for (int j = 0; j < Len(T); j++)

{

if (S[i] == L[j] )

{

if( i==0 || j ==0)

{

MaxLen [i][j] = maximum( in 0th row or 0th column of MaxLen) + 1;

continue;

}

MaxLen [i][j] = 1 + MaxLen[ i - 1 ][ j - 1 ];

}

else

MaxLen[i][j] = maximum( MaxLen[ i - 1][ j], MaxLen [ i ][ j - 1 ]);

}

}

return MaxLen[Len(S) - 1][Len(T) - 1];

}

maximum is the simple function that find maximum of 2 numbers. Remember this function only returns the length of longest common subsequence only. Not the original such substring. We can find such substring in MaxLen array by back tracking and moving upwards. I will explain the logic for this solution some time soon.

I, Haroon

## Google Code Jam India 2006 !

Once again the serene and different Black Screen of TopCoder’s Competition arena was in front of me. Yes I was coding in the Qualification round of Google Code Jam India 2006. It was about 11.30 P.M after another tiring day. I had no compiler installed on my home PC, no IDE, no .NET and no Java. I solved the first problem in Note Pad and then finally started coding in the editor of the competition arena. I have forgotten all the Java syntax and conventions and was still coding in it. Got so many mistakes in syntax and finally coded the 1000 points problem in about 17 minutes. Its was so easy, but I had so many typo and language mistakes in it. Any how it was completed and submitted for above 600 marks. Then I started to code the 250 marks problem, a bit trickier but coded it again without any thing in about 20 minutes and successfully submitted it. Mean while my younger brother was sitting besides me asking me his issues about his Computer Studies paper, so my intentions were partly diverted with tiredness and guiding my bro.. Today when I saw the System Test results I found my both problems has a typo mistake of copy paste and both failed on 1 Test Case each. Google Jam

India has rated me above 1000 till now, a bad one considering how easy were problems and they could have been solved successfully in less than 20 minutes out of 60 minutes. Many other guys from my office tried it and some got 1 right solution or both failed in test cases. But any way once again a nice time pass and good activity to prove ourselves that still we are no that ‘rusted’. Google is really cool in this stuff of arranging such programming competitions from some past years in collaboration with TopCoder with manifold intentions. I hope these experiences turn out to be something good for me other than a pleasant time pass to fulfill the so called self-satisfaction!

## My Fun Time ;) !

Was just sitting in the office at 4:30 P.M when I just read this problem.

“Arrange the letters in a sequence , if there are given letters in a random order as abcbcabcabcabb, we have to arrange them in a sequence means in a fashion of aaaabbbbbcccc(means all the a should come first then all b’s and then all c’s) in O(n) complexity”.

Now thats a very easy problem if i have to solve it for english alphabets. At 4:33 P.M I finished coding it in C++.

P.S: I am able to code so fast as I have always opened a Windows of Visual Studio for C++.

Here is the code I Wrote.

void ArrangeLetters(char input[], int size)

{

int freq_lett[26] = {0};

char * temp = new char[size+1];

for(int index = 0 ; index

freq_lett[input[index]-97]++;

for(int index = 1 ; index

freq_lett[index] = freq_lett[index] + freq_lett[index-1];

for(int index = 0 ; index

{

temp[(freq_lett[input[index]-97]) -1] = input[index];

freq_lett[input[index]-97]–;

}

temp[size] = ”;

for(int index = 0 ; index

input[index] = temp[index];

}

Some of you might be thinking about kind of my fun. But believe me there is so much variety of

people in this world that 1 can expect anything from any one. So thats my way of seeing

fun and hitting a solution of any existing small/long but trickier or at times tougher computational problem or algorithm.

99 Zeroes and Google ^ Google!