On 08/14/2008 I had a technical phone interview with Microsoft Dynamics. It was perhaps my worst interview experience :(... To facilitate the interview process, a LiveMeeting meeting was set up as well.
The interview was scheduled to begin at 6pm CST and last an hour. At about 5:15pm, I powered my notebook to make sure that I wouldn't have any Windows updates asking me to restart the computer during the interview (after all, I had not checked for updates the day prior and it was the week of Patch Tuesday). Sure enough, as soon as Windows started, updates were automatically installing and 15 minutes later I was rebooting. By 5:35pm, I launched LiveMeeting and shortly thereafter I was online and ready.
I received the phone call just a minute or two after the scheduled start time. I'm not sure whether the proper etiquette allows me to reveal the name of my interviewer or not, so I will withhold the name. The interviewer had a pleasant demeanor although I had difficulty understanding him because of a somewhat strong Asian accent (I would guess Indian). [This is probably a good thing because that would prepare one for working at such diverse workplace as Microsoft :) ]. This was further aggravated by phone interference that was mostly resolved after the interviewer called me back. Initially, I had a bluetooth headset so that both of my hands would be uninhibited but with poor quality of phone reception I switched to my handset to remedy that. So, I ended up spending most of the interview holding my handset using my right shoulder as I needed both of my hands to type.
After exchanging greetings, the interviewer asked me some questions about what I had been working on lately and the types of applications that I was working with. After that, he asked me to write some code. I opened Notepad and shared it via LiveMeeting. I was asked which programming language I preferred, to which I emphatically replied, "C#". The interviewer asked me if I could write C++, which I declined since I had not written any C++ code in more than 7 years (since college). I was then asked to write a function to reverse a singly-linked list.
By this point, I was already somewhat unsettled as I was not mentally prepared to write code using Notepad while someone else was watching and potentially scrutinizing my every key stroke. I started writing the function by assuming that there is a LinkedList and a LinkedListNode definition. I verbalized my assumption and was asked to write the class definition. I created the two definitions and then said that I probably did not need a definition for LinkedList since having a reference to the first node was sufficient to work with a linked list. The interviewer asked why I would want a LinkedList defined, to which I replied that LinkedList would contain helper methods (I also alluded to the fact that the generic linked list implementation in .NET 2.0 had a class definition for LinkedList). What I didn't say was that the "Reverse" function should probably be encapsulated within the LinkedList class.
Then, I moved on to implementing the function. By this point, I was quite unsettled... I have never written code to reverse a linked list but I didn't think it would be challenging. As I got to my implementing my loop, I began to panic... Questions like "Is it as easy as I think it is or is there a catch?", "Do I need an inner loop?" and "Do I need only two variables or three?" went through my mind. I was verbalizing some of my thoughts processes, which made me even more unsettled because I knew that everything I said could count against me. I spent more than 30 minutes (I didn't time it but I think it might have been close to 45-50) working on the function. By 6:50pm, I knew I wouldn't finish because I still had to step through my code to make sure that it was working correctly (and that takes longer than using VS debugger!). Roughly at 7:10, the interview ended. The interviewer said the recruiter would follow up with me.
I was distraught... I couldn't solve a fairly straightforward problem! I wouldn't be surprised if I end up on Microsoft's "cannot-solve-a-simple-problem" list :).
I had dinner while still working on the problem mentally. After relaxing a little bit, I went back to the problem. I decided to implement the same algorithm as I was working on during the interview. I spent about 5-10 minutes drawing the solution on paper before writing any code (which I should have done during the interview but I felt really awkward doing it since the interviewer couldn't see me drawing -- I felt compelled to type something to let the interviewer know that I haven't given up). I also opened Visual Studio so that I could actually run and step through the code. In about 20-30 minutes I had the program finished and tested using a simple console application.
I thought I'd post my code here (please feel free to comment on it):
class Program
{
static void Main(string[] args)
{
// create a test list
LinkedList list = new LinkedList();
for (int i = 1; i <= 10; i++)
{
LinkedListNode node = new LinkedListNode();
node.Value = i;
list.AppendLast(node);
}
// print list before reversal
LinkedListNode currentNode;
Console.WriteLine("List before reversal:");
currentNode = list.First;
while (currentNode != null)
{
Console.WriteLine(currentNode.Value);
currentNode = currentNode.Next;
}
Console.WriteLine();
list.Reverse();
// print list after reversal
Console.WriteLine("List after reversal:");
currentNode = list.First;
while (currentNode != null)
{
Console.WriteLine(currentNode.Value);
currentNode = currentNode.Next;
}
Console.WriteLine("Press ENTER to end program");
Console.ReadLine();
}
public class LinkedList
{
public LinkedList()
{
}
private LinkedListNode _firstNode;
/// <summary>
/// Gets the first node in the list.
/// </summary>
public LinkedListNode First
{
get
{
return _firstNode;
}
}
/// <summary>
/// Appends the node at the beginning of the list.
/// </summary>
/// <param name="node">The node to append.</param>
public void AppendFirst(LinkedListNode node)
{
if (_firstNode == null)
_firstNode = node;
else
{
node.Next = _firstNode;
_firstNode = node;
}
}
/// <summary>
/// Appends the node at the end of the list.
/// </summary>
/// <param name="node">The node to append.</param>
public void AppendLast(LinkedListNode node)
{
// if the list is empty, set the first node
// and do nothing
if (_firstNode == null)
_firstNode = node;
else
{
LinkedListNode currentNode = _firstNode;
// get to the last node
while (currentNode.Next != null)
currentNode = currentNode.Next;
// currentNode is now referencing the last node
currentNode.Next = node;
}
}
/// <summary>
/// Reverses the list so that the last node becomes the first
/// node in the list.
/// </summary>
public void Reverse()
{
LinkedListNode currentNode = _firstNode, tempNode = null, firstNode = null;
// traverse and reverse
while (currentNode != null)
{
tempNode = currentNode.Next;
currentNode.Next = firstNode;
firstNode = currentNode;
currentNode = tempNode;
}
// set the first node
_firstNode = firstNode;
}
}
public class LinkedListNode
{
public LinkedListNode()
{
}
private int _value;
private LinkedListNode _next;
public int Value
{
get
{
return _value;
}
set
{
_value = value;
}
}
public LinkedListNode Next
{
get
{
return _next;
}
set
{
_next = value;
}
}
}
}
