Interview Coding: Fibonacci function

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:

F0	F1	F2	F3	F4	F5	F6	F7	F8
0	1	1	2	3	5	8	13	21

 

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.

Interview Coding: Reverse a string in C

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.

Interview Coding: atoi, itoa in C

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.

C# Coding Shortcuts: IsNullorEmpty, Path object, BackgroundWorker, MethodInvoker.

I once heard Chris Sells (in a podcast with Scott Hanselman) mention that the .NET Framework is so vast, that he was constantly uncovering objects/methods that he had already written himself.  Here's a few things that I discovered during the past year, thanks to my co-workers (Andy, Jon, Geoff).  Some of these items are so simple that I was embarrassed not to know about them.  Here is the list:

1.  The simple string.IsNullOrEmpty method. 

if (string.IsNullOrEmpty(imageFileName))
   return false;

Before I encountered this, I was always writing C++ style tests like "if (string != null) && (if string.Length > 0)".  Doing both in one shot is a great piece of shorthand.

2.  The powerful Path object. 

Path.GetDirectoryName(filePathName);

One of the first things I did in C# was to port over a number of C++ methods that dissected a path string, chopping off the extension, returning the folder path, etc.  A nice exercise, but it was totally unnecessary.  The Path object has the following methods: GetDirectoryName, GetExtension, GetFileName, GetFileNameWithoutExtension.

3.  The beautiful BackgroundWorker object.

public class PSPUnpackWorker : BackgroundWorker 
{
    public PSPUnpackWorker()
    {
        WorkerReportsProgress = true;
        WorkerSupportsCancellation = true;
        DoWork += PSPUnpackWorker_DoWork;
    }

Have you ever wanted to perform a task in a background thread?  You can easily spawn off a worker thread on your own by creating a Thread object and calling Start.  But what if you wanted your worker thread to raise an event, to tell you it's completed step X out of 100?  And perhaps hook up this data to a progress bar control?

Don't do it the hard way, the .NET Framework is all setup to accommodate this pattern already with the BackgroundWorker object.

The ComicShowControllerDemo in the Crystal Toolkit has an example of a BackgroundWorker communicating to a ProgressBar control.  First, as shown above, I derive my own specialized class from the BackgroundWorker.  In the constructor, I set the properties in base class to true, WorkerReportsProgress and WorkerSupportsCancellation.  The former property allows me to call the ReportProgress method.  The control containing the ProgressBar can subscribe to the ProgressChanged event of the background worker and determine the percentage of completion.

PSPUnpackWorker _unpackWorker = new PSPUnpackWorker();
_unpackWorker.ProgressChanged += unpackWorker_ProgressChanged;
_unpackWorker.RunWorkerCompleted += unpackWorker_RunWorkerCompleted;
_unpackWorker.RunWorkerAsync();

When RunWorkerAsync is called, the DoWork method inside PSPUnpackWorker is executed:

void PSPUnpackWorker_DoWork(object sender, DoWorkEventArgs e)
{
    foreach (CrystalImageItem imageItem in Collector.GridModel)
    {
        if (CancellationPending)
        {
            e.Cancel = true;
            return;
        }        
        ....
        if (CanRaiseEvents)
        {
            float percent = ((float)++index/(float)Collector.GridModel.Count)*100f;
            int percentDone = Convert.ToInt32(percent);
            ReportProgress(percentDone);
        }
    }
    e.Result = true;
}

Inside the DoWork method, you can perform whatever tasks are required in the background worker.  I've sandwiched these between checking to see if a cancel action was requested at the beginning, and reporting the progress at the end.

4.  The mighty MethodInvoker object.

_imageForm.Invoke(new MethodInvoker(delegate
 {
     _viewerMain.SetImageInfo(imageInfo);
     _viewerMain.ToolTipText = imageItem.ToolTipText;

     SetScale();
 }));

In Windows Forms programming, you often encounter the problem of needing to update the controls on the main form, running in the main UI thread.  If you try to update these controls without using Invoke or BeginInvoke, you will no doubt encounter an error such as "Cross-thread operation not valid: Control X accessed from a thread other than the thread it was created on."

You could take the main Windows Form, test InvokeRequired, and then call Invoke or BeginInvoke.  You would have to create a delegate and pass this as a parameter.  The delegate would take care of calling the controls on the main form.

There's an easier way: use an Anonymous method, coupled with the MethodInvoker (as shown above).  Using this technique, it's like creating an inline delegate.  The code inside the delegate has access to the outerscope variables, such as imageInfo.  It's another great piece of shorthand.

When the code inside the delegate portion becomes too large, I will place them inside a new method, and call that method within the MethodInvoker:

ImageGridView.BeginInvoke(
    new MethodInvoker(delegate
    {
        InitInitialImageImp(index, ignoreGroupHeader);
    }));

You can find some other interesting tips about MethodInvoker and using invoke with UI controls on TimL's .NET Blog.

Converting from uint to a Hexadecimal string value in C#

Here's a short but useful static funtion: converting a uint into a properly formatted hexadecimal string value in C#.

public static string ConvertToHexString(uint value)
        {
            StringBuilder builder = new StringBuilder("0x");
            builder.Append(Convert.ToString(value, 16).PadLeft(8, '0'));
            return builder.ToString();
        }

This is pretty self-explanator, but the ToString method on Convert takes an optional second parameter for the base, which we sit to base 16 for the hexadecimal string value.  If you run this test code:

string test = ConvertToHexString(177);

The hex string value for 177 returned is: 0x000000b1.  The PadLeft method after the ToString call gives us the leading zeroes.  Without PadLeft, all we would see is 0xb1.

Interview Coding: Reversing a Singly Linked List in C

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. 

Let's create a linked list, three nodes, with the values ABC.  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, abc.
    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;
    node3->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. 

// Reverse a singly linked list.
// Take the head of the list and return the new head of
// the reversed list.
node* revlist_simple(node* head)
{
// init the return value (new head) to null
node *ret = NULL;
// walk thru the existing list.
// let's say it's a -> b -> c
while (head != NULL) 
{
// tmp = a, b, c
node *tmp = head;
// head = b, c, null
head = head->next;
// a->next = null
// b->next = a
// c->next b
tmp->next = ret;
// ret = a
// ret =b
// c
ret = tmp;
}
// now the list is:
// c-> b -> a -> null
// return the head of the reverse linked list.
return ret;
}

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.

Thank you to the commenter who suggested this much simpler approach, rather than the first clunky way I tried to do it.