Google Interview Question for SDE1s


Country: United States




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

C++ solution. This one also uses a stack, similar to previous answers
I omitted some code which is not relevant to the question itself, as well as some "friend" commands to make it more readable.

NestedNode contains a value and two pointers: to the nested element and to the next element.

template <class C>
class NestedNode
{
public:
	NestedNode(C value, NestedNode<C> *pNested = NULL) : m_value(value), m_pNested(pNested), m_pNext(NULL) {}
	C value() const { return m_value; }
protected:
	C m_value;
	NestedNode<C> *m_pNested;
	NestedNode<C> *m_pNext;
};

NestedList is a simple list containing head and tail pointers:

template <class C>
class NestedList
{
public:
	NestedList() : m_pHead(NULL), m_pLast(NULL) {}
	NestedNode<C> *head() { return m_pHead; }
	void push_back(NestedNode<C> *pNode) { /* omitted */ }

protected:
	NestedNode<C> *m_pHead;
	NestedNode<C> *m_pLast;
};

Here is the iterator.

template <class C>
class NestedIter 
{
public:
	NestedIter(NestedNode<C> *pNode)
	{
		m_stack.push(pNode);
	}

	NestedNode<C> *next()
	{
		if (m_stack.size() == 0)
			return NULL;

		NestedNode<C> *pCur = m_stack.top();
		m_stack.pop();

		if (pCur->m_pNext)
			m_stack.push(pCur->m_pNext);
		if (pCur->m_pNested)
			m_stack.push(pCur->m_pNested);

		return pCur;
	}

protected:
	stack<NestedNode<C> *> m_stack;
};

And a sample "main"

int main()
{
	NestedList<int> aList;

	aList.push_back(new NestedNode<int>(1) );
	aList.push_back(new NestedNode<int>(2) );
	aList.push_back(new NestedNode<int>(3, new NestedNode<int>(4) ));
	aList.push_back(new NestedNode<int>(5, new NestedNode<int>(6) ));

	NestedIter<int> nestedIter(aList.head());
	NestedNode<int> *pNode;

	while ((pNode = nestedIter.next()) != NULL)
		 cout << pNode->value() << " -> ";
	cout << "|" << endl;
}

- Grr1967 January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

-100: Using extra storage misses the point of the question.

- Anonymous January 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

there is no need to use the stack, just push the nested element between current node and next node. something like,

tempNode=curnode->nextNode;
curNode->nextNode=curNode->nestedNode;
curNode->nextNode=tempNode;

btw I assumed that the linked list will not need to be the same after print. otherwise we always can use a single node entry as a exchange space instead of a stack. It will be initialized with null.

exchangeNode=null;

then in the iterator
whenever we wanna print a value

if(!exchangeNode!=NULL)
{
	new_copy_of_exchangeNode=copy(exchangeNode);
	exchangeNode=NULL;
	return new_copy_of_exchangeNode;
}

else
{
	exchangeNode=curNode->nestedNode;
	tempNode=curNode;
	curNode=curNode->next;
	return tempNode;
}

- hirajhil January 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

package test;

import java.util.*;

public class Test {

	public static void main(String[] args) {

		Node start = new Node(1);

		start.addNextNode(2).addNestedNode(3).addNestedNode(4).addNextNode(5)
				.addNestedNode(6);

		List list = new List(start);
		Iterator<Integer> t = list.iterator();

		while (t.hasNext()) {
			System.out.print(t.next() + "  ");
		}

	}

}

class MyIterator implements Iterator<Integer> {

	Node n1; //traverses main nodes
	Node n2; //traverses nested nodes

	boolean traverseNestedNodes;

	MyIterator(List list) {
		n1 = list.start;
		n2 = null;
	}

	@Override
	public boolean hasNext() {
		return n2 != null || n1 != null;
	}

	@Override
	public Integer next() {
		int value;
		if (n1 == null && n2 == null) {
			throw new NoSuchElementException();
		}

		if (n2 == null) {
			value = n1.value;
			n2 = n1.nestedNodes;
			n1 = n1.next;
		} else {
			value = n2.value;
			n2 = n2.next;
		}

		return value;

	}

	@Override
	public void remove() {

	}
}

class Node {
	int value;
	Node next;

	Node nestedNodes;

	Node(int value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return value + "";
	}

	Node addNextNode(int value) {
		Node nextNode = new Node(value);
		this.next = nextNode;
		return nextNode;
	}

	Node addNestedNode(int value) {
		Node newNode = new Node(value);
		if (nestedNodes == null) {
			nestedNodes = newNode;
		} else {

			Node cursor = nestedNodes;
			while (cursor.next != null) {
				cursor = cursor.next;
			}
			cursor.next = newNode;
		}
		return this;
	}

}

class List {
	Node start;

	List(Node start) {
		this.start = start;
	}

	@Override
	public String toString() {
		Node current = start;
		StringBuilder buf = new StringBuilder();
		while (current != null) {
			buf.append(current + "  ");
			current = current.next;
		}

		return buf.toString();
	}

	Iterator<Integer> iterator() {
		return new MyIterator(this);
	}
}

- Serdar January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can this solution handle situation like
1 --> 2 (3) --> 4(5(6))

- lixiaobai February 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Iterator {

	protected LinkedList<ListNode> flattenedList = LinkedList<ListNode> = new LinkedList<ListNode>();
	ListNode pointer = null;

	public Iterator(ListNode head) {
		pointer = head;
		traverseNodes(head);
	}

	public boolean hasNext() {
		if (pointer == null) return false;
		else return true; 
	}
	
	public ListNode next() {
		ListNode returnVal = pointer;
		pointer = pointer.next();
		return returnVal;
		
	}

	public void traverseNodes(ListNode x) {
		while ( x != null ) {
			flattenedList.add(x);

			// traverses 'downwards'
			if (x.nestedNodes != null) {
				traverseNestedNodes(x.nestedNodes);
			}
			// Iterate through current level's linkedlist
			if (x.next != null) {
				x = x.next;
			}
		}
		return;
	}
}

public class ListNode() {
	int data;
	ListNode nestedNodes;
	ListNode next;
}

- andrew January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

EDIT:
Sorry, I was in a rush

traverseNestedNodes()

call should be

traverseNodes()

- andrew January 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't the next() method return an int that represents the data? I am also not sure whether it's acceptable to first iterate through the input, instead of iterating "on the fly".

- Sunny January 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FlattenIterator implements Iterator<Integer> {
     stack<iterator> st;
     public FlattenIterator(LinkedList<Object> in)
     {
            if (in != null) {
                 st = new Stack<Iterator>(); 
                 st.push(in.iterator()); 
            }
     }
     private void moveToNext() 
     {
            next = null; 
            while (!st.isEmpty())
            {
                     Iterator it = st.peek();
                     if (it.hasNext())
                     {
                             Object o = it.next();
                             if (o  instanceof Integer) { 
                                        next = (Integer)o ;
                                         break;
                             } 
                             if (o instanceof List) {
                                       st.push( (List)o.iterator() ); 
                             }
                     }
                     else { st.pop(); {
            }
     }

     public boolean hasNext() {
          next = null;
          moveToNext();
          return next != null; 
     }
     public Integer next() 
     {
           if (next == null) throw NoSuchElementException;
           return next;
     }
     public void remove()
     {
             throw UnSupportedOperationException;
     }
}

- Anonymous January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// For those want in python, use yield

def flatten(l) :
              for ele in l :
                      if type([]) == type(ele) :
                              flatten(ele)
                      else :
                              yield ele ;

- Anonymous January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yield is specifically disallowed.

- Anonymous January 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Node {
    int value;
    Node *next;
    Node *nextNested;
};

void traverse(Node *start)
{
    if (start != NULL)
    {
        printf("%d ", start->value);
        traverse(start->nextNested);
        traverse(start->next);
    }
}

- Carlo January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Iterator: hasNext, next.

What you have is nonsense, sorry.

- Anonymous January 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I like the anonymous Python solution. Technically, though, lists in Python may not be implemented as linked lists, so here's a solution with explicit linked lists:

class Node:
    data = None
    next = None


class LinkedList:
    head = None

    def append(self, data):
        new_node = Node()
        new_node.data = data
        new_node.next = self.head
        self.head = new_node

    def stringify(self):
        res = ""
        curr = self.head
        while curr is not None:
            if isinstance(curr.data, LinkedList):
                res += curr.data.stringify()
            else:
                res += str(curr.data)
            if curr.next is not None:
                res += " -> "
            curr = curr.next
        return res

- nilkn January 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

test cases:
1) null ?
2) 1
3) 1-2
4) 1-(2-3)-4
4.a) 1-(2-3)-(4-5)
5) 1-(2-(3-4))-5

class Iterator
{
  LinkedList linkedList;
  Iterator: innerIterator = null;

  public Iterator(LinkedList: linkedList){
    this.linkedList = linkedList;
  }

  public Node[] toArray(){
    Node[] nodeArray;

    next = next();    
    if (next == null) return new Node[]();
   do{
    nodeArray.push(next);
    next = next();
   } while(next != null)
    return nodeArray;
  }

  public Node next(){
    Node next = null;
    if( innerIterator != null){
      next = getInnerNext();
      if (next != null) return next;
      clearInnerIterator();
    } 
    
    next = linkedList.next();
    if(next instanceOf LinkedList){
      innerIterator = new Iterator(next);
      return innerIterator.next();
    }

    return this.next;
  }

  private Node getInnerNext(){
    innerIterator.next();
  }
  
  private void clearInnerIterator(){
    innerIterator = null;
  }
}

- grandbora January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can consider this Binary Tree where next pointer of Linked List Node is equivalent to right node of Binary Tree and Nested pointer of Linked List Node as left node of Binary tree. Then simple do pre-order traversal.

- aviundefined January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple DFS Kind of solution for this

Node 
{
	Node next;
	Node nested;
	int value;
}

void iterator(Node head)
{
	if(head == null)
		return;
	System.out.println(head->value);
	iterator(node->nested);
	iterator(node->next);

- aviundefined January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple DFS Kind of solution for this
Node 
{
	Node next;
	Node nested;
	int value;
}

void iterator(Node head)
{
	if(head == null)
		return;
	System.out.println(head->value);
	iterator(node->nested);
	iterator(node->next);

- aviundefined January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple DFS Kind of solution for this
Node 
{
	Node next;
	Node nested;
	int value;
}

void iterator(Node head)
{
	if(head == null)
		return;
	System.out.println(head->value);
	iterator(node->nested);
	iterator(node->next);

- aviundefined January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple DFS Kind of solution for this
Node 
{
	Node next;
	Node nested;
	int value;
}

void iterator(Node head)
{
	if(head == null)
		return;
	System.out.println(head->value);
	iterator(node->nested);
	iterator(node->next);

- aviundefined January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A composite iterator (composite pattern) can be designed for as s solution to this problem. The main intent of Composite lets clients treat individual objects and compositions of objects uniformly. We can come up with a Composite iterator which will implement existing Iterator and internally will make use of Stack. One of the solution suggested in this thread (FlattenIterator to be precise) is in fact a composite iterator.

- Rakesh Roy January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

there is no need to use the stack, just push the nested element between current node and next node. something like,

tempNode=curnode->nextNode;
curNode->nextNode=curNode->nestedNode;
curNode->nextNode=tempNode;

btw I assumed that the linked list will not need to be the same after print. otherwise we always can use a single node entry as a exchange space instead of a stack. It will be initialized with null.

exchangeNode=null;

then in the iterator
whenever we wanna print a value

if(!exchangeNode!=NULL)
{
	new_copy_of_exchangeNode=copy(exchangeNode);
	exchangeNode=NULL;
	return new_copy_of_exchangeNode;
}

else
{
	exchangeNode=curNode->nestedNode;
	tempNode=curNode;
	curNode=curNode->next;
	return tempNode;
}

- hirajhil January 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

So Did you enter google?

- IWILLALSOENTERGOOGLE January 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

No he got a job as a delivery guy. Now he enters Google in the behind. Hahaha.

- Anonymous January 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Simple DFS Kind of solution for this

Node 
{
	Node next;
	Node nested;
	int value;
}

void iterator(Node head)
{
	if(head == null)
		return;
	System.out.println(head-->value);
	iterator(node.nested);
	iterator(node.next);

- aviundefined January 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not an iterator, you are just printing values.

- hirajhil January 26, 2014 | Flag


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