Given two 1d vectors, implement an iterator to return their elements alternately.
For example, given two 1d vectors:
v1 = [1, 2]
v2 = [3, 4, 5, 6]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be:
[1, 3, 2, 4, 5, 6].
Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?
Clarification for the follow up question - Update (2015-09-18): The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input:
[1,2,3]
[4,5,6,7]
[8,9]
It should return
[1,4,8,2,5,9,3,6,7].Using two iterators, alternatively calling get the next element from each iterator when call next() method for the ZigzagIterator object. If one iterator reaches to the end, then call the other one only from then on.
public class ZigzagIterator {
Iterator iFirst;
Iterator iSecond;
boolean first;
public ZigzagIterator(List v1, List v2) {
iFirst = v1.iterator();
iSecond = v2.iterator();
first = true;
}
public boolean hasNext() {
return iFirst.hasNext() || iSecond.hasNext();
}
public int next() {
int toReturn = 0;
if (first) {
toReturn = iFirst.next();
} else {
toReturn = iSecond.next();
}
if (!iFirst.hasNext()) {
first = false;
} else if (!iSecond.hasNext()) {
first = true;
} else {
first = !first;
}
return toReturn;
}
}
For the follow up, using a list of iterators.
public class CyclingIterator {
private List<iterator<Integer>> iterators;
int index;
public CyclingIterator(List<list<Integer>> lists) {
iterators = new ArrayList<>();
for (int i = 0; i < lists.size(); i++) {
iterators.add(lists.get(i).iterator());
}
}
public int next() {
if (!hasNext()) {
throw new RuntimeException("Empty iterator!");
}
Iterator<integer> curr = iterators.get(index);
int toReturn = curr.next();
if (!curr.hasNext()) {
iterators.remove(index);
} else {
index++;
}
if (index == iterators.size()) {
index = 0;
}
return toReturn;
}
public boolean hasNext() {
return iterators.size() > 0;
}
}
This comment has been removed by the author.
ReplyDeleteIs this an online class? If yes, which class?
ReplyDeletehttps://leetcode.com/problemset/algorithms/
DeleteThere could be many ways to implement this;
ReplyDeleteBelow is one of; where hasNext has O(size) complexity and next has O(1)
class CycleIterator implements Iterator {
private final List innerList;
private final List> items;
private int outerIndex = 0;
private int innerIndex = 0;
public CycleIterator(List> items) {
this.items = items;
innerList = new ArrayList<>();
buildInnerList();
}
/**
* O(size) where size is size of input list
*/
private void buildInnerList() {
innerList.clear();
for (List list : items) {
if (!list.isEmpty() && list.size() > outerIndex)
innerList.add(list.get(outerIndex));
}
outerIndex++;
}
/**
* O(size) where size is size of input list
*
* @return
*/
@Override
public boolean hasNext() {
if (innerIndex == innerList.size()) {
buildInnerList();
innerIndex = 0;
}
return !innerList.isEmpty();
}
/**
* O(1)
*
* @return
*/
@Override
public Integer next() {
return innerList.get(innerIndex++);
}
}
Another one is;
next is O(size) but can be done in O(1) by implementing own DLL so that remove is O(1)
hasNext is O(1)
class ZigZagIterator implements Iterator {
private LinkedList> iterators;
private int index = 0;
public ZigZagIterator(List> items) {
iterators = new LinkedList<>();
for (List list : items)
iterators.add(list.iterator());
}
@Override
public boolean hasNext() {
return !iterators.isEmpty();
}
@Override
public Integer next() {
Iterator current = iterators.get(index);
Integer next = current.next();
if (!current.hasNext())
iterators.remove(index); //this is O(n) But you can implement your own doubly linked list to make it work in O(1)
else
index++;
if (index >= iterators.size())
index = 0;
return next;
}
}
And
you can keep the index array of the list, whenever a list is exhausted, you update the index array by removing that index