Google Interview Question
SDE1sCountry: United States
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;
}
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);
}
}
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;
}
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;
}
}
// For those want in python, use yield
def flatten(l) :
for ele in l :
if type([]) == type(ele) :
flatten(ele)
else :
yield ele ;
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);
}
}
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
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;
}
}
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.
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;
}
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);
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.
NestedList is a simple list containing head and tail pointers:
Here is the iterator.
And a sample "main"
- Grr1967 January 14, 2014