Category: Interesting problems

Here I store some interesting questions and stories from the IT world.

Reversing a 32-bit number

Posted on

Let’s say you have a 32-bit number and you want to reverse it bitwise, regardless of the sign; 0x00000001 will become 0x80000000, and 0x71643257, or 01110001 01100100 00110010 01010111 in binary, will become 11101010 01001100 00100110 10001110, or 0xEA4C268E.

How do you do it in the most efficient way?

The trivial way is to iterate in a loop over 32 bits and on every iteration get a last bit from one of the ends, creating a new number bit by bit:

unsigned reverseBits(unsigned n) {
    unsigned result = 0;
    for (int i = 0; i < 32; ++i) {
        // Extract the least significant bit of `n` and shift it to the correct position
        result = (result << 1) | (n & 1);
        // Shift `n` to process the next bit
        n >>= 1;
    }
    return result;
}

And it works, but it is not efficient, mainly because of the loop itself, which introduces branches. We can play a bit with the loop, replacing for with do { … } while, but it will not save much. Is there a way to remove the loop altogether?

As a matter of fact, yes!

Observe with awe:
unsigned reverse(unsigned x) {
    	x = ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555);
    	x = ((x & 0x33333333) << 2) | ((x >> 2) & 0x33333333);
    	x = ((x & 0x0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F);
    	x = (x << 24) | ((x & 0xFF00) << 8) |
            ((x >> 8) & 0xFF00) | (x >> 24);
    	return x;
}

No branches, no loops, only shifts and logical operations.

Isn’t it genious? What a pity it’s not my code! 🙂 I also would solve the problem with the loop.

A game with coins

Posted on

Another logical riddle frequently asked at the interviews.

Two players play a game that involves a table shaped as a perfect circle with finite radius R and an unlimited set of disc-like coins of radius r, all of the same size and weight. The game is played as follows: the players place coins on the table in turns, one by one. Every coin has to lie flat on the table, it can’t lie on the other coins; the face of the coin should be touching the face of the table; the coin can’t dangle from the table’s edge; it can touch previously placed coins, but they can’t be pushed from their place or dropped from the table. The first player who can’t find a place for his coin loses.
Is there a winning strategy for one of the players? If yes, what is it?

The finite radius of the table and the non-zero radius of the coin, along with the requirement of the coin being laying flat on the face of the table, promises that the game is finite. This problem is known as the circle packing in a circle problem, and it is known to be a generally NP-hard, but for large difference between r and R the approximation of the upper bound for the number of coins is N ≈ 0,9×r 2/R 2​.

400 coins of r = 1 placed on a table of radius R = 21.69 without overlapping. No more coins can be added.
Courtesy of packomania.com.

There is a web site dedicated solely to solving this kind of problems.

Solution

Yes, there is a winning strategy; the player who makes the first turn always wins. He must place his first coin in the very center of the table; each next coin should be placed symmetrically from the place where the second player placed his coin, relative to the center of the table. If the second player succeeds to find a place for his coin, the strategy guarantees that at the next turn the first player will also succeed to place his one. If there is no enough place, the second player will hit the problem first.

Cutting a 3×3×3 cube into 27 1×1×1 cubes

Posted on

This question is one of the logical riddles that interviewers love to ask during job interviews:

There is a 3×3×3 cube. You are asked to cut it into 27 1×1×1 cubes. Every cut is straight and plain, but between the cuts the pieces can be rearranged freely. You are allowed to cut a part, put it on top of the other part and cut them together with the next cut. The question is: what is the minimal amount of cuts that is required for the task?

The original cube with proposed cuts

The trivial solution:

We can perform two cuts parallel to every coordinate plain (X00, 0Y0 and 00Z), just like shown on the illustration above. That would be 6 cuts, and the parts of the cube may be left as they were between the cuts. No rearrangements are needed.

Is there a possibility to achieve the same result with fewer cuts?

Solution 1:

It’s easy to see that every cut at most doubles the number of pieces, unless we put a piece in the way that it will be entirely omitted by the cut. We are going to get 27 cubes, which is less than 32 = 25, but more than 16 = 24. Therefore even theoretically we can’t achieve the goal with less than 5 cuts.

However, when we arrive to the 5th cut, we have to have 18 pieces. It’s more than we can achieve with 4 cuts, therefore we have to use 6 cuts.

Solution 2:

Let’s look at the central part of the big cube. When we finish the task, it becomes a 1×1×1 cube, but currently it is surrounded with cube’s material from all sides. This 1×1×1 cube has 6 faces. Among them, there are no two faces that can be created with the same cut. Therefore, clearing this cube from all other material requires 6 cuts.

Conclusion

The trivial solution is also the most effective one. 😜