20bits: Interview Questions: Shuffling an Array | 20bits
Chris
· 1 year ago
I enjoy reading the posts on this blog. The posts related to programming are entertaining and help exercise my brain.
>> My next article is going to be more about the interview process rather than specific questions
Regarding the interview process, I've found this post very helpful. http://www.joelonsoftware.com/articles/Guerrill... Joel Spolsky has also written a book ("Smart and Gets Things Done") which elaborates on the same ideas in the blog post.
Note: - I could be wrong here but I think you're code example#1 has a typo, you define variable r and don't use it, and use variable k and don't define it
and shouldn't it be n= self.size in example#1 as well as example#2?
Jesse
· 1 year ago
cc,
You're right about the first point, but not the second. Both self.size and size work because we're inside the Array instance.
rue
· 1 year ago
Excellent note about the algorithm.
However, since pragmatism trumps all, the "right" way to shuffle an Array in Ruby is this:
class Array def shuffle! replace(array.sort_by { rand }) end end
As a bonus, it is a language/core lib bug and not your fault if there is a problem with the distribution ;)
Jesse
· 1 year ago
rue,
That's not really true, though. In fact, that "solution" violates multiple requirements of the problems.
One, it's not in-place. Two, whether or not the distribution is uniform depends on the sorting algorithm that <tt>sort_by</tt> uses.
What if the source and destination are picked using a random number generator N times? Given that the generator is unifrom, aren't all permutations possible?
Hanna
· 1 year ago
Hi, Great effort after reading this I really good very nice point how to shuffle array keep it up and post more article also check Pre Developer
Thanks
gman
· 1 month ago
I was asked this question in an interview. I gave the seemingly correct but subtly wrong solution. Good to know the correct solution.
All Comments
>> My next article is going to be more about the interview process rather than specific questions
Regarding the interview process, I've found this post very helpful.
http://www.joelonsoftware.com/articles/Guerrill...
Joel Spolsky has also written a book ("Smart and Gets Things Done") which elaborates on the same ideas in the blog post.
Nice post!
and shouldn't it be n= self.size in example#1 as well as example#2?
You're right about the first point, but not the second. Both self.size and size work because we're inside the Array instance.
However, since pragmatism trumps all, the "right" way to shuffle an Array in Ruby is this:
class Array
def shuffle!
replace(array.sort_by { rand })
end
end
As a bonus, it is a language/core lib bug and not your fault if there is a problem with the distribution ;)
That's not really true, though. In fact, that "solution" violates multiple requirements of the problems.
One, it's not in-place. Two, whether or not the distribution is uniform depends on the sorting algorithm that <tt>sort_by</tt> uses.
Great effort after reading this I really good very nice point how to shuffle array keep it up
and post more article also check Pre Developer
Thanks