Bird
Raised Fist0

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

medium🐞 Bug Identification Q7 of Q15
Bit Manipulation - Maximum Product of Word Lengths
The following code attempts to find the maximum product of word lengths with no common letters. Which line contains a subtle bug that causes incorrect results on some inputs? ```python def maxProduct(words): n = len(words) masks = [] for word in words: mask = 0 for ch in word: mask |= 1 << (ord(ch) - ord('a') + 1) masks.append((mask, len(word))) masks.sort(key=lambda x: x[1], reverse=True) max_prod = 0 for i in range(n): if masks[i][1] * masks[i][1] <= max_prod: break for j in range(i + 1, n): if masks[i][1] * masks[j][1] <= max_prod: break if (masks[i][0] & masks[j][0]) == 0: max_prod = max(max_prod, masks[i][1] * masks[j][1]) return max_prod ```
ALine with masks.sort(key=lambda x: x[1], reverse=True)
BLine with mask |= 1 << (ord(ch) - ord('a') + 1)
CLine with if masks[i][1] * masks[i][1] <= max_prod: break
DLine with if (masks[i][0] & masks[j][0]) == 0:
Step-by-Step Solution
Solution:
  1. Step 1: Analyze bitmask construction

    Bit shift uses (ord(ch) - ord('a') + 1), which shifts bits starting at 1 instead of 0, misaligning character bits.
  2. Step 2: Consequence of bug

    This causes incorrect overlap checks because 'a' corresponds to bit 1 instead of bit 0, leading to false negatives or positives.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Bitmask shift must start at 0 for 'a' [OK]
Quick Trick: Bitmask shift must be zero-based for 'a' [OK]
Common Mistakes:
MISTAKES
  • Off-by-one bit shift in mask
  • Assuming sorting or pruning lines cause bugs
Trap Explanation:
PITFALL
  • Candidates often overlook off-by-one bit shifts, which silently cause wrong overlap checks.
Interviewer Note:
CONTEXT
  • Tests ability to spot subtle bitmask construction bugs
Master "Maximum Product of Word Lengths" in Bit Manipulation

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 Bit Manipulation Quizzes