My friend was asked this question in an interview:
We have a vector of integers consisting only of
deleteconsists of selecting consecutive equal numbers and removing them. The remaining parts are then attached to each other. For e.g., if the vector is [0,1,1,0] then after removing [1,1] we get [0,0]. We need one
deleteto remove an element from the vector, if no consecutive elements are found.
We need to write a function that returns the minimum number of
deletes to make the vector empty.
For e.g., in case of
[0,1,1,0], we need
2 deletes whereas in case of
[1,0,1,0], we need
Pseudo code below:
I am unsure how to solve this question. I feel that we can use a greedy approach:
a. Remove all consecutive equal elements and increment the
delete counter for each;
b. Remove elements of the form
<a, b, c> where
a!=b, because of we had multiple consecutive
bs, it would have been deleted in step (a) above. Increment the
delete counter once as we delete one
c. Repeat steps (a) and (b) as long as we can.
delete counter once for each of the remaining elements in the vector.
But I am not sure if this would work. Could someone please confirm if this is the right approach? If not, how do we solve this?
Source: Windows Questions C++