Interview Question
Software Engineer Interview New York, NY
Facebook(a) first, write a function to calculate the hamming
distance between two binary numbers (b) write a function that takes a list of binary numbers and returns the sum of the hamming distances for each pair (c) find a solution for (b) that works in O(n) time.
Interview Answer
9 Answers
(for question 2)
public static int hammingDistance(String a, String b)
{
int numDigits = Math.max(a.length(), b.length());
int numDiff = 0;
for (int i = 0; i < numDigits; i++)
{
String ithDigitA = extractDigit(a, i, numDigits);
String ithDigitB = extractDigit(b, i, numDigits);
if (!ithDigitA.equals(ithDigitB)) numDiff++;
}
return numDiff;
}
public static String extractDigit(String a, int i, int n)
{
if (i < n  a.length()) return "0";
return a.substring(in+a.length(), in+a.length()+1);
}
public static int setHamming(String[] a)
{
int numDiff = 0;
int numDigits = 0;
for (int i = 0; i < a.length; i++)
{
numDigits = Math.max(numDigits, i);
}
for (int i = 0; i < numDigits; i++)
{
int num0s = 0;
int num1s = 0;
for (String aa : a)
{
String ithDigitAA = extractDigit(aa, i, numDigits);
if (ithDigitAA.equals("0"))
{
num0s++;
}
else
{
num1s++;
}
}
numDiff += (num0s * num1s);
}
return numDiff;
}
A:
int distance( int num1, int num2 )
{
int distance;
while( num1 != 0 && num2 != 0 )
{
distance += num1&1!=num2&1;
num1=num1>>1;
num2=num2>>1;
}
return distance;
}
B:
int distanceSum( std::vector<int> nums )
{
std::unordered_map<int,int> digits;
for( auto& num : nums )
{
int digit = 1;
while( num != 0 )
{
digits[digit]+=num&1;
num = num>>1;
digit++;
}
}
int distanceSum = 0;
for( auto& p : digits )
{
distanceSum += nums.length()p.second;
}
return distanceSum;
}
for Problem C:
/**
* This solution is O(n)
*I wrote it this way so its easier to be understood.
**/
public int getHammingTotalFromBinaryNumbersList(List<String> binaryNumbers){
Map<String,Integer> binaryCounter = new HashMap<String,Integer>; // Key is the <position>_[1 or 0] on the binary number, so if you're at position 1, and you get 0, the key will be 0_1
String positionKey;
int totalCount;
int maxPosition = 0;
foreach(String binaryNumber in binaryNumbers){
if(binaryNumber.Length1 > maxPosition){
maxPosition = binaryNumber.Length1;
}
for(i = 0; i<binaryNumber.Length; i++){
positionKey = i+"_"+binaryNumber.charAt(i);
if(binaryCounter.contains(positionKey)){
//increment the counter inside
totalCount = binaryCounter.get(positionKey);
binaryCounter.put(positionKey, ++totalCount);
}else{
binaryCounter.put(positionKey,1);
}
}
}
//now that we finished the binaryCounter Map, we basically just multiple each values and sum the total.
int hammingTotal = 0;
for(int i = 0; i < maxPosition; i++ ){
if(binaryCounter.containsKey(i+"_1") && binaryCounter.containsKey(i+"_0")){
hammingTotal += binaryCounter.get(i+"_1")*binaryCounter.get(i+"i_0");
}else{
continue;
}
}
return hammingTotal;
}
10001
10101
int GetHammingDistance(string s1, string s2)
{
Debug.Assert(s1.Length == s2.Length);
int distance = 0;
for(int i=0; i<s1.Length;i++)
{
if(s1[i]!=s2[i])
{
distance++;
}
}
return distance;
}
X= 1001
Y= 1011
Z= 0010
XY, XZ, YZ
(3c2) = 3 combinations.
GetAllPairsHammingDistance(List<string> input, int n, out List<int> distances)
{
if(n==2)
{
distances.Add(GetHammingDistance(input[0], input[1]));
}
for(int i=0; i<n, i++)
{
GetAllPairsHammingDistance(input,n1,distances);
Swap(input, i, n);
}
}
GetAllPairsHammingDistance(xyz, 3, "")
GetAllPairsHammingDistance(xyz, 2, "")=> {XY}
GetAllPairsHammingDistance(zyx, 2, "")=> {XY, ZY}
GetAllPairsHammingDistance(zxy, 2, "")=> {XY, ZY, ZX}
XYZ
0 1 2 = 3
X Y Z
 
 0 1
 Y

_ 0 1 = 2
Y Z
 
 _Z
_Y
Problem 1. Add two binary numbers represented as ASCII strings with result
also in form of an ASCII string
//
// Add two binary strings, the solution as follows:
// 1) convert binary strings to unsigned integers
// 2) Add resulting integers
// 3) Convert the result back to binary string
// 4) Reverse the string to obtain the resulting string
//
//
// Convert binary ASCII string to unsigned integer by successive divide by 2
//
uint binStr_to_uint(const char *pStr, int *size)
{
char *pEnd = pStr;
uint num = 0;
while(*pEnd)
num = (num << 1) + (*pEnd++  '0');
*size = pEnd  pStr;
return num;
}
//
// Convert unsigned integer to binary string representation
//
void uint_to_binStr(uint num)
{
while(num) {
*pStr++ = (num & 1) + '0'; //create '0' or '1' char
num >>= 1; //divide by 2
}
*pStr = 0; //terminate the string
}
// Reverse a string
void reverseString(char *pStr)
{
char *pEnd = pStr;
while(*pEnd++)
;
pEnd = 2; //point to last string char
char *pTmp;
while(pStr < pEnd) {
*pTmp = *pEnd;
*pEnd = *pStr;
*pStr++ = *pTmp;
}
}
// Add two binary strings
char *addBinaryStrings(const char *pStr1, const char *pStr2)
{
int size1, size2;
uint num1 = binStr_to_uint(pStr1, &size1);
uint num2 = binStr_to_uint(pStr2, &size2) + num1;
int sizeRes = size1 > size2 ? size1 : size2;
char *pResult = malloc(sizeRes + 2); //add space for carry and EOS
if(pResult == 0)
return 0;
uint_to_binStr(num2, pResult);
reverseString(pResult);
return (pResult);
}
Problem 2. Find Humming distance between two numbers. The problem
did not specify what format the numbers are in, so I assumed unsigned
integers.
//
// Find Humming distance
//
int hummingDistnce(uint num1, uint num2)
{
num1 = num1 ^ num2; //Humming distance is simply an XOR
num2 = 0;
while(num1) {
++num2; //count '1' bits
num1 &= num1  1;
}
return num2;
}
The second part of the problem is simple, just traverse the list selecting pairs of numbers and call hummingDistance() function each time.
Corrections to my previous example:
// Convert binary ASCII string to unsigned integer by successive divide by 2
should say ....multiply by 2 instead of divide by 2
Another minor error fix,
function uint_to_binStr(uint num) definition should also have a pointer to char parameter like below:
void uint_to_binStr(uint num, char *pStr)
Third correction,
In function reverseString(), the temporary char variable should be defined as "char tmp;" instead of "char *pTmp", so the code block should be:
char tmp;
while(pStr < pEnd) {
tmp = *pEnd;
*pEnd = *pStr;
*pStr++ = tmp;
Add Answers or Comments
To comment on this question, Sign In with Facebook or Sign Up
(for question 1)
public static String addBinaryStrings(String a, String b)
{
if ((null == a)  (null == b)) return null;
return int2bstring(bstring2int(a) + bstring2int(b));
}
public static int bstring2int(String a)
{
int sum = 0;
int multiplier = 1;
while (a.length() > 0)
{
String lastChar = a.substring(a.length()2, a.length());
if (lastChar.equals("1")) sum += multiplier;
multiplier *= 2;
a = a.substring(0, a.length()1);
}
return sum;
}
public static String int2bstring(int i)
{
if (0 == i) return "0";
String s = "";
while (i > 0)
{
if ((i % 2) == 0)
{
s = "1" + s;
}
else
{
s = "0" + s;
}
i /= 2;
}
return s;
}