Data Structures: Solve 'Contacts' Using Tries

[@chengqian5737]

I watched lots of your video, you're the best who explains a problem clearly with easy understandable code.

[@galfas09]

The variable CharCode is not being used. By the way thanks a lot for your videos they are great and helping me a lot. =D

[@lg2389]

Why would you increment the size at the beginning of the add method? Shouldn't you increment the size once you set a node?

[@chiyang4776]

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.

[@frankhou5574]

size stands for the size of the node itself, not children's size.

[@ultimatesin3544]

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...

[@gadiben-amram1471]

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?

[@rohishd]

Yes, that is what I thought as well.

[@rohishd]

I generally like her solutions but this solution is not really that great.

[@dmitryWeirdo]

Yes we have, but the description of this HackerRank task implies that there are no duplicate words in the input.

[@ibrahimalshubaily9520]

Thank you Gayle

[@tomyang7788]

what is the getCharIndex(char c) function for and why does it return c - a ?

[@mnsayeed999]

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').

[@vishnusingh4118]

@@mnsayeed999 I think you meant 'a' has an ASCII value of 97. Because 65 is for 'A'

[@waagnermann]

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

[@AbhishekSingh-op2tr]

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?

[@dovgoldberg]

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.

[@gravity_vi]

isn't it wrong you need to return the count of contacts that start with the string 's' and not all the strings which have prefixes as 's'.

[@haseebshahid3581]

I don't think this will find the count of contacts that exist containing that substring or start with that substring

[@justynastaron-kajkowska3906]

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.

[@doktoren99]

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

[@SulavTimsina]

How does the getCharIndex() method work?

[@nikhilpatil611]

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?

[@mayankgupta2543]

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?

[@amlanch]

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;

[@TheOwlTheOne]

Her lectures are so hard to understand because her voice is so attractive i only listen to her but not understand anything😂

[@mangono8]

why did she want the value at 5:35?

[@ovu-t8d]

if getNode(current) returned null the Node child would still be equal to null, when you try call child.add(...) it would just throw errors

[@MaminaZvezdochka]

Thanks so much!

[@emilianolaneri]

thanks!

[@SuyashSoni248]

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

[@programming_and_snacks5192]

I didn't understand code at all. Can someone explain it using example - "bat"

[@victorriurean]

nice

[@sukumarkuppusamy4218]

findcount() is still confusing. Anybody please help with clear content.

[@beastbeautybiker6656]

She didn't update size before calling the findCount method recur.

[@davidwoosley]

Is there any practical application where this solution is, in fact, the best solution? I simply cannot think of one.

[@deadismarth7]

I phone contacts idk

[@programming_and_snacks5192]

Code would be clear if she actually walked through an example like "bat". Can someone walk through the code using this example?

[@Manu-wb2uv]

Does that means that every single child has 26 childrens ? Isn't that a lot of memory usage?

[@haroonalishah1940]

Great, but your voice stuck and dies at the end of the statement. :/

[@eduanlenine]

WTF are you doing here?

[@mindfreak191191]

A more intuitive sample of tries using dictionary - paste.ofcode.org/5jR9ApVSYV9qmaxx7cN36p

[@SpaceFalconIO]

Now try doing this in Javascript.

[@endargon]

Implying it would be more difficult ?

[@TheHTMLCode]

why would doing it in JS be any more different? If you wanted to write it in assembly then I'd accept your point above :P

[@ElcoBrouwervonGonzenbach]

class Node { constructor () { this.size = 0 } add (s) { this.size++ if (s.length === 0) { return } const current = s.shift() if (!this[current]) { this[current] = new Node() } this[current].add(s) } find (s) { if (s.length === 0) { return this.size } const child = this[s.shift()] if (!child) { return 0 } return child.find(s) } } Gotta turn the input string into an array first: contact = op_temp[1].split('')

[@garykim6649]

Can you try to do it in machine language please?