Amazon Interview Question Software Developers
Country: United States
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class ResultIterator<E> {
Iterator<E> iter1;
Iterator<E> iter2;
Set<E> set;
Iterator<E> iterator;
public ResultIterator(Iterator<E> iter1, Iterator<E> iter2) {
this.iter1 = iter1;
this.iter2 = iter2;
set = new LinkedHashSet<E>();
iterator=set.iterator();
addElements(iter1, iter2);
}
public void addElements(Iterator<E> iter1, Iterator<E> iter2) {
while (iter1.hasNext()) {
set.add(iter1.next());
}
while (iter2.hasNext()) {
set.add(iter2.next());
}
}
public boolean hasNext() {
return iterator.hasNext();
}
public E Next() {
return iterator.next();
}
}
From your example, looks like corresponding words of each array index either match, or don't match (and will never match in the future). Given this, it's rather simple:
a = null, b = null;
for every time it.next() is called:
a = itA.next()
b = itB.next()
if(a == b) {
return a;
} else {
if(a != null) {
tmp = a;
a = null;
return tmp;
} else {
tmp = b;
b = null;
return tmp;
}
}
class ResultIterator{
private List<String> wrds;
ResultIterator(Iterator it1, Iterator it2){
wrds = new ArrayList<String>();
fillWords();
}
public boolean hasNext(){
return !wrds.isEmpty();
}
public String next(){
if(wrds.isEmpty()){
return null;
}
String ret = wrds.remove(0);
fillWords();
return ret;
}
private void fillWords(){
if(it1.hasNext()){
wrds.add(it1.next());
}
if(it2.hasNext()){
String s = it.next();
if(wrds.isEmpty() || !s.equals(wrds.get(wrds.size() - 1))){
wrds.add(s);
}
}
}
}
class ResultIterator<E> {
iterator<E> itr1;
iterator<E> itr2;
iterator<E> itr1_begin;
ResultIterator(iterator<E> itr1, iterator<E> itr2) {
this.itr1 = itr1;
this.itr2 = itr2;
this.itr1_begin = itr1;
}
bool hasnext {
if(itr1.hasnext()) return true;
else{
while(itr2.hasnext()){
iterator<E> temp_itr2 = itr2;
E current = temp_itr2.next();
iterator<E> _itr1 = itr1_begin;
boolean no_match = true;
while(no_match && _itr1.hasnext()) {
if(_itr1.next().equals(current) {
itr2.next();
no_match = false;
}
}
if(no_match) return true;
}
return false;
}
}
E next() {
if(!hasnext()) return null;
if(itr1.hasnext()) return itr1.next();
else itr2.next();
}
}
The trick here is to save the value in case where the data is different and consider on hasNext().
public static class ResultIterator <E extends Comparable<E>> {
private Iterator<E> itr1;
private Iterator<E> itr2;
private E savedNext = null;
ResultIterator(Iterator<E> itr1, Iterator<E> itr2) {
this.itr1 = itr1;
this.itr2 = itr2;
}
public boolean hasNext() {
return itr1.hasNext() || itr2.hasNext() || savedNext != null;
}
public E next() {
if (savedNext != null) {
E ret = savedNext;
savedNext = null;
return ret;
}
if (itr1.hasNext() && itr2.hasNext()) {
E nextItr1 = itr1.next();
E nextItr2 = itr2.next();
int cmp = nextItr1.compareTo(nextItr2);
if (cmp == 0) {
return nextItr1;
} else if (cmp > 0) {
savedNext = nextItr1;
return nextItr2;
} else {
savedNext = nextItr2;
return nextItr1;
}
}
if (itr1.hasNext()) {
return itr1.next();
}
return itr2.next();
}
}
class ResultIterator <E extends Comparable<E>> {
private Iterator<E> itr1;
private Iterator<E> itr2;
private E savedNext = null;
private int itrNo = 0;
ResultIterator(Iterator<E> itr1, Iterator<E> itr2) {
this.itr1 = itr1;
this.itr2 = itr2;
}
public boolean hasNext() {
return itr1.hasNext() || itr2.hasNext() || savedNext != null;
}
public E next() {
if(savedNext != null && itrNo != 0){
E nextItr = itrNo == 1 ? itr2.next() : itr1.next();
int cmp = nextItr.compareTo(savedNext);
if(cmp == 0){
savedNext = null;
itrNo = 0;
return nextItr;
} else if(cmp < 0){
return nextItr;
} else {
itrNo = 0;
return savedNext;
}
}
if(itr1.hasNext() && itr2.hasNext()){
E nextItr1 = itr1.next();
E nextItr2 = itr2.next();
int cmp = nextItr1.compareTo(nextItr2);
if (cmp == 0) {
return nextItr1;
} else if (cmp > 0) {
savedNext = nextItr1;
itrNo = 1;
return nextItr2;
} else{
savedNext = nextItr2;
itrNo = 2;
return nextItr1;
}
}
if(itr1.hasNext()){
return itr1.next();
}
return itr2.next();
}
}
package com.vidya.thread;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class ResultIterator <String extends Comparable<String>> {
private Set<String> resultSet;
private Iterator<String> setIterator;
ResultIterator(Iterator<String> itr1, Iterator<String> itr2) {
addToSet(itr1, itr2);
setIterator = resultSet.iterator();
}
private void addToSet(Iterator<String> itr12, Iterator<String> itr22) {
resultSet = new LinkedHashSet<>();
while(itr12.hasNext()){
resultSet.add(itr12.next());
}
while(itr22.hasNext()){
resultSet.add(itr22.next());
}
}
public boolean hasNext() {
return setIterator.hasNext();
}
public String next() {
return setIterator.next();
}
}
package com.vidya.thread;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
public class ResultIterator <String extends Comparable<String>> {
private Set<String> resultSet;
private Iterator<String> setIterator;
ResultIterator(Iterator<String> itr1, Iterator<String> itr2) {
addToSet(itr1, itr2);
setIterator = resultSet.iterator();
}
private void addToSet(Iterator<String> itr12, Iterator<String> itr22) {
resultSet = new LinkedHashSet<>();
while(itr12.hasNext()){
resultSet.add(itr12.next());
}
while(itr22.hasNext()){
resultSet.add(itr22.next());
}
}
public boolean hasNext() {
return setIterator.hasNext();
}
public String next() {
return setIterator.next();
}
}
I sincerely doubt that is possible. If the iterator does not generate an ordered sequence - this is not possible to crack it - an iterator does not traverse backward - unless it is ListIterator - and thus... we have a foundational problem with the question.
- NoOne February 04, 2017Given the iterators are generating ordered sequence - it is trivially same as the merge concept - and is highly doable - w/o any storage.
If not, I can not think of any solution.