We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
My first solution was identical and it didn't pass testcase 12:
fromcollectionsimportdefaultdictfromsysimportstdin# clean and concise implementation that will fail on testcase 12# due to python wasting too much memory on deep chains# of characters.classNode(object):def__init__(self):self.children=defaultdict(Node)self.num_usage=0classTrie(object):def__init__(self):self.root=Node()defadd(self,word):node=self.rootforcharinword:node=node.children[char]node.num_usage+=1deffind(self,partial):node=self.rootforcharinpartial:ifcharnotinnode.children:return0node=node.children[char]returnnode.num_usagen=int(raw_input().strip())trie=Trie()fora0inxrange(n):op,contact=stdin.readline().strip().split()ifop=='add':trie.add(contact)elifop=='find':printtrie.find(contact)
The problem here is that python is allocating too much memory on storage container for each node (in your case it is list, in my case it is defaultdict, etc.). That is why on testcase it is throwing error because grader exceeds its memory limit. The solution for python guys is to notice that we add a lot of very long (len == 21) rare (occurs only once) words, however, when we try to find partial, the length of partial doesn't exceed 5 (it wasn't told in tutorial, I found it imperically looking into testacases). It reflects normal situation with words -> the deeper we are going into the trie the smaller frequency becomes for each node. So we are wasting a lot of memory on very deep chains in our trie.
One possible solution here is to store in the node the entire remaining suffix for each such long word if this suffix occurs only once. Only if we see this suffix again we split it into the usual trie structure. On example from the task it will be:
Such scheme allows to save memory by preserving whole suffix (like 'errank') instead of creating deep chain where on each level we would have to allocate storage container for children. This is a bit stupid for this task because this optimization doesn't change memory consumption on global scale in terms of O(n) notation. Personally, I think that the grader memory limit must be slightly increased for this task.
In case you wonder here is optimized solution:
fromcollectionsimportdefaultdictfromsysimportstdin# the whole stupid split suffix functionality# is only here because very rare long words will screw memory# consumption otherwiseclassNode(object):def__init__(self):self.val=''self.children=defaultdict(Node)self.num_usage=0@propertydefis_whole_suffix(self):returnself.num_usage==1@propertydefchildren_suffix(self):assertself.is_whole_suffix# meaningful only for whole suffixesreturnself.val[1:]defsplit_suffix(self):assertself.is_whole_suffix# meaningful only for whole suffixeschild=self.children[self.val[1]]child.val=self.val[1:]child.num_usage+=1defadd(self,char):ifself.is_whole_suffix:# preserve memory by concatinatingself.val+=char# characters in suffix if the wordreturnself# is used only oncechild=self.children[char]ifchild.is_whole_suffixandlen(child.val)>1:child.split_suffix()child.val=charchild.num_usage+=1returnchilddefget(self,char):assertself.has(char)# because defaultdict is usedreturnself.children[char]defhas(self,char):returncharinself.childrendefhas_same_suffix(self,rest_partial):assertself.is_whole_suffix# meaningful only for whole suffixesreturnself.children_suffix[:len(rest_partial)]==rest_partialclassTrie(object):def__init__(self):self.root=Node()defadd(self,word):node=self.rootforcharinword:node=node.add(char)deffind(self,partial):node=self.rootfori,charinenumerate(partial):ifnode.is_whole_suffix:rest_partial=partial[i:]returnint(node.has_same_suffix(rest_partial))ifnotnode.has(char):return0node=node.get(char)returnnode.num_usagen=int(raw_input().strip())trie=Trie()fora0inxrange(n):op,contact=stdin.readline().strip().split()ifop=='add':trie.add(contact)elifop=='find':printtrie.find(contact)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Tries: Contacts
You are viewing a single comment's thread. Return to all comments →
My first solution was identical and it didn't pass testcase 12:
The problem here is that python is allocating too much memory on storage container for each node (in your case it is list, in my case it is defaultdict, etc.). That is why on testcase it is throwing error because grader exceeds its memory limit. The solution for python guys is to notice that we add a lot of very long (len == 21) rare (occurs only once) words, however, when we try to find partial, the length of partial doesn't exceed 5 (it wasn't told in tutorial, I found it imperically looking into testacases). It reflects normal situation with words -> the deeper we are going into the trie the smaller frequency becomes for each node. So we are wasting a lot of memory on very deep chains in our trie. One possible solution here is to store in the node the entire remaining suffix for each such long word if this suffix occurs only once. Only if we see this suffix again we split it into the usual trie structure. On example from the task it will be:
Such scheme allows to save memory by preserving whole suffix (like 'errank') instead of creating deep chain where on each level we would have to allocate storage container for children. This is a bit stupid for this task because this optimization doesn't change memory consumption on global scale in terms of O(n) notation. Personally, I think that the grader memory limit must be slightly increased for this task.
In case you wonder here is optimized solution: