Explore our sites

Stack Exchange
tour help
Take the tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 0 down vote favorite
1

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.

share|improve this question
1  
-1 for failure to Make sure you include your code in your question –  Ross Patterson Feb 22 '13 at 0:10
 
very sorry about that. Edited the question to include the relevant portion(s) of the code –  Travis Kaufman Feb 22 '13 at 3:38
1  
+1 for adding the code. –  Ross Patterson Feb 22 '13 at 11:39
add comment

closed as off-topic by Malachi, Jamal♦ Dec 11 '13 at 17:55

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question must contain working code for us to review it here. For questions regarding specific problems encountered while coding, try Stack Overflow. After getting your code to work, you may edit this question seeking a review of your working code." – Malachi, Jamal
If this question can be reworded to fit the rules in the help center, please edit the question.

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
1  
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!! –  Travis Kaufman Feb 22 '13 at 20:20
add comment
up vote 3 down vote

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.

share|improve this answer
1  
+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. –  Ross Patterson Feb 22 '13 at 11:44
 
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! –  Travis Kaufman Feb 22 '13 at 20:18
add comment

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