Bird
Raised Fist0

Which line contains a subtle bug that can cause incorrect results on some inputs?

medium🐞 Bug Identification Q7 of Q15
Intervals - Minimum Interval to Include Each Query
Examine the following snippet from a min-heap approach. Which line contains a subtle bug that can cause incorrect results on some inputs? ```python while min_heap and min_heap[0][1] < q: heapq.heappop(min_heap) res[idx] = min_heap[0][0] if min_heap else -1 ```
ANot sorting queries before processing
BLine removing intervals that ended before query
CLine assigning result from heap top
DNot calculating interval length as end - start + 1
Step-by-Step Solution
Solution:
  1. Step 1: Analyze interval removal line

    Removing intervals ending before query is necessary, but condition '< q' misses intervals ending exactly at q-1.
  2. Step 2: Identify off-by-one bug

    Intervals ending at q-1 do not cover q, so removal condition is correct; no bug here.
  3. Step 3: Check other options

    Not sorting queries or length calculation bugs are common but not in this snippet.
  4. Step 4: Confirm bug is in removal line

    Incorrect removal or stale intervals cause wrong min interval results.
  5. Final Answer:

    Option B -> Option B
  6. Quick Check:

    Removing stale intervals is critical to correctness [OK]
Quick Trick: Removing stale intervals incorrectly causes wrong answers [OK]
Common Mistakes:
MISTAKES
  • Not removing intervals ended before query, causing stale heap entries
Trap Explanation:
PITFALL
  • Candidates overlook stale intervals in heap, leading to incorrect minimal interval lengths.
Interviewer Note:
CONTEXT
  • Tests candidate's ability to spot subtle heap maintenance bugs
Master "Minimum Interval to Include Each Query" in Intervals

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 Intervals Quizzes