Implement a MapSum class with insert, and sum methods.
For the method insert, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.
For the method sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.
Example 1: Input: insert("apple", 3), Output: Null Input: sum("ap"), Output: 3 Input: insert("app", 2), Output: Null Input: sum("ap"), Output: 5
Please comment on performance and style
using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace TrieQuestions
{
[TestClass]
public class TrieMapSum
{
[TestMethod]
public void MapSumTest()
{
MapSum mapSum = new MapSum();
mapSum.Insert("apple", 3);
Assert.AreEqual(3, mapSum.Sum("ap"));
mapSum.Insert("app", 2);
Assert.AreEqual(5, mapSum.Sum("ap"));
}
}
public class MapSum
{
private TrieMSNode Head;
/** Initialize your data structure here. */
public MapSum()
{
Head = new TrieMSNode();
}
public void Insert(string key, int val)
{
var current = Head;
foreach (var letter in key)
{
if (!current.Edges.ContainsKey(letter))
{
current.Edges.Add(letter, new TrieMSNode());
}
current = current.Edges[letter];
}
current.IsTerminal = true;
current.Value = val;
}
public int Sum(string prefix)
{
int sum = 0;
var current = Head;
foreach (var letter in prefix)
{
if (!current.Edges.ContainsKey(letter))
{
return sum;
}
current = current.Edges[letter];
}
// we use dfs for each edges of the trie;
return DFS(current);
}
private int DFS(TrieMSNode current)
{
if (current == null)
{
return 0;
}
int sum = current.IsTerminal ? current.Value : 0;
foreach (var edge in current.Edges.Values)
{
sum += DFS(edge);
}
return sum;
}
}
internal class TrieMSNode
{
public Dictionary<char, TrieMSNode> Edges { get; set; }
public bool IsTerminal;
public int Value;
public TrieMSNode()
{
Edges = new Dictionary<char, TrieMSNode>();
IsTerminal = false;
Value = 0;
}
}
}