Source code for converting an Interger into String.

void IntToStr( int num) {

bool bNegative =false;
if( num < 0)
bNegative =true;
char * str = new char[11];
int i =0;
while( num != 0) {

str[i++] = num % 10 + '0';
num /=10;
}
i--; int j =0;
while( j
char ch = str[j];
str[j] = str[i];
str[i] = ch;
j++; i--;
}

}

Source code for reversing a string.( charecter by charecter)

void ReverseString( char str[]) {

int start =0 ;int end = strlen(str)-1;
while(start < end) {

char ch = str[start];
str[start] = str[end];
str[end] = ch;

start++; end--;
}
}

Source code for converting a string to an integer value.

int StrToInt( char str[]) {

bool bFlagNeative =false;
if( str[0] == '-') {

bFlagNeative =true;
}
int i=0;
int num =0;
while(str[i] != '\0') {

num *=10;
num+= (str[i++] - '0');
}
if(bFlagNeative)
num *= -1;
return num;

}

Reversing words from a string( containin more than one words separated by space - etc)

bool reverseWords( char str[] ){
char *buffer;
int tokenReadPos, wordReadPos, wordEnd, writePos = 0;

/* Position of the last character is length - 1 */
tokenReadPos = strlen(str) - 1;

buffer = (char *) malloc(tokenReadPos + 2);
if( !buffer )
return false; /* reverseWords failed */

while( tokenReadPos >= 0 ){

if( str[tokenReadPos] == ' ' ){ /* Non-word characters */
/* Write character */
buffer[writePos++] = str[tokenReadPos--];

} else { /* Word characters */
/* Store position of end of word */
wordEnd = tokenReadPos;

/* Scan to next non-word character */
while( tokenReadPos >= 0 && str[tokenReadPos] != ' ' )
tokenReadPos--;

/* tokenReadPos went past the start of the word */
wordReadPos = tokenReadPos + 1;

/* Copy the characters of the word */
while( wordReadPos <= wordEnd ){
buffer[writePos++] = str[wordReadPos++];
}
}
}
/* null terminate buffer and copy over str */
buffer[writePos] = '\0';
strcpy(str, buffer);

free(buffer);

return true; /* ReverseWords successful */
}

Source code for reversing a singly linked list.

Reverse( Node **head) {

Node *curr = *head;
Node *prev =NULL;
Node *next =*head;
while( curr !=NULL) {


next = curr->next;
curr->next = prev;
prev = curr;
curr = next;

}
*head = prev;
}

Source code for Finding a Cycle in a singly linked list ?

bool Cycle(Node **head) {

Node *pCurr = *head;
Node *pCurNex = *head;

if( *head == NULL ) {
return false;
}
do {
pCurr=pCurr->next;
pCurNex= pCurNex->next->next;

}while((pCurr != pCurNex) && pCurr != NULL && pCurNex != NULL && pCurNex->next!= NULL);
if(pCurr == NULL || pCurNex ==NULL || pCurNex->next == NULL)
return false;
else
return true;
}

Telephone Words

People often give others their telephone number as a word representing the seven-digit number. For example, if my telephone number were 866-2665, I could tell people my number is “TOOCOOL,” instead of the hard-to-remember seven-digit number. Note that many other possibilities (most of which are nonsensical) can represent 866-2665. You can see how letters correspond to numbers on a telephone keypad. Write a routine that takes a seven-digit telephone number and prints out all of the possible “words” or combinations of letters that can represent the given number. Because the 0 and 1 keys have no letters on them, you should change only the digits 2–9 to letters. You’ll be passed an array of seven integers, with each element being one digit in the number. You may assume that only valid phone numbers will be passed to your routine. You can use the helper routine char getCharKey( int telephoneKey, int place ) which takes a telephone key (0–9) and a place of either 1, 2, 3 and returns the character corresponding to the letter in that position on the specified key. For example, GetCharKey(3, 2) will return ‘E’ because the telephone key 3 has the letters “DEF” on it and ‘E’ is the second letter.

It’s worthwhile to define some terms for this problem. A telephone number consists of digits. Three letters correspond to each digit (except for 0 and 1, but when 0 and 1 are used in the context of creating a word, you can call them letters). The lowest letter, middle letter, and highest letter will be called the digit’s low value, middle value, and high value, respectively. You will be creating words, or strings of letters, to represent the given number.

First, impress the interviewer with your math skills by determining how many words can correspond to a seven-digit number. This requires combinatorial mathematics, but if you don’t remember this type of math, don’t panic. First, try a one-digit phone number. Clearly, this would have three words. Now, try a two-digit phone number - say, 56. There are three possibilities for the first letter, and for each of these there are three possibilities for the second letter. This yields a total of nine words that can correspond to this number. It appears that each additional digit increases the number of words by a factor of 3. Thus, for 7 digits, you have 3⁷ words, and for a phone number of length n, you have 3ⁿ words. Because 0 and 1 have no corresponding letters, a phone number with 0s or 1s in it would have fewer words, but 3⁷ is the upper bound on the number of words for a seven-digit number.

Now you need to figure out an algorithm for printing these words. Try writing out some words representing one of the author’s old college phone numbers, 497-1927, as an example. The most natural manner in which to list the words is alphabetical order. This way, you always know which word comes next and you are less likely to miss words. You know that there is on the order of 3⁷ words that can represent this number, so you won’t have time to write them all out. Try writing just the beginning and the end of the alphabetical sequence. You will probably want to start with the word that uses the low letter for each digit of the phone number. This guarantees that your first word is the first word in alphabetical order. Thus, the first word for 497-1927 becomes ‘G’ for 4 because 4 has “GHI” on it, ‘W’ for 9, which has “WXY” on it, ‘P’ for 7, which has “PRS” on it, and so on, resulting in “GWP1WAP”.

As you continue to write down words, you ultimately create a list that looks like the following:

GWP1WAP

GWP1WAR

GWP1WAS

GWP1WBP

GWP1WBR

…

IYS1YCR

IYS1YCS

It was easy to create this list because the algorithm for generating the words is relatively intuitive. Formalizing this algorithm is more challenging. A good place to start is by examining the process of going from one word to the next word in alphabetical order.

Because you know the first word in alphabetical order, determining how to get to the next word at any point gives you an algorithm for writing all the words. One important part of the process of going from one word to the next seems to be that the last letter always changes. It continually cycles through a pattern of P-R-S. Whenever the last letter goes from S back to P, it causes the next-to-last letter to change.

Try investigating this a little more to see if you can come up with specific rules. Again, it’s probably best to try an example. You may have to write down more words than in the example list to see a pattern (a three-digit phone number should be sufficient, or the previous list will work if it’s expanded a bit). It looks as if the following is always true: Whenever a letter changes, its right neighbor goes through all of its values before the original letter changes again. Conversely, whenever a letter resets to its low value, its left neighbor increases to the next value.

From these observations, there are probably two reasonable paths to follow as you search for the solution to this problem. You can start with the first letter and have a letter affect its right neighbor, or you can start with the last letter and have a letter affect its left neighbor. Both of these approaches seem reasonable, but you’ll have to choose one. For now, try the former and see where that gets you.

You should examine exactly what you’re trying to do at this point. You’re working with the observation that whenever a letter changes, it causes its right neighbor to cycle through all of its values before it changes again. You’re now using this observation to determine how to get from one word to the next word in alphabetical order. It may help to formalize this observation: Changing the letter in position i causes the letter in position i + 1 to cycle through its values. When you can write an algorithm in terms of how elements i and i + 1 interact with each other, it often indicates recursion, so try to figure out a recursive algorithm.

You have already discovered most of the algorithm. You know how each letter affects the next; you just need to figure out how to start the process and determine the base case. Looking again at the list to try to figure out the start condition, you’ll see that the first letter cycles only once. Therefore, if you start by cycling the first letter, this causes multiple cycles of the second letter, which causes multiple cycles of the third letter - exactly as desired. After you change the last letter, you can’t cycle anything else, so this is a good base case to end the recursion. When the base case occurs, you should also print out the word because you’ve just generated the next word in alphabetical order. The one special case you have to be aware of occurs when there is a 0 or 1 in the given telephone number. You don’t want to print out any word three times, so you should check for this case and cycle immediately if you encounter it.

In list form, the steps look like this:

If the current digit is past the last digit
   Print the word because you're at the end
Else
   For each of the three digits that can represent the current digit, going from
low to high
       Have the letter represent the current digit
       Move to next digit and recurse
       If the current digit is a 0 or a 1, return

The code is as follows:

static final int PHONE_NUMBER_LENGTH = 7;

void printTelephoneWords( int[] phoneNum ){
   char[] result = new char[ PHONE_NUMBER_LENGTH ];

   doPrintTelephoneWords( phoneNum, 0, result );

}

void doPrintTelephoneWords( int[] phoneNum, int curDigit,
                           char[] result ){
   if( curDigit == PHONE_NUMBER_LENGTH ){
     System.out.println( new String( result ) );
   return;
   }

   for( int i = 1; i <= 3; i++ ){
       result[ curDigit ] = getCharKey( phoneNum[curDigit], i );
       doPrintTelephoneWords( phoneNum, curDigit + 1, result );
       if( phoneNum[curDigit] == 0 ||
           phoneNum[curDigit] == 1) return;
   }
}

What is the running time of this algorithm? It can be no less than O(3ⁿ) because there are 3ⁿ solutions, so any correct solution must be at least O(3ⁿ). Getting each new word requires only constant time operations so the running time is indeed O(3ⁿ).

Important

Reimplement PrintTelephoneWords without using recursion.

The recursive algorithm doesn’t seem to be very helpful in this situation. Recursion was inherent in the way that you wrote out the steps of the algorithm. You could always try emulating recursion using a stack-based data structure, but there may be a better way involving a different algorithm. In the recursive solution, you solved the problem from left to right. You also made an observation that suggested the existence of another algorithm going from right to left: Whenever a letter changes from its high value to its low value, its left neighbor is incremented. Explore this observation and see if you can find a nonrecursive solution to the problem.

Again, you’re trying to figure out how to determine the next word in alphabetical order. Because you’re working from right to left, you should look for something that always happens on the right side of a word as it changes to the next word in alphabetical order. Looking back at the original observations, you noticed that the last letter always changes. This seems to indicate that a good way to start is to increment the last letter. If the last letter is at its high value and you increment it, you reset the last letter to its low value and increment the second-to-last letter. Suppose, however, that the second-to-last number is already at its high value. Try looking at the list to figure out what you need to do. From the list, it appears that you reset the second-to-last number to its low value and increment the third-to-last number. You continue carrying your increment like this until you don’t have to reset a letter to its low value.

This sounds like the algorithm you want, but you still have to work out how to start it and how to know when you’re finished. You can start by manually creating the first string as you did when writing out the list. Now you need to determine how to end. Look at the last string and figure out what happens if you try to increment it. Every letter resets to its low value. You could check whether every letter is at its low value, but this seems inefficient. The first letter resets only once, when you’ve printed out all of the words. You can use this to signal that you’re done printing out all of the words. Again, you have to consider the cases where there is a 0 or a 1. Because 0 and 1 effectively can’t be incremented (they always stay as 0 and 1), you should always treat a 0 or a 1 as if it were at its highest letter value and increment its left neighbor. In outline form, the steps are as follows:

Create the first word character by character
Loop infinitely:
    Print out the word
    Increment the last letter and carry the change
    If the first letter has reset, you're done

Here is the solution based on this sort of algorithm:

Tip

Note that you can cut down on the calls to getCharKey by storing each letter’s three values in variables, rather than making repeated calls to see whether a value is low, middle, or high. This makes the code a little more difficult, and this sort of optimization is probably unnecessary in the context of this solution.

static final int PHONE_NUMBER_LENGTH = 7;

void printTelephoneWords( int phoneNum[] ){
   char[] result = new char[ PHONE_NUMBER_LENGTH ];
   int i;

   /* Initialize the result (in our example,
    * put GWP1WAR in result).
    */
   for( i = 0; i < PHONE_NUMBER_LENGTH; i++ )
       result[i] = getCharKey( phoneNum[i], 1 );

   /* Main loop begins */
   while( true ){
       for( i = 0; i < PHONE_NUMBER_LENGTH; ++i ){
           System.out.print( result[i] );
       }
       System.out.print( '\n' );

       /* Start at the end and try to increment from right
        * to left.
        */
       for( i = PHONE_NUMBER_LENGTH - 1; i >= -1; i-- ){
           /* You're done because you
            * tried to carry the leftmost digit.
            */
           if( i == -1 ) return;

           /* Otherwise, we're not done and must continue. */

           /* You want to start with this condition so that you can
            * deal with the special cases, 0 and 1 right away.
            */
           if( getCharKey( phoneNum[i], 3 ) == result[i] ||
               phoneNum[i] == 0 || phoneNum[i] == 1 ){
               result[i] = getCharKey( phoneNum[i], 1 );
               /* No break, so loop continues to next digit */
           } else if ( getCharKey( phoneNum[i], 1 ) == result[i] ){
               result[i] = getCharKey( phoneNum[i], 2 );
               break;
           } else if ( getCharKey( phoneNum[i], 2 ) == result[i] ){
               result[i] = getCharKey( phoneNum[i], 3 );
               break;
           }
       }
   }
}

What’s the running time on this algorithm?

Again, there must be at least 3ⁿ solutions, so the algorithm can be no better than O(3ⁿ) if it is correct. There is slight constant overhead in finding each word, but you can ignore it. Therefore, this is also an O(3ⁿ) solution.

Combinations of a String using recursion.

Implement a function that prints all possible combinations of the characters in a string. These combinations range in length from one to the length of the string. Two combinations that differ only in ordering of their characters are the same combination. In other words, “12” and “31” are different combinations from the input string “123”, but “21” is the same as “12”.

This is a companion problem to finding the permutations of the characters in a string. If you haven’t yet worked through that problem, you may want to do so before you tackle this one.

Following the model of the solution to the permutation problem, try working out an example by hand and see where that gets you. Because you are trying to divine an algorithm from the example, you again need to be systematic in your approach. You might try listing combinations in order of length. The input string “wxyz” is used in the example. Because the ordering of letters within each combination is arbitrary, they are kept in the same order as they are in the input string to minimize confusion.

w	wx	wxy	wxyz
x	wy	wxz
y	wz	wyz
z	xy	xyz
	xz
	yz

Open table as spreadsheet

Some interesting patterns seem to be emerging, but there’s nothing clear yet, certainly nothing that seems to suggest an algorithm. Listing output in terms of the order of the input string (alphabetical order, for this input string) turned out to be helpful in the permutation problem. Try rearranging the combinations you generated and see if that’s useful here.

w	x	y	z
wx	xy	yz
wxy	xyz
wxyz	xz
wxz
wy
wyz
wz

Open table as spreadsheet

This looks a little more productive. There is a column for each letter in the input string. The first combination in each column is a single letter from the input string. The remainder of each column’s combinations consist of that letter prepended to each of the combinations in the columns to the right. Take, for example, the “x” column. This column has the single letter combination “x”. The columns to the right of it have the combinations “y”, “yz”, and “z”, so if you prepend “x” to each of these combinations you find the remaining combinations in the “x” column: “xy”, “xyz”, and “xz”. You could use this rule to generate all of the combinations, starting with just “z” in the rightmost column and working your way to the left, each time writing a single letter from the input string at the top of the column and then completing the column with that letter prepended to each of the combinations in columns to the right. This is a recursive method for generating the combinations. It is space inefficient because it requires storage of all previously generated combinations, but it indicates that this problem can be solved recursively. See if you can gain some insight on a more-efficient recursive algorithm by examining the combinations you’ve written a little more closely.

Look at which letters appear in which positions. All four letters appear in the first position, but “w” never appears in the second position. Only “y” and “z” appear in the third position, and “z” is in the fourth position in the only combination that has a fourth position (“wxyz”). Therefore, a potential algorithm might involve iterating through all allowable letters at each position: w–z in the first position, x–z in the second position, and so on. Check this idea against the example to see if it works: It seems to successfully generate all the combinations in the first column. However, when you select “x” for the first position, this candidate algorithm would start with “x” in the second position, generating an illegal combination of “xx”. Apparently the algorithm needs some refinement.

To generate the correct combination “xy”, you really need to begin with “y”, not “x”, in the second position. When you select “y” for the first position (third column), you need to start with “z” because “yy” is illegal and “yx” and “yw” have already been generated as “xy” and “wy”. This suggests that in each output position you need to begin iterating with the letter in the input string following the letter selected for the preceding position in the output string. Call this letter your input start letter.

It may be helpful to summarize this a little more formally. You need to track the output position as well as the input start position. Begin with the first position as the output position, and the first character of the input as the input start position. For a given position, sequentially select all letters from the input start position to the last letter in the input string. For each letter you select, print the combination and then generate all other combinations beginning with this sequence by recursively calling the generating function with the input start position set to the next letter after the one you’ve just selected and the output position set to the next position. You should check this idea against the example to make sure it works. It does - no more problems in the second column. Before you code, it may be helpful to outline the algorithm just to make sure you have it.

Tip

For comparison, the performance side of the arms-length recursion style/performance trade-off discussed in the permutation problem was chosen. The performance and style differences between the two possible approaches are not as dramatic for the combination algorithm as they were for the permutation algorithm.

For each letter from input start position to end of input string
   Select the letter into the current position in output string
   Print letters in output string
   If the current letter isn't the last in the input string
Generate remaining combinations starting at next position with iteration starting
at next letter beyond the letter just selected

After all that hard work, the algorithm looks pretty simple! You’re ready to code it. Here’s a C# version:

void combine( string str ){
   int           length = str.Length;
   char[]        instr = str.ToCharArray();
   StringBuilder outstr = new StringBuilder();
   doCombine( instr, outstr, length, 0, 0 );
}

void doCombine( char[] instr, StringBuilder outstr, int length,
               int level, int start ){
   for( int i = start; i < length; i++ ){
       outstr.Append( instr[i] );
       Console.WriteLine( outstr );

       if( i < length - 1 ){
           doCombine( instr, outstr, length, level + 1, i + 1 );
       }

       outstr.Length = outstr.Length - 1;
   }
}

This solution is sufficient in most interviews. Nevertheless, you can make a rather minor optimization to doCombine that eliminates the if statement. Given that this is a recursive function, the performance increase is probably negligible compared to the function call overhead, but you might want to see if you can figure it out just for practice.

You can eliminate the if statement by removing the final iteration from the loop and moving the code it would have executed during that final iteration outside the loop. The general case of this optimization is referred to as loop partitioning, and if statements that can be removed by loop partitioning are called loop index dependent conditionals. Again, this optimization doesn’t make much difference here, but it can be important inside nested loops.

Permutations of a String using recursion.

Implement a routine that prints all possible orderings of the characters in a string. In other words, print all permutations that use all the characters from the original string. For example, given the string “hat”, your function should print the strings “tha”, “aht”, “tah”, “ath”, “hta”, and “hat”. Treat each character in the input string as a distinct character, even if it is repeated. Given the string “aaa”, your routine should print “aaa” six times. You may print the permutations in any order you choose.

Manually permuting a string is a relatively intuitive process, but describing an algorithm for the process can be difficult. In a sense, the problem here is like being asked to describe how you tie your shoes: You know the answer, but you probably still have to go through the process a few times to figure out what steps you’re taking.

Try applying that method to this problem: Manually permute a short string and try to reverse-engineer an algorithm out of the process. Take the string “abcd” as an example. Because you’re trying to construct an algorithm from an intuitive process, you want to go through the permutations in a systematic order. Exactly which systematic order you use isn’t terribly important - different orders are likely to lead to different algorithms, but as long as you’re systematic about the process you should be able to construct an algorithm. You want to choose a simple order that will make it easy to identify any permutations that you might accidentally skip.

You might consider listing all the permutations in alphabetical order. This means the first group of permutations will all start with “a”. Within this group, you first have the permutations with a second letter of “b”, then “c”, and finally “d”. Continue in a like fashion for the other first letters.

abcd	bacd	cabd	dabc
abdc	badc	cadb	dacb
acbd	bcad	cbad	dbac
acdb	bcda	cbda	dbca
adbc	bdac	cdab	dcab
adcb	bdca	cdba	dcba

Open table as spreadsheet

Before you continue, make sure you didn’t miss any permutations. Four possible letters can be placed in the first position. For each of these four possibilities, there are three remaining possible letters for the second position. Thus, there are 4×3 = 12 different possibilities for the first two letters of the permutations. Once you’ve selected the first two letters, two different letters remain available for the third position, and the last remaining letter is put in the fourth position. If you multiply 4×3×2×1 you have a total of 24 different permutations; there are 24 permutations in the previous list, so nothing has been missed.

This calculation can be expressed more succinctly as 4! - you may recall that n! is the number of possible arrangements of n objects.

Now examine the list of permutations for patterns. The rightmost letters vary faster than the leftmost letters. For each letter that you choose for the first (leftmost) position, you write out all the permutations beginning with that letter before you change the first letter. Likewise, once you’ve picked a letter for the second position, you write out all permutations beginning with this two-letter sequence before changing the letters in either the first or second position. In other words, you can define the permutation process as picking a letter for a given position and performing the permutation process starting at the next position to the right before coming back to change the letter you just picked. This sounds like the basis for a recursive definition of permutation. Try to rephrase it in explicitly recursive terms: To find all permutations starting at position n, successively place all allowable letters in position n, and for each new letter in position n find all permutations starting at position n + 1 (the recursive case). When n is greater than the number of characters in the input string, a permutation has been completed; print it and return to changing letters at positions less than n (the base case).

You almost have an algorithm; you just need to define “all allowable letters” a little more rigorously. Because each letter from the input string can appear only once in each permutation, “all allowable letters” can’t be defined as every letter in the input string. Think about how you did the permutations manually. For the group of permutations beginning with “b”, you never put a “b” anywhere but the first position because when you selected letters for later positions, “b” had already been used. For the group beginning “bc” you used only “a” and “d” in the third and fourth positions because both “b” and “c” had already been used. Therefore, “all allowable letters” means all letters in the input string that haven’t already been chosen for a position to the left of the current position (a position less than n). Algorithmically, you could check each candidate letter for position n against all the letters in positions less than n to determine whether it had been used. You can eliminate these inefficient scans by maintaining an array of Boolean values corresponding to the positions of the letters in the input string and using this array to mark letters as used or unused, as appropriate.

In outline form, this algorithm looks like the following:

If you're past the last position
   Print the string
   Return
Otherwise
   For each letter in the input string
   If it's marked as used, skip to the next letter
   Else place the letter in the current position
       Mark the letter as used
       Permute remaining letters starting at current position + 1
       Mark the letter as unused

Tip

Separating the base case from the recursive case as performed here is considered good style and may make the code easier to understand, but it does not provide optimum performance. You can significantly optimize the code by invoking the base case directly without a recursive call if the next recursive call invokes the base case. In this algorithm, that involves checking whether the letter just placed was the last letter - if so, you print the permutation and make no recursive call; otherwise, a recursive call is made. This eliminates n! function calls, reducing the function call overhead by approximately a factor of n (where n is the length of the input string). Short-circuiting the base case in this manner is called arms-length recursion and is considered poor style, especially in academic circles. Whichever way you choose to code the solution, it is worthwhile to mention the advantages of the alternate approach to your interviewer.

Here’s a Java version of this algorithm:

void permute( String str ){
   int          length = str.length();
   boolean[]    used = new boolean[ length ];
   StringBuffer out = new StringBuffer();
   char[]       in = str.toCharArray();

   doPermute( in, out, used, length, 0 );
}

void doPermute( char[] in, StringBuffer out,
               boolean[] used, int length, int level ){
   if( level == length ){
       System.out.println( out.toString() );
       return;
   }

   for( int i = 0; i < length; ++i ){
       if( used[i] ) continue;

       out.append( in[i] );
       used[i] = true;
       doPermute( in, out, used, length, level + 1 );
       used[i] = false;
       out.setLength( out.length() - 1 );
   }
}

Structurally, this function uses a wrapper method called permute to allocate two arrays, one for the flags and one to hold the input characters, and a StringBuffer for building the output string. Then it calls the recursive portion, doPermute, to actually do the permutation. The characters are appended to the StringBuffer as appropriate. When the recursive call returns, the last character is dropped simply by reducing the buffer’s length.

Binary Search using recursion.

Implement a function to perform a binary search on a sorted array of integers to find the index of a given integer. Use this method declaration: int binarySearch( int[] array, int lower, int upper, int target ); Comment on the efficiency of this search and compare it with other search methods.

In a binary search, you compare the central element in your sorted search space (an array, in this case) with the item you’re looking for. There are three possibilities. If it’s less than what you’re searching for, you eliminate the first half of the search space. If it’s more than the search value, you eliminate the second half of the search space. In the third case, the central element is equal to the search item and you stop the search. Otherwise, you repeat the process on the remaining portion of the search space. If it’s not already familiar to you from computer science courses, this algorithm may remind you of the optimum strategy in the children’s number-guessing game in which one child guesses numbers in a given range and a second responds “higher” or “lower” to each incorrect guess.

Because a binary search can be described in terms of binary searches on successively smaller portions of the search space, it lends itself to a recursive implementation. Your method will need to be passed the array it is searching, the limits within which it should search, and the element for which it is searching. You can subtract the lower limit from the upper limit to find the size of the search space, divide this size by two, and add it to the lower limit to find the index of the central element. Next compare this element to the search element. If they’re equal, return the index. Otherwise, if the search element is smaller, then the new upper limit becomes the central index – 1; if the search element is larger, the new lower limit is the central index + 1. Recurse until you match the element you’re searching for.

Before you code, consider what error conditions you’ll need to handle. One way to think about this is to consider what assumptions you’re making about the data you are being given and then consider how these assumptions might be violated. One assumption, explicitly stated in the problem, is that only a sorted array can be searched, so you’ll want to detect unsorted lists. You can do this by checking whether the value at the upper limit is less than the value at the lower limit, although this won’t catch all unsorted lists. If the limits are wrong, you should return an error code. (Another way to handle this case would be to call a sort routine and then restart the search, but that’s more than you need to do in an interview.)

Another assumption implicit in a search may be a little less obvious: The element you’re searching for is assumed to exist in the array. If you don’t terminate the recursion until you find the element, you’ll recurse infinitely when the element is missing from the array. You can avoid this by returning an error code if the upper and lower limits are equal and the element at that location is not the element you’re searching for. Finally, you assume that the lower limit is less than or equal to the upper limit. For simplicity, you can just return an error code in this case, although in a real program you’d probably want to either define this as an illegal call and use an assert to check it (for more efficient programs) or silently reverse the limits when they are out of order (for easier programming).

Now you can translate these algorithms and error checks into C# code:

const int NOT_IN_ARRAY = -1;
const int ARRAY_UNORDERED = -2;
const int LIMITS_REVERSED = -3;

int binarySearch( int[] array, int lower, int upper, int target ){
   int center, range;

   range = upper - lower;
   if (range < 0) {
       return LIMITS_REVERSED;
   } else if( range == 0 && array[lower] != target ){
       return NOT_IN_ARRAY;
   }

   if( array[lower] > array[upper] )
       return ARRAY_UNORDERED;

   center = ((range)/2) + lower;

   if( target == array[center] ){
       return center;
   } else if( target < array[center] ){
       return binarySearch( array, lower, center - 1, target );
   } else {
       return binarySearch( array, center + 1, upper, target );
   }
}

Note that the example returns an error code instead of throwing an exception. You could use this as a chance to discuss the pros and cons of exception throwing with the interviewer.

Although the preceding routine completes the given task, it is not as efficient as it could be. As discussed at the beginning of this chapter, recursive implementations are generally less efficient than equivalent iterative implementations.

If you analyze the recursion in the previous solution, you can see that each recursive call serves only to change the search limits. There’s no reason why you can’t change the limits on each iteration of a loop and avoid the overhead of recursion. The method that follows is a more-efficient, iterative analog of the recursive binary search:

int iterBinarySearch( int[] array, int lower, int upper, int target ){
   int center, range;

   if( lower > upper )
       return LIMITS_REVERSED;

   while( true ){
       range = upper - lower;
       if( range == 0 && array[lower] != target )
           return NOT_IN_ARRAY;

       if( array[lower] > array[upper] )
           return ARRAY_UNORDERED;

       center = ((range)/2) + lower;
       if( target == array[center] ){
           return center;
       } else if( target < array[center] ){
           upper = center - 1;
       } else {
           lower = center + 1;
       }
   }
}

A binary search is O(log(n)) because half of the search is eliminated (in a sense, searched) on each iteration. This is more efficient than a simple search through all the elements, which would be O(n).

However, in order to perform a binary search the array must be sorted, an operation that is usually O(n log(n)), unless of course the array is always kept in sorted order.

What is Recursion ? Explain in detail.

Recursion

Recursion is a deceptively simple concept: Any routine that calls itself is recursive. Despite this apparent simplicity, understanding and applying recursion can be surprisingly complex. One of the major barriers to understanding recursion is that general descriptions tend to become highly theoretical, abstract, and mathematical. Although there is certainly value in that approach, this chapter will instead follow a more pragmatic course, focusing on example, application, and comparison of recursive and iterative (nonrecursive) algorithms.

Understanding Recursion

Recursion is most useful for tasks that can be defined in terms of similar subtasks. For example, sort, search, and traversal problems often have simple recursive solutions. A recursive routine performs a task in part by calling itself to perform the subtasks. At some point, the routine encounters a subtask that it can perform without calling itself. This case, in which the routine does not recurse, is called the base case; the former, in which the routine calls itself to perform a subtask, is referred to as the recursive case.

Tip

Recursive algorithms have two types of cases: recursive cases and base cases.

These concepts can be illustrated with a simple and commonly used example: the factorial operator. n! (pronounced “n factorial”) is essentially the product of all integers between n and 1. For example, 4! = 4 ^_ 3 ^_ 2 ^_ 1 = 24. n! can be more formally defined as follows:

n! = n (n – 1)!
0! = 1! = 1

This definition leads easily to a recursive implementation of factorial. The task is determining the value of n!, and the subtask is determining the value of (n – 1)! In the recursive case, when n is greater than 1, the routine calls itself to determine the value of (n – 1)! and multiplies that by n. In the base case, when n is 0 or 1, the routine simply returns 1. Rendered in any C-like language, this looks like the following:

int factorial( int n ){
   if (n > 1) {  /* Recursive case */
       return factorial(n-1) * n;
   } else {        /* Base case */
       return 1;
   }
}

In illustrating the operation of this routine when computing 4!. Notice that n decreases by 1 each time the routine recurses. This ensures that the base case will eventually be reached. If a routine is written incorrectly such that it does not always reach a base case, it will recurse infinitely. In practice, there is usually no such thing as infinite recursion: Eventually a stack overflow occurs and the program crashes - a similarly catastrophic event. (There is a form of recursion, called tail recursion, that can be optimized by the compiler to use the same stack frame for each recursive call. An appropriately optimized tail recursive algorithm could recurse infinitely because it wouldn’t overflow the stack.)

Tip

Every recursive case must eventually lead to a base case.

This implementation of factorial represents an extremely simple example of a recursive routine. In many cases, your recursive routines may need additional data structures or an argument that tracks the recursion level. Often the best solution in such cases is to move the data structure or argument initialization code into a separate routine. This wrapper routine, which performs initialization and then calls the purely recursive routine, provides a clean, simple interface to the rest of the program.

For example, if you need a factorial routine that returns all of its intermediate results (factorials less than n), as well as the final result (n!), you most naturally return these results as an integer array, which means the routine needs to allocate an array. You also need to know where in the array each result should be written. These tasks are most easily accomplished using a wrapper routine, as follows:

int[] allFactorials( int n ){ /* Wrapper routine */
   int[] results = new int[ n == 0 ? 1 : n ];
   doAllFactorials( n, results, 0 );
   return results;
}

int doAllFactorials( int n, int[] results, int level ){
   if( n > 1 ){  /* Recursive case */
       results[level] = n * doAllFactorials( n - 1, results, level + 1 );
       return results[level];
   } else {        /* Base case */
       results[level] = 1;
       return 1;
   }
}

You can see that using a wrapper routine enables you to hide the array allocation and recursion level tracking to keep the recursive routine very clean. In this case, it’s possible to determine the appropriate array index from n, avoiding the need for the level argument, but in many cases there is no alternative to tracking the recursion level as shown here.

Tip

It may be useful to write a separate wrapper routine to do initialization for a complex recursive routine.

Although recursion is a very powerful technique, it is not always the best approach, and rarely is it the most efficient approach. This is due to the relatively large overhead for routine calls on most platforms. For a simple recursive routine like factorial, many computer architectures spend more time on call overhead than the actual calculation. Iterative routines, which use looping constructs instead of recursive routine calls, do not suffer from this overhead and are frequently more efficient.

Tip

Iterative solutions are usually more efficient than recursive solutions.

Any problem that can be solved recursively can also be solved iteratively. Iterative algorithms are often quite easy to write, even for tasks that might appear to be fundamentally recursive. For example, an iterative implementation of factorial is relatively simple. It may be helpful to expand the definition of factorial, such that you describe n! as the product of every integer between n and 1, inclusive. You can use a for loop to iterate through these values and calculate the product:

int factorial( int i ){
   int n, val = 1;
   for( n = i; n > 1; n-- )  /* n = 0 or 1 falls through */
       val *= n;
   return val;
}

This implementation is significantly more efficient than our previous recursive implementation because no routine calls are involved. Although it represents a different way of thinking about the problem, it’s not really any more difficult to write than the recursive implementation.

For some problems, there are no obvious iterative alternatives like the one just shown. It’s always possible, though, to implement a recursive algorithm without using recursive calls. Recursive calls are generally used to preserve the current values of local variables and restore them when the subtask performed by the recursive call is completed. Because local variables are allocated on the program’s stack, each recursive instance of the routine has a separate set of the local variables, so recursive calls implicitly store variable values on the program’s stack. You can therefore eliminate the need for recursive calls by allocating your own stack and manually storing and retrieving local variable values from this stack.

Implementing this type of stack-based interactive routine tends to be significantly more complicated than implementing an equivalent routine using recursive calls. In languages like Java or C#, a stack-based iterative implementation of a recursive algorithm won’t be more efficient than the recursive version. Given the large increase in complexity, you should implement recursive algorithms with recursive calls unless instructed otherwise. An example of a recursive algorithm implemented without recursive calls is given in the solution to the “Preorder Traversal, No Recursion” problem in Chapter 5.

Tip

A recursive algorithm can be implemented without recursive calls by using a stack, but it’s usually more trouble than it’s worth.

In an interview, a working solution is of primary importance; an efficient solution is secondary. Unless you’ve been told otherwise, go with whatever type of working solution comes to you first. If it’s a recursive solution, you might want to mention the inefficiencies inherent in recursive solutions to your interviewer, so it’s clear that you know about them. In the rare instance that you see a recursive solution and an iterative solution of roughly equal complexity, you should probably mention them both to the interviewer, indicating that you’re going to work out the iterative solution because it’s likely to be more efficient.

Searching M th Element from the end of Linked List.

Given a singly-linked list, devise a time- and space-efficient algorithm to find the mth-to-last element of the list. Implement your algorithm, taking care to handle relevant error conditions. Define mth to last such that when m = 0, the last element of the list is returned.

Solution:

Why is this a difficult problem? Finding the mth element from the beginning of a linked list would be an extremely trivial task, because singly-linked lists can only be traversed in the forward direction. For this problem you are asked to find a given element based on its position relative to the end of the list. While you traverse the list, however, you don’t know where the end is, and when you find the end there is no easy way to backtrack the required number of elements.

You may want to tell your interviewer that a singly-linked list is a particularly poor choice for a data structure when you frequently need to find the mth-to-last element. If you were to encounter such a problem while implementing a real program, the correct and most-efficient solution would probably be to substitute a more-suitable data structure (such as a doubly-linked list) to replace the singly-linked list. Although this comment shows that you understand good design, the interviewer will still want you to solve the problem as it was originally phrased.

How, then, can you get around the problem that there is no way to traverse backward through this data structure? You know that the element you want is m elements from the end of the list. Therefore, if you traverse m elements forward from an element and that places you exactly at the end of the list, you have found the element you were searching for. One approach is to simply test each element in this manner until you find the one you’re searching for. Intuitively, this feels like an inefficient solution because you will be traversing over the same elements many times. If you analyze this potential solution more closely, you will see that you would be traversing m elements for most of the elements in the list. If the length of the list is n, the algorithm would be approximately O(mn). You need to find a solution more efficient than O(mn).

What if you stored some of the elements (or, more likely, pointers or references to the elements) as you traversed the list? Then, when you reach the end of the list, you could look back m elements in your storage data structure to find the appropriate element. If you use an appropriate temporary storage data structure, this algorithm would be O(n) because it requires only one traversal through the list. Yet this approach is far from perfect. As m becomes large, the temporary data structure would become large as well. In the worst-case scenario, this approach might require almost as much storage space as the list itself - not a particularly space-efficient algorithm.

Perhaps working back from the end of the list is not the best approach. Because counting from the beginning of the list is trivial, is there any way to count from the beginning to find the desired element? The desired element is m from the end of the list, and you know the value of m. It must also be l elements from the beginning of the list, although you don’t know l. However, l + m = n, the length of the list. It’s easy to count all the elements in the list. Then you can calculate l = n – m, and traverse l elements from the beginning of the list. Although this process involves two passes through the list, it’s still O(n). It requires only a few variables’ worth of storage, so this method is a significant improvement over the previous attempt. If you could change the functions that modify the list such that they would increment a count variable for every element added and decrement it for every element removed, you could eliminate the count pass, making this a relatively efficient algorithm. Again, though this point is worth mentioning to the interviewer, he or she is probably looking for a solution that doesn’t modify the data structure or place any restrictions on the methods used to access it.

Assuming you must explicitly count the elements in the current algorithm, you will have to make almost two complete traversals of the linked list. A very large list on a memory-constrained system might exist mostly in paged-out virtual memory (on disk). In such a case, each complete traversal of the list would require a large amount of disk access to swap the relevant portions of the list in and out of memory. Under these conditions, an algorithm that made only one complete traversal of the list might be significantly faster than an algorithm that made two traversals, even though they would both be O(n). Is there a way to find the target element with a single traversal?

The counting-from-the-beginning algorithm obviously demands that you know the length of the list. If you can’t track the length so that you know it ahead of time, you can determine the length only by a full-list traversal. There doesn’t seem to be much hope for getting this algorithm down to a single traversal.

Try reconsidering the previous linear time algorithm, which required only one traversal but was rejected for requiring too much storage. Is it possible to reduce the storage requirements of this approach?

When you reach the end of the list, you are really interested in only one of the m elements you’ve been tracking - the element that is m elements behind your current position. You are tracking the rest of the m elements merely because the element m behind your current position changes every time your position advances. Keeping a queue m elements long whereby you add the current element to the head and remove an element from the end every time you advance your current position ensures that the last element in the queue is always m elements behind your current position.

In effect, you are using this m element data structure to make it easy to implicitly advance an m-behind pointer in lock step with your current position pointer. However, this data structure is unnecessary - you can explicitly advance the m-behind pointer by following each element’s next pointer just as you do for your current position pointer. This is as easy as (or perhaps easier than) implicitly advancing by shifting through a queue, and it eliminates the need to track all the elements between your current position pointer and your m-behind pointer. This algorithm seems to be the one you’ve been looking for: linear time, a single traversal, and negligible storage requirements. Now you just need to work out the details.

You’ll use two pointers: a current position pointer and an m-behind pointer. You will have to ensure that the two pointers are actually spaced m elements apart; then you can advance them at the same rate. When your current position is the end of the list, m-behind will point to the mth-to-last element. How can you get the pointers spaced properly? If you count elements as you traverse the list, you can move the current position pointer to the mth element of the list. If you then start the m-behind pointer at the beginning of the list, they will be spaced m elements apart.

Are there any error conditions you need to watch for? If the list is less than m elements long, then there is no mth-to-last element. In such a case, you would run off the end of the list as you tried to advance the current position pointer to the mth element, possibly dereferencing a null pointer in the process. Therefore, check that you don’t hit the end of the list while doing this initial advance.

With this caveat in mind, you can implement the algorithm. Note that it’s easy to introduce off-by-one errors in any code that spaces any two things m items apart or counts m items from a given point. You may want to refer to the exact definition of “mth to last” given in the problem and try a little example on paper to make sure you get your counts right, particularly in the initial advancement of the current pointer.

Element *findMToLastElement( Element *head, int m ){
  Element *current, *mBehind;
  int i;

  /* Advance current m elements from beginning,
   * checking for the end of the list
   */
  current = head;
 for (i = 0; i <>next) {
         current = current->next;
     } else {
         return NULL;
     }
 }

 /* Start mBehind at beginning and advance pointers
  * together until current hits last element
  */
 mBehind = head;
 while( current->next ){
     current = current->next;
     mBehind = mBehind->next;
 }

 /* mBehind now points to the element we were
  * searching for, so return it
  */
  return mBehind;
}

Fibonacci-Delete

Fibonacci-Delete (H, x)

The above Procedure deletes node x's key from a given fibonacci heap H. It uses operation ‘Fibonacci–Heap–Extract–Min’, and ‘Decerase-key’.
Step 1 Decrease the key to – 
call to Decrease-key (H, x, – )
Step 2 Extract the minimum key
call to Fibonacci-Heap-Extract-Min (H)

Fabonnacci Heap Cascade-Cut

Cascade-Cut (H, y)

The above Procedure consider various cases of y being marked and unmarked. The Procedure calls itself repeatedly until either a root or an unmarked node is found.
Step 1 Initialization
set z  Parent [y]
Step 2 Checking y to be marked or unmarked
if (z  Nil) then
if (mark [y] = FALSE) then
mark [y]  TRUE
else
call to Cut (H, y, z)
call to Cascade-Cut (H, z).
Step 3 Return at the point of call
return

Fabonacci heap Cut

Cut (H, x, y)

The above Procedure cut off the link between x and its parent y, making x a root.
Step 1 Cut off the links
remove x form the child list of y,
set deg [y]  deg [y] – 1
add x to the root list of H.
Step 2 Initialization
set parent [x]  Nil
set mark [x]  FALSE
Step 3 Return at the point of call
return

Decrease-key

Decrease-key (H, x, k)

The above procedure decreases the key of x to k. It uses operation ‘Cut’ and ‘Cascade-Cut’ to maintain any violation.
Step 1 Is greater ?
if (k > key [x]) then
message : “new key is greater than the current key”.
Step 2 Initialization
set key [x]  k
set y  parent [x]
Step 3 Checking, cut off the link, adding to the root list.
if (y  Nil and key [x] < key [y]) then
call to Cut (H, x, y).
call to Cascade-Cut (H, y)
Step 4 Up date min [H] pointer
if (key [x] < key [min [H]) then
set min [H]  x
Step 5 Return at the point of call
return

Fibonacci-Link

Fibonacci-Link (H, y, x)

The above procedure links y to x in a given fibonacci heap H. The degree of x is incremented and mark of y, if any, is cleared.
Step 1 Removing
remove y form the root list of H.
Step 2 Adjusting node y, incrementing degree
make y a child of x,
set deg [x]  deg [x] + 1.
Step 3 Cleared marks.
set mark [y]  FALSE.

Fibonacci Heap Consolidate

Consolidate (H)

The above Procedure consolidates the rooted trees in the root list of Fibonacci Heap H until all the trees have distinct degrees. It also uses an auxilliary ‘A’, if A [i] = y, then y is currently a root with deg [y] i.
Step 1 Loop, Initialization
for i  0 to D(n [H])
set A [i]  Nil.
Step 2 loop 1, processing of each node in the root list
for each node w in the root list of H
set x  w
set d  deg [x]
loop 2
while ( A [d]  Nil)
set y  A[d]
if (key [x] > key [y]) then
set x  y
call to Fibonacci-Link (H, y,x).
set A [d]  Nil.
set d  d + 1.
end loop 2
end loop 1
set A [d]  x
Step 3 Initialization, empties the root list.
set min [H]  Nil
Step 4 loop, reconstruction
for i  0 to D(n [H])
if ( A [i]  Nil) then
add A [i] to the root list of H.
if (min [H] = Nil or key [A [i] < key (min [H])
then
set min [H]  A [i]
end loop

Fibonacci-Heap-Extract-Min

Fibonacci-Heap-Extract-Min (H)

The above Function extracts the node having minimum key from the fibonacci heap H. For convenience we assume that, when a node is removed from a root list, pointers remaining in the list are updated, but pointer in the extracted nodes remain unaltered.
Step 1 Initialization
set z  min [H]
Step 2 If not empty
if (z  Nil ) then
loop
for each child x of z
add x to the root list of H
set Parent [x]  Nil
Step 3 Remove z from the root list of H
if (z = right [z] ) then
set min [H ]  Nil
else
set min [H]  right [z]
call to consolidate (H)
Step 4 Increase the number of nodes.
set n [H]  n [H] + 1.
Step 5 Return value at the point of call
return (z).

Fibonacci-Heap-Union

Fibonacci-Heap-Union (H1, H2)

The above Function unites two fibonacci heaps H1 and H2 by simply concatenating their root lists. The new min [H] pointer points to the minimum key node of the resulting fibonacci heap H.
Step 1 Creating an empty fibonacci heap
set H  create-Fibonacci-Heap
Step 2 Initialization
set min [H]  min [H1]
Step 3 Concatenating the root list of H2 with root list of H
if (min [H1] = Nil or (min [H2]  Nil and min [H2] < min [H1])) then
set min [H]  min [H2]
Step 4 Addition of new nodes
set n [H]  n[H1] + n [H2]
Step 5 Free the objects H1 and H2, return value at the points of call
return (H)

Fibonacci-Heap-Insert

Fibonacci-Heap-Insert (H, x)

The above procedure inserts a node x in a given fibonacci heap H. The node x is added to the left of the min [H] pointer.
Step 1 Initialization
set deg [x]  0
set Parent [x]  Nil
set child [x]  Nil
set left [x]  right [x]  x
set mark [x]  FALSE.
Step 2 Concatenation of root list containing x with root list H.
if (min [H] = Nil or key [k] < key [min [H]) then
set min [H]  x
Step 3 Addition of new node
set n [H]  n [H] + 1

Bimomial-Heap-Delete

Bimomial-Heap-Delete (H, x)

The above procedure deletes node x's key from a given binomial heap. It uses operation ‘Binomial-Heap-Extract-Min’, and ‘Decrease-key’.
Step 1 Decreasing the key to – 
call to Decrease-key (H, x, – )
Step 2 Extracting the minimum key
call to Binomial-Heap-Extract-Min(H)

Decrease-key

Decrease-key (H, x, k)

The above Procedure decreases a key value of node x to the key ‘k’, in a given heap, H.
Step 1 Is greater ?
if (k > key [x]) then
message : “new key is greater than current key”.
else goto step 2
Step 2 Initialization
set key [x]  k
set y  x
set z  Parent [y]
Step 3 Adjusting the node at proper position, loop
while ((z  Nil) and (key [y] < key [z])
set key [y]  key [z]
set y  z
set z  Parent [y]
Step 4 Return at the point of all
return.

Binomial-Heap-Extract-Min

Binomial-Heap-Extract-Min (H)

The above function extracts a node with minimum key from the Heap. It uses ‘Binomial-Heap-Union’ operation.
Step 1 Finding ‘x’
First find the node ‘x’ having minimum key in the root list of H, and remove the node from the list.
Step 2 Creating an empty binomial heap.
H1  Create-Binomial-Heap (x)
Step 3 Adjusting pointers
reverse the linked list order of x's children, and set head [H1] as new head pointer.
Step 4 Uniting H and H1 binomial heaps.
H  Binomial-Heap-Union (H, H1)
Step 5 Return value at the point of call
return (x)

Binomial-Heap-Insert

Binomial-Heap-Insert (H, x)

The above Procedure inserts a node ‘x’ in a given binomial heap, ‘H’. It uses a ‘Binomial-Heap-Union’ operation for uniting the heap H, and heap H1 which contains the node ‘x’.
Step 1 Creating an empty Binomial heap.
set H1  Create-Binomial-Heap (x)
Step 2 Initialization
set Parent [x]  Nil
set Lchild [x]  Nil
set sib [x]  Nil
set deg [x]  0
set head [H1]  x.
Step 3 Uniting H and H1 binomial heaps.
H  Binomial-Heap-Union (H, H1)

Binomial-Heap-Union

Binomial-Heap-Union (H1, H2)

The above Function unites two binomial heaps, H1 and H2. It uses an auxiliary operation ‘Binomial Heap-Merge’, and operation ‘Binomial-Link’ for processing.
Step 1 Creating an empty Heap
set H  Create-Binomial-Heap (x)
Step 2 Merging both the binomial heaps
set head [H]  Binomial-Heap-Merge (H1, H2)
Step 3 Is empty ?
if (head [H] = NLL) then
message : “Empty”
return (H)
Step 4 Initialization
set Prex  Nil
set x  head [H]
set nextx  sib [x]
Step 5 Loop, managing nodes at proper position.
while (nextx  Nil)
if ((deg [x]  deg [nextx]) or (sib [next x]  Nil and deg [sib [nextx]] = deg [x])
then
set Prex  x
set x  nextx
else if (key[x]  key [nextx]) then
call to Binomial-Link (nextx, x)
else if (Prex = Nil) then
set head [H]  nextx
else
set sib [Prex]  next x
call to Binomial Link (x, nextx)
set x  nextx
set nextx  sib [x]
Step 6 return value at the point of call
return (H)

Heap Binomial-Link

Binomial-Link (y, z)

The above Procedure links Bk – 1 tree rooted at ‘y’ and Bk tree rooted at ‘z’. It makes ‘z’ the parent of ‘y’. By this Procedure node ‘z’ becomes the root of a Bk tree.
Step 1 Initialization, making parent.
set Parent [y]  z
Step 2 Making sibling of y to the left-child of z.
set sib [y]  Lchild [z]
Step 3 Making ‘y’ the left child to ‘z’
set Lchild [z]  y
Step 4 Increment the degree by 1
set deg [z]  deg [z] + 1

Binomial-Heap-Minimum

Binomial-Heap-Minimum (H)

The above Function obtains an element with minimum key value from the given binomial heap, ‘H’. The Function returns the pointer which points to the node having minimum key value.
Step 1 Initialization
set y  Nil
set x  head [H]
set min  
Step 2 Loop, obtaining minimum key value
whil (x  Nil)
if (key [x] < min) then
set min  key [x]
set y  x
set k  sib [x]
setting sibling
Step 3 Return at the point of call
return y.

Create-Binomial-Heap

Create-Binomial-Heap (x)

The above Function creates an empty binomial heap by setting head pointer to nil.
Step 1 Setting of pointers
set head [H]  nil
Setp 2 return value at the point of call
return (H)

Heap-Increase-key

Heap-Increase-key (H, i, k)

The above Procedure increases value of the element i's key with the new value ‘k’, which is assumed to be atleast as large as element i's current value.
Step 1 Is Smaller ?
If (k < H [i]) then
message :“new key ’k’ is smaller than current key”
return
else
goto step 2
Step 2 Adusting the new key ‘k’
set H [i]  k
loop
while (i > 1 and H [Parent (i) ] < H [i] )
set H [i]  H [Parent (i) ]
set i  Parent (i)
end loop
Step 3 return at the point of call
return

Heap Extract-Maximum

Heap Extract-Maximum (H)

The above Function removes and returns the element having largest key value from the given heap. The heap-size is decremented by 1 after removing the element. The Function calls ‘Heapify’ for fixing the new heap.
Step 1 Is empty ?
If (heap-size [H] < 1) then
message “underflow heap”
else
goto step 2
Step 2 Initialization, and adjusting the volues.
set max  H[1]
set H [1]  H [heap-size [H] ]
set heap-size [H]  heap-size [H] – 1
Step 3 fixing new heap
call to Heapify (H, 1)
Step 4 return value at the point of call
return (max)

Heap Insert

Insert (H, k)

The above procedure inserts an element with key value ‘k’ in a given maximum heap. The heap-size in incremented by 1 after the insertion of the element with key ‘k’.
Step 1 Incrementing the array size, assuming size does not exceed the maximum array size.
set heap-size [H]  heap-size [H] + 1
Step 2 initialization
set i  heap-size [H]
Step 3 loop, obtaining proper position
while (i > 1 and H [Parent (i)] < k
set H [i]  H [Parent (i)]
set i  Parent (i)
Step 4 Insertion
set H [i]  k
Step 5 return at the point of call
return

Build-Heap

Build-Heap (H)

The above Procedure builds up the heap in a bottom up manner by using Heapify. All array elements in a subarrray are all leaves of the tree. Thus, each leaf is a heap of size 1.
Step 1 Initialization
set heap-size [H]  length [H]
Step 2 fixing
for i  down to 1
call to Heapify (H, i)
Procedure Heap-sort (H)
The above procedure sorts the element of a given array using heap sort technique. The procedure makes a call to Build-Heap, and Heapify.
Step 1 Building
Call to Build-heap (H)
Step 2 loop, exchanging root, and fixing the heap.
for i  length [H] down to 2
set H [1]  H [i]
set heap-size [H] ¬ heap-size [H] – 1
call to Heapify (H, 1)
Step 3 return at the point of call
return

Heapify

Heapify (H, i)

The above Procedure fixes the heap for index ‘i’ where ‘i’ refers to the index such that the tree rooted at H[i] is a heap. This Procedure recursively calls itself until the given heap is fixed.
Step 1 Left child, and right child, initialization
set l  Lchild (i)
set r  Rchild (i)
Step 2 Place the maximum value, left child
if (l  heap-size [H] and H [l] > H[i]) then
set max  l
else
set max  i
Step 3 Place the maximum value, right child
if (r  heap-size [H] and H [r] > H [max]) then
set max  r
Step 4 Checking with parent
if (max  i) then
set H [i]  H [max]
Step 5 fixing of heap
Call to Heapify (H, max)

KMP-Matcher

KMP-Matcher (T, P)

The above procedure computes whether the given pattern P is present in the text string T or not. It uses auxiliary function ‘compute-prefix’ to compute Pf.
Step 1 Initialization
set n  length [T]
set m  length [P]
Calling Compute-Prefix
set Pf  Compute-prefix (P).
Numbers of characters matched
set q  0
Step 3 loop, scanning from left to right along text
for i  1 to n
while (q > 0 and P [q + 1]  T [i] )
set q  Pf [q]
no matching of next character
i f (P [q + 1] = T [i]) then
set q  q + 1
matching of next character
if (q = m) then
whether all character of P matched ?
display : “pattern occur with shift” i – m.
set q  Pf [q]
look for next match

Compute-Prefix (P)

Compute-Prefix (P)

The above Function Computes the prefix function, which determines the shifting of pattern matches within itself.
Step 1 Initialization
set m  length [P]
set Pf [1]  0
set k  0
Step 2 loop, computation of possible shifts
for q  2 to m
while (k> 0 and P[k + 1]  P [q])
set k  Pf [k]
if (P [k + 1] = P [q] ) then
set k  k + 1
set Pf [q] k
Step 3 return value at the point of call
return (Pf)

Rabin-karp-Match

Rabin-karp-Match (T, P, d, q)

The above procedure finds the pattern string P in the given text string T. The variable ‘d’ indicates the radix, and ‘q’ is some prime.
Step 1 Initialization
set n  length [T]
set m  length [P]
set h  dm– 1 mod q.
set P  0, to  0.
Step 2 Preprocessing of the string, loop
for i  1 to m
set P  (dp + P [i] ) mod q.
set to  (dto + T [i] ) mod q.
Step 3 Matching the pattern string
for S  0 to n – m
if (P = ts) then
if (P [1..m]  T[S + 1.... S + m] then
display : “occurrence of pattern with shift”
if ( S < n – m) then
set ts + 1  (d (ts – T [S + 1] h) + T [S + m + 1] ) mod q.
Step 4 return at the point of call.
return

Brute-Force-String Matching

Brute-Force-String Matching (T, P) :


The above Function finds the position of the first character of the pattern P in T if the pattern is present in T, otherwise it returns – 1.
Step 1 Initialization, loop
set n  length [T]
set m  length [P]
for i  0 to n-m
set i  0
while (j < m and P [j] = T [i + j] )
set j  j + 1
if (j = m) then
return i
Step 2 Return value at the point of call.
return – 1

Binary Tree Search

Btsearch (Bt, k)

The above Function searches the desired element from a given binary tree, and returns ‘true’ if matches. The pointer variable ‘Bt’ holds the address of the root node. Variable ‘k’ holds the key-value of the element to be searched. The Function works in a recursive manner. The structure of a node is same as described earlier.

Step 1 Is Empty ?
if (BtEmpty (Bt)) then
message : “Empty tree”
return false
Step 2 Root node is the node to be searched
if (data (Bt) = k) then
return true
Step 3 If key value is less than root
if (k < data (Bt)) then
return (Btsearch (Lchild (Bt), k))
Step 4 If key value is greater than root.
if (k > data (Bt)) then
return (Btsearch (Rchild (Bt), K))

Postorder Tree traversal

Procedure Postorder (Bt)

The above Procedure traveses a given binary tree using postorder traversal method. The pointer variable ‘Bt’ stores the address of the root node. The Node structure is same as described earlier. The Procedure traverses the binary tree in a recursive manner.
Step 1 Is empty ?
if (BtEmpty (Bt)) then
message : ‘‘Empty tree’’
return.
Step 2 Traverse the left subtree
if (Lchild (Bt)  NULL) then
call to postorder (Lchild (Bt))
Step 3 Travese the right subtree
if (Rchild (Bt)  NULL) then
call to postorder (Rchild (Bt))
Step 4 Process the root node
if (Bt  NULL) then
display : data (Bt)
Step 5 Return at the point of call
return.

code for part order travesal is given below :

void Postorder_Traversal (node*Bt)
{
if (Bt ! = NULL)
{
Postorder_Traversal (Bt  Lchild);
Postorder_Traversal (Bt  Rchild);
printf (“%d”, Bt  item);
}
}

Inorder Traversal

Procedure Inorder (Bt)

The above Procedure traverses the binary tree using Inorder traversal method, the pointer ‘Bt’ points to the root node. Node structure is same as discussed earlier. The Procedure traverses the binary tree in a recursive manner.
Step 1 Is empty ?
if (BtEmpty (Bt)) them
message : “Empty tree”
return
Step 2 Traverse the left sub-tree
if (Lchild (Bt)  NULL) then
call to Inorder (Lchild (Bt))
Step 3 Process the root node
if (Bt  NULL) then
display ; data (Bt)
Step 4 Traverse the right sub-tree
if (Rchild (Bt)  NULL) then
call to Inorder (Rchild (Bt)
Step 5 Return at the point of call



return


code is given below:

void Inorder_Traversal (node * Bt)
{
if (Bt ! = NULL)
{
Inorder_Traversal (Bt  Lchild);
prinft (“%d”, Bt  item)
Inorder_Traversal (Bt  Rchild);
}
}

Pre Order Traversal

Procedure Preorder (Bt)

The above Procedure traverses the binary tree using preorder traversal method. The pointers variable ‘Bt’ stores th address of the root node. The node structure is same as described before. The procedure traverses the binary tree in a recursive manner.
Step 1 Is empty ?
if (BtEmpty (Bt)) then
message : “Empty tree”
return
Step 2 Process the root node
if (Bt  NULL) then
display : (data (Bt))
Step 3 Traverse the left sub-tree
if (Lchild (Bt)  NULL) then
call to preorder (Lchild (Bt))
Step 4 Traverse the right sub-tree
if (Rchild (Bt)  NULL) then
call to preorder (Rchild (Bt))
Step 5 Return at the point of call
return
Equivalent C code for preorder traversing is given below:
void Preorder_Traversal (node * Bt)
{
if (Bt ! = NULL)
{
printf (“%d”, Bt  item);
Preorder_Traversal (Bt  Lchild);
Preorder_Traversal (Bt  Rchild);
}
}

Bucket Sort

Procedure Bucket Sort (A) :

The above procedure assumes that the input is an n-element array A, such that each element A [1] satisfies 0 £ A [i] <>


Step 1 Initialization
set n ¬ length [A]
Step 2 insertion at proper place, loop
for i ¬ 1 to n
insert element A [i] into list B [ ë n A [i] û ]
Step 3 sort the list, loop
for i ¬ 0 to n – 1
sort list B [i] using insertion sort.
Step 4 sorting, combining.
concatenate list B [0], B [1], .... B [n – 1] together in order.

Radix sort

Procedure Radix sort (A, d) :
The above procedure assumes that each element in the n-element array A has d digits, where digit 1 is the low order digit and digit d is the high order digit.

Step 1 Loop, internal sort.
for i ¬ 1 to d
perform stable sort to sort and Array A on digit i.