I just went back to my hotel from LinkedIn onsite interview. It could be my last onsite interview of my first full time job seeking. Honestly speaking, finding a job was extremely frustrating and painful. But as Ray wrote in his book PRINCIPLES, “Every time you confront something painful, you are at a potentially important juncture in your life — you have the opportunity and to choose healthy and painful truth or unhealthy but confortable delusion. It is a chance to identify your weakness and grow up.”
Expected Cost of Linear Probing
Danni is taking Comp580 at Rice. She is learning to analyze the expected cost of linear probing which is used to handle the collision in hashing. I want to share some interesting results without diving into details.
Therom: With 3-independent hashing we can prove an O(logn) expected costs of look up.
Therom: With 5-independent hashing we can prove an O(1) expected costs of look up.
The proof are basically propability and statistics, it needs to use Chebyshev’s Inequalities, 4th moment bound and the variable independence derived from the 3/5-indenpendent hashing. If interested, this stanford lecture note is very useful.
My First Post
This is my first personal webiste. Danni helped me a lot in building the enviroment!
The blog would track my daily study and thoughts. Hopefully, I can update it continuously…
Useful links to build your hexo website:
https://hexo.io/docs/setup
https://www.jianshu.com/p/5fc4672b7d2e