Bird
Raised Fist0

Which line contains the subtle bug that can cause the function to return an invalid string with adjacent duplicates?

medium🐞 Bug Identification Q7 of Q15
Greedy Algorithms - Reorganize String (No Two Adjacent Same)
Consider this buggy code snippet for reorganizing a string. Which line contains the subtle bug that can cause the function to return an invalid string with adjacent duplicates? ```python freq = Counter(s) max_heap = [(-count, ch) for ch, count in freq.items()] heapq.heapify(max_heap) prev_count, prev_char = 0, '' result = [] while max_heap: count, ch = heapq.heappop(max_heap) result.append(ch) heapq.heappush(max_heap, (prev_count, prev_char)) # Line X prev_count, prev_char = count + 1, ch ```
ALine where heap is initialized with negative counts
BLine X: Always pushing prev_count and prev_char without checking if prev_count < 0
CLine where prev_count and prev_char are updated after pushing
DLine where result.append(ch) is called
Step-by-Step Solution
Solution:
  1. Step 1: Identify bug in heap push

    Line X pushes prev_count and prev_char unconditionally, even when prev_count is zero, causing duplicates.
  2. Step 2: Correct approach

    Should push prev_count and prev_char only if prev_count < 0 to avoid placing same char consecutively.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Unconditional push causes adjacency violation [OK]
Quick Trick: Must check prev_count < 0 before pushing back [OK]
Common Mistakes:
MISTAKES
  • Forgetting condition before pushing back
  • Assuming always safe to push previous char
  • Misplacing update of prev_count
Trap Explanation:
PITFALL
  • Many candidates miss the conditional check, causing subtle adjacency bugs.
Interviewer Note:
CONTEXT
  • Tests bug identification in near-correct greedy heap code.
Master "Reorganize String (No Two Adjacent Same)" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Greedy Algorithms Quizzes