Recently in Interview Coding Category

Here's another question that is often asked, reversing a string in C.  I think most people can get through this one easily, creating a temporary char variable and swapping the first and last values.  However, I came across a slight optimization to this method:

char *strrev2(char *s,int n)
{
       int i=0;
       while (i<n/2)
       {
           //uses the null character as the temporary storage,
           // for the front character.
           *(s+n) = *(s+i);
           // swap the front and last character.
           *(s+i) = *(s + (n - i -1));
           // put the front character in n-1 position.
           *(s+n-i-1) = *(s+n);
           i++;
       }
       // tie off the string with the NULL character.
       *(s+n) = '\0';
       return s;
}
char* strrev(char* s)
{
       return strrev2(s, strlen(s));
}

With this example, you don't need a temporary variable.  You use the char at the end of the string, the one that holds the NULL (\0) character that marks the end of the string.  Just remember to put the NULL character back when you are done.

A slight twist: afterward, the interviewer may ask you how to reuse this code to reverse a sentence.  This is why I wrote strrev2.  I won't write the code that does this, but here's the general algorithm:

1. Call strrev to reverse the entire string at one time.
2. Take the new string, parse the tokens separated by whitespace and delimeters.
3. Reverse each token inside the reversed sentence string.
4. The result should be a perfectly reversed string.

Converting a string to an integer is another classic interview question.  I was asked this one during my Microsoft interview in 1991 and I was so nervous I butchered it badly.  I still remember sweating bullets even now, almost twenty years later.  Fortunately, the manager took pity and allowed me to play a debugging exercise where I discovered the mistakes I had made.

The function atoi is shorthand for ascii to integer.  You call it like this:

    int fooval = atoi("123");

It can be written in a few lines of code, but it hinges on your awareness of the Ascii table.  ASCII stand for American Standard Code for Information Interchange; it’s the fundamental building block that allows computers to exchange information.  There are codes for uppercase alphanumeric characters (A-Z) in the range 65-90, and the lowercase alphanumeric characters (a-z) in the range 97-122.  Numerals 0-9 are in the range 48-57.  Your knowledge of the Ascii table can help you not only with these interview coding exercises, but many others as well.

Another concept that will aid you is the knowledge of how C works with character pointers:

char* index = "123";

The index variable is a pointer, but it points at the first character in the char string (1).  If you increment the index, it will point at the next char value (2).  You can determine when you’ve reached the end of the string by testing the value to see if it is the NULL character, \0.  All C strings are terminated by this value.  You have to remember to look for the NULL character when searching C strings, and if you are creating a new string, you have to remember to place that at the end.

Now that we are armed with this knowledge, we can write atoi:

int atoi( char* pStr ) 
{
  int iRetVal = 0; 
 
  if ( pStr )
  {
    while ( *pStr && *pStr <= '9' && *pStr >= '0' ) 
    {
      iRetVal = (iRetVal * 10) + (*pStr - '0');
      pStr++;
    }
  } 
  return iRetVal; 
}

This implementation starts off by clearing out iRetVal with 0.  In case the string is NULL or empty, the return value will be 0.  We loop through the string, looking for numeric characters.  When we encounter one, we determine the integer value (*pstr - ‘0’) and add that iRetVal.  iRetVal gets multiplied by 10 to make the correct scale value.  Note that the first time around, iRetVal is 0.  Finally, we increment the char index to move to the next character in the string.

This is pretty simple and straightforward, although it isn’t perfect.  What if there is a negative sign in the string (“-123’).  Whenever you write code during an interview, it won’t be perfect.  It’s important to be able to identify weaknesses and bugs in your code to the interviewer.

The reverse function for integer to ascii, itoa, is a bit more complex.  I was asked to write this just a couple of years ago during an interview.  Funny enough, the engineer who asked me to write it was an ex-Microsoft engineer.  I solved it correctly for a default case where the number is base 10.  He showed me a way to write it for base 10, base 16, or any base value.  You will call itoa like this:

    printf("itoa(123) = %s\n",itoa(123));

This is the default way of calling itoa.  The return value is “123” which is output by the printf function.  But, as this ex-Microsoft engineer asked me, what if we wanted to output the hexadecimal value, “7b”?  You would call an overloaded itoa function like this, with the base (16 for hexadecimal) like this:

    printf("itoa(123) = %s\n",itoa(123, 16));

Now let’s write the function.  We will actually write two functions here.  If you do this during interview, you will score extra points.  First the itoa function that takes the base as the second parameter:

char *itoa(int n, int b) 
{
    static char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz";
    int i=0, sign;
    char *s = new char[100];
    
    if ((sign = n) < 0)
        n = -n;

    do {

        s[i++] = digits[n % b];

    } while ((n /= b) > 0);

    if (sign < 0)

        s[i++] = '-';

    s[i] = '\0';

    return strrev(s);

}

And now the default itoa function, which assumes the most common case, where we call it for base 10 numbers:

char *itoa(int n) 
{
    return itoa(n, 10);
}

This itoa function with the base parameter makes use of a character array called digits.  This array contains the values 0-9, followed by the lowercase alphanumeric values a-z.  These values will be used for the individual characters in the return string value:

    static char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz";

The first thing we need to do is check the sign of the number we need to convert.  Is it less than 0?  If so, we’ll need to remember this for later.

Now we do a tight compact loop through number n:

    do {
        s[i++] = digits[n % b];
    } while ((n /= b) > 0);

The char string holding the return value starts getting the individual digits chopped off number n.  We chop them off using the modulus operator: %.  When b is set to 10 and n is 123, n % b becomes 123 mod 10.  The value of that mod is 3.  Index 3 inside the digits array is the character ‘3’.

The loop prunes the digits off the number n.  N gets reduced (by the base number) as the loop goes on with the expression “n /= b”.  When N is 123, the first time through this loop, it becomes 12.

Let’s picture what happens to the return char string s and integer n as the loop progresses:

First pass:  n = 12, s = “3”

Second pass: n = 1, s = “32”

Third pass: n = 0, s = “321”

The loop terminates when n reaches 0.  Now we take a look at the sign value.  If the number was negative, we had the char minus sign (1).  Don’t forget to mark the end of the string with the NULL character as I mentioned previously.

Now we almost have the return string value, except it is in reverse.  You can call strrev to reverse it back to the proper form and return the value.

This may lead into writing a function to reverse a string value…which I will write next time.

Here's a classic interview whiteboard exercise: reversing a singly linked list.  This was extremely popular in the 1980s and 1990s, because C/C++ were the most popular languages at that time.  You had to have a basic knowledge of pointers, linked lists, allocating/deallocating memory, etc, and you could guarantee that this question would be asked.  But as we've moved into languages liked Java and C#, which provide advanced functionality to manage the heap with garbage collection, and especially with C#'s use of generic collections in .NET Framework 2.0, most of us have pleasantly forgotten about the drudge work in managing linked lists.  But it's still a valid interview question, though when you are asked, it's like getting hit with an arctic blast of wind.

I will present a solution in C, perhaps not the perfect one, as there are many approaches.

First of all, let's define a Node structure that is the building block of the linked list:

// Node structure representing a single item in the list.
struct node
{
    node(char val) {a = val;}
    char a;
    node* next;
};

This is a very simple Node structure, it contains a single char, and a pointer to the next node in the linked list.  The constructor takes a char value so we can construct the object and set the value at the same time.  You want to keep this simple during the interview.  You could create a C++ solution to this problem, using templates, but that could take much longer.

Let's create a linked list, four nodes, with the values ABCD.  It won't be necessary for you to write this code during the interview, but just in case you were born after 1980 and never saw a linked list constructed before, here it is:

    // Test revlist with a list of 4 items, abcd.
    node* head = NULL;
    node* node1 = new node('a');
    head = node1;
    node* node2 = new node('b');
    node1->next = node2;
    node* node3 = new node('c');
    node2->next = node3;
    node* node4 = new node('d');
    node3->next = node4;
    node4->next = NULL;

Now let's write the function that reverses this list.  There are a few ways to do it.  One way is to loop through the list, create a temporary node pointer, and swap node pairs until you get to the end.  That's perfectly valid, yet when I see this type of problem, I think about using recursion, which is how I tried to address it:

// Reverse a singly linked list.
// Take the head of the list and return the new head of
// the reversed list.
node* revlist(node* head)
{
    node* ptr = head;
    node* newHead = NULL;
    // if the list is empty, return NULL, or
    // if the list has only 1 item, return that item.
    if ((ptr == NULL) ||  (ptr->next == NULL))
    {
        return ptr;
    }
    // Linked list has 2 or more items.
    // Are we at the end of the list?
    if (ptr->next->next != NULL)
    {
        // no, keep traversing the list until the end.
        newHead = revlist(ptr->next);
    }
    else
    {
        // the new head of the list is the last item.
        newHead = ptr->next;
    }
    // next item points to the previous item.
    ptr->next->next = ptr;
    // previous item is now the tail, it points to NULL.
    ptr->next = NULL;
    // return the head of the reverse linked list.
    return newHead;
 }

This is pretty straightforward.  The function starts at the head of the singly linked list and returns the new head of the reversed linked list.  It does not leave the original list untouched.  For that, we would need to make a copy, but we're trying to keep this solution simple.

Let's examine this section by section.  The first if-statement is vital:

    // if the list is empty, return NULL, or
    // if the list has only 1 item, return that item.
    if ((ptr == NULL) ||  (ptr->next == NULL))
    {
        return ptr;
    }

If the linked list has 0 items, the head ptr is NULL.  We must detect this and return NULL.  Alternatively, if this list has only 1 node, there's nothing to reverse.  We must detect this and return back that node to the caller.

    // Linked list has 2 or more items.
    // Are we at the end of the list?
    if (ptr->next->next != NULL)
    {
        // no, keep traversing the list until the end.
        newHead = revlist(ptr->next);
    }

This if-statement uses recursion to traverse the linked list all the way to the last two nodes.  If the list is ABCD, the first time this function is called, it's looking at B->next and detecting if that is NULL.  Since it is not, it calls revlist again, with B as the head of the list.  It will be called another time, pointing to C as the head of the list.

    else
    {
        // the new head of the list is the last item.
        newHead = ptr->next;
    }

When C is the head, the else clause will be executed.  At this point, we are at the next to last node in the linked list.  The new head of the reversed linked list will be the last node in the original list.  C->next points to D.  The D node will be the new head.

    // next item points to the previous item.
    ptr->next->next = ptr;
    // previous item is now the tail, it points to NULL.
    ptr->next = NULL;

Now that we've found the head of the reverse list, it's time to start swapping nodes.  The first time we execute this code ptr is really the C node.  C points to D, the tail of the list.  Now we swap them.  D points to the previous node, C.  C points to NULL, because it is now the tail.  As the recursive stack unwinds, the rest of the list is reversed:

ptr == C, C -> D, swap, reversed list is D -> C

ptr == B, B -> C, swap, reversed list is D -> C -> B

ptr == A, A -> B, swap, reversed list is D -> C -> B -> A

Finally, we need to return the new head of the reversed linked list:

    // return the head of the reverse linked list.
    return newHead;

This seems obvious, but a mistake could be made in the previous if-statement if you don't set newhead in the recursive call.  Once the last node in the old linked list is found, it is returned through the recursive stack.

As I said at the beginning of this article, this isn't the only way to reverse a linked list.  There are many other approaches that are probably more efficient.

Programmers and software developers must undergo a series of tests and trials during their interview process before they are judged worthy.  During a phone screen you typically get questions that test your basic knowledge of Windows, C# and .NET Framework, and if you pass that stage you are invited for an in-person interview.  During that interview, at least one person on the development team will ask you to go to the whiteboard and write some code.  Joel on Software has some pretty good guidelines on what sort of code a candidate will write.

It's a great technique for detecting if the person really is a coder/programmer and not a poser.  (Or, as one of my college professors once said, to weed out the Spicolis.)  Whenever my company is hiring someone, myself or someone on my team will make the candidate perform this coding exercise.

However, when I am the candidate, I look forward to whiteboard coding about as much as a trip to the dentist.  I actively dread the moment when someone says, go to the whiteboard and write some code.  I feel a certain pain in my mind, akin to that dreaded pinch when the dentist injects Novocain into my mouth.  When I arrive at the whiteboard, my mind goes blank.  My knees feel weak.  I feel as if I suddenly belong in the marketing group.  Only I'm not thin or attractive enough to work in marketing.

Therefore, to overcome this fear, I've started collecting all kinds of interview whiteboard coding examples, and will share them with you here.  Most of the code you will see here is not the code I wrote during my interview.  But even if the interview went well or it was a disaster, I went home and tried to write the code when I was more relaxed.

I review these examples before going into a new interview.  I don't memorize the code per se; I do remember the general pattern of the solution and stumble through it on the whiteboard.

I'll be writing several articles in the weeks ahead, but this post will keep an index of all whiteboard code, which will be written in C:

Interview Coding: Fibonacci sequence

Interview Coding: Reversing a Singly Linked List in C

Interview Coding: atoi, itoa in C

Interview Coding: Reverse a string in C

Writing a function that returns the nth number in a Fibonacci sequence can either be the easiest interview whiteboard question or the hardest.  If you're like me, your daily activities revolve around events, delegates, background threads, data grid views, custom controls, or reading about some new area of C# and .NET that you've never encountered before.  A strange sequence of numbers stuns you like a phaser on Star Trek.  Even worse, you've probably heard of Fibonacci during your days at the University or in other interviews, but you just can't recall what it is.

If you're unfamiliar with Fibonacci, the interviewer will usually prep you by giving you a list of the first few numbers:

0 1 1 2 3 5 8 13 21

The interviewer should explain the most obvious property of the Fibonacci sequence: each number is the sum of the previous two numbers, if N > 1.  1 is the sum of 0+1, 2 is the sum of 1+1, 3 is the sum of 2+1, etc.  There are other properties of the Fibonacci sequence, which you can read about on this Wikipedia article.

You will be asked to write a function that returns the result of Fib(n).  The Wikipedia article explains clearly, if N > 1, the Fibonacci result is F(n-1) + F(n-2).  If you see this, you can almost write the code, but it may not be explained to you in this fashion.  The interviewer may tell you that Fib(1) == 1, and Fib(5) == 5.  How can that be?  It's helpful to think of the Fibonacci sequence in an array, starting at index 0:

Now you can see, ironically enough, that Fib(5) is 5, but there's a logical reason, it's at index 5.  Fib(4) doesn't equal 4, it equals 3, because it is the 4th (after 0) in the sequence.  Once you understand that, you can start to write the code:

int fib(int n)
{
    if (n <= 1)
        return n;

    return fib(n-1) + fib(n-2);

}

This is the preferred way to write a Fibonacci function, because it uses recursion.  If N is 0 or 1, that value will be returned.  If N is greater than 1, the fib function calls itself recursively, not once, but twice, with the 2 previous numbers in the sequence, n-1 and n-2.  If you call this with N set to 2, then fib will call itself twice with fib(1) and fib(0), which will return 1 and 0, and the sum will be 1.  It works like this for any higher value as well.

The wrong approach would be to set the Fibonacci sequence in a pre-defined array, and going to the Nth index and returning the value there.  But the interviewer will point out that the sequence can go on infinitely and you could never set down all the values.

This is not a perfect function.  If the numbers are negative, a negative value is returned.  You can argue that there will be a buildup of recursive stack values (if N is 10000 the stack will be enormous), or that we are losing performance by making two recursive calls in one function.

Why is recursion the preferred method?  It makes the code simple and easy to understand.  If you look at the Fibonacci definition in the Wikipedia article, the code above resembles that pseudocode definition almost perfectly.  You've solved the problem in the fewest lines of code.  We always hope to hire programmers who can deliver elegant solutions to complex problems.