Apple Interview Question
SDE1sCountry: United States
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;
}
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 ,
- carlosgsouza April 17, 2015