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.

Generate database scripts from model classes by using Fluent NHibernate

Fluent NHibernate provides an approach to write model mappings in strongly typed C# code which gives you the benefits such as better readability, easier refactoring and compile-time checking. However, one thing you should be aware is that it still generates the NHibernate's stardand xml mapping files in the run time thereby it might give you a performance hit in some cases.

Any way, let's start a little journey in which we will create a small Visual Studio project with several simple domain models, the relevant mapping classes and the code to generate the MS SQL Server database scripts.

1. Create a C# console application project named "OrderingSystem".

2. In the project add reference to nhibernate.dll and fluentnhibernate.dll. You can download them from Fluent NHibernate or through NuGet. It is version 1.2 at the time of writing this post which is an open source software under BSD license.

3. In the project add a folder named "Domain". In the folder add a class file named "Name.cs" which contains the code of the value object Name. Please add the relevant usings and default namespaces.

public class Name
{
    public virtual string FirstName { get; set; }
    public virtual string LastName { get; set; }
}

4. Still in this folder added another class file named "Customer.cs" which represents the entity of Customer.

public class Customer
{
    public virtual Guid Id { get; set; }
    public virtual Name Name { get; set; }
}

5. Add other model classes in this folder.

public class Employee
{
    public virtual Guid Id { get; set; }
    public virtual string EmployeeId { get; set; }
    public virtual Name Name { get; set; }
}

public class Product
{
    public virtual Guid Id { get; set; }
    public virtual string Name { get; set; }
    public virtual decimal CostPrice { get; set; }
    public virtual DateTime AddedDate { get; set; }
}

public class OrderItem
{
    public virtual Guid Id { get; set; }
    public virtual Product Product { get; set; }
    public virtual int Quantity { get; set; }
    public virtual Order Order { get; set; }
}

public class Order
{
    public virtual Guid Id { get; set; }
    public virtual Customer Customer { get; set; }
    public virtual Employee Employee { get; set; }
    public virtual IList Items { get; set; }
    public virtual DateTime Date { get; set; }
}

We have created six domain model classes which contains one value object and five entities. The models we created only contain properties and they don't have any behaviors. Since the purpose of this post is about generating the database scripts from models and their mappings so let's keep it simple and move one.

6. In the project add another folder called "Mapping". In this folder add a map file named "NameMap.cs" for the value object "Name" with default namespace. If you have installed ReSharper then it will prompt you to add correct usings in the file.

public class NameMap : ComponentMap<Name>
{
    public NameMap()
    {
        Map(n => n.FirstName).Not.Nullable();
        Map(n => n.LastName).Not.Nullable();
    }
}

7. In the folder add a map file named "CustomerMap.cs" for the entity "Customer".

public class CustomerMap : ClassMap<Customer>
{
    public CustomerMap()
    {
        Id(c => c.Id).GeneratedBy.GuidComb();
        Component(c => c.Name);
    }
}

From the above two mappings we can see that because of the beauty of strongly typed C# it is very readable and concise.

8. Let's add the rest mapping files.

public class EmployeeMap : ClassMap<Employee>
{
    public EmployeeMap()
    {
        Id(e => e.Id).GeneratedBy.GuidComb();
        Map(e => e.EmployeeId).Not.Nullable();
        Component(e => e.Name);
    }
}

public class ProductMap : ClassMap<Product>
{
    public ProductMap()
    {
        Id(p => p.Id).GeneratedBy.GuidComb();
        Map(p => p.Name).Not.Nullable();
        Map(p => p.CostPrice).Not.Nullable();
        Map(p => p.AddedDate).Not.Nullable();
    }
}

public class OrderItemMap : ClassMap<OrderItem>
{
    public OrderItemMap()
    {
        Id(i => i.Id).GeneratedBy.GuidComb();
        References(i => i.Product).Not.Nullable();
        Map(i => i.Quantity).Not.Nullable();
        References(i => i.Order).Not.Nullable();
    }
}

public class OrderMap : ClassMap<Order>
{
    public OrderMap()
    {
        Id(o => o.Id).GeneratedBy.GuidComb();
        References(o => o.Customer).Not.Nullable();
        References(o => o.Employee).Not.Nullable();
        HasMany(o => o.Items).Inverse();
        Map(o => o.Date).Not.Nullable();
    }
}

We have finished creating the models and mappings. So far so simple. Press F6 and make sure it builds successfully.

9. Open Microsoft SQL Server Management Studio and log in to the local database server with Windows Authentication. Create a database named "OrderingSystem".

10. In the project create a class file named "DbScriptBuilder.cs" which contains the code for generating the database script file.

using System.Text;
using FluentNHibernate.Cfg;
using FluentNHibernate.Cfg.Db;
using NHibernate.Tool.hbm2ddl;
using OrderingSystem.Domain;

namespace OrderingSystem
{
    public class DbScriptBuilder
    {
        private const string ConnString = "server=(local);database=OrderingSystem;Integrated Security=SSPI;";

        public void Build(string filePath)
        {
            var sb = new StringBuilder();
            var config = Fluently.Configure()
                .Database(MsSqlConfiguration.MsSql2008.ConnectionString(ConnString))
                .Mappings(m => m.FluentMappings.AddFromAssemblyOf())
                .BuildConfiguration();

            var exporter = new SchemaExport(config);
            exporter.Create(s => sb.Append(s), false);

            using (var writer = new StreamWriter(filePath))
            {
                writer.WriteLine(sb);
                writer.Flush();
            }
        }
    }
}

If you use SQL Server Express then please change "server=(local)" to "server=.\\SQLEXPRESS".
11. Open program.cs and add code into the Main method

var fileName = string.Format(@"c:\temp\OrderingSystem_{0}.sql",
    DateTime.Now.ToString("yyyy_MM_dd_hh_mm_ss"));

new DbScriptBuilder().Build(fileName);
Console.WriteLine("Finished generating script file.");

12. Press F6 and make sure it builds the project successfully. Press Ctl+F5 and you should be able to see the text "Finished generating script file." from the screen.

13. Go the the folder c:\temp and find the sql script file just generated. Open it in SSMS and run it in database OrderingSystem. Congratulations! You have successfully generated the tables and their relationships from the models and mapping classes without writing any sql code!

Source code download >>

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.