Bit Manipulation Under Constraints | Dataford Interview Questions

Yelp's review-quality pipeline encodes each processed review batch as an integer fingerprint. Due to duplicated processing, every fingerprint appears exactly three times except one fingerprint that appears once. Given the list of fingerprints, return the unique value using bit manipulation.

You must run in linear time and use constant extra space. Input values are signed 32-bit integers, and the returned value must also be interpreted as a signed 32-bit integer.

Formal Specification

Implement single_number(nums), where nums is a non-empty list of integers. Exactly one value appears once, and every other distinct value appears exactly three times. Return the value that appears once.

Constraints

1 <= len(nums) <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
Exactly one value appears once
Every other distinct value appears exactly three times

Function Signature

def single_number(nums):

Your question is Bit Manipulation Under Constraints. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem