Today, I was having an Online assessment for recruitment, And there was a question.
You have given a CD (Compact Disk). CD has n sector which mean CD is basically an circular array of size n.
In each sector, we can store one bit only.(i.e. 0 or 1).
Example of CD with 7 sectors: 1001010
You have given intial state of that CD and you wanted to convert that into some final state.
You can only do write operation(meaning converting 0 to 1). Write operation is done by a writing head whose position are also given.
Note: position of writer has been fixed.
We can only rotate the disk, whether cirular left or right to adjust in order to write into that particluar sector. Take an example to understand,
IntitalState: 01010
FinalState: 01110
writer: 10010
Here, writer denotes that all position having 1 we can write into that particular sector of the CD. In one time, only one head can be used to write.
Task is to determine minimum cost require to convert the intitalState to finalState.
- Cost of doing a rotation (wether one right or left) is 2.
- Cost of writing in one index is 3.
So in above example, we first rotate the disk
InitialState: 01010 > 00101 > 00111
writer(fixed):10010 10010 10010
(rotate) (write)
Total cost here is 2X1 + 3X1 = 5
How one can solve this?
My approach:
What I was thinking, that we must first rotate the initial state such that max number of 1 present in initialState will match final state. Then, We must check what are all those places that are having missing 1.
Then mark all those missing 1 places, (store 2 in that position)
Then we keep doing Below:
- We starting matching (rotating either left or right) the string such that max no. of 2 matches with write head and we do the writing, repeat again until we have all 2 filled up.
Is this approach correct? Is there is any other approach?