CareerCup

/*
	->( ) -> ( ) -> (null) -> ( ) -> ( )
	          1                4      5
	          2                       6
	          3
*/

class LinkedListOfLinkedListIterator implements Iterator<T> {
 
	LinkedList<LinkedList<T>> parentList;
	
	Iterator<LinkedList<LinkedList<T>>> parentIt;
	LinkedList<T> childIt;

	public LinkedListOfLinkedListIterator(LinkedList<LinkedList<T>> list) {
		this.parentList = list;
		
		if(list != null) {	
			this.parentIt = parentList.iterator();
		}
	}

	public boolean hasNext() {
		if(parentList == null) {
			return false;
		}

		if(childIt != null && childIt.hasNext()) {
			return true
		} else {
			// This child list has no next elements, move the parent list iterator
			while(parentIt.hasNext()) {
				LinkedList<T> childList = parent.next();

				// The next element of the parent list is not null
				if(childList != null) {
					// Get the iterator of the child list. If we have next element, return true
					childIt = childList.iterator();
					if(childIt.hasNext()) {
						return true;
					}
				} else {
					childIt = null;
				}
			}
		}

		// The childIt had no next elements. Then, we looked for another child list in the parent list and we haven't found any lists with elements
		return false;
	}

	public T next() {
		// If hasNext returns true, childIt is positioned and ready to return the next element
		if(hasNext()) {
			return childIt.next();
		} else {
			throw new NoSuchElementException("It is over :(");
		}
	}

	public void remove() {
		throw new UnsupportedOperationException("This is too difficult");
	}
}

package algos;

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

/**
 * Created by paramasivami on 4/22/16.
 */
public class ListOfListIterator<T> implements Iterator<T> {



    private List<Iterator<T>> iterators;

    public ListOfListIterator(List<Iterator<T>> iterators){
        this.iterators = iterators;
    }
    @Override
    public boolean hasNext() {
        for(int i = 0; i < iterators.size(); i++){
            if(iterators.get(i).hasNext()) return true;
        }
        return false;
    }

    @Override
    public T next() {
        for(int i=0; i < iterators.size(); i++){
            Iterator<T> n = iterators.get(i);
            if(n.hasNext()) return n.next();
        }
        return null;
    }

    public static void main(String[] args) {
        List<List<Integer>> elements = new ArrayList<>();

        for(int i=0;i<3;i+=2){
            List<Integer> inner = new ArrayList<>();
            inner.add(i);
            inner.add(i+1);
            elements.add(inner);
        }

        List<Iterator<Integer>> iterators = new LinkedList<>();
        elements.forEach(
                element -> iterators.add(element.iterator())
        );

        ListOfListIterator l = new ListOfListIterator(iterators);
        while(l.hasNext()) System.out.println(l.next());
    }

}

Here my implementation using C

#include <stdio.h>

struct list2 { int data; struct list2 * next; };
struct list1 { struct list2 * node; struct list1 * next; };

typedef struct list1 * listp;
typedef struct list2 * listc;

listp addparent ( listp start, listc data ){
	listp node,loop;
	
	node = ( listp ) malloc ( sizeof (struct list1) );
	if( node == NULL ) { printf("can't allocate size, exiting\n"); }
	
	if (start==NULL){
		node->node=data;
		node->next=NULL;
		return node;
	}
	
	loop=start;
	while ( loop->next != NULL ) loop=loop->next;
	
	loop->next=node;
	node->next=NULL;
	node->node=data;

	return start;
}


listc add ( listc start, int data ){
	listc node,loop;
	
	node = ( listc ) malloc ( sizeof (struct list2) );
	if( node == NULL ) { printf("can't allocate size, exiting\n"); }
	
	if (start==NULL){
		node->data=data;
		node->next=NULL;
		return node;
	}
	
	loop=start;
	while ( loop->next != NULL ) loop=loop->next;
	
	loop->next=node;
	node->next=NULL;
	node->data=data;

	return start;
}

void printlist ( listp start ){
	listp loop1;
	listc loop2;
	loop1=start;
	
	while ( loop1!= NULL ) {
		loop2=loop1->node;	
		while ( loop2!= NULL ) {	
			printf("%d\t",loop2->data);
			loop2=loop2->next;
		}
		printf("\n");
		loop1=loop1->next;		
	}
}

int main(int argc, char **argv)
{
	listc start=NULL;
	listp parent=NULL;
	int i,j;
	
	for(j=0;j<5;j++){
		start=NULL;
		for (i=j+1;i<10;i++)
			start=add(start,i);
		parent=addparent(parent,start);
		
	}
	printlist(parent);
	
	return 0;
}

I got the same question in Apple phone screen.

Consider a linked list that could have two types of elements:
1. element
2. another linked list

class LinkedListOfLinkedListsIterator<T1> implements Iterator<T1> {

    Iterator<Object> parentIterator = listOfLists.iterator();
    Iterator<T1> childIterator;

    @Override
    public boolean hasNext() {
      if (childIterator != null && childIterator.hasNext()) {
        return true;
      }
      return parentIterator.hasNext();
    }

    @Override
    public T1 next() {
      if (childIterator != null) {
        if (childIterator.hasNext()) {
          return childIterator.next();
        }
        childIterator = null;
      }

      while (parentIterator.hasNext()) {
        Object p = parentIterator.next();
        if (p instanceof LinkedList) {
          childIterator = ((LinkedList<T1>) p).iterator();
          if (childIterator.hasNext()) {
            return childIterator.next();
          }
          childIterator = null;
        } else {
          return (T1)p;
        }
      }
      return null;
    }
  }

import java.util.Iterator;

/**
 * @author Sabuj Das 
 *
 */
public class LinkedList<T> implements Iterable<T>{

	private Node<T> head;
	
	
	public void add(T item){
		if(head == null){
			head = new Node<T>(item);
		}
		else {
			Node<T> temp = head;
			while(temp.next != null)
				temp = temp.next;
			Node<T> node = new Node<T>(item);
			temp.next = node;
		}
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Iterable#iterator()
	 */
	public Iterator<T> iterator() {
		return new LinkedIterator();
	}
	
	private final class LinkedIterator implements Iterator<T>{

		private Node<T> start;
		
		/**
		 * 
		 */
		public LinkedIterator() {
			start = head;
		}
		
		/* (non-Javadoc)
		 * @see java.util.Iterator#hasNext()
		 */
		public boolean hasNext() {
			if(start == null)
				return false;
			return start != null;
		}

		/* (non-Javadoc)
		 * @see java.util.Iterator#next()
		 */
		public T next() {
			Node<T> temp = start;
			start = start.next;
			return temp.value;
		}

	}
	
	private final class Node<T>{
		T value;
		Node<T> next;
		
		/**
		 * @param value
		 */
		public Node(T value) {
			this.value = value;
		}
		
		
	}
	
	public static void main(String[] args) {
		args = new String[]{"A", "B", "C"};
		LinkedList<LinkedList<String>> lll = new LinkedList<LinkedList<String>>();
		for (int i = 0; i < args.length; i++) {
			String s = args[i];
			LinkedList<String> ll = new LinkedList<String>();
			for(int j=0; j<10; j++)
				ll.add(s+  "_" + j);
			lll.add(ll);
		}
		
		Iterator<LinkedList<String>> outer = lll.iterator();
		while(outer.hasNext()){
			LinkedList<String> ll = outer.next();
			Iterator<String> inner = ll.iterator();
			while(inner.hasNext()){
				System.out.print(inner.next() + " , ");
			}
			System.out.println();
		}
	}

}

O/P:

A_0 , A_1 , A_2 , A_3 , A_4 , A_5 , A_6 , A_7 , A_8 , A_9 , 
B_0 , B_1 , B_2 , B_3 , B_4 , B_5 , B_6 , B_7 , B_8 , B_9 , 
C_0 , C_1 , C_2 , C_3 , C_4 , C_5 , C_6 , C_7 , C_8 , C_9 ,