Interview Question: What is Stack Overflow?

Q: What is Stack Overflow?
A: It is a website many people seeking answers from. It is created by the guy writes blogs on Joel on software...

Q: Hang on, I am not asking the website StackOverflow.com and I am not interested in who the hell created it. I am asking Stack, space, Overflow.
A: Ah I see, the Stack Overflow. What is Stack Overflow? It is, stack, hmmm, overflows. In another way, the stack blows out.

Q: Why would it blow out, I mean, overflow?
A: It overflows simply because too much stuff put into the stack while more things are being put in it. Think about last time you blew out a balloon.

Q: Can't remember I ever did that ... anyway, how could it happen, say, in .Net?
A: In .Net normally it happens when it tries to do a recursion too deeply. By default in .Net application running on Windows the stack size is 1 MB. Because of the nature of recursion the method invokes itself repeatedly and each invoke creates a stack frame and each stack frame contains a set of local variables. When it reaches 1 MB and it tries to add another stack frame it throws StackOverflowException.

Q: How can you prevent it from happening, say, you have a very deep tree and you need to traverse it?
A: Of cause a easy solution is to increase the stack for the thread. From .net 4.0 you can define a stack size larger than 1 MB in the Thread constructor, assuming you have the full trust of the code. But this is a bad solution because normally you wouldn't be able to know how big size you need thereby it is still possible to blow it up. If it is a very large tree then we can use the class Stack, which is allocated in the heap, to push and pop the nodes. Here is an example:

public IEnumerable<Node> Iterate(Node rootNode)
{
    if (rootNode == null) yield break;

    var stack = new Stack<Node>();
    stack.Push(rootNode);

    while (stack.Any())
    {
        var currentNode = stack.Pop();
        yield return currentNode;

        if (currentNode.Left != null) stack.Push(currentNode.Left);
        if (currentNode.Right != null) stack.Push(currentNode.Right);
    }
}

public class Node
{
    public string Name { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
}

Q: What is tail-call recursion?
A: Tail-call recursion is a special case of recursion, in which the last call returns the value immediately. In this case since every call is just simply returns a value which gets from the call it calls thereby we can optimize it by using the same stack frame rather than creating a new one. Sometimes we call it tail-call optimization. Functional languages support this but not C# or CLR until .net 4.0 CLR in a 64bit Windows, which might be optimized by the jitter.

Interview Question: What is Singleton pattern and its implementation in C#?

The other day I talked to my college who just came back from interviewing a candidate. During the conversation he mentioned that he asked the candidate to write some code to implement the Singleton pattern. This reminded me an excellent post from Jon Skeet: Implementing the Singleton Pattern in C#.

It is a very common pattern that you might see it everyday, for example, ServiceLocator. For the basic purpose it is simple: the class only only has one instance at a time.

class Singleton
{
    private Singleton()
    {
    }

    private static Singleton _instance;

    public static Singleton Instance
    {
        get
        {
            if (_instance == null)
                _instance = new Singleton();

            return _instance;
        }
    }
}

The implementation does two things:
1. sets the constructor to private thereby nowhere else outside of the class can instantiate the class.
2. exposes an instance of itself by a public static property; if the instance does not exist yet, instantiates one.

If there is only one thread runs the code then this simple implementation is good enough. But when there are multiple threads and concurrency happens multiple threads can jump into the _instance = new Singleton() and create multiple instances thereby violates the pattern's purpose. In this case we just need to add a lock to prevent multiple threads jumping into the line of code.

class Singleton
{
    private Singleton()
    {
    }

    private static Singleton _instance;
    private static readonly object _locker = new object();

    public static Singleton Instance
    {
        get
        {
            lock(_locker)
            {
                if (_instance == null)
                    _instance = new Singleton();

                return _instance;
            }
        }
    }
}

You might be concerned that every time it accesses the instance it locks the locker which is a bit more expensive. But in the commercial projects I have ever done it did not cause any performance issue. If still concerns you then the double-checked locking trick could be helpful (here it is only about C# implementation).

In some cases you might need lazyness. The implementation with Lazy<T> is quite elegant

class Singleton
{
    private Singleton()
    {
    }

    private static Lazy _lazy = new Lazy(() => new Singleton());

    public static Singleton Instance
    {
        get { return _lazy.Value; }
    }
}

and it is thread safe. Lazy<T>() or Lazy<T>(Func<T>) are thread safe because by default it uses LazyThreadSafetyMode.ExecutionAndPublication mode which provides thread safety. It has thread unsafe way though such as Lazy<T>(false) , Lazy<T>(LazyThreadSafetyMode.None) and Lazy<t>(Func<T>, LazyThreadSafetyMode.None). Maybe in single thread application you can use the thread unsafe ones and gain some performance benefits. Other than that I can't think of any real-life situations I need them.