Google Interview Question


Country: United States
Interview Type: In-Person




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

public class RoundRobinIterator {
    List<Iterator> iterators;
    int index;  //current element
    int size;

    public RoundRobinIterator(List<Iterator> iter) {
        iterators = iter;
        size = iterators.size();
        index = 0;
        if(size > 0) locateNext();
    }

    public Object next() {
        locateNext();
        if(size == 0) return null;
        return iterators.get(index).next();
    }

    public boolean hasNext() {      // tradeoff - O(1) or O(n) ?
        if(size == 0) return false;
        return true;

    }

    private void locateNext() {
        if(iterators.get(index).hasNext()) {
            index = (index + 1) % size;
        }
        while(size > 0 && !iterators.get(index).hasNext()) {
            Iterator tmp = iterators.get(index);
            iterators.set(index, iterators.get(size - 1));
            iterators.set(size - 1, tmp);
            size--;
            if(index == size) index = 0;
        }
    }

}

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

We provide ONE TO ONE courses that cover everything in an interview including
the latest interview questions categorized by companies,
algorithms,
SYSTEM DESIGN Courses(highly recommended for people interviewing with FLAG)
and mock interviews.

All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work.

Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.

Welcome to contact us with any questions. Thanks for reading.

- acoding167 March 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea would be to keep track of which "Iterator" in the list was last accessed. If we reach the end of the list, then wrap it up from the beginning again.

Wrapping part can be done using count % size of the list

The Next method will check if the given iterator has any data left, if not, remove that iterator from the last so that next time this iterator is not accessed.

Here is a sample implementation with the result.

Time Complexity:
next: O(N) --> as we may end up scanning the entire list to get the value
hasNext: O(N)

public class IteratorRoundRobin {
    public static void main(String[] args) {
        List<Integer> l1 = new ArrayList<>();
        l1.add(1);

        List<Integer> l2 = new ArrayList<>();
        l2.add(10);l2.add(11);

        List<Integer> l3 = new ArrayList<>();
        l3.add(20);l3.add(21);l3.add(22);l3.add(23);l3.add(24);

        List<Iterator> input = new ArrayList<>();
        input.add(l3.iterator());
        input.add(l2.iterator());
        input.add(l1.iterator());
        RoundRobinIterator rri = new RoundRobinIterator(input);

        System.out.println("rri.hasNext() = " + rri.hasNext()); //Expected value: true
        System.out.println("rri.next() = " + rri.next()); //20
        System.out.println("rri.hasNext() = " + rri.hasNext()); //true
        System.out.println("rri.next() = " + rri.next()); //10
        System.out.println("rri.next() = " + rri.next()); //1
        System.out.println("rri.next() = " + rri.next()); //21
        System.out.println("rri.next() = " + rri.next()); //11
        System.out.println("rri.next() = " + rri.next()); //22
        System.out.println("rri.next() = " + rri.next()); //23
        System.out.println("rri.hasNext() = " + rri.hasNext()); //true
        System.out.println("rri.next() = " + rri.next()); //24
        System.out.println("rri.hasNext() = " + rri.hasNext()); //false
    }
}

class RoundRobinIterator {
    List<Iterator> list = null;
    int size = 0;
    int count = 0;
    public RoundRobinIterator(List<Iterator> itrs) {
        list = itrs;
        size = list.size();
    }

    public Object next(){
        Object result = null;
        while(list.size() > 0 || result != null) {
            Iterator itr = list.get(count % list.size());
            if (itr.hasNext()) {
                result = itr.next();
                count++;
                break;
            } else {
                list.remove(count % list.size());
            }
        }
        return result;
    }

    public boolean hasNext() {
        boolean result = false;
        while(list.size() > 0) {
            Iterator itr = list.get(count % list.size());
            if(itr.hasNext()) {
                result = true;
                break;
            } else {
                list.remove(count % list.size());
            }
        }
        return result;
    }
}

Result:
======
rri.hasNext() = true
rri.next() = 20
rri.hasNext() = true
rri.next() = 10
rri.next() = 1
rri.next() = 21
rri.next() = 11
rri.next() = 22
rri.next() = 23
rri.hasNext() = true
rri.next() = 24
rri.hasNext() = false

- Saurabh March 15, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package ru.vitvlkv.collections;

import java.util.*;

public class RoundRobinCompositeIterator<E> implements Iterator<E> {

    private List<Iterator<E>> iterators;
    private Iterator<Iterator<E>> i;
    private Iterator<E> iterator;

    public RoundRobinCompositeIterator(Iterator<E> ...iterators) {
        if (iterators.length == 0) {
            throw new IllegalArgumentException("At least one iterator should be given");
        }
        this.iterators = new LinkedList<>();
        Arrays.stream(iterators)
                .filter(it -> it.hasNext())
                .forEach(it -> this.iterators.add(it));
        incCurrent();
        skipUntilHasNext();
    }

    @Override
    public boolean hasNext() {
        return !iterators.isEmpty() && iterator.hasNext();
    }

    @Override
    public E next() {
        if (iterators.isEmpty()) {
            throw new NoSuchElementException();
        }
        E result = iterator.next();
        incCurrent();
        skipUntilHasNext();
        return result;
    }

    private void skipUntilHasNext() {
        while (!iterators.isEmpty() && !iterator.hasNext()) {
            i.remove();
            incCurrent();
        }
    }

    private void incCurrent() {
        if (i == null || !i.hasNext()) {
            i = iterators.iterator();
        }
        iterator = i.hasNext() ? i.next() : null;
    }
}

- vlkv March 16, 2019 | 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