FastPrepFair Coin from a Biased Coin
Problems/Fair Coin from a Biased Coin

Fair Coin from a Biased Coin

Anthropic logoAnthropic● EasyFULLTIMEPHONE SCREEN
QuestionExamples

Problem statement

Source note: In a coding phone screen the candidate had to turn a biased coin into a fair coin, and the interviewer said to simply implement it instead of proving why it is fair. The same round had a second, debugging part that the report does not describe.

The report gives no interface, input format, limits or examples. Practice choices: the biased coin's results arrive as a recorded string of H and T instead of a function you call; flips are read in non-overlapping pairs from the start; a pair of two different flips gives its first flip as the fair result, and a pair of equal flips is thrown away; you return up to k fair results in order and stop once you have k; if the flips run out first you return what you have, and a last unpaired flip is ignored. The limits and all examples are ours. The debugging part is not part of this problem.

The judged task matches the report at about 70%.

You need a fair coin, but the only coin you have is biased. It lands heads with some unknown probability p, where 0 < p < 1, and tails otherwise, and every flip is independent of the others.

The string flips records the biased coin's results in order: 'H' is heads and 'T' is tails. Turn it into at most k fair results with this procedure:

  1. Read the flips in consecutive pairs that do not overlap: positions 0 and 1, then 2 and 3, and so on.
  2. If the two flips of a pair differ, the pair produces one fair result equal to its first flip: HT gives 'H' and TH gives 'T'.
  3. If the two flips of a pair are the same (HH or TT), the pair produces nothing and is discarded.
  4. Stop as soon as k fair results have been produced. If the flips run out first, stop there. A last flip without a partner is ignored.

Return the fair results in the order they were produced, as one string. It can be shorter than k, or empty, when the flips run out.

The problem statement continues
Pro

Examples

Example 1

flips = "HHTHTTHT"k = 2return = "TH"

The pairs are HH, TH, TT and HT. HH and TT are discarded. TH gives T and HT gives H, so the two fair results are "TH".

02 · Example 2
FastPrep Pro
Reported in 1 Anthropic interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week
All Anthropic interview questionsSee Anthropic hiring insights
CodePython 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
from collections import defaultdict
 
class Solution:
def solve(self, values, queries):
# Build the adjacency structure
n = len(values)
graph = defaultdict(list)
for u, v in queries:
graph[u].append(v)
 
best = [float("inf")] * n
heap = [(0, 0)]
while heap:
cost, node = heapq.heappop(heap)
if cost > best[node]:
continue
Run and Submit unlock with Pro
FastPrep Pro
Reported in 1 Anthropic interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week