Return to Question

We're going to make our own Contacts application! The application must perform two types of operations:

• add name, where is a string denoting a contact name. This must store as a new contact in the application.

• find partial, where is a string denoting a partial name to search the application for. It must count the number of contacts starting with and print the count on a new line.

Given sequential add and find operations, perform each operation in order.

We're going to make our own Contacts application! The application must perform two types of operations:

• add name, where is a string denoting a contact name. This must store as a new contact in the application.

• find partial, where is a string denoting a partial name to search the application for. It must count the number of contacts starting with and print the count on a new line.

Given sequential add and find operations, perform each operation in order.

I have been trying to solve this HackerRank problem. What I came up is this

class TrieNode():
 def __init__(self):
 self.children = {}
 self.word_count = 0
class Trie():
 def __init__(self):
 self.root = self.get_node()
 def get_node(self):
 return TrieNode()
 def add(self, key):
 crawl = self.root
 for char in key:
 if char not in crawl.children:
 crawl.children[char] = self.get_node()
 crawl = crawl.children[char]
 crawl.word_count += 1
 def get_prefix(self, key):
 crawl = self.root
 for char in key:
 if char not in crawl.children:
 return None
 crawl = crawl.children[char]
 return crawl
 def find(self, key):
 node = self.get_prefix(key)
 return node.word_count if node else 0

The code above is a modification of this from GeeksForGeeks. The modifications that I have done are keeping a word_count for every trie node. This denotes how many words start with the prefix ending in that node's letter. The other modification is using a hashmap to keep children rather than lists.

On HackerRank, 9/11 test cases pass, and the other 2 timeout. I can't figure out where I can optimize this further.

I know of a radix tree that is an optimized version of a normal trie, but that saves on space, rather than time, so I haven't explored that option.

Can anyone help me figure out where I can optimize for time in my code?

Thanks!

I have been trying to solve this HackerRank problem:

We're going to make our own Contacts application! The application must perform two types of operations:

• add name, where is a string denoting a contact name. This must store as a new contact in the application.

• find partial, where is a string denoting a partial name to search the application for. It must count the number of contacts starting with and print the count on a new line.

Given sequential add and find operations, perform each operation in order.

What I came up is this

class TrieNode():
 def __init__(self):
 self.children = {}
 self.word_count = 0
class Trie():
 def __init__(self):
 self.root = self.get_node()
 def get_node(self):
 return TrieNode()
 def add(self, key):
 crawl = self.root
 for char in key:
 if char not in crawl.children:
 crawl.children[char] = self.get_node()
 crawl = crawl.children[char]
 crawl.word_count += 1
 def get_prefix(self, key):
 crawl = self.root
 for char in key:
 if char not in crawl.children:
 return None
 crawl = crawl.children[char]
 return crawl
 def find(self, key):
 node = self.get_prefix(key)
 return node.word_count if node else 0

The code above is a modification of this from GeeksForGeeks. The modifications that I have done are keeping a word_count for every trie node. This denotes how many words start with the prefix ending in that node's letter. The other modification is using a hashmap to keep children rather than lists.

On HackerRank, 9/11 test cases pass, and the other 2 timeout. I can't figure out where I can optimize this further.

I know of a radix tree that is an optimized version of a normal trie, but that saves on space, rather than time, so I haven't explored that option.

Can anyone help me figure out where I can optimize for time in my code?

Thanks!