I'm running Vista x64 SP2 and Windows Media Player 11. I have an NVIDIA GeForce 8600 graphics card. I also make sure that the "Allow screen saver during playback" is unchecked in WMP -> Tools -> Options. After 20 minutes my screen saver kicks in.

Anyhow I've solved the problem with the screen saver. I like to keep my system as updated as possible, so I install NVIDIA's drivers directly from their website. Yesterday I removed NVIDIA's drivers, and I let Windows install it's own drivers for the graphics card. Of course Microsoft is just packaging a form of NVIDIA's drivers, but now my screen saver stays disabled when I play a movie.

## Thursday, February 18, 2010

## Saturday, February 6, 2010

### Interesting HW interview question... Serial binary input divisible by 5

I'm in California at the third round of interviews and I'm asked a question that baffled me. Given a serial input of a binary number, write a state machine that tells if that value is divisible by 5.

I first solved the problem thinking the input was MSB first. This is pretty trivial. 5 states and some very simple movements. Then it was clarified that they wanted it solved LSB first. I thought about it but I could not come up with a solution.

It is now the next day and I approached the problem again. I have a good and clear solution, but I'd love to know if there is a better one.

WARNING - Solution below:

A single bit, in any location, when converted to decimal will always end in either 2, 4, 8, or 6 except of course the least significant bit which is 1.

1, 2, 4, 8, 16, 32, 64, 128, 256...

1, 2, 4, 8, 6, 2, 4, 8, 6...

A divide by 5 problem at any given time can be in one of five situations. It's either 0, 1, 2, 3, or 4 from being divisible by 5. Ie: it is 0 and is divisible, or 1 and needs another 4, or 2 and needs another 3...

By combining both of these ideas you can build a state machine with 20 states that easily solves this problem. It's like 5 small 4-stated machines. The 4-stated machine keeps moving between 2, 4, 8, and 6 when there's a 0 input, and moves to one of the other machines when there is a 1. Of course you need an extra start state to deal with the first bit. And anytime you are in the 0 4-stated machine then the value is divisible.

Best way to explain is by example:

current value, add value (c, a) where c goes from 0 to 4 and a is 2, 4, 8, or 6.

Starting in first bit state:

Value that will be given is 25 (11001).

1: First bit state moves to (1, 2) since current value is 1 and next bit will add 2.

0: (1, 2) moves to (1, 4) since current value is still 1 and next bit will add 4.

0: (1, 4) moves to (1, 8) since current value is still 1 and next bit will add 8.

1: (1, 8) moves to (4, 6) since current value is now 4 (9 divided by 5 leaves a remainder of 4) and next bit will add 6.

1: (4, 6) moves to (0, 2) since current value is now 0 (10 divided by 5 leaves a remainder of 0) and next bit will add 2.

That's it.

I first solved the problem thinking the input was MSB first. This is pretty trivial. 5 states and some very simple movements. Then it was clarified that they wanted it solved LSB first. I thought about it but I could not come up with a solution.

It is now the next day and I approached the problem again. I have a good and clear solution, but I'd love to know if there is a better one.

WARNING - Solution below:

A single bit, in any location, when converted to decimal will always end in either 2, 4, 8, or 6 except of course the least significant bit which is 1.

1, 2, 4, 8, 16, 32, 64, 128, 256...

1, 2, 4, 8, 6, 2, 4, 8, 6...

A divide by 5 problem at any given time can be in one of five situations. It's either 0, 1, 2, 3, or 4 from being divisible by 5. Ie: it is 0 and is divisible, or 1 and needs another 4, or 2 and needs another 3...

By combining both of these ideas you can build a state machine with 20 states that easily solves this problem. It's like 5 small 4-stated machines. The 4-stated machine keeps moving between 2, 4, 8, and 6 when there's a 0 input, and moves to one of the other machines when there is a 1. Of course you need an extra start state to deal with the first bit. And anytime you are in the 0 4-stated machine then the value is divisible.

Best way to explain is by example:

current value, add value (c, a) where c goes from 0 to 4 and a is 2, 4, 8, or 6.

Starting in first bit state:

Value that will be given is 25 (11001).

1: First bit state moves to (1, 2) since current value is 1 and next bit will add 2.

0: (1, 2) moves to (1, 4) since current value is still 1 and next bit will add 4.

0: (1, 4) moves to (1, 8) since current value is still 1 and next bit will add 8.

1: (1, 8) moves to (4, 6) since current value is now 4 (9 divided by 5 leaves a remainder of 4) and next bit will add 6.

1: (4, 6) moves to (0, 2) since current value is now 0 (10 divided by 5 leaves a remainder of 0) and next bit will add 2.

That's it.

Subscribe to:
Posts (Atom)