Amazon Interview Question
Software Engineer / Developerspaint like BWBWWBWWWB ......
how to generate two or more W ???
Sol : After painting by W leave some space without paint. Again paint with W.
Consider 8 sectors on the disk. Paint 4 consecutive sectors with one paint, say White. Then paint one adjacent sector with Black paint. Then the next adjacent sector to this one with White paint and the remaining two sectors with Black paint.
So the disk now looks like ....W W W W B W B B... in a circular fashion.
Once you can see a sequence having 4 consecutive whites, you can tell which direction the disk is spinning.
After 4 whites, if you get one black and then one white, it is spinning in the clockwise direction.
After 4 whites, if you get 2 blacks and one white, it is spinning in the anti-clockwise direction.
Oops ! I have correction in the last two lines in my answer:
So the disk now looks like ....W W W W B W B B... in a circular clockwise fashion.
I meant After 4 whites, if you get one black and then one white, it is spinning in the ANTI-clockwise direction.
After 4 whites, if you get 2 blacks and one white, it is spinning in the Clockwise direction.
I've verified that WWBBBWBW is one of the correct answer.
If we use binary, the equivalent question is:
" find an eight digital binary string where the circular left shift and the circular left shift for the inverse string are different."
This brings me to think:
" Is there an invariant while doing the left shifting? (no matter how we do circular left shift on this string, we can apply some logical operation to that binary string and get an invariant) while inverting that string changes this invariant? "
Assign uniques codes to clockwise and counter-clockwise. Whichever one appears will indicate direction of spin.
This problem is analogous to finding Endianess.
I got this question in cisco....
paint with white and black each color is painted only once...
say u split the cd into 8 sectors.... pain the first sector white and second sector black...
if it is rotating clockwise... u will see the white first and then black... if it is anticlockwise... u will see black with an interval of 6 sectors and then u will see white...
I know i have not explained my solution clearly.. but i guess u guys are intelligent enough to understand.
Blanks are unnecessary. I found that the easiest way is to paint it as BWBWWB.
If the sensor detect BWWBWB or BWBBWW, the CD runs the opposite direction.
One possible solution can be WBBWWWB with the most optimised approach.
- Anonymous May 28, 2008Please validate, if posible...
Cheers!!