FastPrepMaximum Equal-Bit Pairs in a Subsequence
Problems/Maximum Equal-Bit Pairs in a Subsequence

Maximum Equal-Bit Pairs in a Subsequence

Amazon logoAmazon● MediumINTERNOA

Updated Nov 2026

QuestionExamples

Problem statement

Source note: This was a coding question in an Amazon online assessment for an SDE intern role. The candidate shared the full prompt: pick any subsequence of a binary string and count the neighbors that are the same bit, with the function name, two worked examples and the limits.

Nothing that changes the answer was missing. The third example here is new, and it shows that keeping both kinds of bits can win.

Our version is about 98% the same as the shared prompt.

You are given a binary string signal. Choose a subsequence of it: delete zero or more characters and keep the rest in their original order.

In the subsequence you keep, every two neighboring characters that are the same bit, "00" or "11", form one equal-bit pair. Pairs may share a character, so "111" has 2 pairs.

The problem statement continues
Pro

Examples

Example 1

signal = "10101"return = 2

Keep only the three '1' characters to get "111". It has 2 equal-bit pairs: the first and second characters, and the second and third characters.

No subsequence does better. A kept string with 3 pairs needs four equal bits, or all five characters in only two blocks of equal bits. The string has only three 1s and two 0s, and it switches bits at every step, so neither is possible. The answer is 2.

02 · Example 2
FastPrep Pro
Reported in 1 Amazon 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

More Amazon Online Assessment questions

  • Get Smallest Base SegmentOA · Seen Nov 2026
  • Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
  • Minimum Grid InconvenienceOA · Seen Nov 2026
  • Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
  • Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
  • First Non-Repeating CharacterOA · ONSITE INTERVIEW · Seen Nov 2026
  • Two SumOA · PHONE SCREEN · Seen Nov 2026
  • Minimum Merge ConflictsOA · Seen Nov 2026
  • Shopping Cart BillingOA · Seen Nov 2026
  • Fill One Exact-Length Binary WindowOA · Seen Nov 2026

Similar questions at other companies

  • Longest Subsequence That Is a SubstringBooking.com · OA
  • Count Digit Replacements with No Equal Adjacent DigitsMicrosoft · OAMicrosoft interview questions
  • Palindrome CounterGoldman Sachs · OAGoldman Sachs interview questions
  • Longest String ChainVisa · OAVisa interview questions
  • Minimum-Cost Digit String DecodingSquadStack.ai · OA
  • Maximum Redundancy After One Segment FlipBloomberg LP · OABloomberg LP interview questions
  • Substrings Without a Target SubsequencePhonePe · OAPhonePe interview questions
  • Minimum Edit-Distance String for Each QueryTarget · OA
  • Longest Subsequence That Is a SubstringWells Fargo · OAWells Fargo interview questions
  • Non-Alternating Binary PartitionsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions

Amazon interview experiences

  • Amazon SWE OA with AI Coding: 1 Experience
  • Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
  • Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
  • Amazon BIE Intern SQL and Interview Questions: 17 Experiences
  • Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
  • Amazon SDE II (L5) Interview Questions: 5 Experiences
See Amazon 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 Amazon 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