I added one line but also removed one :-)
class Solution(object): def __init__(self, nums): self.pick = lambda target: random.choice([i for i, num in enumerate(nums) if num == target])
@StefanPochmann It is surprising that it is accepted because it creates an array of size len(nums) if all nums are the same, and there is a test like that. And, unfortunately, neither
sample work with generators (the latter is surprising because they could just make it use Reservoir Sampling algorithm).
@SergeyTachenov I just tested it, the only test case where all numbers are the same is
nums = . The
choice function could also use reservoir sampling, no?
@StefanPochmann Yes, of course it could, I have no idea what I was thinking. These 04:30 am contests certainly have negative effect on thinking ability.
It's weird that you only see
nums =  because my Java code failed on something that had a lot of 3's in there. Maybe there were a few other numbers mixed in, though, I'm not sure, and I can't see my past submissions for contest problems.
@SergeyTachenov Unless the test cases were changed, I think you're talking about
nums = [1,2,3,3,3]. And maybe you're confusing
nums with the
target parameters? There are 5000
pick calls in that test case and every time it's
target = 3.
I just tested some more, the largest list I ever build has 22 indexes. Determined with this:
class Solution(object): def __init__(self, nums): self.nums = nums def pick(self, target): indexes = [i for i, num in enumerate(self.nums) if num == target] if len(indexes) > 21: return None return random.choice(indexes)
This gets "Wrong Answer", but if I change 21 to 22, it gets accepted.
@StefanPochmann @SergeyTachenov While possibly unrelated, can you please suggest where I could read up on problems like these? Lately, it seems a lot of the problems are based on uniformly random choices.
@StefanPochmann Sure, that's what I was thinking about. Didn't realize those were arguments to pick calls.
@babhishek21 This particular problem is about Reservoir Sampling, which I learned from Wikipedia. Other problems about uniformly random choices require totally different approaches, that's one of the reasons they are difficult. Unless you know the right algorithm in advance, you'll have to know the probability theory pretty well to figure out one yourself.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.