Interview Question
Country: United States
A simple recursion solution is:
public Vector<Integer> eraseOddNumber(Vector<Integer> v) {
return eraseOddNumberHelper(v, 0);
}
private Vector<Integer> eraseOddNumberHelper(Vector<Integer> v, int ndx) {
if (v == null || ndx >= v.size()) {
return v;
}
if (v.get(ndx) % 2 == 1) {
v.remove(ndx);
} else {
ndx++;
}
return eraseOddNumberHelper(v, ndx);
}
vector<int> removeOddNums(vector<int> vec) {
for (int i = 0; i < vec.size();) {
if (vec[i] % 2 == 1) {
vec.erase(vec.begin() + i);
} else {
++i;
}
}
return vec;
}
That solution it's not nice because every time you erase an element you have to move all the next ones ones place to the left, so it's a quadratic algorithm. The best approach I think would be to do something like the partition of Quicksort, and then when you are finished you resize the vector to hold only the even numbers. (Linear, in-place solution).
If it's not required for you to do it in place the easiest way it's to count the number of even elements, create a vector of exactly that size and copy them from the original array.
Also in your solution you are passing a vector by copy (that's already O(n) time and extra space you are consuming). Consider passing a pointer or using a reference instead.
The best way in which I think it can be done is by first taking out all the elements in a separate vector which satisfy the condition. Then removing all the elements from the given Vector. Later adding all the elements back into the given vector.
- vermashubhang June 15, 2014