2
\$\begingroup\$

Practicing hacker rank questions and would love some feedback on how I could perform optimizations on a Trie.

This code will add a bunch of names into a trie and then when asked will turn how many names belong to a partial match. eg.

jenn, jennifer, george, jenny

partial => jen
return => 3
using System;
using System.Collections.Generic;
using System.IO;

namespace ConsoleApplication1
{
    class Solution
    {
        static void Main(String[] args)
        {
            int N = Int32.Parse(Console.ReadLine());
            string[,] argList = new string[N, 2];
            for (int i = 0; i < N; i++)
            {
                string[] s = Console.ReadLine().Split();
                argList[i, 0] = s[0];
                argList[i, 1] = s[1];
            }

            Trie trie = new Trie();

            for (int i = 0; i < N; i++)
            {
                switch (argList[i, 0])
                {
                    case "add":
                        trie.add(argList[i, 1]);
                        break;
                    case "find":
                        Console.WriteLine(trie.find(argList[i, 1]));
                        break;
                    default:
                        break;
                }
            }
        }
    }

    class Trie
    {
        private readonly Trie[] _trieArray = new Trie[26];
        private int _findCount = 0;
        private bool _data = false;
        private char _name;
        private int _occurances = 0;

        public void add(string s)
        {
            s = s.ToLower();
            add(s, this);
        }

        private void add(string s, Trie t)
        {
            char first = Char.Parse(s[0].ToString());
            int index = first - 'a';

            if (t._trieArray[index] == null)
            {
                t._trieArray[index] = new Trie {_name = first};
            }

            if (s.Length > 1)
            {
                add(s.Substring(1), t._trieArray[index]);
            }
            else
            {
                t._trieArray[index]._data = true;
            }

            t._trieArray[index]._occurances++;
        }

        public int find(string s)
        {
            s = s.ToLower();
            find(s, this);

            int ans = _findCount;
            _findCount = 0;
            return ans;
        }

        private void find(string s, Trie t)
        {
            if (t == null)
            {
                return;
            }
            if (s.Length > 0)
            {
                char first = Char.Parse(s[0].ToString());
                int index = first - 'a';
                find(s.Substring(1), t._trieArray[index]);
            }
            else
            {
                _findCount = t._occurances;
            }
        }

    }
}
\$\endgroup\$
2
\$\begingroup\$

You don't validate your input. If the user enters a string with no space in it, you'll get an exception.

s[0] is a character, so why do you convert it to a string to convert it back to a character?

You should avoid allocating _trieArray until you need it. Otherwise you'll allocate a bunch of memory you don't use (in all your leaf nodes).

You don't need to use _findCount. Your private find method can just return that value.

As an additional exercise, rewrite add to not be recursive, and avoid making all those (sub)string copies.

\$\endgroup\$
2
\$\begingroup\$

Some additional points:

To me it is easier to deal with if you separate the Trie from it's nodes. To this end a Node class would help.

Instead of using an array, I think you can get better performance by using a Dictionary<char,Node> to hold the children of each node.

Using a separate Node class gives you the option to optimize your prefix count by keeping a count of each word that has the prefix up to that point.

A Trie class with a Node class using a Dictionary could look something like this:

class Trie
{
    private class Node
    {
        public char value = '\0';
        public int wordCount = 0;
        //public Node parent = null; for future use
        public Dictionary<char, Node> children = new Dictionary<char, Node>();

        public Node() { }
        public Node(char value)
        {
            this.value = value;
        }
        public Node AddChild(char value)
        {
            Node temp = new Node();
            if (!children.TryGetValue(value,out temp))
            {
                temp = new Node();
                children.Add(value, temp);
                //children[value].parent = this;
            }
            temp.wordCount++;
            return temp;
        }
    }
    private readonly Node root = new Node();

    public Trie() { }

    public void AddWord(string word)
    {
        Node temp = root;
        foreach (char c in word)
        {
            temp = temp.AddChild(c);                
        }
    }
    public int prefixCount(string prefix)
    {
        Node temp = root;
        foreach (char c in prefix)
        {
            if (!temp.children.TryGetValue(c,out temp))
            {
                return 0;
            }
        }
        return temp.wordCount;
    }

}

A solution could look like this:

public static void RunSolution(TextReader sin,TextWriter sout )
{
    int lines = int.Parse(sin.ReadLine());
    Trie contacts = new Trie();
    for(int line = 0; line < lines; ++line)
    {
        var instructions = sin.ReadLine().Split(' ');
        switch(instructions[0])
        {
            case "add":
                {
                    contacts.AddWord(instructions[1]);
                    break;
                }
            case "find":
                {
                    sout.WriteLine(contacts.prefixCount(instructions[1]));
                    break;
                }
            default:
                {
                    throw new InvalidDataException("no op code");
                }
        }
    }
}

With this all Trie operations become O(n) the length of the string, since any lookups are close to O(1).

\$\endgroup\$
  • \$\begingroup\$ Smart solution! \$\endgroup\$ – Henrik Hansen Nov 19 '18 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.