Top 4 Bit manipulation Interview Questions
Browse 4 real-world technical and behavioral interview questions about Bit manipulation. Review scenarios, edge cases, and architectural best practices.
Assign n tasks to n workers at minimum cost, with n up to 20. Why a bitmask, and what does it cost?
Bitmask DP keeps the cheapest cost for every subset of workers already used. The number of set bits says which task comes next, so there are 2^n states with n moves each, O(2^n * n) time and 2^n memory. At n = 20 that is about a million states, where trying all 20! orders is hopeless.
Every number in the array appears three times except one. Find the single number in O(1) extra space, and make sure it works for negatives.
Count, for each of the 32 bit positions, how many numbers have that bit set, and keep the count modulo 3. Tripled values contribute multiples of 3, so the bits with a remainder belong to the single number. Setting bit 31 makes a Java int negative, so negative answers come out right in O(32n) time and constant space.
Count the set bits in a 32-bit integer. Now tell me what your loop does when I hand it a negative number.
Shifting and masking works only if the shift does not sign-extend, so a signed right shift on a negative value never terminates. Either shift with the unsigned operator or clear the lowest set bit with n and n minus 1, which terminates for every input including the minimum value.
Every value in an array appears twice except one. Find it, and tell me when bit tricks are worth reaching for
XOR-folding the array leaves the unpaired value because a^a is 0 and XOR is commutative and associative, giving O(n) time and O(1) space under a precondition worth stating. That specific trick is narrow; masks used as integer sets are the part of bit manipulation that earns real work.