Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
With additional assumptions
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
// Ignores ConcurrentModificationExceptions
public class Lists<T> implements Iterable<T> {
private List<List<T>> lists;
public Lists(List<List<T>> lists) {
this.lists = lists;
}
@Override
public Iterator<T> iterator() {
return new ListsIterator();
}
public class ListsIterator implements Iterator<T> {
private Iterator<List<T>> listsIter;
private Iterator<T> listIter;
private void hop() {
listIter = null;
if (listsIter == null) {
return;
}
while (listsIter.hasNext()) {
List<T> list = listsIter.next();
// Here is the flattening
if (list == null || list.isEmpty()) {
listsIter.remove();
} else {
listIter = list.iterator();
break;
}
}
}
public ListsIterator() {
if (lists != null) {
listsIter = lists.iterator();
}
hop();
}
@Override
public boolean hasNext() {
if (listIter == null) {
return false;
}
if (listIter.hasNext()) {
return true;
}
hop();
if (listIter == null) {
return false;
}
return true;
}
@Override
public T next() {
if (listIter == null) {
throw new NoSuchElementException();
}
if (listIter.hasNext()) {
return listIter.next();
}
hop();
if (listIter == null) {
throw new NoSuchElementException();
}
return listIter.next();
}
@Override
public void remove() {
if (listIter == null) {
throw new IllegalStateException();
}
listIter.remove();
if (!listIter.hasNext()) {
hop();
}
}
}
public static void main(String[] args) {
// Test 0
Lists<Integer> lists = new Lists<Integer>(null);
Iterator<Integer> i = lists.iterator();
System.out.println(i.hasNext());
try {
i.next();
} catch (NoSuchElementException e) {
}
try {
i.remove();
} catch (IllegalStateException e) {
}
// Test 1
List<List<Integer>> test1 = new ArrayList<List<Integer>>();
test1.add(null);
List<Integer> list = new LinkedList<Integer>();
list.add(1);list.add(2);
test1.add(list);
test1.add(Collections.<Integer>emptyList());
list = new LinkedList<Integer>();
list.add(3);list.add(4);
test1.add(list);
lists = new Lists<Integer>(test1);
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
i.remove();
}
System.out.println();
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
}
System.out.println();
}
}
From my understanding, "flattening" in this case is just returning the first inner list and ignoring all other inner lists. Let me know if this is correct.
Also, provide a more detailed example. eg. what is the unflattened output for [[6,8,9],[4,5,3],[1,2,7]] ?
I answered this incorrectly during the interview. But now when I did it, I managed to do it properly.
Here's my code : (Please suggest if you think anything's wrong with it)
import java.util.ArrayList;
import java.util.List;
public class FlattenList {
List<List<Integer>> vv;
private int currentIndex = 0;
private int currentList = 0;
private FlattenList(List<List<Integer>> vv) {
this.vv = vv;
}
public boolean hasNext() {
while(currentList < this.vv.size()) {
List<Integer> thisList = this.vv.get(currentList);
if(currentIndex < thisList.size()) {
return true;
}
else {
currentList++;
}
}
return false;
}
public int next() {
if(hasNext()) {
List<Integer> thisList = this.vv.get(currentList);
if(currentIndex == thisList.size() - 1) {
int temp = currentIndex;
currentIndex = 0;
currentList++;
return thisList.get(temp);
}
else if(currentIndex < thisList.size()) {
return thisList.get(currentIndex++);
}
}
return -1;
}
public static void main(String[] args) {
int[] ints1 = {8, 3, 5};
List<Integer> intList = new ArrayList<Integer>();
for (int index = 0; index < ints1.length; index++)
{
intList.add(ints1[index]);
}
int[] ints2 = {2, 7};
List<Integer> intList2 = new ArrayList<Integer>();
for (int index = 0; index < ints2.length; index++)
{
intList.add(ints2[index]);
}
List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();
listOfLists.add(intList);
listOfLists.add(intList2);
FlattenList fl = new FlattenList(listOfLists);
while(fl.hasNext())
System.out.println(fl.next());
}
}
I don't think this works. Your constructor takes in a List<List<Integer>>. In the given example, [[6,8], 4], [6,8] is a list of integers bur 4 is only an integer. Your constructor, and thus the rest of your code, needs to distinguish between a list<integer> and an integer.
I don't think your solution works. Your constructor takes in a List<List<Integer>>. But according to the question, you need to take in a list<XX> where XX could be either a list<integer> or an integer. Thus, your solution will only work if the input string was [[6,8],[4]] where the 4 is inside another list.
I don't think your solution works. Your constructor takes in a List<List<Integer>>. But according to the question, you need to take in a list<XX> where XX could be either a list<integer> or an integer. Thus, your solution will only work if the input string was [[6,8],[4]] where the 4 is inside another list.
I recommend making it so that hasNext() does not increment currentList or change any other class variables. All of that work should be done inside next().
your code does not handle, list within list within list , etc ie multiple levels of nesting in the lists.
like [[[[12,23,23,3],2,2],1],9]
With additional assumptions
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
// Ignores ConcurrentModificationExceptions
public class Lists<T> implements Iterable<T> {
private List<List<T>> lists;
public Lists(List<List<T>> lists) {
this.lists = lists;
}
@Override
public Iterator<T> iterator() {
return new ListsIterator();
}
public class ListsIterator implements Iterator<T> {
private Iterator<List<T>> listsIter;
private Iterator<T> listIter;
private void hop() {
listIter = null;
if (listsIter == null) {
return;
}
while (listsIter.hasNext()) {
List<T> list = listsIter.next();
// Here is the flattening
if (list == null || list.isEmpty()) {
listsIter.remove();
} else {
listIter = list.iterator();
break;
}
}
}
public ListsIterator() {
if (lists != null) {
listsIter = lists.iterator();
}
hop();
}
@Override
public boolean hasNext() {
if (listIter == null) {
return false;
}
if (listIter.hasNext()) {
return true;
}
hop();
if (listIter == null) {
return false;
}
return true;
}
@Override
public T next() {
if (listIter == null) {
throw new NoSuchElementException();
}
if (listIter.hasNext()) {
return listIter.next();
}
hop();
if (listIter == null) {
throw new NoSuchElementException();
}
return listIter.next();
}
@Override
public void remove() {
if (listIter == null) {
throw new IllegalStateException();
}
listIter.remove();
if (!listIter.hasNext()) {
hop();
}
}
}
public static void main(String[] args) {
// Test 0
Lists<Integer> lists = new Lists<Integer>(null);
Iterator<Integer> i = lists.iterator();
System.out.println(i.hasNext());
try {
i.next();
} catch (NoSuchElementException e) {
}
try {
i.remove();
} catch (IllegalStateException e) {
}
// Test 1
List<List<Integer>> test1 = new ArrayList<List<Integer>>();
test1.add(null);
List<Integer> list = new LinkedList<Integer>();
list.add(1);list.add(2);
test1.add(list);
test1.add(Collections.<Integer>emptyList());
list = new LinkedList<Integer>();
list.add(3);list.add(4);
test1.add(list);
lists = new Lists<Integer>(test1);
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
i.remove();
}
System.out.println();
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
}
System.out.println();
}
}
With assumptions
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
// Ignores ConcurrentModificationExceptions
public class Lists<T> implements Iterable<T> {
private List<List<T>> lists;
public Lists(List<List<T>> lists) {
this.lists = lists;
}
@Override
public Iterator<T> iterator() {
return new ListsIterator();
}
public class ListsIterator implements Iterator<T> {
private Iterator<List<T>> listsIter;
private Iterator<T> listIter;
private void hop() {
listIter = null;
if (listsIter == null) {
return;
}
while (listsIter.hasNext()) {
List<T> list = listsIter.next();
// Here is the flattening
if (list == null || list.isEmpty()) {
listsIter.remove();
} else {
listIter = list.iterator();
break;
}
}
}
public ListsIterator() {
if (lists != null) {
listsIter = lists.iterator();
}
hop();
}
@Override
public boolean hasNext() {
if (listIter == null) {
return false;
}
if (listIter.hasNext()) {
return true;
}
hop();
if (listIter == null) {
return false;
}
return true;
}
@Override
public T next() {
if (listIter == null) {
throw new NoSuchElementException();
}
if (listIter.hasNext()) {
return listIter.next();
}
hop();
if (listIter == null) {
throw new NoSuchElementException();
}
return listIter.next();
}
@Override
public void remove() {
if (listIter == null) {
throw new IllegalStateException();
}
listIter.remove();
if (!listIter.hasNext()) {
hop();
}
}
}
public static void main(String[] args) {
// Test 0
Lists<Integer> lists = new Lists<Integer>(null);
Iterator<Integer> i = lists.iterator();
System.out.println(i.hasNext());
try {
i.next();
} catch (NoSuchElementException e) {
}
try {
i.remove();
} catch (IllegalStateException e) {
}
// Test 1
List<List<Integer>> test1 = new ArrayList<List<Integer>>();
test1.add(null);
List<Integer> list = new LinkedList<Integer>();
list.add(1);list.add(2);
test1.add(list);
test1.add(Collections.<Integer>emptyList());
list = new LinkedList<Integer>();
list.add(3);list.add(4);
test1.add(list);
lists = new Lists<Integer>(test1);
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
i.remove();
}
System.out.println();
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
}
System.out.println();
}
}
With assumptions.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
// Ignores ConcurrentModificationExceptions
public class Lists<T> implements Iterable<T> {
private List<List<T>> lists;
public Lists(List<List<T>> lists) {
this.lists = lists;
}
@Override
public Iterator<T> iterator() {
return new ListsIterator();
}
public class ListsIterator implements Iterator<T> {
private Iterator<List<T>> listsIter;
private Iterator<T> listIter;
private void hop() {
listIter = null;
if (listsIter == null) {
return;
}
while (listsIter.hasNext()) {
List<T> list = listsIter.next();
// Here is the flattening
if (list == null || list.isEmpty()) {
listsIter.remove();
} else {
listIter = list.iterator();
break;
}
}
}
public ListsIterator() {
if (lists != null) {
listsIter = lists.iterator();
}
hop();
}
@Override
public boolean hasNext() {
if (listIter == null) {
return false;
}
if (listIter.hasNext()) {
return true;
}
hop();
if (listIter == null) {
return false;
}
return true;
}
@Override
public T next() {
if (listIter == null) {
throw new NoSuchElementException();
}
if (listIter.hasNext()) {
return listIter.next();
}
hop();
if (listIter == null) {
throw new NoSuchElementException();
}
return listIter.next();
}
@Override
public void remove() {
if (listIter == null) {
throw new IllegalStateException();
}
listIter.remove();
if (!listIter.hasNext()) {
hop();
}
}
}
public static void main(String[] args) {
// Test 0
Lists<Integer> lists = new Lists<Integer>(null);
Iterator<Integer> i = lists.iterator();
System.out.println(i.hasNext());
try {
i.next();
} catch (NoSuchElementException e) {
}
try {
i.remove();
} catch (IllegalStateException e) {
}
// Test 1
List<List<Integer>> test1 = new ArrayList<List<Integer>>();
test1.add(null);
List<Integer> list = new LinkedList<Integer>();
list.add(1);list.add(2);
test1.add(list);
test1.add(Collections.<Integer>emptyList());
list = new LinkedList<Integer>();
list.add(3);list.add(4);
test1.add(list);
lists = new Lists<Integer>(test1);
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
i.remove();
}
System.out.println();
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
}
System.out.println();
}
}
With assumptions
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
// Ignores ConcurrentModificationExceptions
public class Lists<T> implements Iterable<T> {
private List<List<T>> lists;
public Lists(List<List<T>> lists) {
this.lists = lists;
}
@Override
public Iterator<T> iterator() {
return new ListsIterator();
}
public class ListsIterator implements Iterator<T> {
private Iterator<List<T>> listsIter;
private Iterator<T> listIter;
private void hop() {
listIter = null;
if (listsIter == null) {
return;
}
while (listsIter.hasNext()) {
List<T> list = listsIter.next();
// Here is the flattening
if (list == null || list.isEmpty()) {
listsIter.remove();
} else {
listIter = list.iterator();
break;
}
}
}
public ListsIterator() {
if (lists != null) {
listsIter = lists.iterator();
}
hop();
}
@Override
public boolean hasNext() {
if (listIter == null) {
return false;
}
if (listIter.hasNext()) {
return true;
}
hop();
if (listIter == null) {
return false;
}
return true;
}
@Override
public T next() {
if (listIter == null) {
throw new NoSuchElementException();
}
if (listIter.hasNext()) {
return listIter.next();
}
hop();
if (listIter == null) {
throw new NoSuchElementException();
}
return listIter.next();
}
@Override
public void remove() {
if (listIter == null) {
throw new IllegalStateException();
}
listIter.remove();
if (!listIter.hasNext()) {
hop();
}
}
}
public static void main(String[] args) {
// Test 0
Lists<Integer> lists = new Lists<Integer>(null);
Iterator<Integer> i = lists.iterator();
System.out.println(i.hasNext());
try {
i.next();
} catch (NoSuchElementException e) {
}
try {
i.remove();
} catch (IllegalStateException e) {
}
// Test 1
List<List<Integer>> test1 = new ArrayList<List<Integer>>();
test1.add(null);
List<Integer> list = new LinkedList<Integer>();
list.add(1);list.add(2);
test1.add(list);
test1.add(Collections.<Integer>emptyList());
list = new LinkedList<Integer>();
list.add(3);list.add(4);
test1.add(list);
lists = new Lists<Integer>(test1);
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
i.remove();
}
System.out.println();
i = lists.iterator();
while (i.hasNext()) {
System.out.print(i.next() + " ");
}
System.out.println();
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
public class FlatList<T> implements Iterator<T>, Iterable<T> {
List<List<T>> listOfList;
int elemIndex = 0;
int listIndex = 0;
List<T> curList;
public FlatList(List<List<T>> listOfList) {
this.listOfList = listOfList;
if (listOfList.size() > 0)
curList = listOfList.get(0);
}
@Override
public boolean hasNext() {
while (listIndex < listOfList.size()) {
if (elemIndex < curList.size())
return true;
if (++listIndex < listOfList.size()) {
curList = listOfList.get(listIndex);
elemIndex = 0;
}
}
return false;
}
@Override
public T next() {
if (elemIndex >= curList.size())
return null;
return curList.get(elemIndex++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
@Override
public Iterator<T> iterator() {
return this;
}
public static void main(String[] args) {
List<List<Integer>> listoflist = new ArrayList<List<Integer>>();
List<Integer> intList;
for (int i = 0; i < 5; i++) {
intList = new ArrayList<Integer>();
for (int j = 0; j < i; j++)
intList.add(j);
listoflist.add(intList);
}
FlatList<Integer> flatlist = new FlatList<>(listoflist);
Iterator<Integer> iter = flatlist.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}
Hi. I want to clarify what this question really wants us to answer.
So the input is a list of lists - List<List<Integer>>
Now we do: flatten(List<List<Integer>> which returns the String such as [[2,4,6], [5], [1, 10, 9]].
So hasNext() must work with a String ?
The approach I came up with was: Have two pointers, one at the start of a list and one at the end of the list (by list, I mean one list inside the superlist) and work with these pointers to retrieve next.
Is this the right understanding of the problem ?
import java.util.LinkedList;
import java.util.List;
public class FlatList {
LinkedList<Integer> flatList = new LinkedList();
int index = 0;
public FlatList(List<List<Integer>> original){
for (List<Integer> sublist : original){
for(Integer i : sublist){
flatList.add(i);
}
}
// Clean up some space
original.clear();
}
Integer getNext(){
return flatList.get(index++);
}
boolean hasNext(){
return index >= flatList.size();
}
}
Here's my solution in Java:
========================
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class FlatList implements Iterable<Integer> {
List<List<Integer>> list;
public FlatList(List<List<Integer>> list) {
this.list = list;
}
@Override
public Iterator<Integer> iterator() {
Iterator<Integer> it = new Iterator<Integer>() {
int primaryIndex = 0;
int secondaryIndex = 0;
@Override
public Integer next() {
if(! hasNext())
return null;
// fetch the data to return
Integer data = list.get(primaryIndex).get(secondaryIndex);
// advance the indices
if( secondaryIndex <= list.get(primaryIndex).size() -2) {
// may still reach list.get(primaryIndex).size() -1 which
// is valid but not further
secondaryIndex ++;
// primaryIndex is unchanged
} else {
primaryIndex ++;
// set seconaryIndex to the start
secondaryIndex = 0;
}
// Return
return data;
}
@Override
public boolean hasNext() {
return (primaryIndex < list.size());
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
};
return it;
}
public static void main(String[] args) {
List<List<Integer>> l = new LinkedList<List<Integer>>();
List<Integer> l1 = new LinkedList<Integer>();
l1.add(2);
l1.add(3);
List<Integer> l2 = new LinkedList<Integer>();
l2.add(4);
l2.add(5);
List<Integer> l3 = new LinkedList<Integer>();
l3.add(6);
l3.add(7);
l.add(l1);
l.add(l2);
l.add(l3);
FlatList list = new FlatList(l);
Iterator<Integer> it = list.iterator();
while(it.hasNext()) {
System.out.println(it.next().intValue());
}
System.out.println("done");
}
}
And another one, using a single index & the iterator of the inner lists:
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class FlatList2 implements Iterable<Integer> {
List<List<Integer>> list;
public FlatList2(List<List<Integer>> list) {
this.list = list;
}
@Override
public Iterator<Integer> iterator() {
Iterator<Integer> it = new Iterator<Integer>() {
int primaryIndex = 0;
@Override
public Integer next() {
if(! hasNext())
return null;
// fetch the data to return
Integer data = ((Iterator<Integer>) list.get(primaryIndex)).next();
if(data == null)
primaryIndex ++;
// Return
return data;
}
@Override
public boolean hasNext() {
return (primaryIndex < list.size()-1 || (primaryIndex == list.size() -1
&& ((Iterator<Integer>) list.get(primaryIndex)).hasNext()));
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
};
return it;
}
}
Here is a solution in C#. Simply convert it to Java.
It doesn't implement IEnumerable<int> but this can be added very easily.
public class FlatIntList
{
private List<List<int>> allLists;
private int rowIndex;
private int cellIndex;
public FlatIntList(List<List<int>> data)
{
this.allLists = data;
this.BeginIteration();
}
public void BeginIteration()
{
this.rowIndex = 0;
this.cellIndex = 0;
// omit the empty lists
this.SkipEmptyLists();
}
public bool HasNext()
{
if (this.rowIndex < this.allLists.Count &&
this.cellIndex < this.allLists[this.rowIndex].Count)
{
return true;
}
return false;
}
public int Next()
{
int result = this.allLists[this.rowIndex][this.cellIndex];
this.Iterate();
return result;
}
private void Iterate()
{
if (this.cellIndex < this.allLists[this.rowIndex].Count - 1)
{
// iterate on current row
this.cellIndex++;
}
else
{
// go to the next row
this.cellIndex = 0;
this.rowIndex++;
// omit the empty lists
this.SkipEmptyLists();
}
}
private void SkipEmptyLists()
{
while (this.rowIndex < this.allLists.Count &&
this.allLists[this.rowIndex].Count == 0)
{
this.rowIndex++;
}
}
}
// test the solution
public class Program
{
public static void Main(string[] args)
{
// data
List<List<int>> data = new List<List<int>>()
{
new List<int>(){},
new List<int>(){1},
new List<int>(){2, 3},
new List<int>(){},
new List<int>(){},
new List<int>(){4, 5, 6, 7, 8},
new List<int>(){9},
new List<int>(){},
};
FlatIntList flat = new FlatIntList(data);
// print twice to test it in a better way
for (int x = 0; x < 2; x++)
{
flat.BeginIteration();
while (flat.HasNext())
{
int number = flat.Next();
Console.Write(number);
Console.Write(", ");
}
Console.WriteLine();
}
}
}
/**
*
*/
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* @author Bhumir Jhaveri
*
*/
public class ListInsideListIterator {
/**
* @param args
*/
public static void main(String[] args) {
List list1 = new ArrayList();
List<Integer> listInner1 = new ArrayList <Integer>();
listInner1.add(12);
listInner1.add(2);
listInner1.add(312);
List<Integer> listInner2 = new ArrayList <Integer>();
listInner2.add(4412);
listInner2.add(44);
listInner2.add(42);
list1.add(listInner1);
list1.add(listInner2);
list1.add(3433);
ListInsideListIterator listIterator = new ListInsideListIterator(list1);
while(listIterator.hasNext()) {
System.out.println(listIterator.next());
}
}
List localList;
int currentElement, currentListCounter;
/**
* @param list1
*
*/
public ListInsideListIterator(List list1) {
localList = list1;
}
private Integer next() {
Integer output = new Integer(0);
int currentCounter =0;
Iterator listIterator = ((List)this.localList.get(currentListCounter)).iterator();
while (listIterator.hasNext()) {
if( currentCounter < currentElement) {
currentCounter++;
listIterator.next();
continue;
} else {
currentElement++;
output = Integer.parseInt(""+listIterator.next());
break;
}
}
return output;
}
private void decideCurrentListCounter() {
for(; currentListCounter<localList.size();) {
if(currentElement != ((List)localList.get(currentListCounter)).size()) {
return;
}
currentListCounter++;
currentElement =0;
break;
}
}
private boolean hasNext() {
if(this.localList.get(currentListCounter) instanceof Integer) {
return false;
}
decideCurrentListCounter();
if(currentListCounter < localList.size()) {
if(this.localList.get(currentListCounter) instanceof Integer) {
return false;
} else {
return true;
}
} else {
return false;
}
}
}
Implementation same as everyone here: basically keep the List<List<Integer>> as an instance variable, as well as an index pointing to current list (currentList) and another index pointing to current position of current list (currentIndex). Just hopefully more compact and correct :)
It would actually be much easier had I first convert the List<List<Integer>> into just a List<Integer>, but I actually want to do it the harder (and less efficient) way.
class FlattenList {
private List<List<Integer>> lists;
private int currentList = 0;
private int currentIndex = 0;
public FlattenList(List<List<Integer>> lists) {
this.lists = lists;
findNext(false);
}
public boolean hasNext() {
return (currentList < lists.size() && currentIndex < lists.get(currentList).size());
}
public int next() {
// assuming hasNext() would return true
int result = lists.get(currentList).get(currentIndex);
findNext(true);
return result;
}
private void findNext(boolean advance) {
if(advance)
currentIndex++;
while(currentList < lists.size() && currentIndex >= lists.get(currentList).size()) {
currentList++;
currentIndex=0;
}
}
}
My C# implementation is here. Java should be almost same. Notice that HasNext() and Next() methods are very similar. They can be combined, too.
public class NestedList
{
private int row;
private int col;
private List<List<int>> items;
public NestedList(List<List<int>> items)
{
this.items = items;
}
public bool HasNext()
{
if (this.items == null)
{
return false;
}
// while not end of first level items
while (row < this.items.Count)
{
if (items[row] == null || items[row].Count == 0)
{
col = 0;
row++;
}
else if (col == items[row].Count)
{
col = 0;
row++;
}
else
{
return true;
}
}
return false;
}
public int Next()
{
if (this.items == null)
{
throw new IndexOutOfRangeException();
}
// while not end of first level items
while (row < this.items.Count)
{
if (items[row] == null || items[row].Count == 0)
{
col = 0;
row++;
}
else if (col == items[row].Count)
{
col = 0;
row++;
}
else
{
return items[row][col++];
}
}
throw new IndexOutOfRangeException();
}
public static void Test()
{
List<List<int>> items = new List<List<int>>()
{
new List<int>(){3, 4, 5},
new List<int>(){},
new List<int>(){6},
new List<int>(){7, 8},
null,
new List<int>(){9, 10},
};
NestedList list = new NestedList(items);
while (list.HasNext())
{
Console.WriteLine(list.Next());
}
}
}
My solution holds an iterator to the outer list and a second iterator to the inner list. It seems to me simpler than what I see from others.
public class ListOfLists {
private List<List<Integer>> outerList;
private Iterator<List<Integer>> outerListIter;
private List<Integer> innerList;
private Iterator<Integer> innerListIter;
public void init() {
outerListIter = outerList.iterator();
if(outerListIter.hasNext()) {
innerList = outerListIter.next();
innerListIter = innerList.iterator();
}
}
public boolean hasNext() {
// run through empty lists
while(outerListIter.hasNext() && ! innerListIter.hasNext()) {
innerList = outerListIter.next();
innerListIter = innerList.iterator();
}
return innerListIter.hasNext();
}
public Integer next() {
if(hasNext()) {
return innerListIter.next();
} else {
throw new NoSuchElementException();
}
}
public static void main(String... arg) {
new ListOfLists().test();
}
public void test() {
outerList = new ArrayList<List<Integer>>();
outerList.add(new ArrayList<Integer>());
outerList.add(Arrays.asList(new Integer[] { 3, 4 }));
outerList.add(Arrays.asList(new Integer[] { 5, 7 }));
outerList.add(new ArrayList<Integer>());
init();
while(hasNext()) {
System.out.print(next() + " ");
}
}
}
your code does not handle, list within list within list , etc ie multiple levels of nesting in the lists.
like [[[[12,23,23,3],2,2],1],9]
Hi guys,
why over complicating it so much. The op just asks for flattening a list of lists of integers and implementing next and hasNext. No need for implementing Iterator thus far. Just forward requests to a backing list that just encapsulates the list of lists.
public class FlattenList { int index = 0; List<Integer> flattenedList = new ArrayList<>(); private FlattenList(){ } public static FlattenList getList(List<List<Integer>> lists){ FlattenList flattenList = new FlattenList(); flattenList.flatten(lists); return flattenList; } private void flatten(List<List<Integer>> lists) { for(List<Integer> list : lists){ flattenedList.addAll(list); } } public boolean hasNext(){ return flattenedList.size() > index; } public Integer next(){ Integer result = flattenedList.get(index); index++; return result; } }and the test should look like this
- jeso April 27, 2013public class FlattenListTest { @Before public void setUp() throws Exception { } @Test public void test() { FlattenList flattenList = FlattenList.getList(Arrays.asList( Arrays.asList(6, 8), Arrays.asList(4) )); assertEquals(new Integer(6), flattenList.next()); assertEquals(new Integer(8), flattenList.next()); assertEquals(new Integer(4), flattenList.next()); assertEquals(false, flattenList.hasNext()); } }