Google Interview Question for SDE-2s


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

public class InterleaveIterator<E> implements Iterator<E> {
	
	private List<Iterator<E>> list;
	private int i;
			
	public InterleaveIterator() {
		initFields();
	}

	public InterleaveIterator(List<Iterator<E>> list) {
		initFields();
		for (Iterator<E> iterator : list) {
			addIterator(iterator);
		}
	}

	private void initFields() {
		list = new ArrayList<>();
		i = 0;
	}
	
	public void addIterator(Iterator<E> it) {
		list.add(it);
	}

	public void removeIterator(int index) {
		list.remove(index);
		
		if (i == index) {
			i++;
		}
		if (i == list.size()) {
			i = 0;
		}
	}

	@Override
	public boolean hasNext() {
		if (list == null || list.isEmpty()) {
			return false;
		}
		int j = i == list.size() ? 0 : i;
		boolean hasNext = hasNextInLoop(j);
		if (!hasNext) {
			j = 0;
			hasNext = hasNextInLoop(j);
		}
		return hasNext;
	}

	private boolean hasNextInLoop(int j) {
		while (j < list.size()) {			
			Iterator<E> it = list.get(j);
			if (it.hasNext()) {
				return true;
			}
			j++;
		}
		return false;
	}
	
	@Override
	public E next() {
		if (list == null || list.isEmpty()) {
			return null;
		}
		if (i == list.size()) {
			i = 0;
		}
		E e = getNextInLoop();
		if (e == null) {
			i = 0;
			e = getNextInLoop();
		}				
		return e;
	}
	
	private E getNextInLoop() {
		while (i < list.size()) {			
			Iterator<E> it = list.get(i);
			i++;
			if (it.hasNext()) {				
				return it.next();
			}			
		}
		return null;
	}	
}

/*
Sample Tests
*/
public static void main(String[] args) {
		InterleaveIterator iter = new InterleaveIterator<>();		
		
		ArrayList<Integer> i1 = new ArrayList<>();
		i1.add(1);
		i1.add(2);
		i1.add(3);
		i1.add(4);
		i1.add(5);
		
		List<Node> i2 = new ArrayList<>();
		i2.add(new Node(1));
		i2.add(new Node(2));
		
		Collection<Element> i3 = new ArrayList<>();
		i3.add(new Element(1));
		i3.add(new Element(2));
		i3.add(new Element(3));
		
		iter.addIterator(i1.iterator());
		iter.addIterator(i2.iterator());
		iter.addIterator(i3.iterator());
		
		while (iter.hasNext()) {
			System.out.print(iter.next() + " , ");
		}
}
// output: 1 , n1 , e1 , 2 , n2 , e2 , 3 , e3 , 4 , 5

- guilhebl May 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static class InterleaveIterator<E> implements Iterator<E>
  {
    ArrayList<Iterator<E>> iters;
    Iterator<Iterator<E>> iterIter;
    int cur;
    public InterleaveIterator(ArrayList<Iterator<E>>  iters)
    {
      this.iters=iters;
      iterIter=iters.iterator();
      cur=-1;
      for(int i=0;i<iters.size();i++)
      {
        if(iters.get(i).hasNext())
        {
          cur=i;
          break;
        }
      }
    }
    @Override 
    public boolean hasNext()
    {
      return cur!=-1;
    }
    @Override
    public E next()
    {
      E ret=iters.get(cur).next();
      
      for(int i=0;i<iters.size();i++)
      {
        int j=(cur+1+i)%iters.size();
        if(iters.get(j).hasNext())
        {
          cur=j;
          return ret;
        }
      }
      cur=-1;
      return ret;
    }
    
  }

- tmat May 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class InterleaveIterator<T> implements Iterator<T>
	{
		List<Iterator> iq;
		int index;
		
		public InterleaveIterator(List<Iterator> ilist)
		{
			index = 0;
			iq = ilist;
		}
		
		@Override
		public boolean hasNext() {
			
			boolean has = false;
			for (Iterator i : iq)
			{
				has |= i.hasNext();
			}
			return has;
		}

		@Override
		public T next() {
			Iterator itr = iq.get(index);
			while (!itr.hasNext())
			{
				advIndex();
				itr = iq.get(index);
			}
			
			T val = (T)itr.next();
			advIndex();
			return val;
		}
		
		void advIndex()
		{
			index = (index < iq.size()-1) ? index+1 : 0;
		}
	}

- lpainton May 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class InterleaveIterators<E> implements Iterator<E>{
	public int cursor;
	public ArrayList<Iterator<E>> list = null;
	
	public InterleaveIterators(){
		list = new ArrayList<Iterator<E>>(); 
		cursor=0;
	}
	public void addIterator(Iterator<E> it){
		list.add(it);
	}
	@Override
	public boolean hasNext(){
		int cnt = 0; 
		if (list==null || list.isEmpty())
			return false;
		boolean hasNext = list.get(cursor).hasNext();
		//iterate till hasNext is false and there are more elements to iterate in next iterator
		while (!hasNext && cnt < list.size()-1){
			cursor++;
			//for interleaving
			if(cursor == list.size())
				cursor=0;
			hasNext = list.get(cursor).hasNext();
			if(hasNext)
				break;
			else
				cnt++;
		}
		return hasNext;
	}
	
	public E next(){
		int current = cursor;
		cursor++;
		//for interleaving
		if(cursor == list.size())
			cursor = 0;
		return list.get(current).next();
	}
	public void remove() {
		throw new UnsupportedOperationException();
		
	}
	
	public static void main(String[] args){
		ArrayList<Integer> i1 = new ArrayList<Integer>();
		i1.add(1);
		i1.add(2);
		i1.add(3);
		i1.add(4);
		i1.add(5);
		ArrayList<Integer> i2 = new ArrayList<Integer>();
		i2.add(11);
		i2.add(12);
		i2.add(13);
		ArrayList<Integer> i3 = new ArrayList<Integer>();
		i3.add(111);
		i3.add(112);
		i3.add(113);
		i3.add(114);
		i3.add(115);
		i3.add(116);
		i3.add(117);
		i3.add(118);
		
		InterleaveIterators<Integer> iter = new InterleaveIterators<Integer>();
		iter.addIterator(i1.iterator());
		iter.addIterator(i2.iterator());
		iter.addIterator(i3.iterator());
		
		while(iter.hasNext()){
			System.out.print(iter.next() + " ");
		}
	}

}

- Ved May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class InterleaveIterators<E> implements Iterator<E>{
	public int cursor;
	public ArrayList<Iterator<E>> list = null;
	
	public InterleaveIterators(){
		list = new ArrayList<Iterator<E>>(); 
		cursor=0;
	}
	public void addIterator(Iterator<E> it){
		list.add(it);
	}
	@Override
	public boolean hasNext(){
		int cnt = 0; 
		if (list==null || list.isEmpty())
			return false;
		boolean hasNext = list.get(cursor).hasNext();
		//iterate till hasNext is false and there are more elements to iterate in next iterator
		while (!hasNext && cnt < list.size()-1){
			cursor++;
			//for interleaving
			if(cursor == list.size())
				cursor=0;
			hasNext = list.get(cursor).hasNext();
			if(hasNext)
				break;
			else
				cnt++;
		}
		return hasNext;
	}
	
	public E next(){
		int current = cursor;
		cursor++;
		//for interleaving
		if(cursor == list.size())
			cursor = 0;
		return list.get(current).next();
	}
	public void remove() {
		throw new UnsupportedOperationException();
		
	}
	
	public static void main(String[] args){
		ArrayList<Integer> i1 = new ArrayList<Integer>();
		i1.add(1);
		i1.add(2);
		i1.add(3);
		i1.add(4);
		i1.add(5);
		ArrayList<Integer> i2 = new ArrayList<Integer>();
		i2.add(11);
		i2.add(12);
		i2.add(13);
		ArrayList<Integer> i3 = new ArrayList<Integer>();
		i3.add(111);
		i3.add(112);
		i3.add(113);
		i3.add(114);
		i3.add(115);
		i3.add(116);
		i3.add(117);
		i3.add(118);
		
		InterleaveIterators<Integer> iter = new InterleaveIterators<Integer>();
		iter.addIterator(i1.iterator());
		iter.addIterator(i2.iterator());
		iter.addIterator(i3.iterator());
		
		while(iter.hasNext()){
			System.out.print(iter.next() + " ");
		}
	}
}

- ved May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The same question was asked in my phone interview.

import java.util.*;
public class InterleaveIterators<E> implements Iterator<E>{
	public int cursor;
	public ArrayList<Iterator<E>> list = null;
	
	public InterleaveIterators(){
		list = new ArrayList<Iterator<E>>(); 
		cursor=0;
	}
	public void addIterator(Iterator<E> it){
		list.add(it);
	}
	@Override
	public boolean hasNext(){
		int cnt = 0; 
		if (list==null || list.isEmpty())
			return false;
		boolean hasNext = list.get(cursor).hasNext();
		//iterate till hasNext is false and there are more elements to iterate in next iterator
		while (!hasNext && cnt < list.size()-1){
			cursor++;
			//for interleaving
			if(cursor == list.size())
				cursor=0;
			hasNext = list.get(cursor).hasNext();
			if(hasNext)
				break;
			else
				cnt++;
		}
		return hasNext;
	}
	
	public E next(){
		int current = cursor;
		cursor++;
		//for interleaving
		if(cursor == list.size())
			cursor = 0;
		return list.get(current).next();
	}
	public void remove() {
		throw new UnsupportedOperationException();
		
	}
	
	public static void main(String[] args){
		ArrayList<Integer> i1 = new ArrayList<Integer>();
		i1.add(1);
		i1.add(2);
		i1.add(3);
		i1.add(4);
		i1.add(5);
		ArrayList<Integer> i2 = new ArrayList<Integer>();
		i2.add(11);
		i2.add(12);
		i2.add(13);
		ArrayList<Integer> i3 = new ArrayList<Integer>();
		i3.add(111);
		i3.add(112);
		i3.add(113);
		i3.add(114);
		i3.add(115);
		i3.add(116);
		i3.add(117);
		i3.add(118);
		
		InterleaveIterators<Integer> iter = new InterleaveIterators<Integer>();
		iter.addIterator(i1.iterator());
		iter.addIterator(i2.iterator());
		iter.addIterator(i3.iterator());
		
		while(iter.hasNext()){
			System.out.print(iter.next() + " ");
		}
	}

}

- Ved May 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As input has different types of iterator, So can not make it generic.

import java.util.Arrays;
import java.util.Iterator;

/**
 * Created by Akshay on 5/27/2016.
 */

public class InterLeaveIterator implements Iterator {

    private Iterator<?>[] iterators;
    private int currentIndex;

    public InterLeaveIterator(Iterator<?>... iterators) {
        this.iterators = iterators;
        if (iterators.length == 0) {
            throw new IllegalArgumentException();
        }
        currentIndex = -1;
    }


    public boolean hasNext() {

        boolean hasNext = false;
        for (int i = 0; i < iterators.length; i++) {

            currentIndex = ++currentIndex % iterators.length;
            hasNext = iterators[currentIndex].hasNext();

            if (hasNext)
                return true;
        }

        return hasNext;
    }

    public Object next() {
        Object o = iterators[currentIndex].next();

        return o;
    }

    public void remove() {

    }


    public static void main(String a[]) {

        Iterator iterator =
                new InterLeaveIterator(
                        Arrays.asList(new Integer[]{1, 2, 3, 4, 5, 6}).iterator(),
                        Arrays.asList(new String[]{"a", "b", "c"}).iterator(),
                        Arrays.asList(new Double[]{1.1, 1.2, 1.3, 1.4}).iterator()
                );

        while (iterator.hasNext()) {
            System.out.println(iterator.next().toString());
        }
    }
}

- akshay May 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;

public class InterleaveIterator<E> implements Iterator<E> {
	
	List<Iterator<E>> listIterator = null;
	int rows = 0;
	int columns = 0;
	int totalListsOfIterator = -1;
	E next;
	Iterator<E> iterator ;
	int maximunSizeList = 5;
	
	InterleaveIterator(List<Iterator<E>> listIter){
		listIterator = listIter;
		totalListsOfIterator = listIterator.size();
	}
	
	public static void main(String[] args) {

		Collection<Object> listIntegers = new ArrayList<Object>();
		
		listIntegers.add(1);
		listIntegers.add(2);
		listIntegers.add(3);
		listIntegers.add(4);
		
		List listTwo = new ArrayList<String>();
		
		listTwo.add("Str1");
		listTwo.add("Str2");
		listTwo.add("Str3");
		listTwo.add("Str4");
		listTwo.add("Str5");
		
		ArrayList<Object> i3 = new ArrayList<Object>();
		i3.add(111);
		i3.add(112);
		i3.add(113);
		i3.add(114);
		i3.add(115);
		i3.add(116);
		i3.add(117);
		i3.add(118);
		
		List<Iterator<Object>> listIterator = new ArrayList<Iterator<Object>>();
		
		listIterator.add(listIntegers.iterator());
		listIterator.add(listTwo.iterator());
		listIterator.add(i3.iterator());
		
		InterleaveIterator<Object> interleaveIterator = new InterleaveIterator<Object>(listIterator);
		
		
		while (interleaveIterator.hasNext()){
			
			Object  object = interleaveIterator.next();
			System.out.println(object);
		}
		
	}
	
	@Override
	public boolean hasNext() {
		
		boolean hasNext = false;
		
		if (columns < totalListsOfIterator ){
			
			iterator = listIterator.get(columns++);
			
			if ( iterator.hasNext() ){
				
					next = iterator.next();
					hasNext = true;	
				
			}else{
				
				while ( columns < totalListsOfIterator ){
					
					iterator = listIterator.get(columns++);
					
					if ( iterator.hasNext() ){
					
						next = iterator.next();
						hasNext = true;	
						break;
					}
				}
				
			}
			
		}
		
		if (columns == totalListsOfIterator){
			columns = 0;	
		}
			
		return hasNext;
	}

	@Override
	public E next() {
		iterator.remove();
		return next;
	}

	@Override
	public void remove() {
		iterator.remove();
	}

}

- israAzul June 15, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More