Quick Overview

This multipart question evaluates spatial and analytic geometry for exact area computation, combinatorial counting and probability for card-hand enumeration, and discrete optimization and worst-case algorithmic analysis as exemplified by the two-egg drop problem.

Calculate area, flush probability, egg drops

Company: Talroo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

##### Question Given two quarter-circles inside a 1×1 square (centers at bottom-left and top-right corners), find the exact area of their overlapping region. From a standard 52-card deck draw 5 cards at once. What is the probability of getting a flush (five cards of the same suit) while excluding straight flushes? Show the counting formula. With a 100-floor building and unlimited marbles but at most two allowed to break, design a strategy that minimizes the worst-case number of drops needed to determine the highest safe floor, and state that minimum number of drops, explaining your reasoning.

Overview: This multipart question evaluates spatial and analytic geometry for exact area computation, combinatorial counting and probability for card-hand enumeration, and discrete optimization and worst-case algorithmic analysis as exemplified by the two-egg drop problem.

You have a building with n floors (1..n), unlimited marbles, but at most two marbles are allowed to break in total. Determine the minimum number of drops required in the worst case to guarantee finding the highest safe floor (the highest floor from which a marble does not break). Return that minimum number.

Constraints

  • 1 <= n <= 10^12
  • You may adapt your next drop based on previous outcomes.
  • At most two marbles may break (equivalent to two eggs).
  • Return the minimum number of drops in the worst case.
  • Target time complexity: O(1) or O(log n).
  • Use 64-bit integer arithmetic; avoid floating-point rounding.

Hints

  1. With two breakable marbles, the optimal strategy uses decreasing step sizes: t, t-1, t-2, ...
  2. You can cover t(t+1)/2 floors in t drops in the worst case.
  3. Find the smallest integer t such that t(t+1)/2 >= n; use integer square root to avoid floating-point issues.

Loading coding console...

Show the approach

Approach

With two breakable marbles, an optimal strategy is to drop the first marble at floor t, then t+(t-1), then t+(t-1)+(t-2), and so on. In the worst case, you will make t drops: either the first marble breaks on the k-th drop and you use up to (k-1) additional drops with the second marble to search the last interval, or it never breaks. The total number of floors safely covered equals the triangular number t(t+1)/2. Therefore, the minimum worst-case drops is the smallest integer t such that t(t+1)/2 >= n. The implementation computes t using integer square root and verifies coverage.

Time complexity:
O(1)
Space complexity:
O(1)