Learn how to create a contact list using tries. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. www.hackerrank....
bcuz then size would equal number of words stored as in the graph on the right side. it only size++ at child = new Node(), then size will increment only at where it branches out.
It's a funny place for it and confused me for a while - but it does work - why? - think about what happens on the final node whenever you're adding a new string... If you were adding "ANDY", then at the end of the recursive method call - you'd be entering add() with node Y and with index = s.length... so if you don't increment size before returning, size for node Y would be zero...
question - at the add() function, shouldn't we check if the contact we try to add already in the trie tree? if so, the "size++" is wrong since there will be no adding to the number of contacts on that string route... what am I missing?
If surely does, if every name, that you have added, has all letters different and different letters then any other name, because then all nodes have size 1 (or doesn't exist) and therefore also last node have size 1, which is returned (or 0 is returned, if letter from name, that you are looking for, was never added). Handling duplicates is not solved in the add method, so find method also ignores it and doesn't work, as you would expect in the final solution, for the same reason - children doesn't track order of the characters.
when I am a client who is using this class, from where should I get the index parameter while invoking findCount method?shouldn`t I just pass my "prefix" string and get the number of words corresponding to it?I think I don`t have to care bout something besides my prefix
At 2.24, for children instance variable's data type, she said though HashMap would take more memory but they(HM) would make certain operations easier. What does she mean by that? Wouldn't taking an array of length 26 every time is inefficient, since a node would not always have all 26 characters as children?
An array is a collection of the same data types that are indexed. So with an an array of Ints you have 32bits stored in each item. With a hashmap there is a set of keys and values. So to store a hashmap of Integers would require the 32 bits per int plus the bytes used to store the key.
If anyone managed to implement this in Swift let me know. Id love to take a look at it. Ive tried dictionaries with already implemented words for quick lookup .etc. but im still timing out on some of the tests
There is minor bug in the code. The add method will set the size to one plius the word length because of "if (index == s.length() ) return; " in the add() method. It should be if (index == s.length() -1) return;
It is just to get the index of a character in the children[ ] array. children[ ] array is of size 26 (number of characters 'a' to 'z'). Java works on unicode characters concept, and since 'a' has an ASCII value of 65 (return type of getCharIndex(char c) is int, so it automatically converts character to its ascii value) and we have to place it at children[0.....25], so we do, ascii value of(c) - ascii value of('a').
This logic would not work with duplicates, correct? A Trie will not have duplicates but by this logic size still gets incremented. Am I missing something?
Nope i think you are right, the better place to increment size would be after setNode() call. As it ensures that a new node is added, so now increment the size. What say?
What if I want to delete a contact from my contacts' directory? I've implemented deletion also - github.com/suyash248/ds_algo/blob/master/Trie/contacts_list.py
