Search Suggestions System - Leetcode 1268 - Python
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/search-...
0:00 - Read the problem
0:55 - Drawing Explanation
8:25 - Coding Explanation
leetcode 1268
#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Discord: discord.gg/ddjKRXPqtk
Correction: Time complexity is O(nlogn + n + m) where n is size of products, and m is length of searchWord.
Bug brain time
It should be S*nlogn + n + m where s is avg string length.
can you make a video one day for all the complexities.
Very nice correction
it is actually a little worse than that because we have to account for copying over the strings into the result map at the end. so it would be something like S*nlogn + n + m * S
Thank you very much for these helpful videos. I did Blind75 and watched your solutions for those 75 questions! I must say, the solutions help me a lot for my tech round interviews!
Nice man , i used a binary search but two Pointer is more intuitive and easier to remember for me now. 👍
Woah! This was my Amazon question last year! Thank you for this video, Neetcode! I’ve been meaning to re-attempt this! 😃
Did you get it right?
@@ObtecularPk No, I ran out of time 😅
Did u place in Amazon
@@ramkrushnamadole874 what do you think? If she missed a question and ran outta time.
@@ramkrushnamadole874 No, but I did get to try again 6 months later, and then I failed again 😅
But the moral of the story is- it wasn’t the end of the world 🙂 After that first failure, I was still able to interview with Meta (twice), Amazon again, and then Google as well last May 🙂
Each time I interviewed, I got A LOT better, but I’m still not quite there yet 🤷🏻♀️
I think if you want to interview with FAANG/MANGA, just do it 🙂 If anything, it’ll give you an idea of where you currently stand and what you need to work on 😄🤷🏻♀️
Hey @NeetCode, wouldn't it be faster to use a slice on the final append to answer instead of that for j in range loop?
ie: answer.append(products[l:min(3, r - l + 1)+l])
result.append(products[l:r+1][:3]) also works
Thank you. The explanation was really good. Better than leetcode solution page.
You're right. The first idea that came to mind was Trie, but the implementation was not easy.
Out of all the channels that try to help people transition into tech, this one has to be the most useful. Seriously these problem coding skills, as petty as they appear, as huge for getting an offer.
For those who are wondering the purpose of 2nd pointer(right ptr.) as it isn't obvious in the video due to the example. In the example, it appears like we could get the solution for each typed character with constant amount of work i.e check the next 3 words from the current index of first pointer(left/top) and if they match the typed character add the word to the list and then append to the result List. The efficient way to verify the next 3 words from current index of first pointer(left ptr.) is just check the current char directly instead of reverifying all the previous chars of the next 3 words are also matching the prefix typed so far of the searchWord. Too much blabbering 🙃..... In short 2nd pointer is to limit the search space and guarantee that as long as the index of 1st pointer(left ptr) is less than or equal to 2nd pointer (right ptr) we are still in valid search space and avoid reverifying all the previous chars of the next 3 words from 1st pointer. Example :
sorted search list = [mobile, monitor, mousepad, muumuu, tsunami, vault...]
searchWord = mouse
1) char 'm' = [mobile, monitor, mouse]
2) char 'o' = [mobile, monitor, mouse]
3) char 'u' = [mouse] ->
*current search char is 'u' with prefix searched so far "mo", without a second pointer we would have to reverify "mo" is also a prefix for words mousepad, muumuu, tsunami.*
Thank You!
Wouldn't it be better to use binary search to move the pointers instead of just moving it by 1?
Anyway, great explanation!
binary search is more complex, because of the string slicing required in comparison.
Your explenations are great.
Thanks! 🙂
Masterpiece 👌👌👌
I really have no clue how are we supposed to come up with this sort of answers during an interview if we never saw the problem 😅
yep same bro
How about res.append(products[l:min(l+3, r+1)]) instead of lines 15-18
really amazing explanation....
Very clever!
For the testcase of ["havana"] "havana", r will be 5, which occurs an error that list index out of range for products[r] and products[r][i]. How do you fix this?
my bad, the right pointer should be len(products) - 1.
which would fix the issue of my question
Question, would this algo scale for a database table (sorted always) with millions of data? hmmmmmmm
Idk if it was corrected but lexicographically and alphabetically are different. The former is alphabetically order preceded by a length comparison
So this is asking for alphabetical and shortest results
But question does not mention about products being sorted (or coming in order)
2 pointer solution is so neeeeeeeeeeeeet!!!
Hi Neetcode, love your succinct and clear explanation! Would you be willing to make videos on more advanced concepts like Segment Trees and String Hashing/KMP algorithm?
Right pointer doesn't change complexity right?i could just iterate all words with left pointer and sfill find the first match, then just pick the first 3 matches from there
Yes, as you iterate with your left pointer and check if it matches, you also need to check with left + 1 and left + 2 if it matches with the left pointer. And you need to ensure left + 1 and left + 2 are less than len(searchWord)
Can I send a graph question and also a simple question that I didn't get to solve. Will you have look into that
I'd use a TreeMap / std::map, which will do the l/r portion in logN time
Yeah i solved using the same technique
Hello, what's the app you use for doodling?
Paint3d
@@NeetCode :D
this is just to complex to get in my head :/.
i always pause the video to try to understand it but i don't get when he adds a bunch of code in the same line, i feel frustrated😢
I think on your website you should list this problem under two pointers rather than binary search.
here after a year! and after 2 jobs:)
beautiful
Hey please mention the the time and space complexity for every question you solve
He did at 7:47
yesterday I took a test from aquasec this was my question with a bit of twist, insteaf of prefix I had suffix and instead of just one search word I had an array of multiple words
Can you do this problem as a Trie?
❤️
It gives a TLE now right?
The future generations are very lucky because by that time you might have completed videos for most of the leetcode problems!
Solved it using Trie + DFS. Should've realized that there was a much simpler solution using binary search or two pointer :/
Leetcode 82 pls🙏
hello teacher,
i have two question? math is important to software engineer?
Second question? can i do better math?
third/Sir, I'd like to work with Google in the future. Can I?
go out and touch grass
I believe Trie will be more practical if the word list is mutable.
It's more of a concept and application I believe
How would you implement it with trie?i get you add all words character by character. But what when you search them up?you search until the prefix but then?you'll have to explore all the children subtrees and get the first 3 lexically minor
@@memeproductions4182 maybe a dfs preorder traversal
@@memeproductions4182 In your TrieNode class, have two attributes - children and suggestions. As you insert your product to the TrieNode, also add the product in the suggestions field.
Suggestions can be an array and you can sort this array whenever you insert to it. Also, ensure that you pop out the elements whenever suggestions.size is greater than 3.
Sorry if you didn't understand this. Will be happy to elaborate on this
@@dynamic.6302 won't that take more time to keep updating the suggestion at every insert?
I tried the dfs approach, took 2887ms while the two-pointer took only 115ms
easiest solution
This doesnt seem scalable because you would need to sort every word first.
5 seconds in: trie trie trie trie
const suggestedProducts = (products, searchWord) => {
let ans = [];
products.sort();
for (let i = 0; i < searchWord.length; i++) {
const curr_search = searchWord.slice(0, i + 1);
let temp = [];
for (let j = 0; j < products.length; j++) {
if (products[j].startsWith(curr_search)) {
if (temp.length < 3) {
temp.push(products[j]);
}
}
}
ans.push(temp);
}
return ans;
};