Hacker Rank: Counting names with prefix matches using a trie
up vote
2
down vote
favorite
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;
}
}
}
}
c# performance programming-challenge trie
add a comment |
up vote
2
down vote
favorite
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;
}
}
}
}
c# performance programming-challenge trie
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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;
}
}
}
}
c# performance programming-challenge trie
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;
}
}
}
}
c# performance programming-challenge trie
c# performance programming-challenge trie
edited Nov 18 at 7:15
t3chb0t
33.7k744108
33.7k744108
asked Nov 18 at 1:12
Luke Xu
1556
1556
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
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.
add a comment |
up vote
2
down vote
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 = '';
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).
Smart solution!
– Henrik Hansen
Nov 19 at 20:38
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
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.
add a comment |
up vote
2
down vote
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.
add a comment |
up vote
2
down vote
up vote
2
down vote
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.
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.
answered Nov 18 at 1:48
1201ProgramAlarm
2,9552821
2,9552821
add a comment |
add a comment |
up vote
2
down vote
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 = '';
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).
Smart solution!
– Henrik Hansen
Nov 19 at 20:38
add a comment |
up vote
2
down vote
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 = '';
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).
Smart solution!
– Henrik Hansen
Nov 19 at 20:38
add a comment |
up vote
2
down vote
up vote
2
down vote
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 = '';
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).
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 = '';
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).
edited Nov 19 at 20:34
answered Nov 19 at 19:02
tinstaafl
6,320727
6,320727
Smart solution!
– Henrik Hansen
Nov 19 at 20:38
add a comment |
Smart solution!
– Henrik Hansen
Nov 19 at 20:38
Smart solution!
– Henrik Hansen
Nov 19 at 20:38
Smart solution!
– Henrik Hansen
Nov 19 at 20:38
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f207888%2fhacker-rank-counting-names-with-prefix-matches-using-a-trie%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown