0
\$\begingroup\$

I wrote some Java code for Spotify's Reversed Binary Numbers puzzle and I tested it on my machine and I am almost positive that it behaves as expected. However, when I send it to puzzle AT spotify.com it kicks it back saying I have the "wrong answer", and nothing else.

Frustrating as this is, I can't for the life of me seem to figure out why the code I have wouldn't work. I even went so far as to remove all error messages that result from bad input, thinking that maybe that was causing it to fail. I was wondering if anyone here with a keener eye than my own could possibly help me hunt down the bug?

Here is a snippet of the most relevant portion of the code:

/**
 * Reverse the bits of an integer between 1 ≤ n ≤ 1000000000.
 *    i.e. 11 (1011) becomes 13 (1101)
 *
 * @param n The integer to reverse.
 * @return The reversed integer.
 */
public static int reverseBits(int n) {
  // 1-indexed MSB Position
  int msbPosition = findMSBPosition(n);
  int reversed = 0;

  for (int i = 0; i < msbPosition; i++) {
    int mask = 1 << i;
    int bit = (n & mask) >> i;
    reversed |= (bit << (msbPosition - i - 1));
  }

  return reversed;
}

/**
 * Find the 1-indexed position of the MSB of a number.
 *    i.e. For the number 11 (1011), findMSBPosition() would return 4.
 *
 * @param n The number to find the MSB for.
 * @return The 1-indexed position of the MSB.
 * @protected
 */
protected static int findMSBPosition(int n) {
  int msbPos = 0;
  int testNum = 1;
  while (testNum <= n) {
    msbPos++;
    testNum <<= 1;
  }

  return msbPos;
}

The full code can be found in this gist.

As a caveat and as information I am NOT APPLYING TO SPOTIFY NOR HAVE ANY INTENTION TO. I'm just doing this to stay sharp and since "wrong answer" is less than helpful output I'd love to know where I messed up. Thank you so much.

\$\endgroup\$
0
2
\$\begingroup\$

The code (on the gist) currently handles only command line parameter inputs instead of stdin. From https://www.spotify.com/us/jobs/tech/reversed-binary/:

Input is read from stdin.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ oh wow -_- that happened to be the issue. Making that one tweak solved the problem. It definitely pays not to glaze over any portion of a problem description, and make sure I always have a thorough knowledge of the problem domain. Thanks so much for your sharp eyes and for helping me with this!! \$\endgroup\$ Feb 22 '13 at 20:20
3
\$\begingroup\$

I do not see any problems inside the given range. I would have used already existing methods:

public static int reverse2(final int n) {
    return Integer.valueOf(new StringBuilder(Integer.toBinaryString(n)).reverse().toString(), 2);
}

Which is probably to best readable version.


If we want to do it by ourself and do not want to create a string and stringbuilder:

With recursion:

public static int reverse3(final int newNumber, final int number) {
    if (number == 0)
        return newNumber;
    return reverse3((newNumber << 1) | (number & 1), number >> 1);
}

Without recursion:

public static int reverse4(int number) {
    int newNumber = 0;
    while (number != 0) {
        newNumber = (newNumber << 1) | (number & 1);
        number >>= 1;
    }
    return newNumber;
}

Hint: I have only considered the given range. I did not think about negative numbers.


You could try to avoid Scanner and use Integer.parseInt inside a try/catch. Who knows what they throw at you at the command line. The nextInt from Scanner does a Integer.parseInt, but it also tries to match tokens.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ +1 for both the Java-esque toBinaryString() version and the I-can-do-it-myself-Dad-look-no-hands version. The latter is more appropriate for an interview answer. \$\endgroup\$ Feb 22 '13 at 11:44
  • \$\begingroup\$ The existing methods would definitely be the way to go for most cases. However as @RossPatterson pointed out I was coming at it from an interview standpoint. Furthermore I was trying to keep the code as lean and mean as possible, maximizing throughput and minimizing stack space so I tried to keep it mostly to bitwise operations on primitives. However the recursive and dynamic solutions provided are definitely very interesting and could definitely be implemented as improvements. Thanks so much for your insight! \$\endgroup\$ Feb 22 '13 at 20:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.