Insert Delete GetRandom O(1) - Leetcode 380 - Python
Vložit
- čas přidán 30. 06. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/insert-...
0:00 - Read the problem
1:30 - Drawing Explanation
8:32 - Coding Explanation
leetcode 380
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#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
Hey man, thank you so much for the videos. I was so glad to see one of the questions you covered in my interview, nailed it, then got the Amazon offer! Keep doing what you're doing!!
Thank you so much Marco!!
That moment when NeetCode has the video posted of the problem you're stuck on. I know you probably hear this a lot, but thank you so much. You are a lifesaver
Hey neetcode, just wanna add another "thank you" message to your stack. Thank you so much and it's been helping me a lot and you are really amazing and I hope to see more in the future!
More tricky than what i figured at first sight ! Thanks for the video :)
man being at google u are so much consistent , quite remarkable. can u make a video on "work pressure" at google .
Hey neet, great video as always! I watched your video on finally being employed the other day and I was curious about if you still plan on creating some videos on system design? I think you're one of the best educators on this platform and I would really love to see your take on the topic :)
It was really a great explanation because it is how we would actually reach the optimal answer. You backtracked the thinking of a person trying to solve this problem first time.
I was asked this in a Bloomberg phone interview yesterday.
Hey, wanted to thank you as I used your videos to practice before coding interviews and I did well and I got the job!, Thanks man! :D, I'll be sure to subscribe to your Patreon using money from my first paycheck.
That's awesome, congrats on the job 🎉👏
@@NeetCode just to clarify. why do you use 2 data structures if you can use only one "set". This data type has method pop. pop() - Remove and return an arbitrary element from the set. Raises KeyError if the set is empty. Just use
def getRandom(self) -> int:
tmp = self.values.pop()
self.values.add(tmp)
return tmp
@@0yustas0 That's a good point, but I wonder if it would satisfy the problem's definition of "random". In this case if we call random() multiple times, will it return the same val?
@@NeetCode I understand you point. But in the same time, I'm not sure that if you call "random" function a few times, it should return "the same val". Only when you play with seeds. Random in python is "pseudo-random ". Even inside "random" they use different algorithms :) In any case, thank you.
@@0yustas0 pop() returns an arbitrary element which means it can return whatever the set wants. You can't rely on it to be at all random, or pseudo-random. In practice, at least for the CPython interpreter, pop() just returns the first element in the set.
If you try to use pop() and then add() back it will just cycle through all the elements in the set in order which is not the slightest bit random, or pseudo-random.
what an explanation man, perfect !!! 🙌🙌🙌
thank you for a detailed and easy explanation buddy!
Congrats on 100k subscribers 🎉👏
Thanks bro , your are the best of best i ever scene now days i always looking for your solution because you are explaining all the optimal solution
That's awesome man, thanks a lot :)
Feels like you were not feeling well while making this video as I am following yor videos for quite long time now.
We appreciate your efforts bro 🙂
Hello sir ur videos are great,amazing explanation,please make it in java language
Hi...please make a video on Logic building and how to increase problem solving skill for beginners...! Using python.
hey neetcode curious what you use to record your whiteboard. is it a desktop software or you do it on ipad
I just use Paint3D (free) and a mouse with low dpi
Thanks NeetCode! just want to say it actually won't work when removing the last item! changing line 20 and 21 will fix it.
instead of creating a separate list and updating elements in it based on hashmap values, we can just use a hashset and the get random value as ` return random.choice(list(self.numSet)) `
Please do system design videos
I think it should be len(self.numList)-1 shouldn't it? Or you'll constantly have the wrong index
Not really because we are adding the element in the next line. If we were to add the element in the list before we add it to hashmap, then we would need to do -1 but not in this case
Use linklist instead of array.
Store the pointer to node instead of index in hashmap
You need O(1) index for get random which you don’t have with a linked list
but that might run into memory fragmentation issues? sounds good otherwise, I knew there must be a better way. Thanks! Ah, crap, Andrew is is right, you need index for getrandom, dang it
I used a Doubly Linked List to store the vals and operate in O(1) time. Is that overcomplicating things?
Traversing a linked list is O(n). The getRandom method is no longer O(1).
If you use a array removing anything that is not at the end (or front, depending on how you store data in the array) is also O(n).
In numMap are the values mappedd as.{val:index} or {index:val} ?
The numMap is val: index. The numList is what gives you index: val.
I was given a variation of this problem in an interview last week.
For anyone interested in how'd it go for a normal-ish interviewee:
I had similar solution of keeping a set(good for search) AND a vector(good for random access) and was struggling to optimise the remove (`find` operation in my case).
The interviewer gave a hint "can you try to combine the two data structures?"
And it was a good hint because combining means making links to refer any vector index from the set, and I was able to think of Map in a lil bit.
@@ohyash Thanks for sharing
Hm, thanks man@@ohyash
Can't we just construct a basic hash set our selves? like using linear probing so we actually have a build-in index for elements.
every crud operation is O(1) in hashmap. so why we cant use hashmap in this question
Doesn't using len making it O(n) though?
nvm just found out len is O(1) in python
First
Why not use a linked list?
Searching to check if the element exist in a linked list is O(n) in a linked list making it violate our condition of it being O(1)
Hi. I use the build set type.
class RandomizedSet:
def __init__(self):
self.setNum = set([])
def insert(self, val: int) -> bool:
isPresent = val not in self.setNum
self.setNum.add(val)
return isPresent
def remove(self, val: int) -> bool:
isPresent = val in self.setNum
self.setNum.discard(val)
return isPresent
def getRandom(self) -> int:
return random.choice(list(self.setNum))
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
The memory used is equal of your solution. However, my runtime if almost 3x your solution. I guess because I needed to convert the set into a list to use the random. What do you think?
Yes, converting the set into a list is O(N) time complexity because it has to go through all the elements in the set. So your getRandom() is O(N) time complexity, not O(1).
Since the problem explicitly asks for an O(1) average time complexity for getRandom(), the solution you posted doesn't fulfill the criteria.