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.