Expected Hash Collisions - Quant Trader Interview Question
Difficulty: Medium
Category: Number Theory & Algorithms
Practice quant interview questions from top firms including Jane Street, Citadel, Two Sigma, DE Shaw, and other leading quantitative finance companies.
Topics: probability, hashing, birthday-paradox, algorithms
Problem Description
Your team is building a high-frequency trading system. You're using a hash table to quickly look up order IDs. You have $M$ buckets in your hash table. You expect to insert $N$ order IDs into the table. Approximately how large can $N$ be before you should expect a hash collision?
Assume a perfectly uniform hash function.
Practice this medium trader interview question on MyntBit - the all-in-one quant learning platform with 200+ quant interview questions for Jane Street, Citadel, Two Sigma, and other top quantitative finance firms.