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 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!!
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!
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.
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.
@@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?
@@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.
@@nikhil_a01 Yeah i tried to implement this getRandom method originally using set, if we pop and item from set, store it in temp variable, and add back it again and return the temp, when called getRandom, it kind of keep cycling in a ordered fashion, it was not random
Hey Neetcode, I think this is not a nice implementation as 1- the pop() and append() aren't O(1) operation, 2- it abstract away the hashing part behind the hashmap.
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 :)
hey @NeetCode, I remember this question, the first time I saw the question is you asked in the mock interview to that meta intern youtuber I don't remember his name and I am sure he was rejected at the end of the interview.
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
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
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).
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.
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)) `
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.
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 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!!
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!
I was asked this in a Bloomberg phone interview yesterday.
More tricky than what i figured at first sight ! Thanks for the video :)
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.
man being at google u are so much consistent , quite remarkable. can u make a video on "work pressure" at google .
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 🎉👏
@@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?
@@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.
@@nikhil_a01 Yeah i tried to implement this getRandom method originally using set, if we pop and item from set, store it in temp variable, and add back it again and return the temp, when called getRandom, it kind of keep cycling in a ordered fashion, it was not random
Hey Neetcode, I think this is not a nice implementation as 1- the pop() and append() aren't O(1) operation, 2- it abstract away the hashing part behind the hashmap.
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
Thanks NeetCode! just want to say it actually won't work when removing the last item! changing line 20 and 21 will fix it.
what an explanation man, perfect !!! 🙌🙌🙌
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 :)
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 🙂
Hi...please make a video on Logic building and how to increase problem solving skill for beginners...! Using python.
Congrats on 100k subscribers 🎉👏
hey @NeetCode, I remember this question, the first time I saw the question is you asked in the mock interview to that meta intern youtuber I don't remember his name and I am sure he was rejected at the end of the interview.
thank you for a detailed and easy explanation buddy!
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
How to solve this problem on a locally installed python and run the test cases manually??
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
That's awesome man, thanks a lot :)
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
Hello sir ur videos are great,amazing explanation,please make it in java language
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).
every crud operation is O(1) in hashmap. so why we cant use hashmap in this question
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.
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
Please do system design videos
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)) `
Doesn't using len making it O(n) though?
nvm just found out len is O(1) in python
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)
First
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.