Facebook Interview Question: (a) first, write a function t... | Glassdoor

## Interview Question

Software Engineer Interview New York, NY

# (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.
Tags:
algorithm, complexity, binary, big-o
Answer

## Interview Answer

10 Answers

2

(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;
}

Rahul on May 2, 2013
1

(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(i-n+a.length(), i-n+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;
}

Rahul on May 2, 2013
0

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 nums )
{
std::unordered_map 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;
}

Anonymous on May 10, 2013
1

for Problem C:

/**
* This solution is O(n)
*I wrote it this way so its easier to be understood.
**/

public int getHammingTotalFromBinaryNumbersList(List binaryNumbers){
Map binaryCounter = new HashMap; // Key is the _[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.Length-1 > maxPosition){
maxPosition = binaryNumber.Length-1;
}
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;
}

Kent Buenaventura on May 12, 2013
0

10001
10101

int GetHammingDistance(string s1, string s2)
{
Debug.Assert(s1.Length == s2.Length);

int distance = 0;
for(int i=0; i input, int n, out List distances)
{
if(n==2)
{
distances.Add(GetHammingDistance(input[0], input[1]));
}

for(int i=0; i {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

Vasu on May 19, 2013
0

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; //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 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.

ChrisN on Aug 19, 2013
0

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

ChrisN on Aug 19, 2013
0

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)

ChrisN on Aug 19, 2013
0

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;

ChrisN on Aug 19, 2013
2

public static int hammingDistance(int a, int b) {
int xor = a ^ b;
int distance = 0;
while (xor > 0) {
xor = (xor - 1) & xor;
distance++;
}
return distance;
}

public static int hammingDistance(int[] array) {
int sum = 0;
for (int i=0; i<32; i++) {
int mask = 1 << i;
int num0s = 0;
int num1s = 0;
for (int value : array) {
if ((value & mask) != 0) {
num1s++;
} else {
num0s++;
}
}
sum += num0s * num1s;
}
return sum;
}

Anonymous on Nov 11, 2014

## Add Answers or Comments

To comment on this, Sign In or Sign Up.