News for hackers. Stuff that matters.

A comment on Asana Engineering Interview Guide. Parent comment

Re:Asana Engineering Interview Guide by adrianN on Tuesday March 29, 2016 @04:32AM (#11380218)
If they say average case O(1), worst case O(n), hit them with them with O(log n / loglog n) with high probability from a simple balls-into-bins type argument.
[ Parent | on HN ]
Re:Asana Engineering Interview Guide by nialo on Tuesday March 29, 2016 @08:24AM (#11380921)
Could you expand on the balls-into-bins argument here? It's not quite obvious to me, but I'd really like to understand.
[ Parent | on HN ]
Re:Asana Engineering Interview Guide by adrianN on Tuesday March 29, 2016 @08:52AM (#11381041)
Items are balls, slots in your table are bins. Hash functions are assumed to distribute them randomly (uniformly). See also the Wikipedia article on Balls-into-Bins.

https://en.wikipedia.org/wiki/Balls_into_bins

This reference from the wiki is good http://www14.in.tum.de/personen/raab/publ/balls.pdf

[ Parent | on HN ]