rshaghoulian Java solution - passes 100% of test cases
I use a Trie.
If your tests are hanging/timing out/not finishing, you likely need a faster algorithm.
I keep a "size" at each node that keeps track of how many complete words can be made from that node. This makes my runtime faster since I don't have to recalculate the number of valid words from a node.
import java.util.Scanner; import java.util.HashMap; public class Solution { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); Trie trie = new Trie(); for (int i = 0; i < n; i++) { String operation = scan.next(); String contact = scan.next(); if (operation.equals("add")) { trie.add(contact); } else if (operation.equals("find")) { System.out.println(trie.find(contact)); } } scan.close(); } } /* Based loosely on tutorial video in this problem */ class TrieNode { private HashMap<Character, TrieNode> children = new HashMap<>(); public int size; public void putChildIfAbsent(char ch) { children.putIfAbsent(ch, new TrieNode()); } public TrieNode getChild(char ch) { return children.get(ch); } } class Trie { TrieNode root = new TrieNode(); Trie(){} // default constructor Trie(String[] words) { for (String word : words) { add(word); } } public void add(String str) { TrieNode curr = root; for (int i = 0; i < str.length(); i++) { Character ch = str.charAt(i); curr.putChildIfAbsent(ch); curr = curr.getChild(ch); curr.size++; } } public int find(String prefix) { TrieNode curr = root; /* Traverse down tree to end of our prefix */ for (int i = 0; i < prefix.length(); i++) { Character ch = prefix.charAt(i); curr = curr.getChild(ch); if (curr == null) { return 0; } } return curr.size; } }
From my HackerRank Java solutions.
kruti_bliss11 Awesome! but does it pass all test cases?
rshaghoulian Yes
stani_frolov Great tip with keeping a numbers variable at each node. thanks!
rshaghoulian [deleted]
parthshorey It doesnt work. it breaks at putIfAbsent. is this Java 7 or 8?
rshaghoulian Hi. The code works in Java 8.
singhamitch Thanks that helped me
devfactor That made a huge difference. The run time for the longest test cases (3 and 4 I think) comes down from ~4 seconds to ~ 0.3 seconds! Thank you.
triforcetron [deleted]
aleathorn I did the same. Here is my C++ solution. I probably could have come up with a better class name. What to name thing is always the challenge, isn't it?
class Words { public: Words() {} int fullCountUnder; bool isFullWord; map<char, Words*> m; void insert(string text) { Words* word = this; word->fullCountUnder++; for (char &c : text) { Words* prev = word; word = word->has(c); if (word == NULL) { Words * newWord = new Words(); prev->m.insert(pair<char, Words*>(c, newWord)); word = newWord; } word->fullCountUnder++; } if (word != this) { word->isFullWord = true; } } Words* has(char c) { map<char, Words*>::iterator it = this->m.find(c); if (it != this->m.end()) { return it->second; } return NULL; } int matchCount(string partial) { Words* word = this; for (char& c : partial) { word = word->has(c); if (word == NULL) { return 0; } } return word->fullCountUnder; } };
jattilah Your constructor needs to initialize fullCountUnder.
aleathorn You're right! I'm surprised it worked.
fei_overney In C++, the data members get automatically initialized in the (default) constructor, in this case, fullConutUnder = 0; isFullWord = false; and m is create with size 0
aleathorn Thanks for this. I see that it is initializing these values as you mentioned, but I couldn't find any documentation on whether or not this would always be the case. Obviously it's best to be safe, in case something changes, so I'm curious if this is a feature or a byproduct of how things currently work. Any ideas?
fgleeson68 In modern c++ (c++11,14,17 and so on) there is uniform initialization rules. It is a good habit to use the curly braces {} to specify either default construction (as was happening accidentally in your case) or supply params if using a different constructor. You can do this right in the header file when you declare the variable and avoid adding ugly initialization clauses just before the constructor body as was needed in the past. Although the default constructor will still save you using the curly braces makes your intention more clear to programmers reading your code.
class A { A() = default; private: bool isWord{}; };
naseef_ur_rahman You could replace
map<char, Words*>::iterator it
with
auto it
yl125 I think you can use recursion and it makes the class much simpler. Here is what I did with my class.
class Node{
public: map<char, Node> children; bool isCompleteWord; int words; Node() {isCompleteWord = false; words = 0;} void addContact(string s) { words++; if (s.size() == 0) { isCompleteWord = true; } else { children[s[0]].addContact(s.substr(1)); } } int find(string s) { if (s.size() == 0) { return words; } else { return children[s[0]].find(s.substr(1)); } }};
f_hajirostami Also based on your implementation, there's no need for a default constructor / the Trie(String[] words) method
rshaghoulian Actually it's still needed. Since a non-default constructor was created, Java requires that we create a default constructor as well. If you remove it and try to run the code, you will see that it will fail.
f_hajirostami I did on java 8 and it worked fine
rshaghoulian I should have been clearer: Since my code says:
Trie trie = new Trie();
then I need do define a default constructor since one is not going to be defined for me (since I created a constructor with 1 parameter). I can however remove the line above (or replace it with something else), and then I will be able to remove my default constructor as well. Let me know if you have any other questions.
apontejose Thanks for the words counter tip. That made a huge difference.
Lesson: If your program is timing out, find out the main performance issue and find a way to mitigate it.
arpita_dessai Thank you. Maintaining "size" at each node helped. I was using a (redundant) queue to traverse the trie and then calculate, and that was turning to be very expensive.
coviedodlt Awesome dude, thanks for the tip.
yashpandya212 Thanks a lot. It helps me to programme the code in python.
hartleymack [deleted]rshaghoulian I tested it just now, and it works. Please make sure you are using Java 8.
rnatesan21 not a big deal... for simplicity you could have used: for (char c:str.toCharArray()) for (char c:prefix.toCharArray()) { instead of
for (int i = 0; i < str.length(); i++)
and
for (int i = 0; i < prefix.length(); i++)
rshaghoulian (char c:str.toCharArray())
does make the code look cleaner, but it may make slower since we have to convert the String to a character array before traversing it.
timiareola thank you. i couldnt have done this porblem without your help. her tutorial video didnt do much for me at all. im still a little lost about your solution but with a couple extra run throughs, i should be able to figure it out. Thanks!
Quazar777 how does your algorithm differentiate between the first and second 'h's of 'hackathon'?
rshaghoulian For add, the algorithm just builds the Trie h-a-c-k-a-t-h-o-n.
For find, let's say we're trying to find "h", well it starts at the root of the Trie and searches from there, so it doesn't start at the 2nd h.
maxim_marchal Simple, but clever! This solved my timeouts. Thanks!
vishwa_bhat19 Hi rshaghoulian,
A small doubt here.. in the add method the following two lines of code are confusing me a bit:
curr = curr.getChild(ch); curr.size++;
Why are we incrementing the size variable of the child, shouldn't we be increasing the size variable of the parent?
Shouldn't it be :
curr.size++; curr = curr.getChild(ch);
Thank you in advance!
rshaghoulian Try walking through the add() function, with a word, such as Ben.
- We create B as a child, go to it, and increment it's size
- We create e as a child, go to it, and increment it's size
- We create n as a child, go to it, and increment it's size
Now each letter has proper size.
lricardopena Hello, I do a code similar, but at the end, I need to check if the root is a word, and if is a word, I add one because the test #1 din't pass if we don't do that.
struct Node { map<char, Node*> children; bool isEndOfWord = false; int number_words = 0; }; void add_name(Node *root, string name) { int number_words = 0; for (int i = 0; i < name.size(); i++) { if (root->children[name[i]] == NULL) { root->children[name[i]] = new Node(); } root->number_words++; root = root->children[name[i]]; } root->isEndOfWord = true; } int find_name_partial(Node *root, string partial) { if(!root) return 0; for (int i = 0; i < partial.size(); i++) { if (root->children[partial[i]] == NULL) return 0; root = root->children[partial[i]]; } return root->number_words + (root->isEndOfWord ? 1 : 0); }
mjs486 You need to increment the count of matching words before you update the pointer.
edwarddouglasro1 I did mine with a hashMap, no trees, passes all the test cases, Java 8. Someone tell me if the memory is a problem?
public class Solution { public static final String ADD = "add"; public static final String FIND = "find"; private static HashMap<String, Integer> contactList = new HashMap<String, Integer>(); public static void main(String[] args) { Scanner in = new Scanner(System.in); Integer n = Integer.parseInt(in.nextLine()); for(int a0 = 0; a0 < n; a0++){ String[] opData = in.nextLine().split("\\s+"); if (opData[0].equalsIgnoreCase(ADD)){ addSubstringsToContacts(opData[1]); } if (opData[0].equalsIgnoreCase(FIND)){ System.out.println(numOfPartials(opData[1])); } } } private static int numOfPartials(String partialStringToFind) { int result = 0; if (contactList.containsKey(partialStringToFind)) { result = contactList.get(partialStringToFind); } return result; } private static void addSubstringsToContacts(String contactName) { String partialValue; for (int j = 1; j <= contactName.length(); j++){ partialValue = contactName.substring(0, j); if (contactList.containsKey(partialValue)) { contactList.put(partialValue, contactList.get(partialValue) + 1); } else { contactList.put(partialValue, 1); } } } }
rohan2 [deleted]
tinydino No node, no tree, actually it works. I just use the same mechanise that a searchengine should do.
# all letters, a, ab, abc, .. def edge_ngram(contact): return [contact[0:idx] for idx in range(1, len(contact) + 1)] contact_indices = {} def add(contact): for token in edge_ngram(contact): contact_indices[token] =contact_indices.get(token, 0) + 1 def find(name): return contact_indices.get(name, 0) n = int(input().strip()) for a0 in range(n): op, contact = input().strip().split(' ') if op == 'add': add(contact) elif op == 'find': print(find(contact))
roman_kiselew Hey, this is a great solution! Short and elegant!
matant there is 1 problem with that solution and is that
contact_indicesbecome very big in big inputsQuazar777 size isn't a problem in Python. And time complexity is not very big, because access in a dictionary is O(1).
yanndubois96 The worst case memory complexity of this solution is O(c^L) where c is the number of possible character (in our case 26) and L is the max length of the querry (in our case 21). I agree that O(26^21) is O(1) as these are constants but this means that the worst case memory complexity is 26^21 * 8 bytes ~= 10^28 TeraBytes. I'm not sure what you mean by "size isn't an issue in python" but I'm pretty sure that you can' keep that in memory ! And this in this case they were nice enough to tell us that there are only lower case english caracters. Bottom line : you don't want to show that in an interview
tepperson Not to nit-pick here, but your math is a little off. In Python a string takes up 40 bytes to begin with and since our parameters are that 1 =< N =< 10^5 and 1 =< name =< 21, that means that a string with a maximum possible length of 21 only takes up ~46 bytes in memory:
import sys sys.getsizeof('abcdefghijklmnopqrstu')
If you multiply this by the maxium possible entries, not including find operations, it comes out to ~4.6 MBs.
sachin_kolachana Beautiful!!!!
nthuy neat! and actually used in IR systems!! It uses the postings list of tokenized edge n-gram (more on NLP Information Retrieval here: https://nlp.stanford.edu/IR-book/pdf/02voc.pdf, it was my course textbook)
Here's my Java implementation:
import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
static HashMap<String, Integer> tokenMap = new HashMap<String, Integer>(); public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); for(int a0 = 0; a0 < n; a0++){ String op = in.next(); String contact = in.next(); if (op.equals("add")) { add(contact); } else if (op.equals("find")) { find(contact); } } } static void add(String contact) { String[] splitWords = contact.split("\\s+"); for (String w : splitWords) { for (int i=0; i<=w.length(); i++) { String token = w.substring(0, i); if (tokenMap.containsKey(token)) { int currOccurrences = tokenMap.get(token); tokenMap.put(token, currOccurrences + 1); } else { tokenMap.put(token, 1); } } } return; } static void find(String contact) { if (tokenMap.containsKey(contact)) { System.out.println(tokenMap.get(contact)); } else { System.out.println(0); } }}
rafaeljunqueira Tks for the book! Looks awesome
point_to_null Such an elegant solution. Amazing. So simple I'll try to implement it with BASH.
point_to_null awk ' /^add/{for (idx=1; idx<=length($2); idx++) a[substr($2, 0, idx)]++} /^find/{print(a[$2] + 0)} '
Or, It could be a one-liner if that's your thing. Thanks tinydino, that was good.
uxvxr Very elegant, point_to_null! Nothing short of brilliant, in fact. A couple of questions:
(1) Why does this still pass all tests, given that it completely ignores the first input (the first input is a number which specifies how many total add/find operations will be done)
(2) Why is this time- and space-wise more efficient than simply creating a string of names (for creating the contact list) and, for searching, merely counting grep matches, like this:
read numops contactlist="" for ((i = 0; i < numops; i++)); do read operation name [[ $operation == add ]] && contactlist="$contactlist $name" [[ $operation == find ]] && echo $contactlist | tr " " "\n" | grep -c ^$name done
I believe this code also will pass all tests, but hackerrank systems give me a timeout error on all but three tests! Is this happening because of the for loop I'm running?
ykurtbas Love the brilliance and simplicity although it is not related to the question :)
lizhanguwo amazingly simple and beautiful solution
johannh Very nice solution. Thanks! Here is a c++ version:
vector<string> tokenize(string word){ int n = word.length(); vector<string> tokens (n); for (int i=0; i<n; i++){ tokens[i]=word.substr(0,i+1); } return tokens; } int main(){ unordered_map<string,int> contact_indices; int n; cin >> n; for(int a0 = 0; a0 < n; a0++){ string op; string contact; cin >> op >> contact; if (op=="add"){ vector<string> tokens = tokenize(contact); for (string token: tokens){ contact_indices[token]++; } } if (op=="find"){ cout << contact_indices[contact] << endl; } } return 0; }
danielpham1988 thanks. this version is wonderful. when it comes to performance we need something like this.
ouyahya1 Nice and Clean!!!
konsalexee How much space this solution takes in comparison with the Node solutions?
ramin_z Trie solution (node in this context) space is O(sum of words' lengths). The space complexity for this solution is O(n*|largest word|^2) where n is the number of the words.
nikhilpandey360 if this solution passes the tests why mine failing? it says timeout.
contacts= [] n = int(input().strip()) for i in range(n): op, contact = (input().strip().split(' ')) if op =="add": contacts.append(contact) else: count = 0 for x in contacts: if contact in x:count+=1 print(count)
narape Because your solution is O(n) for every query and n is too large and/or too many queries.
I did mine using sorted sets and then I counted how many elements had a subset with the right bounderies (O(log n) to find the bounderies).
Using tries would be even better as it would be O(log k) where k is the length of the string
saikumarm4 yes, we can get the solution in multiple ways. The objective of the question is for us to understand the behaviour of tree and make effective use of it.
tovin07 Yep, so beautiful!
We can use collections.Counter to get a shorter solution
from collections import Counter def grams(contact): return [contact[:i] for i in range(1, len(contact)+1)] counter = Counter() n = int(input().strip()) for a0 in range(n): op, contact = input().strip().split(' ') if op == 'add': counter.update(grams(contact)) elif op == 'find': print(counter.get(contact, 0))
cinguilherme brilliant
ebbbarr [deleted]Quazar777 wickkkked!
jcchuks1 Hi, I implemented in python 2.7 and am getting Segmentation Fault error on test case 12 only.
Running my code on my machine works fine and passes test case 12. I understand Segmentation Fault has to do with something like acessing some unallocated memory stack. Is there another definition for Segmentation Fault specific to Hackerrank.
See code below. Please if you run it and figure out how to pass the test case 12, please kindly share your what you did differently. Thanks
EDIT: It passes all test cases including test case 12, just add
slots = ["children","char","is_word","words_count"]class Node: __slots__ = ["children","char","is_word","words_count"] def __init__(self,char=None): self.char = char self.count = 0 self.children = [] n = int(raw_input().strip()) root = Node() def add(contact): global root node = root charNo = 0 for char in contact: noOfChildren = len(node.children) childIndex = 0 charNotFound = True while childIndex < noOfChildren : if char == node.children[childIndex].char: node.children[childIndex].count += 1 node = node.children[childIndex] charNotFound = False break childIndex += 1 if charNotFound: newCharNode = Node(char) newCharNode.count += 1 node.children.append(newCharNode) node = newCharNode def find(contact): global root node = root previous = None charNotFound = True for char in contact: noOfChildren = len(node.children) childIndex = 0 charNotFound = True while childIndex < noOfChildren: if char == node.children[childIndex].char: node = node.children[childIndex] charNotFound = False break childIndex += 1 if charNotFound: return 0 return node.count for a0 in xrange(n): op, contact = raw_input().strip().split(' ') if op == "add": add(contact) elif op == "find": print find(contact)
kuddai92 My first solution was identical and it didn't pass testcase 12:
from collections import defaultdict from sys import stdin # clean and concise implementation that will fail on testcase 12 # due to python wasting too much memory on deep chains # of characters. class Node(object): def __init__(self): self.children = defaultdict(Node) self.num_usage = 0 class Trie(object): def __init__(self): self.root = Node() def add(self, word): node = self.root for char in word: node = node.children[char] node.num_usage += 1 def find(self, partial): node = self.root for char in partial: if char not in node.children: return 0 node = node.children[char] return node.num_usage n = int(raw_input().strip()) trie = Trie() for a0 in xrange(n): op, contact = stdin.readline().strip().split() if op == 'add': trie.add(contact) elif op == 'find': print trie.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:
- We add 'hack'. Our trie becomes: root -> 'h' -> 'ack'
- We add 'hackerrank'. Our trie becomes: root -> 'h' -> 'a' -> 'c' -> 'k' -> 'errank'
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:from collections import defaultdict from sys import stdin # the whole stupid split suffix functionality # is only here because very rare long words will screw memory # consumption otherwise class Node(object): def __init__(self): self.val = '' self.children = defaultdict(Node) self.num_usage = 0 @property def is_whole_suffix(self): return self.num_usage == 1 @property def children_suffix(self): assert self.is_whole_suffix # meaningful only for whole suffixes return self.val[1:] def split_suffix(self): assert self.is_whole_suffix # meaningful only for whole suffixes child = self.children[self.val[1]] child.val = self.val[1:] child.num_usage += 1 def add(self, char): if self.is_whole_suffix: # preserve memory by concatinating self.val += char # characters in suffix if the word return self # is used only once child = self.children[char] if child.is_whole_suffix and len(child.val) > 1: child.split_suffix() child.val = char child.num_usage += 1 return child def get(self, char): assert self.has(char) # because defaultdict is used return self.children[char] def has(self, char): return char in self.children def has_same_suffix(self, rest_partial): assert self.is_whole_suffix # meaningful only for whole suffixes return self.children_suffix[:len(rest_partial)] == rest_partial class Trie(object): def __init__(self): self.root = Node() def add(self, word): node = self.root for char in word: node = node.add(char) def find(self, partial): node = self.root for i, char in enumerate(partial): if node.is_whole_suffix: rest_partial = partial[i:] return int(node.has_same_suffix(rest_partial)) if not node.has(char): return 0 node = node.get(char) return node.num_usage n = int(raw_input().strip()) trie = Trie() for a0 in xrange(n): op, contact = stdin.readline().strip().split() if op == 'add': trie.add(contact) elif op == 'find': print trie.find(contact)
jcchuks1 Yeah, I agree. The allocated memory needs to be increased for python. I got the intuition behind the 'hack'/'hackerrank' example.
I am trying to avoid importing libraries. I am thinking instead of using an list, I could do with a linkedlist. That way I might be able to control list size.
class LinkNode: def __init__(self,SomeNode=None): self.node = SomeNode self.next = NextNodeOfSomeNode
kuddai92 It may work as lists have to use additional memory to amortize possible future 'appends'. Although the whole problem is that in Python any self creating objects are just taking too much memory upon their creation in contrast to primitives. I suspect this happens because primitives like strings because they are implemented in C internally. It will be interesting to see if LinkedList can do the job.
bitmalloc I don't think you need that much complexity. As the problem states, only lowercase English characters are used, so it's a constant number and you could just use a list and append as you find the chars, only using the memory allocations required at a time, iterating through children should not be an issue. In the case of the original post by jcchuks1, I think the problem may be due to other issue.
Surprisingly the following solution worked for me using a dynamic array, after failing with dicts and sets (with the proper hashing). Probably a linked list would work too:
class TrieNode(object): def __init__(self, char): self.char = char self.children = [] self.is_word = False # the number of words this prefix is part of self.words_count = 0 def get_child(self, c): for child in self.children: if child.char == c: return child return None class Trie(object): def __init__(self): self.root = TrieNode("*") # token root char def add(self, word): curr = self.root for c in word: next_node = curr.get_child(c) if next_node is None: next_node = TrieNode(c) curr.children.append(next_node) next_node.words_count += 1 curr = next_node curr.is_word = True def find(self, prefix): curr = self.root for c in prefix: next_node = curr.get_child(c) if next_node is None: return 0 # prefix not found curr = next_node return curr.words_count
jcchuks1 Nice work bitmalloc! Suprisingly, I ran your code and it still gave Segmentation fault for same test case as mine.
I just added
o = Trie() for a0 in xrange(n): op, contact = raw_input().strip().split(' ') if op == "add": o.add(contact) elif op == "find": print o.find(contact)
BTW: Linkedlist didn't pass the grader either. My LinkedList implementation had more segmenation faults and with few testcases passed. I will still stick to my original implementation till I see something different since this Hackerrank Platform Dependent.
daviryan Thanks bitmalloc! This works great with ruby for all tests: #!/bin/ruby class TrieNode attr_accessor :char, :words_count, :children, :is_word def initialize (char = nil, is_word = false) @char = char @words_count = 0 # num of words this prefix is a part of @children = [] @is_word = is_word end def get_child(c) for child in @children if child.char == c return child end end return nil end end # end TrieNode class class Trie def initialize @root = TrieNode.new("*") end def add word curr = @root word.chars.each do |w| next_node = curr.get_child(w) if next_node == nil next_node = TrieNode.new(w) curr.children << next_node end next_node.words_count += 1 curr = next_node end curr.is_word = true end def find prefix curr = @root prefix.chars.each do |c| next_node = curr.get_child(c) if next_node == nil puts "0"; return # prefix not found end curr = next_node end puts curr.words_count end end # end class Trie t = Trie.new n = gets.strip.to_i for a0 in (0..n-1) instructions = gets.strip.split(' ') t.add(instructions[1]) if instructions[0] == "add" t.find(instructions[1]) if instructions[0] == "find" end
DaBigBadNuttin what is the purpose of is_word...seems like it was added in there for some idea initially but turns out it wasn't needed.
DaBigBadNuttin this is a really good solution, it inspired me to create one on the same idea but without classes
#!/bin/rubyrequire 'json' require 'stringio' n = gets.to_i dic = {} n.times do |n_itr| opContact = gets.rstrip.split op = opContact[0].to_s.rstrip contact = opContact[1].to_s.rstrip if op == "add" word = "" contact.split("").each do |letter| word += letter if (dic[word]) dic[word] += 1 else dic[word] = 1 end end elsif op == "find" puts dic[contact] || 0 end end
AdrielKlein I had the same problem as you. All my tests were passing except for a runtime error on test case #12.
If you look at some of the other posts in this discussion, someone else points out in this comment that the HackerRank machines are running out of space because you're creating too many Nodes.
As he point out, you can greatly reduce the number of Nodes created by storing multiple letters in a single node, and then expanding it only when necessary.
I created this solution and it makes the Runtime Error go away:
class Node(object): def __init__(self, letters=None): self.letters = letters self.children = {} self.num_occurences = 1 def expand(self): if not self.letters: return self.children[self.letters[0]] = Node(self.letters[1:]) self.letters = None class Trie(object): def __init__(self): self.root = Node() def add_contact(self, contact): node = self.root for i in range(len(contact)): letter = contact[i] if letter not in node.children: new_node = Node(letters=contact[i + 1:]) node.children[letter] = new_node break else: node = node.children[letter] node.expand() node.num_occurences += 1 def get_num_occurences(self, contact): node = self.root for letter in contact: if letter not in node.children: return 0 node = node.children[letter] node.expand() return node.num_occurences n = int(input().strip()) trie = Trie() for i in range(n): op, contact = input().strip().split(' ') if op == 'add': trie.add_contact(contact) else: print(trie.get_num_occurences(contact))
I hope that helps!
tangestani An easy way to save memory is to use
__slots__on your objects.For example:
class Node: __slots__ = ['size', 'children'] def __init__(self): self.size = 0 self.children = {}
crobertob Thanks! This worked for me and was enough to pass all the tests.
buaaluqiang Thank you so much!!! It worked for me.
stberg3 Great, simple solution that got me past Case 12!
pkoprows Took me from failing on three examples to passing all of them. Thanks!
nolan34 Thanks @tangestani !
Vector1991 Thanks man great hack.
17loc Thanks a lot! It also solved case 12 for me! Is this some sort of a black magic spell? ;)
congpeisong This worked!
z_smith32 you.. you the real MVP
ashu1710 Yes, that worked for me as well. Thank you so much :).
aaron_hampt [deleted]
rraahhuul Thanks! Adding slots to the class definition worked, but it only works for new-style classes (if using Python2) i.e.
Class should extend 'object'
class Node(object):nagashayan1 True, didn't work with out using 'object' thanks man.
santagada my solution was simple, if having a node costs too much memory, why not just keep the dictionaries:
root = {'childrens': 0} def add_word(word): node = root node['childrens'] += 1 for l in word: n = node.get(l, None) if n is None: n = {'childrens': 0} node[l] = n node = n node['childrens'] += 1 def search_partial(prefix): node = root for l in prefix: if l not in node: return 0 node = node[l] return node['childrens']
it went all the way from 451mb of memory to 286mb on the worst case. Maybe using an object with a list and slots or a subclass of list with slots could use even less, but now I'm tired and want to sleep :)
Paul_Denton My C++ solution uses less lines of code, try to simplify.
Aditya0007 Can you please put up your c++ code. I'm not able to rectify test case 13.
Paul_Denton This is not the place to post solutions, after all you are suposed to come up with it yourself. If you are that desperate I think you can access the leaderboard or editorial, but will get no points after that for your solution.
ericclone I think there is a small ambiguity in the editorial. The problem statement is not specific about how duplicate contact should be handled. According to the editorial, no contact will be added twice. But this is not clearly stated as an assumption. I spent quite some time handling duplicate contacts which turned out to be unnecessay.
I think the statement should be more specific for the sake of correctness.
Talasu Seconded. I wasn't sure whether I should increase the count for completely duplicate items. IE "3 add bob add bob find b" = 2 or 1? I implemented 2 first (easier), and it worked. But the problem statement should really say how to handle duplicates. Especially if the editorial does.
billr7 Anyone else have trouble getting the Javascript version to be accepted? I get failures on 5 and 12, although sometimes aborts on those. I've tried it with iterative tries, recursive tries and other tweaks. I downloaded #5 and it has no output, so I shouldn't be getting the wrong answer here.
spark4 I am having issues getting my JS solution getting accepted as well, but am getting timeout errors on 3,4 & 7.
Here is my code. Do you mind sharing what you did so that we can compare?
function main() { var trie = {}, n = parseInt(readLine()), resp = ''; for(var a0 = 0; a0 < n; a0++){ var op_temp = readLine().split(' '), op = op_temp[0].trim(), contact = op_temp[1].trim(); switch(op){ case 'add': addName(contact, trie); break; case 'find': resp += (resp.length === 0) ? findPartial(contact, trie) : '\n'+findPartial(contact, trie); break; default: break; } } console.log(resp); return; } function addName(name, trie){ var tree = trie; for(var i = 0; i < name.length; i ++){ if(!tree[name[i]]) tree[name[i]] = {}; tree = tree[name[i]]; if(i === name.length - 1 && !tree["*"]) tree["*"] = "*"; } return; } function findPartial(partial, trie){ var prefixTree = trie, numPartials = 0; for(var i = 0; i < partial.length; i ++){ if(prefixTree[partial[i]]) prefixTree = prefixTree[partial[i]]; else return numPartials; } var stack = [prefixTree]; while(stack.length > 0){ var currTree = stack.pop(); for(var letter in currTree){ if(letter === "*") numPartials++; else stack.push(currTree[letter]); } } return numPartials; }
billr7 This is my most pared down iterative version.
var Trie = function() { this.children = {}; this.count = 0; }; Trie.prototype.insert = function(str) { var iterator = this; for (var i = 0; i < str.length; i++) { var c = str.charAt(i); if (iterator.children[c] === undefined) { iterator.children[c] = new Trie(); } iterator.count++; iterator = iterator.children[c]; } iterator.count++; }; Trie.prototype.find = function(str) { var iterator = this; for (var i = 0; i < str.length; i++) { var c = str.charAt(i); if (iterator.children[c] === undefined) { return 0; } iterator = iterator.children[c]; } return iterator.count; };
davencia1 here is a recursive solution for you as well:
function main() { var n = parseInt(readLine()); var contactList = {'words': 0}; var addWord = function(contactList, letters){ if (!letters[0]) {return} if (!contactList[letters[0]]) { contactList[letters[0]] = {'words': 1}; } else { contactList[letters[0]].words += 1; } var newList = contactList[letters[0]]; letters.shift(); addWord(newList, letters); } var checkWord = function (contactList, contact){ if (contact.length === 1){ if (contactList[contact]) { return console.log(contactList[contact].words); } else { return console.log(0); } } if (!contactList[contact[0]]){ return console.log(0); } else { contactList = contactList[contact[0]]; contact.shift(); checkWord(contactList, contact) } } for(var a0 = 0; a0 < n; a0++){ var op_temp = readLine().split(' '); var op = op_temp[0]; var contact = op_temp[1]; if (op === 'add') { contactList.words += 1; contact = contact.split(''); addWord(contactList, contact); } else { contact = contact.split(''); checkWord(contactList, contact); } } }
fforres I got a similar solution, but it's giving me an error on tests 5 and 12. I'm guessing because of memory errors.
Both mine and your solution are giving me the same errors though. How about you?
Here's my solution
function analizeContacts(){ this.contactObject = { letters: {}, data: 0 }; this.currentFinds = []; } analizeContacts.prototype.find = function(term){ const termChars = term.split(''); let currentWords = null; let searchObject = this.contactObject.letters; for( let i = 0; i < termChars.length; i++) { const el = termChars[i]; if(searchObject[el]) { currentWords = searchObject[el].data; searchObject = searchObject[el].letters; } else { currentWords = 0; break; } } if(currentWords !== null) { this.currentFinds.push(currentWords); } } analizeContacts.prototype.add = function(term) { const termChars = term.split(''); let searchObject = this.contactObject; for( let i = 0; i < termChars.length; i++) { const el = termChars[i]; if (!searchObject.letters[el]) { searchObject.letters[el] = {}; searchObject.letters[el].letters = {}; searchObject.letters[el].data = 1; } else { searchObject.letters[el].data++ } searchObject = searchObject.letters[el]; } } analizeContacts.prototype.results = function() { this.currentFinds.forEach((el) => { console.log(el); }); } function main() { var n = parseInt(readLine()); const analize = new analizeContacts(); for(var a0 = 0; a0 < n; a0++){ var op_temp = readLine().split(' '); var op = op_temp[0]; var contact = op_temp[1]; analize[op](contact); } analize.results() }
joaosa I'm experiencing the same issue with tests 5 and 12
will_shaver I solved it in a very different way, and very much a "hack" that is solving it only based on the problem given, not a real-world solution. We don't actually store contacts in our system, we're storing indexes. So instead of expecting to actually get the contacts back, we're just getting a count. That plus knowing searches aren't more than 6 chars long makes things trivial:
function main() { var contacts = []; var n = parseInt(readLine()); var tree = {}; for(var a0 = 0; a0 < n; a0++){ var op_temp = readLine().split(' '); var op = op_temp[0]; var contact = op_temp[1]; switch(op){ case 'find': console.log(findContacts(tree, contact)); break; case 'add': addContact(tree, contact); break; } } } function addContact(tree, contact){ const len = Math.min(contact.length + 1, 7); for(var i = 1; i < len; i ++){ const idx = contact.substr(0,i); if(tree[idx]){ tree[idx]++; } else { tree[idx] = 1; } } } function findContacts(tree, search){ return tree[search] || 0; }
This gives trees like:
{ h: 2, ha: 2, hac: 2, hack: 2, hacke: 1, hacker: 1 }
Which obvously the findContacts() function executes super fast as it is using a native primitive for the hash lookup. Passing on all accounts. No fancy tree/splitting needed.
aaronranard How do you know searches are no more than 6 characters long? In the constraints listing it says 1 <= partial <= 21, so in theory 21 should be the limit, no?
I'm implementing an almost identical soution but it's running out of memory creating an index 21 characters long * 100000 words.
ion01 @kuddai92 reported they were only five characters. https://www.hackerrank.com/challenges/ctci-contacts/forum/comments/192063
tb003 I've re-implemented this in Java and it works great!
if(op.equals("add")) { for(int i = 1; i <= contact.length(); i++) { String sub = contact.substring(0, i); Integer currentCount = contacts.get(sub); if(null == currentCount) { contacts.put(sub, 1); } else { contacts.put(sub, 1 + currentCount); } } } else if(op.equals("find")) { Integer maybeCount = contacts.get(contact); int count = null == maybeCount ? 0 : maybeCount; System.out.println(count); }
johnsouth FYI - The search length hack isn't necessary. I made a full index and still passed all of them the first try in JavaScript.
julianabsatz I tried reimplementing this and it worked, but I had to download a couple of tests. Be careful as there are tests that only do 'find' and tests that try to look for common array functions like 'pop' or 'map'
tony_z My solution is pretty simple but it times out on half the tests, so I guess it's no good.
function main() { var n = parseInt(readLine()); var contacts = []; for(var a0 = 0; a0 < n; a0++){ var op_temp = readLine().split(' '); var op = op_temp[0]; var contact = op_temp[1]; if (op === 'add') { contacts.push(contact); } else if (op === 'find') { var matches = contacts.filter(el => el.indexOf(contact) == 0); console.log(matches.length); } } }
rbellebon yeah, I did the same approach but I used includes:
if (op === 'add') { contactsList.push(contact); } else if( op === 'find') { const value = contactsList.filter( name => name.includes(contact)) console.log(value.length); }
I need to understand why is it timing out...
chrisjaynes I'm pretty happy with my functional version. It passes all of the tests.
const root = {} function main() { var n = parseInt(readLine()); for(var a0 = 0; a0 < n; a0++){ var op_temp = readLine().split(' '); var op = op_temp[0]; var contact = op_temp[1]; if (op === "add"){ add(contact, root) } if (op === "find"){ const result = find(contact, root) console.log(result) } } } const add = (value, node)=>{ const char = value.substring(0,1) if (node[char]){ node[char].count++ } else { node[char] = { count: 1} } if (value.length > 1){ const rest = value.substring(1) add(rest, node[char]) } } const find = (value, node)=>{ if (value.length == 1){ if (node[value]){ return node[value].count } return 0 } const char = value.substring(0,1) if (node[char]){ const rest = value.substring(1) return find(rest, node[char]) } return 0 }
km003 I was able to get it after building a map of all the possible partials, approaches that just tried to iterate over all the names and check matches with substring or regex would timeout.
class ContactBook { constructor() { this.tree = new Map(); } add(name) { let p = ""; for (let c of name) { p += c; let node = []; if (this.tree.has(p)) { node = this.tree.get(p); } node.push(name); this.tree.set(p, node); } } find(partial) { if (!this.tree.has(partial)) { return 0; } return this.tree.get(partial).length; } }
gussy Python 3 - bit of a hack but it works.
import bisect n = int(input().strip()) contacts = [] for a0 in range(n): op, contact = input().strip().split(' ') if op == 'add': bisect.insort_left(contacts, contact) if op == 'find': left = bisect.bisect_left(contacts, contact) right = bisect.bisect_left(contacts, contact + 'zzzzzzz', left) print(right - left)
hedleypanama What a pretty neat library: I tried it with Python 2 and it also worked!
qwerytiop Isn't bisect.insort implemented with the list.insert function, which is usually O(n), which gives total O(n^2)? How does this manage to run that fast?
aod7br Yeah it works and passes all testcases, but the right cota is wrong... there could be
contact+'zzzzzzzaaa'in the list and you would not count it. I think the correct way to calculate the rightmost element should beright=bisect_right(contacts, chr(ord(contact[0]+1)), left)
and having stablished the right cota, you would still need to check if all elements between
leftandrightdo start with contact:for s in islice(contacts, left, right): if s.startswith(contact): total+=1 return total
please someone correct me if I am wrong
DerPferd I think here is a simpler way to solve this problem. Change the last character to the next character than subtract left from right:
left = bisect.bisect_left(contacts, contact) prefix_next = contact[:-1] + chr(ord(contact[-1])+1) right = bisect.bisect_left(contacts, prefix_next) print right-left
aod7br Yeah good solution. This way I dont have to check the elements between left and right, since prefix_left MUST be the next element after all elements start with contact
marc_torsoc No need of any complicated structure, just create a map with each of the possible substrings, and counters that increment for each new contact. My solution in C++ (in Python doing the same is straightforward):
int main(){ int n; map<string,int> agenda; cin >> n; for(int a0 = 0; a0 < n; a0++){ string op; string contact; cin >> op >> contact; if(op == "add"){ for(int i=0;i<=contact.length();i++){ agenda[contact.substr(0,i)]++; } } else{ cout << agenda[contact] << endl; } } return 0; }
wrinl3 Here's a similar stupid (but working) solution in Python 3. I doubt you should solve this problem using anything other than a Trie during an actual interview, tho - the problem is way too obviously geared towards it.
from collections import Counter c = Counter() def add(name): for i in range(1, len(name)+1): c[name[:i]]+=1 def find(partial): print(c[partial]) n = int(input().strip()) for a0 in range(n): op, contact = input().strip().split(' ') if(op == 'add'): add(contact) else: find(contact)
scottmk But this is far less memory efficient than implementing a trie. You're creating way too many strings. If you implemented a simple trie where each node had the letter it represented, an integer of all complete words its children makes, and a set of all its child nodes, the space would be significantly smaller and the lookup still linear.
EDIT: I take it back. Lookup in your solution is constant, not linear. So your solution is faster but uses more space. The map you wrote has a space complexity of roughly O(kn), where k is the average number of letters in a word and n is the number of words. In a solution with a trie, the space complexity is O(n), where n is the total number of unique letters. More or less. I think in this case it's worth saving on space and sacrifice lookup.
Paul_Denton Haha maybe they should have a very large test case that exceeds the memory limit in this case.
dmangeni Very clean. Does it pass all the tests?
cool_shark My solution in C++
struct Node { unordered_map<char, Node*> children; int count; Node() { count = 0; } }; class Trie { private: Node *_root; public: Trie() { _root = new Node(); } void add(string str) { Node *node = _root; for (char c : str) { if (node->children.find(c) == node->children.end()) { Node *newNode = new Node(); node->children[c] = newNode; node = newNode; } else { node = node->children[c]; } node->count++; } } int find(string str) { Node *node = _root; for (char c : str) { if (node->children.find(c) == node->children.end()) { return 0; } else { node = node->children[c]; } } return node->count; } };
ameyajoshi You didnt get any segmentation faults?
melroy_tellis This wouldn't work if contact names are repeated for the ADD operation.
ameyajoshi That can be resolved by having a boolean variable to indicate the end of the word.
Serg675 [deleted]
elenaa_ursu I solved this by returning from the add operation if the string already exists in the trie.
void add(string str) { if (find(str) != 0) { return; } ... }
ameyajoshi Well this wont work.
we add "facebook" to trie , at this point node->count is 1 .
Next we try to add "face" , in your case it wont add this word , by that i mean the node->count will remain 1 , when i expect node count for nodes f,a,c,e to increment to 2.
so if try to do a substring match fa, yours will always return 1 ,when i expect it to be 2
melroy_tellis Yes, your solution would work only if the words to be added appear in lexicographical order. The most general way is to add an end-of-word flag for each node and update the count only if it's not set for the last node of the word.
Serg675 [deleted]Serg675 [deleted]Serg675 This particular task condition is that all names are unique.
rishabh_malviya I don't understand how the new Nodes you create still live after you exit the function.
All the
Node* newNode = new Node()
create new Node pointers in the scope of the function, but as soon as you exit, they should be destroyed, right?
richa_dohre no, it can only be deleted if we delete it using 'delete' operator(since it is allocated in heap area not in stack), or at the termination of program.
rishabh_malviya Okay, so a variable constructed with the
newcommand can only be deleted by
deleteirrespective of the scope in which it was declared.
Is this correct?
melroy_tellis Yes. That's how dynamic memory allocation works in C++. If the memory is not deallocated by the program, it will continue to occupy heap space and cause a memory leak.
richa_dohre yup!
Paul_Denton I ended up with:
class Trie { struct Node { int nWordsWithThisPrefix = 0; bool isCompleteWord = false; map<char, Node> children; }; public: void addWord(string word) { Node* node = &_root; for (char c: word) { node = &(node->children[c]); node->nWordsWithThisPrefix++; } node->isCompleteWord = true; } int countWordsWithPrefix(string prefix) const { const Node* node = &_root; for (char c: prefix) { auto result = node->children.find(c); if (result == node->children.end()) { return 0; } else { node = &(result->second); } } return node->nWordsWithThisPrefix; } private: Node _root; }; int main() { int n = 0; cin >> n; Trie trie; for (int i=0; i<n; ++i) { string command, s; cin >> command; cin >> s; if ("add" == command) { trie.addWord(s); } else if ("find" == command) { cout << trie.countWordsWithPrefix(s) << "\n"; } } return 0; }
Paul_Denton This has a memory leak, right? Unless you implement a destructor for the Trie class. Why not keep the Nodes in the map instead of just pointers to the nodes, containers allocate memory anyways.
Paul_Denton Ah just noticed that it already had been discussed. You should read up on RAII ;)
nfollett89 Is it just me, or is the limitation on resources forcing the solutions to be overly hacky/ugly?
Obviously if you aren't using tries then you're not going to make it, but my best implementation had a few test cases fail due to segmentation faults. I suspected this might have to do with my heavy use of dictionaries (Python 2) to store the children in a children[char] = trie_node() fashion, so I turned it into a list... I no longer got segmentation faults but now it times out even though I have a lookup array so that I don't have to iterate through the children like crazy.
After reading through some discussion posts that passed, it seems most/all of them had to use some method which goes against coding best practices in the name of simply getting it to work.
I hope I'm wrong - perhaps I'm just not seeing the right optimization opportunity. Anyone else struggling with this aspect of the problem?
davissallen One year later... same problem. Using Python 2 with tries and dictionaries to hold children seems like a great approach but still does not pass 3/15 test cases.
sheva_ukraine97 Thanks to C++'s STL, there're only 2 lines of code.
int main(){ int n; cin >> n; set<string> contacts; for(int a0 = 0; a0 < n; a0++){ string op; string contact; cin >> op >> contact; if (op == "add") contacts.insert(contact); else cout << distance(contacts.lower_bound(contact), contacts.upper_bound(contact + char('z' +1))) << endl; } return 0; }
NicoleB Can you explain why you need the +1 in char('z' +1) instead of just contact + 'z'?
Sort 482 Discussions, By:
Please Login in order to post a comment