Trie in a Google Interview

The problem comes from Daily Coding Problem, here it is:

Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Implement a PrefixMapSum class with the following methods:

• insert(key: str, value: int): Set a given key's value in the map. If the key already exists, overwrite the value.
• sum(prefix: str): Return the sum of all values of keys that begin with a given prefix.

For example, you should be able to run the following code:

mapsum.insert("columnar", 3)
assert mapsum.sum("col") == 3

mapsum.insert("column", 2)
assert mapsum.sum("col") == 5

One way to solve this is to build a prefix trie in the following way:

1. Start with a simple trie implementation: hash table for the children nodes, the cumulative val, whether the node is a word, and the value of the word
2. When adding the word, set the cumulative along the way and check whether the current node is a word
3. If it is, make sure to return the word value in a ref variable to be dealt with later
4. In the outer code, when you're adding the word, if the word already exists (see #3), remove it from cumulative
5. The prefix cumulative call becomes straightforward

This leads to a O(2*Len(word))-time insert cost, and O(Len(prefix))-time cumulative cost. Code is below and right here on Git: https://github.com/BorisVasilenko/dailycodingproblem/blob/master/DailyCodingProbem05042019.cs

Cheers, ACC.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace DailyCodingProblem
{
    class DailyCodingProbem05042019
    {
        public void Process()
        {
            PrefixSumTrie pst = new PrefixSumTrie();
            pst.AddWord("foo", 5);
            pst.AddWord("foobar", 15);
            string prefix = "foo";
            Console.WriteLine("Cummulative for {0}: {1}", prefix, pst.Cummulative(prefix));
            pst.AddWord("foo", 15);
            Console.WriteLine("Cummulative for {0}: {1}", prefix, pst.Cummulative(prefix));
            pst.AddWord("foofighters", 100);
            Console.WriteLine("Cummulative for {0}: {1}", prefix, pst.Cummulative(prefix));

        }
    }

    class PrefixSumTrie
    {
        private Hashtable children = null;
        private bool isWord = false;
        private int cummulative = 0;
        private int wordVal = 0;

        public PrefixSumTrie()
        {
            children = new Hashtable();
            isWord = false;
            cummulative = 0;
            wordVal = 0;
        }

        public void AddWord(string word, int val)
        {
            int previousVal = -1;
            AddWord(word, val, ref previousVal);
            if (previousVal > 0)
            {
                RemoveWord(word, previousVal);
            }
        }

        public int Cummulative(string prefix)
        {
            if (String.IsNullOrEmpty(prefix))
            {
                return cummulative;
            }
            if (children.ContainsKey(prefix[0]))
            {
                return ((PrefixSumTrie)children[prefix[0]]).Cummulative(prefix.Substring(1));
            }
            return 0;
        }

        private void AddWord(string word, int val, ref int previousVal)
        {
            cummulative += val;
            if (String.IsNullOrEmpty(word))
            {
                if (isWord)
                {
                    previousVal = wordVal;
                }
                isWord = true;
                wordVal = val;
            }
            else
            {
                if (!children.ContainsKey(word[0]))
                {
                    children.Add(word[0], new PrefixSumTrie());
                }
                PrefixSumTrie child = (PrefixSumTrie)children[word[0]];
                child.AddWord(word.Substring(1), val, ref previousVal);
            }
        }

        private void RemoveWord(string word, int val)
        {
            if (cummulative > 0)
            {
                cummulative -= val;
            }
            if (!String.IsNullOrEmpty(word) && children.ContainsKey(word[0]))
            {
                ((PrefixSumTrie)children[word[0]]).RemoveWord(word.Substring(1), val);
            }
        }
    }
}