Google Interview Question
Software Engineer / DevelopersCountry: United States
Why are you using recursion when you can simply add all element of inner list or collection object using addAll() method in same order!!
In the code, if you see, the recursion is to check if the obj is instance of Collection. We can't just do addAll for the collection as it can contain collection again. Imagine something like List<List<List...>>> In that case we go till the collection with plain objects not instance of Collection and then add them to the list.
May be yes i can optimize the code. I was just trying to show what i thought could be a way of implementing :)
Well, I went through your code, it works perfectly with any structure of input. However, your space usage is too large...
The write way to do is to NOT store the flattened list in RAM, but instead, keep a stack of iterators, and keep track of current iterator that we use to pop() next elements.
When current iterator is NULL, pop next element from the stack and proceed.
I wish my answer explains clearly. Thanks!
import java.util.ArrayList;
import java.util.Iterator;
public class Problem {
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> integers = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++) {
ArrayList<Integer> temp = new ArrayList<Integer>();
for (int j = 0; j < i; j++) {
temp.add(i);
}
integers.add(temp);
}
ArrayList<Iterator<Integer>> iter = new ArrayList<Iterator<Integer>>();
for (int i = 0; i < integers.size(); i++) {
iter.add(integers.get(i).iterator());
}
Iterator<Iterator<Integer>> iterator = iter.iterator();
ArrayList<Integer> arrInts = new ArrayList<Integer>();
while(iterator.hasNext()){
Iterator<Integer> i = iterator.next();
while(i.hasNext()){
int j = i.next();
arrInts.add(j);
}
}
for (int i = 0; i < arrInts.size(); i++) {
System.out.println(arrInts.get(i));
}
}
}
class FlatIterator implements Iterator{
List<Object> list;
Stack<Iterator> stack;
Iterator currIterator;
public FlatIterator(List<Object> l){
this.list=l;
stack = new Stack<Iterator>();
currIterator = list.iterator;
}
boolean hasNext() {
if(!currIterator.hasNext()){
if(stack.isEmpty())
return false;
else{
return stack.peek().hasNext();
}
}else{
return true;;
}
}
Integer next() {
if(currIterator.hasNext()){
Object curr =currIterator.next();
if(curr instanceof Integer)
return curr;
else{
stack.push(currIterator);
currIterator = curr.iterator;
return this.next();
}
} else if(!stack.isEmpty()){
currIterator = stack.pop();
return this.next();
}
}
}
package com.google.practice;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
class CrazyIterator implements Iterator<String>{
public CrazyObject c;
public CrazyIterator(CrazyObject c){
this.c = c;
}
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
if(!this.c.myCharacter.get(this.c.cposition).equals("#")){
if(this.c.myCharacter.get(this.c.cposition).equals("@")){
this.c.cposition++;
this.c = this.c.mySperm.get(this.c.sposition++);
this.hasNext();
}
return true;
}else{
if(this.c.myParent!=null){
this.c = this.c.myParent;
return this.hasNext();
}
}
return false;
}
@Override
public String next() {
// TODO Auto-generated method stub
return this.c.myCharacter.get(this.c.cposition++);
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
}
class CrazyObject implements Iterable{
public List<String> myCharacter;
public List<CrazyObject> mySperm;
public CrazyObject myParent=null;
public int cposition = 0,sposition=0;
public CrazyObject(){
myCharacter = new ArrayList<String>();
mySperm = new ArrayList<CrazyObject>();
}
public void test(){}
@Override
public Iterator iterator() {
// TODO Auto-generated method stub
return new CrazyIterator(this);
}
public String toString(){
String s = "[",s1;
CrazyIterator ct = (CrazyIterator) this.iterator();
while(ct.hasNext()){
s1 = ct.next();
if(s1.length()>0)
s = s +(s1+",");
}
return s.substring(0,s.length()-1)+"]";
}
}
public class Iter {
public static void main(String[] arg){
String s = "[[0,1,2],[3,4,5],[6,7,8],[9,10,11],[]]";//"[1,2,[3,[4,5]],6]";
CrazyObject crazyFamily = buildCrazyObject(s);
System.out.println(crazyFamily);
}
public static CrazyObject buildCrazyObject(String s){
String n = "";
CrazyObject crazy = null,previous = null;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='['){
CrazyObject c = new CrazyObject();
if(crazy!=null){
crazy.myCharacter.add("@");
crazy.mySperm.add(c);
}
c.myParent = crazy;
crazy = c;
}else if(s.charAt(i)==']'){
crazy.myCharacter.add(n);
n="";
crazy.myCharacter.add("#");
previous = crazy;
crazy = crazy.myParent;
}else if(s.charAt(i)!=','){
n = n+s.charAt(i);
}else{
crazy.myCharacter.add(n);
n="";
}
}
return previous;
}
}
package google;
import org.junit.Test;
import java.util.*;
import static org.junit.Assert.*;
public class FlattenIteratorTest {
@Test
public void test() {
List<Object> lst = Arrays.asList(1,
Arrays.asList(2, 3),
Collections.emptyList(),
4,
Arrays.asList(Arrays.asList(5, 6), 7),
Collections.emptyList()
);
FlattenIterator it = new FlattenIterator(lst);
for (int i = 1; i <= 7; i++) {
assertTrue(it.hasNext());
assertEquals(i, (int) it.next());
}
assertFalse(it.hasNext());
try {
it.next();
} catch (NoSuchElementException e) {
return;
}
fail("Doesn't throw NoSuchElementException when has no elements.");
}
private static class FlattenIterator implements Iterator<Integer> {
private LinkedList<Object> elements = new LinkedList<>();
public FlattenIterator(List lst) {
elements.addAll(lst);
unwrap();
}
private void unwrap() {
while (!elements.isEmpty() && elements.peek() instanceof List) {
List l = (List) elements.poll();
elements.addAll(0, l);
}
}
@Override
public boolean hasNext() {
return !elements.isEmpty();
}
@Override
public Integer next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
Integer val = (Integer) elements.poll();
unwrap();
return val;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
}
{{
function Iterator (_data) {
// closure
var self = this;
self.next = function () {
var value = null;
if (data.length > 0) {
value = data.shift();
if (value instanceof Array) {
value = new Iterator(value);
}
}
return value;
};
self.hasNext = function () {
return data.length > 0? true : false;
};
var data = _data;
}
function IteratorOfIterators (_data) {
// closure
var self = this;
//////////////////////
// public
self.hasNext = function () {
findNextIterator();
return (next != null);
};
self.next = function () {
return next;
};
////////////////////////
// private
var findNextIterator = function () {
if (stackOfIterators.length !== 0)
{
if (stackOfIterators[stackOfIterators.length-1].hasNext())
{
next = stackOfIterators[stackOfIterators.length-1].next();
if (next instanceof Iterator)
{
stackOfIterators.push(next);
findNextIterator();
}
}
else
{
stackOfIterators.pop();
findNextIterator();
}
}
else
{
next = null;
}
};
// stack of iterators
var stackOfIterators = [];
stackOfIterators.push(new Iterator(_data));
// current iterator
var next = null;
}
var listOfLists = [[1,2],[3,[4,5]],6];
//var listOfLists = [1,2,[3,4,5],6, [7,[8,9,[10,11]],12] ,13];
var it = new IteratorOfIterators(listOfLists);
while (it.hasNext() === true) {
console.log(it.next());
}
}}
{{
function Iterator (_data) {
// closure
var self = this;
self.next = function () {
var value = null;
if (data.length > 0) {
value = data.shift();
if (value instanceof Array) {
value = new Iterator(value);
}
}
return value;
};
self.hasNext = function () {
return data.length > 0? true : false;
};
var data = _data;
}
function IteratorOfIterators (_data) {
// closure
var self = this;
//////////////////////
// public
self.hasNext = function () {
findNextIterator();
return (next != null);
};
self.next = function () {
return next;
};
////////////////////////
// private
var findNextIterator = function () {
if (stackOfIterators.length !== 0)
{
if (stackOfIterators[stackOfIterators.length-1].hasNext())
{
next = stackOfIterators[stackOfIterators.length-1].next();
if (next instanceof Iterator)
{
stackOfIterators.push(next);
findNextIterator();
}
}
else
{
stackOfIterators.pop();
findNextIterator();
}
}
else
{
next = null;
}
};
// stack of iterators
var stackOfIterators = [];
stackOfIterators.push(new Iterator(_data));
// current iterator
var next = null;
}
var listOfLists = [[1,2],[3,[4,5]],6];
//var listOfLists = [1,2,[3,4,5],6, [7,[8,9,[10,11]],12] ,13];
var it = new IteratorOfIterators(listOfLists);
while (it.hasNext() === true) {
console.log(it.next());
}
}}
function flat(list) {
if (!Array.isArray(list)) {
return [list];
}
const [first, ...rest] = list;
return rest.length? flat(first).concat(flat(rest)): flat(first) ;
}
function flat2(list){
let result = [];
list.forEach(item => {
if (!Array.isArray(item)){
result.push(item);
}else {
result = result.concat(flat2(item));
}
});
return result;
}
Through this program we create our own iterator based on the actual iterator by java collections. We read the input collection, read the complete data and add them to array list and then iterator over it to get information. This may not the actual solution but this works.
- Sunil February 24, 2014Correct me i am wrong!