INTERVIEW JOB CODING TASKS – Calculate Tree depth and a number of leaves4 min read

Season 1 – Prologue

So… You want to get that developer job, right?

You are preparing (or not) yourself and You pass all the “theory” questions. And then You are assigned more stuff to do…You get a bunch of coding tasks to complete. It seems so exhausting and daunting to do. It takes time and You are probably working somewhere and have a life of course. But the future employer doesn’t care and wants You to complete these tasks so You can be evaluated.

Well, to make your future interviews a little bit less stressful, I’ll share some of the most common interview coding tasks with You!

So You can, yes – You guessed it, have a life also and not just worry about some XYZ employer results. Which, if you are lucky, will give you some feedback after the whole process and will not behave like a black hole in a universe (like, thanks for the input, but completely lacks the output / their response).

I really don’t know if anyone of you were “victims” of a bad future wannabe employer, in a sense that they disrespected your precious time. Like having a marathon 5+ hours interview and then looping it for a few days and finally when this exhausting marathon is over, they don’t give you any response. Or worse, they say like: “Oooh, great! Everything looks fine and perfect, we think you are a match! We will give you an offer for sure.” and then nothing. Days passed, weeks passed, months passed and still nothing! And You are like wtf!?

I know for sure these things happen. It happened not just to me, but also to a bunch of guys I know!

So to spare your precious time I’ll be sharing coding tasks with you.

Please feel free to send me your coding tasks and I will gladly solve them for you.

Let’s make together a solid base of possible interview coding tasks so we can ease life for future developer interviews.

Task 1: Find the depth of a tree and the number of leaves for a defined “path” in an existing tree.

We have an already defined tree like this one:

Each element of this string array is representing a node. Parent node is defined as a element in a row, followed by other node which is parent node of the next node. Root element is defined by “-1”.

So, root element is 5, and it is a parent to 6, 2 and 0 nodes. Node 2 is parent to 1 and 3. Node 1 is parent to 4.

If you enter in command prompt: “your_compiled_app.exe 5 2 5 2 1 -1 5 0” result is going to be:

Tree height: 3 Number of leaves: 4

Let’s get to the business – show me the code

Model:

public class TreeNode<T>
{
    public T Data { get; set; }
    public TreeNode<T> Parent { get; set; }
    public List<TreeNode<T>> Children { get; } = new List<TreeNode<T>>();
}

Extensions:

public static class StringArrayExtensions
{
    public static List<int> ConvertArrayOfStringsToListOfIntegers(this string[] array)
    {
        return Array.ConvertAll(array, int.Parse).ToList();
    }
}

public static class TreeNodeExtension
{
    public static int TreeHeight<T>(this TreeNode<T> root, int depth)
    {
        var result = depth;
​
        foreach (var node in root.Children)
        {
            result = Math.Max(result, TreeHeight(node, depth + 1));
        }
​
        return result;
    }
​
    public static int LeafCount<T>(this T rootNode, Func<T, IEnumerable<T>> childrenF)
    {
​
        return EnumerateLeaves(rootNode, childrenF).ToList().Count;
    }
​
    private static IEnumerable<T> EnumerateLeaves<T>(this T rootNode, Func<T, IEnumerable<T>> childrenF)
    {
        var children = childrenF(rootNode);
​
        var hasChildren = children != null && children.Any();
​
        if (!hasChildren)
        {
            yield return rootNode;
        }
        else
        {
            foreach (var node in childrenF(rootNode))
            {
                foreach (var child in EnumerateLeaves(node, childrenF))
                {
                    children = childrenF(child);
                    hasChildren = childrenF(child) != null && children.Any();
                    if (!hasChildren)
                    {
                        yield return child;
                    }
                }
            }
        }
    }
}

Main program:

static void Main(string[] args)
    {
        if (args.Length <= 0) return;
​
        var indexList = args.ConvertArrayOfStringsToListOfIntegers();
​
        var unLinkedTreeNodes = new List<TreeNode<int>>();
​
        for (var i = 0; i < indexList.Count; i++)
        {
            unLinkedTreeNodes.Add(new TreeNode<int>(){ Data = i });
        }
        
        TreeNode<int> rootNode = null;
        var linkedTreeNodes = new List<TreeNode<int>>();
​
        linkedTreeNodes = unLinkedTreeNodes;
​
        for (var index = 0; index < indexList.Count; index++)
        {
            var nodeName = indexList[index];
​
            var isRootNode = (nodeName == -1);
​
            if (isRootNode)
            {
                var parent = unLinkedTreeNodes[index];
                rootNode = parent;
            }
            else
            {
                var unlinkedNode = unLinkedTreeNodes[index];
                unlinkedNode.Parent = linkedTreeNodes.FirstOrDefault(n => n.Data == nodeName);
​
                linkedTreeNodes.FirstOrDefault( n => n.Data == nodeName)?.Children.Add(unlinkedNode);
            }
        }
​
        var treeHeight = rootNode.TreeHeight(0);
        var leafCount = rootNode.LeafCount(root => root.Children);
​
        Console.WriteLine($"Tree height: {treeHeight}");
        Console.WriteLine($"Tree number of leaves: {leafCount}");
​
        Console.ReadLine();
    }

Conclusion

This is only the beginning. More to come soon. If you have any questions regarding this, feel free to message me, mail me etc..

As stated before, feel free to send me your coding tasks and I will gladly solve them for you.

Let’s make together a solid base of possible interview coding tasks so we can ease life for future developer interviews.