At first: This is a really nice question for an interview. You can show off your knowledge of data structures and algorithms here, but you can also demonstrate how familiar you are with your programming language and concepts like test driven development for example.
So, what went wrong here? At the first sight, your solution looks "ok". If you look a little closer, there are some issues:
Data Structures
You were pretty spot on when choosing a tree here. You could have done a little better by calling it with its common name, Trie. That comes from retrieval and is described in detail over here.
This data structure in its simplest form (we don't need any more for solving your problem) consists of trie nodes that have 1.) children where each child is assigned a character and 2.) a marker if this node is the last character of a word (so that we can distinguish a prefix of a word and a complete word).
You tried printing a graph as an example, which unfortunately got lost in formatting. Here is one from Wikipedia:
In your solution, you have used two HashSets (of TreeNodes and chars). I don't understand what the Index set is for, as you didn't include your code for adding nodes. The bigger problem I see here is the type HashSet itself: They describe unordered lists of stuff ("sets"), and you are trying to access them using an indexer (e.g. root.Nodes[str[currentIndex]]). This will not only give unpredicted results, it won't even compile. There is no indexer on HashSet.
What you actually want to use here is a Dictionary. Looking at the graph above, we seem to be navigating along using characters. That means, in every node, having one character we can determine the next node to go to. A dictionary can do that for us.
The whole thing
Rather than trying to come up with some working code during the interview, I would have talked about the architectural and algorithmic features of the to-be-built solution. I guess, if you had written out some unit tests that specify the behavior of the system it would have come out better than writing code that obviously won't even compile.
Let's see how we can easily build the whole thing using TDD (Test Driven Development), writing tests first and then bringing them from red to green by developing and refactoring our Trie.
Please create an empty Unit Test Project and create a new file in there. Add the NuGet package "FluentAssertions". You can paste each method stepwise to see how the solution matures. If there is a [TestMethod] attribute above, add it to the TrieTests class. If there is no attribute, add or update the method in TrieNode.
We start with:
[TestClass]
public class TrieTests
{
private readonly TrieNode trie = new TrieNode();
[TestMethod]
public void AddingDoesntThrow()
{
this.trie.Add("word");
}
}
public class TrieNode
{
public void Add(string blah)
{
throw new NotImplementedException();
}
}
Ok. We need to add stuff to the trie, so we have an Add. Test will be red. Update Add method:
public void Add(string blah)
{
}
Bam, test is green now. Next one! (Don't do more that you need to make your test green. Deleting the NotImplementedException is enough for now.)
[TestMethod]
public void FindEmptyString()
{
this.trie.Add("");
this.trie.Find("").Should().BeTrue();
}
public bool Find(string query)
{
throw new NotImplementedException();
}
Test is red.
public bool Find(string query)
{
return true;
}
Test is green! But wait. What if there is nothing in the trie?
[TestMethod]
public void FindInEmptyTrieReturnsFalse()
{
this.trie.Find("").Should().BeFalse();
}
Test is red, because we have no logic at all. Let's add the isWord boolean field and use it:
public class TrieNode
{
private bool isWord;
public void Add(string s)
{
if (s.Length == 0)
{
this.isWord = true;
}
}
public bool Find(string query)
{
if (query.Length == 0)
{
return this.isWord;
}
return false;
}
}
Okay, our trie works with empty strings! What happens if somebody passes null?
[TestMethod]
public void FindWithNullQueryThrows()
{
Action find = () => this.trie.Find(null);
find.ShouldThrow<ArgumentNullException>();
}
Test is red. We need to check the argument and throw an exception:
public bool Find(string query)
{
if (query == null)
{
throw new ArgumentNullException("query");
}
if (query.Length == 0)
{
return this.isWord;
}
return false;
}
Let's add support for real words now:
[TestMethod]
public void FindWordReturnsTrue()
{
this.trie.Add("word");
this.trie.Find("word").Should().BeTrue();
}
This is the tricky part. To make this work, we have to add the aforementioned dictionary of child nodes. Adding "word" creates child nodes for each character; finding "word" checks if the next child node exists and recurses down the tree: A trie node finds "word" if it has a child node "w" and this child node finds "ord".
public class TrieNode
{
private readonly Dictionary<char, TrieNode> children
= new Dictionary<char, TrieNode>();
private bool isWord;
public void Add(string s)
{
if (s.Length == 0)
{
this.isWord = true;
return;
}
var c = s[0];
var child = GetOrCreateChild(c);
child.Add(s.Substring(1));
}
private TrieNode GetOrCreateChild(char c)
{
TrieNode child;
if (!children.TryGetValue(c, out child))
{
child = new TrieNode();
children.Add(c, child);
}
return child;
}
public bool Find(string query)
{
if (query == null)
{
throw new ArgumentNullException("query");
}
if (query.Length == 0)
{
return this.isWord;
}
var c = query[0];
var child = this.GetChild(c);
return child != null && child.Find(s.Substring(1));
}
private TrieNode GetChild(char c)
{
TrieNode child;
return this.children.TryGetValue(c, out child) ? child : null;
}
}
We can even add further tests to check if everything works as expected:
[TestMethod]
public void FindLongerWordReturnsTrue()
{
this.trie.Add("word");
this.trie.Add("wording");
this.trie.Find("wording").Should().BeTrue();
}
[TestMethod]
public void FindPrefixReturnsFalse()
{
this.trie.Add("word");
this.trie.Find("wor").Should().BeFalse();
}
Both green already! Now we still have something to do: We need the wildcard support.
[TestMethod]
public void FindWithWildcardReturnsTrue()
{
this.trie.Add("word");
this.trie.Find("w??d").Should().BeTrue();
}
Instead of looking for one child node, a "?" means looking in all child nodes. We can generalize that: GetChild(char) gets renamed to GetChildren(char) and returns an IEnumerable:
public class TrieNode
{
private readonly Dictionary<char, TrieNode> children
= new Dictionary<char, TrieNode>();
private bool isWord;
public void Add(string s)
{
if (s.Length == 0)
{
this.isWord = true;
return;
}
var c = s[0];
var child = GetOrCreateChild(c);
child.Add(s.Substring(1));
}
private TrieNode GetOrCreateChild(char c)
{
TrieNode child;
if (!children.TryGetValue(c, out child))
{
child = new TrieNode();
children.Add(c, child);
}
return child;
}
public bool Find(string query)
{
if (query == null)
{
throw new ArgumentNullException("query");
}
if (query.Length == 0)
{
return this.isWord;
}
var c = query[0];
var child = this.GetChildren(c);
return child.Any(x => x.Find(query.Substring(1)));
}
private IEnumerable<TrieNode> GetChildren(char c)
{
if (c == '?')
return this.children.Values;
TrieNode child;
return this.children.TryGetValue(c, out child)
? new[] { child }
: Enumerable.Empty<TrieNode>();
}
}
You could add additional features like a collection of values for each trie node or prefix search, but I guess this simple implementation would have solved your question.
