Archive for December, 2017

A Simple Trie Implementation Via C#

    public class Trie
    {
        private TrieNode RootNode { get; set; }

        public Trie()
        {
            RootNode = new TrieNode('^', 0, null);

        }

        public void Insert(string s)
        {
            var commonPrefix = GetPrefix(s);
            var current = commonPrefix;

            for (var i = current.Depth; i < s.Length; i++)
            {
                var newNode = new TrieNode(s[i], current.Depth + 1, current);
                current.ChildNodes.Add(newNode);
                current = newNode;
            }

            current.ChildNodes.Add(new TrieNode('$', current.Depth + 1, current));
        }

        public TrieNode GetPrefix(string word)
        {
            var current = RootNode;
            var result = current;

            foreach (char c in word)
            {
                current = current.FindChildNode(c);
                if (current == null)
                {
                    break;
                }
                result = current;
            }
            return result;
        }
    }
public class TrieNode
{
    private char Value { get; set; }
    public List<TrieNode> ChildNodes { get; set; }
    private TrieNode Parent { get; set; }
    public int Depth { get; set; }

    public TrieNode( char value, int depth, TrieNode parent)
    {
        ChildNodes = new List<TrieNode>();
        Parent = parent;
        Value = value;
        Depth = depth;
    }

    public bool IsLeaf()
    {
        return ChildNodes.Any();
    }

    public TrieNode FindChildNode(char c)
    {
        TrieNode node = null;

        foreach (var variable in ChildNodes)
        {
            if (variable.Value == c)
            {
                return variable;
            }

        }
        return node;
    }
}


Sort a String containing R, G and B Dutch National Flag Problem

        public string SortAnArrayInParticularOrder(string input)
        {
            if (string.IsNullOrEmpty(input))
            {
                Console.WriteLine("input string in Empty or null"); return string.Empty;
            }
            var values = input.ToLowerInvariant().ToCharArray();

            Console.WriteLine("Before");
            Console.WriteLine(string.Join(",", values));
            Debug.WriteLine("Before :" + string.Join(",", values));
            int[] count = { 0, 0, 0 };
            char[] charOrder = { 'R', 'G', 'B' };
            int i = 0;

            while (i < values.Length)
            {
                switch (values[i])
                {
                    case 'r':
                        count[0]++;
                        break;
                    case 'b':
                        count[2]++;
                        break;
                    case 'g':
                        count[1]++;
                        break;
                }
                i++;
            }
            int tempCount = 0;

            for (i = 0; i < charOrder.Length; i++)
            {
                tempCount += count[i];
            }
            if (tempCount < charOrder.Length)
            {

                Console.WriteLine("Input String is not valid");
                return "";

            }
            int k = 0;

            List<char> resultList = new List<char>();
            for (i = 0; i < 3; ++i)
            {
                for (int j = 0; j < count[i]; ++j)
                {
                    resultList.Add(charOrder[i]);
                }
            }
            Console.WriteLine("After");
            Console.WriteLine(string.Join(",", resultList));
            Debug.WriteLine("Before : " + string.Join(",", values));
            Debug.WriteLine("After : " + string.Join(",", resultList));
            return string.Join("", values);
        }