How to return an iterator over even numbers, given an iterator over a list of integers?
I was asked this question in a java interview. I am assigned an iterator for a list of integers. I need to write a function that returns this iterator as an argument and returns an iterator for even numbers only. I was told I cannot change the original list of numbers. Hence, removing odd numbers from the list is not a solution. Please advise. Thank.
source to share
Well, you just need to create a new Iterator that takes an existing Iterator and overwrites its hasNext and the following methods. The only difficulty is that a good iterator that behaves nicely should obviously only use O (1) space, so creating a new list and using that bad style - hence we need a little bookkeeping. Something like the following, simplified pseudocode with no error handling, assuming null as an invalid value, etc., but for some general solution - should give you the basic idea:
Iterator<T> it;
T next;
NewIterator(Iterator<T> it) {
this.it = it;
setNext();
}
void setNext() {
while (it.hasNext()) {
T val = it.next();
if (validT(val)) {
next = val;
return;
}
}
next = null; // lets assume null is invalid.
}
boolean hasNext() {
return next != null;
}
T next() {
T ret = next;
setNext();
return ret;
}
source to share
Iterator<Integer> itr;
int cur;
OddIterator(Iterator<Integer> itr) {
this.itr = itr;
cur = 0;
}
public boolean hasNext() {
if ((cur & 1) == 1) {
return true;
}
while (itr != null && itr.hasNext()) {
cur = itr.next();
if ((cur & 1) == 1) {
return true;
}
}
return false;
}
public int next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
int tmp = cur;
cur = 0;
return tmp;
}
Hope this helps you. If there are any errors in my code. Please let me know.
source to share