Hudson River Trading–styleInternAlgorithm Development InternshipQuestion #59
You roll a six-sided fair die repeatedly until you obtain each face at least once. On average, how many times do you need to roll the die?
Free worked solution · Quant Blueprint
147/10 = 14.7 rolls on average.
- After k different faces have appeared, the probability the next roll is new is (6 − k)/6.
- The waiting time to the next new face is geometric with mean 6/(6 − k), counting its successful roll.
- Add the six stages: 1 + 6/5 + 6/4 + 6/3 + 6/2 + 6 = 14.7. Linearity of expectation justifies adding their means.
Common mistake
Six is the minimum, not the mean. Repeats become especially costly when only one face remains unseen.
Follow-up
For n equally likely faces, the expected collection time is nHₙ, where Hₙ = 1 + 1/2 + ⋯ + 1/n.
Original educational explanation for this practice question. Reviewed . Firm-style practice; the label describes the collection’s preparation context.
More Hudson River Trading–Style Intern Questions
Given an array of integers, determine for each number if it can be written as the sum of two Fibonacci numbers.Given a set of points on the coordinate plane, determine how many distinct squares can be formed using these points as vertices.Given a set of points on a coordinate system, determine how many rectangles can be formed such that all four corners of the rectangle have their vertices among the given points.Given two strings S1 and S2, find the length of their longest common subsequence. If there is no common subsequence, return 0.q1: Check if given numbers can be written as the sum of two numbers in the Fibonacci sequence. q2: Perform specified data manipulation tasks using pandas. q3: Count the number of non-axis-aligned squares that can be formed from a list of points. q4: Count the number of non-axis-aligned rectangles that can be formed from a list of points.
Practice the Reasoning Behind the Answer
Bring your target roles and interview timeline to a free quant consult. Discuss your preparation priorities and how Quant Blueprint’s lessons, practice and mock interviews can help.
Book a Free Quant ConsultYour goals · your preparation · your next steps