Minimum Egg Drops
Updated
Problem statement
You have eggs identical eggs and a building with floors numbered from 1 through floors. There is an unknown critical floor f from 0 through floors. An egg dropped from a floor above f breaks; an egg dropped from f or below survives.
A surviving egg may be used again. A broken egg is discarded. You may choose each next drop using all earlier outcomes. Return the smallest number of drops that is sufficient to determine f with certainty in the worst case.
With zero floors, f is already known and the answer is zero.
Function
minimumEggDrops(eggs: int, floors: int) → intExamples
Example 1
eggs = 2floors = 36return = 8With two eggs, seven drops can cover at most 7+6+5+4+3+2+1=28 floors. Eight drops can cover 8+7+6+5+4+3+2+1=36 floors, so eight is both necessary and sufficient.
Example 2
eggs = 3floors = 14return = 4Three drops with three eggs can cover at most 7 floors. Four drops can cover 4+6+4=14 floors, so the minimum worst-case count is four.
Example 3
eggs = 1floors = 4return = 4With only one egg, skipping a floor could leave its threshold unresolved after a break. Testing floors in order needs four drops in the worst case.
Constraints
1 <= eggs <= 10.0 <= floors <= 200.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Longest Increasing SubsequenceAmazon · ONSITE INTERVIEW
- Minimum Removals for a Nice ArrayAdobe · ONSITE INTERVIEWAdobe interview questions
- Longest Increasing SubsequenceMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Minimum Cost for TicketsRoku · ONSITE INTERVIEWRoku interview questions
- Longest Increasing SubsequencePeopleStrong · ONSITE INTERVIEWPeopleStrong interview questions
- Maximum Total Length of Non-Overlapping IntervalsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Russian Doll EnvelopesGoogle · ONSITE INTERVIEWGoogle interview questions
- Russian Doll EnvelopesInMobi · ONSITE INTERVIEWInMobi interview questions
- Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
- Longest Increasing SubsequenceAngel One · PHONE SCREEN
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)