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

9 Answers

0

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

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<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.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<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,n-1,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

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) + (*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.

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

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up