# boards

iterator 实现 如何 peek()，pop()?Bloomberg phone interview 面经

combinations 有没有 iterative的方法阿 ?G电面题 + 求祝福

 1 (共1页)
l*********h

1
"Program an iterator for a List which may include nodes or List i.e. * {0,
{1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"

Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
/**
*
* {0,{1,2}, 3 ,{4,{5, 6}}}
*
* 0 - 1 - 2 - 3 - 4 - 5 - 6
*
*/
class DeepIterator implements Iterator {
private Stack stack;
public DeepIterator(ArrayList finalLists){
stack = new Stack();
stack.push(finalLists.iterator());
}
public boolean hasNext() {
if (stack.isEmpty()) {
return false;
} else {
Iterator iterator = stack.peek();
if (!iterator.hasNext()) {
stack.pop();
return hasNext();
} else {
return true;
}
}
}
public Object next() {
if (hasNext()) {
Iterator iterator = stack.peek();
Object object = iterator.next();
if (object instanceof ArrayList) {
stack.push(((ArrayList) object).iterator());
return next();
} else {
return object;
}
}
return null;
}
public void remove() {
}
}
//下面是输出的例子
public class Question {
public Iterator getIterator(ArrayList lists) {
return new DeepIterator(lists);
}

public static void main(String[] args) {
ArrayList finalLists = new ArrayList();

ArrayList firstLevelList = new ArrayList();

firstLevelList = new ArrayList();
ArrayList secondLevelList = new ArrayList();

System.out.print("The original Lists is --- > " + finalLists);
Question sol = new Question();
Iterator iterator = sol.getIterator(finalLists);
System.out.println();
System.out.print("The flatten Lists is --- > ");
while(iterator.hasNext()) {
System.out.print(iterator.next() + " --> ");
}
}
}

Composite Pattern 似的 有一个 Item 的 interface, singleItem 和 listItem

s*****r

2

code不clean，变量太多，用first和second这些是大忌，变量名没有含义。这题有一个

0,

【在 l*********h 的大作中提到】
: "Program an iterator for a List which may include nodes or List i.e. * {0,
: {1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"
: 今天翻Design Pattern 的时候看到iterator and composite pattern 突然发现这个和
: 前一阵一直不会写的Deep Iterator有点像
: 大概思路是这样的，用一个stack 存放 iterator 如果到了最底层是Integer就输出，
: 如果iterator.next还是个List,就把这个List的iterator 扔到stack里面，然后
: Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果
: 已经遍历到最后用完了，就直接扔出stack
: 底下是程序

l*n

3
arraylist没有控制类型是什么意思？java是可以check list类型的，到了最后的
integer层的时候，instanceof (ArrayList
l*********h

4

【在 l*n 的大作中提到】
: arraylist没有控制类型是什么意思？java是可以check list类型的，到了最后的
: integer层的时候，instanceof (ArrayList
l*********h

5

【在 s*****r 的大作中提到】
: 俺虽然没仔细看，扫一眼，知道你的面试基本完了
: code不clean，变量太多，用first和second这些是大忌，变量名没有含义。这题有一个
: 变量就OK了
:
: 0,

P*******r

6

0,

【在 l*********h 的大作中提到】
: "Program an iterator for a List which may include nodes or List i.e. * {0,
: {1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"
: 今天翻Design Pattern 的时候看到iterator and composite pattern 突然发现这个和
: 前一阵一直不会写的Deep Iterator有点像
: 大概思路是这样的，用一个stack 存放 iterator 如果到了最底层是Integer就输出，
: 如果iterator.next还是个List,就把这个List的iterator 扔到stack里面，然后
: Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果
: 已经遍历到最后用完了，就直接扔出stack
: 底下是程序

n****e

7
L家要求这么高啊？正在准备L家on site。前辈有什么建议。

【在 s*****r 的大作中提到】
: 俺虽然没仔细看，扫一眼，知道你的面试基本完了
: code不clean，变量太多，用first和second这些是大忌，变量名没有含义。这题有一个
: 变量就OK了
:
: 0,

p*u

8

class Collection
{
public:
T next() {

if (_type == 0)
{
if (_index == 0)
{
_index++;
return _value
}
else
{
throw Exception;
}
}
else
{
while (_index < buckets.size())
{
if (_buckets[_index].hasNext())
return _buckets[_index].next();
_index++;
}
throw Exception;
}
}

boolean hasNext() {
if (_type == 0)
{
// because we have only one value
// the index is initialized to zero at first
if (_index == 0)
return true;
else
return false;
}
else
{
int tmp = _index;
// in case we have empty buckets[_index], so we should
loop over it
while (tmp < buckets.size())
{
if (buckets[tmp].hasNext())
return true;
tmp++;
}
if (tmp == _buckets.size())
return false; // all the buckets are used
}
}
private:
std::vector _buckets;
T _value;
int _type; // 0: value 1: buckets
int _index; // the current iterator position in buckets, or the
value is used or not
};

0,

【在 l*********h 的大作中提到】
: "Program an iterator for a List which may include nodes or List i.e. * {0,
: {1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"
: 今天翻Design Pattern 的时候看到iterator and composite pattern 突然发现这个和
: 前一阵一直不会写的Deep Iterator有点像
: 大概思路是这样的，用一个stack 存放 iterator 如果到了最底层是Integer就输出，
: 如果iterator.next还是个List,就把这个List的iterator 扔到stack里面，然后
: Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果
: 已经遍历到最后用完了，就直接扔出stack
: 底下是程序

n****e

9

【在 p*u 的大作中提到】
: 电面写的这段代码，过了。
: class Collection
: {
: public:
: T next() {
:
: if (_type == 0)
: {
: if (_index == 0)
: {

J****3

10

e********r

11

import scala.collection.mutable.ArrayBuffer
def deepFlatten(list: Seq[Any]):ArrayBuffer[Int] = list match {
case Nil => ArrayBuffer()
case elem::rest => elem match {
case v: Int => v +=: deepFlatten(rest)
case l: Seq[Any] => deepFlatten(l) ++=: deepFlatten(rest)
}
}

class DeepIterator(list: Seq[Any]) {
val content = deepFlatten(list)
def hasNext = !content.isEmpty
def next = {
content -= item
item
}
}
J****3

12

m*****n

13

// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator
n****e

14

1， Collection只能遍历一边，第二次遍历就出错了。
2， 这里没有iterator的 implementation。 如何用c++实现iterator

【在 p*u 的大作中提到】
: 电面写的这段代码，过了。
: class Collection
: {
: public:
: T next() {
:
: if (_type == 0)
: {
: if (_index == 0)
: {

D*T

15

import java.util.*;
class ArrayPosition {
ArrayList array;
int index;
ArrayPosition(ArrayList array) {
this.array = array;
index = 0;
}
Object peekItem() {
return array.get(index);
}
Object takeItem() {
return array.get(index++);
}
}
public class DeepIteratorII implements Iterator {
private Stack stack;
public DeepIteratorII (ArrayList al) {
stack = new Stack();
}
public boolean hasNext() {
if (stack.isEmpty()) {
return false;
}
ArrayPosition top = stack.peek();
if (top.array.size()<=top.index) {
stack.pop();
return hasNext();
}
if (top.peekItem() instanceof ArrayList) {
stack.push(new ArrayPosition( (ArrayList) top.takeItem()));
return hasNext();
}
return true;
}
public T next() {
ArrayPosition top = stack.peek();
return (T) top.takeItem();
}
public void remove() {
ArrayPosition top = stack.peek();
top.array.remove(--top.index);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
DeepIteratorII di = new DeepIteratorII(al);
while (di.hasNext()) {
int m = (Integer) di.next();
if (m == 4) {
di.remove();
System.out.println("Remove "+m);
}
else {
System.out.println(m);
}
}
di = new DeepIteratorII(al);
while (di.hasNext()) {
int m = (Integer) di.next();
System.out.println(m);
}
}
}
n****e

16

ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));

DeepIterator所对应的list是：{1, {2, 3, {4, 5}, 6}, 7}。 应该是类似这种的。

ok

【在 D*T 的大作中提到】
: 想了一下，这个问题好像不是那么容易。楼主的code如果末尾有个空的List会出错。我
: 不太懂C++所以pdu的只是半懂，不过感觉我的想法和ta估计差不多。moridin的code很
: 神奇，我实在看不太懂。
: 的。
: import java.util.*;
: class ArrayPosition {
: ArrayList array;
: int index;
: ArrayPosition(ArrayList array) {

D*T

17

【在 n****e 的大作中提到】
: 多谢回复。
: ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
: 上面这段codes中，al依然只是一般的ArrayList。 不是DeepIterator所对应的list吧？
: DeepIterator所对应的list是：{1, {2, 3, {4, 5}, 6}, 7}。 应该是类似这种的。
:
: ok

n****e

18

specified element to the end of this list.
http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.ht

ArrayList al 应该需要注明ArrayList里面element的type吧。 比如：
ArrayList al = ...

【在 D*T 的大作中提到】
: 这个应该没错。这样al搞出来的是{1,2,3,{4,5},{}}。我用debugger跟进去了，应该是
: 没问题的。
:
: 吧？

D*T

19
ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));

ArrayList的确应该说明generic的类型为好，不过因为al里既有List又有Integer，实

n****e

20

【在 D*T 的大作中提到】
: ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
: 这句括号内部得到{1,2,3}，进入constructor返回的依然是{1,2,3}
: 这句括号内部是{4,5}，加到原来al上于是变成{1,2,3,{4,5}}
: 这句括号内部是{}，加到al上变成{1,2,3,{4,5},{}}
: ArrayList的确应该说明generic的类型为好，不过因为al里既有List又有Integer，实
: 际上就是ArrayList

Bloomberg phone interview 面经Leetcode: Symmetric Tree有没有好的iterative的解法？
L家面试题 iterator for nested integer求讨论Facebook Phone Interview
G电面题 + 求祝福灭三哥也不容易
b*****6

21

public class DeepIterator {
private Stack
l*********h

22
"Program an iterator for a List which may include nodes or List i.e. * {0,
{1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"

Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
/**
*
* {0,{1,2}, 3 ,{4,{5, 6}}}
*
* 0 - 1 - 2 - 3 - 4 - 5 - 6
*
*/
class DeepIterator implements Iterator {
private Stack stack;
public DeepIterator(ArrayList finalLists){
stack = new Stack();
stack.push(finalLists.iterator());
}
public boolean hasNext() {
if (stack.isEmpty()) {
return false;
} else {
Iterator iterator = stack.peek();
if (!iterator.hasNext()) {
stack.pop();
return hasNext();
} else {
return true;
}
}
}
public Object next() {
if (hasNext()) {
Iterator iterator = stack.peek();
Object object = iterator.next();
if (object instanceof ArrayList) {
stack.push(((ArrayList) object).iterator());
return next();
} else {
return object;
}
}
return null;
}
public void remove() {
}
}
//下面是输出的例子
public class Question {
public Iterator getIterator(ArrayList lists) {
return new DeepIterator(lists);
}

public static void main(String[] args) {
ArrayList finalLists = new ArrayList();

ArrayList firstLevelList = new ArrayList();

firstLevelList = new ArrayList();
ArrayList secondLevelList = new ArrayList();

System.out.print("The original Lists is --- > " + finalLists);
Question sol = new Question();
Iterator iterator = sol.getIterator(finalLists);
System.out.println();
System.out.print("The flatten Lists is --- > ");
while(iterator.hasNext()) {
System.out.print(iterator.next() + " --> ");
}
}
}

Composite Pattern 似的 有一个 Item 的 interface, singleItem 和 listItem

s*****r

23

code不clean，变量太多，用first和second这些是大忌，变量名没有含义。这题有一个

0,

【在 l*********h 的大作中提到】
: "Program an iterator for a List which may include nodes or List i.e. * {0,
: {1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"
: 今天翻Design Pattern 的时候看到iterator and composite pattern 突然发现这个和
: 前一阵一直不会写的Deep Iterator有点像
: 大概思路是这样的，用一个stack 存放 iterator 如果到了最底层是Integer就输出，
: 如果iterator.next还是个List,就把这个List的iterator 扔到stack里面，然后
: Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果
: 已经遍历到最后用完了，就直接扔出stack
: 底下是程序

l*n

24
arraylist没有控制类型是什么意思？java是可以check list类型的，到了最后的
integer层的时候，instanceof (ArrayList
l*********h

25

【在 l*n 的大作中提到】
: arraylist没有控制类型是什么意思？java是可以check list类型的，到了最后的
: integer层的时候，instanceof (ArrayList
l*********h

26

【在 s*****r 的大作中提到】
: 俺虽然没仔细看，扫一眼，知道你的面试基本完了
: code不clean，变量太多，用first和second这些是大忌，变量名没有含义。这题有一个
: 变量就OK了
:
: 0,

P*******r

27

0,

【在 l*********h 的大作中提到】
: "Program an iterator for a List which may include nodes or List i.e. * {0,
: {1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"
: 今天翻Design Pattern 的时候看到iterator and composite pattern 突然发现这个和
: 前一阵一直不会写的Deep Iterator有点像
: 大概思路是这样的，用一个stack 存放 iterator 如果到了最底层是Integer就输出，
: 如果iterator.next还是个List,就把这个List的iterator 扔到stack里面，然后
: Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果
: 已经遍历到最后用完了，就直接扔出stack
: 底下是程序

n****e

28
L家要求这么高啊？正在准备L家on site。前辈有什么建议。

【在 s*****r 的大作中提到】
: 俺虽然没仔细看，扫一眼，知道你的面试基本完了
: code不clean，变量太多，用first和second这些是大忌，变量名没有含义。这题有一个
: 变量就OK了
:
: 0,

p*u

29

class Collection
{
public:
T next() {

if (_type == 0)
{
if (_index == 0)
{
_index++;
return _value
}
else
{
throw Exception;
}
}
else
{
while (_index < buckets.size())
{
if (_buckets[_index].hasNext())
return _buckets[_index].next();
_index++;
}
throw Exception;
}
}

boolean hasNext() {
if (_type == 0)
{
// because we have only one value
// the index is initialized to zero at first
if (_index == 0)
return true;
else
return false;
}
else
{
int tmp = _index;
// in case we have empty buckets[_index], so we should
loop over it
while (tmp < buckets.size())
{
if (buckets[tmp].hasNext())
return true;
tmp++;
}
if (tmp == _buckets.size())
return false; // all the buckets are used
}
}
private:
std::vector _buckets;
T _value;
int _type; // 0: value 1: buckets
int _index; // the current iterator position in buckets, or the
value is used or not
};

0,

【在 l*********h 的大作中提到】
: "Program an iterator for a List which may include nodes or List i.e. * {0,
: {1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"
: 今天翻Design Pattern 的时候看到iterator and composite pattern 突然发现这个和
: 前一阵一直不会写的Deep Iterator有点像
: 大概思路是这样的，用一个stack 存放 iterator 如果到了最底层是Integer就输出，
: 如果iterator.next还是个List,就把这个List的iterator 扔到stack里面，然后
: Recusion next()方法。每回从stack里面取的时候看看那个iterator有没有用完，如果
: 已经遍历到最后用完了，就直接扔出stack
: 底下是程序

n****e

30

【在 p*u 的大作中提到】
: 电面写的这段代码，过了。
: class Collection
: {
: public:
: T next() {
:
: if (_type == 0)
: {
: if (_index == 0)
: {

inorder traversal的空间复杂度是O(N) 还是O(logN)?讨论一个题目

J****3

31

e********r

32

import scala.collection.mutable.ArrayBuffer
def deepFlatten(list: Seq[Any]):ArrayBuffer[Int] = list match {
case Nil => ArrayBuffer()
case elem::rest => elem match {
case v: Int => v +=: deepFlatten(rest)
case l: Seq[Any] => deepFlatten(l) ++=: deepFlatten(rest)
}
}

class DeepIterator(list: Seq[Any]) {
val content = deepFlatten(list)
def hasNext = !content.isEmpty
def next = {
content -= item
item
}
}
J****3

33

m*****n

34

// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator
n****e

35

1， Collection只能遍历一边，第二次遍历就出错了。
2， 这里没有iterator的 implementation。 如何用c++实现iterator

【在 p*u 的大作中提到】
: 电面写的这段代码，过了。
: class Collection
: {
: public:
: T next() {
:
: if (_type == 0)
: {
: if (_index == 0)
: {

D*T

36

import java.util.*;
class ArrayPosition {
ArrayList array;
int index;
ArrayPosition(ArrayList array) {
this.array = array;
index = 0;
}
Object peekItem() {
return array.get(index);
}
Object takeItem() {
return array.get(index++);
}
}
public class DeepIteratorII implements Iterator {
private Stack stack;
public DeepIteratorII (ArrayList al) {
stack = new Stack();
}
public boolean hasNext() {
if (stack.isEmpty()) {
return false;
}
ArrayPosition top = stack.peek();
if (top.array.size()<=top.index) {
stack.pop();
return hasNext();
}
if (top.peekItem() instanceof ArrayList) {
stack.push(new ArrayPosition( (ArrayList) top.takeItem()));
return hasNext();
}
return true;
}
public T next() {
ArrayPosition top = stack.peek();
return (T) top.takeItem();
}
public void remove() {
ArrayPosition top = stack.peek();
top.array.remove(--top.index);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
DeepIteratorII di = new DeepIteratorII(al);
while (di.hasNext()) {
int m = (Integer) di.next();
if (m == 4) {
di.remove();
System.out.println("Remove "+m);
}
else {
System.out.println(m);
}
}
di = new DeepIteratorII(al);
while (di.hasNext()) {
int m = (Integer) di.next();
System.out.println(m);
}
}
}
n****e

37

ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));

DeepIterator所对应的list是：{1, {2, 3, {4, 5}, 6}, 7}。 应该是类似这种的。

ok

【在 D*T 的大作中提到】
: 想了一下，这个问题好像不是那么容易。楼主的code如果末尾有个空的List会出错。我
: 不太懂C++所以pdu的只是半懂，不过感觉我的想法和ta估计差不多。moridin的code很
: 神奇，我实在看不太懂。
: 的。
: import java.util.*;
: class ArrayPosition {
: ArrayList array;
: int index;
: ArrayPosition(ArrayList array) {

D*T

38

【在 n****e 的大作中提到】
: 多谢回复。
: ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
: 上面这段codes中，al依然只是一般的ArrayList。 不是DeepIterator所对应的list吧？
: DeepIterator所对应的list是：{1, {2, 3, {4, 5}, 6}, 7}。 应该是类似这种的。
:
: ok

n****e

39

specified element to the end of this list.
http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.ht

ArrayList al 应该需要注明ArrayList里面element的type吧。 比如：
ArrayList al = ...

【在 D*T 的大作中提到】
: 这个应该没错。这样al搞出来的是{1,2,3,{4,5},{}}。我用debugger跟进去了，应该是
: 没问题的。
:
: 吧？

D*T

40
ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));

ArrayList的确应该说明generic的类型为好，不过因为al里既有List又有Integer，实

n****e

41

【在 D*T 的大作中提到】
: ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
: 这句括号内部得到{1,2,3}，进入constructor返回的依然是{1,2,3}
: 这句括号内部是{4,5}，加到原来al上于是变成{1,2,3,{4,5}}
: 这句括号内部是{}，加到al上变成{1,2,3,{4,5},{}}
: ArrayList的确应该说明generic的类型为好，不过因为al里既有List又有Integer，实
: 际上就是ArrayList
b*****6

42

public class DeepIterator {
private Stack
x**********g

43

D********e

44

【在 s*****r 的大作中提到】
: 俺虽然没仔细看，扫一眼，知道你的面试基本完了
: code不clean，变量太多，用first和second这些是大忌，变量名没有含义。这题有一个
: 变量就OK了
:
: 0,

l******s

45
A validated C# Enumerator solution.

public class EmbeddedList : IEnumerable{
private bool isValue;
private T val;
private IList> ElementList = new List>();
public EmbeddedList() { isValue = false; }
public EmbeddedList(T t) { val = t; isValue = true; }
EmbeddedList newElement = new EmbeddedList(t);
}
private IEnumerable getList(){
if(isValue) yield return val;
foreach (var tList in ElementList)
foreach (var t in tList.getList()) yield return t;
}
public IEnumerator GetEnumerator(){
foreach (var t in getList()) yield return t;
}
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
}
class Program{
static void Main(string[] args){
EmbeddedList el = new EmbeddedList(1);
EmbeddedList el2 = new EmbeddedList(4);
EmbeddedList el3 = new EmbeddedList(6);
EmbeddedList e = new EmbeddedList();
EmbeddedList ee = new EmbeddedList();
//ee: [[[1,2,3,[4,5,[6,7],8],9],10],11]
foreach (int i in ee) Console.WriteLine(i);
//result: 1,2,3,4,5,6,7,8,9,10,11
}
}
j******d

46
class ListNode {
public:
int val;
ListNode *next; // point to the next of self list
ListNode *down; // point to the head of nested list
};
class DeepIterator {
public:

bool hasNext(){
return cur != NULL;
}

int next(){
int val = cur->val;
if (cur->down) {
stk.push(cur);
cur = cur->down;
} else {
while (cur->next == NULL && stk.empty() == false) {
cur = stk.top(); stk.pop();
}
cur = cur->next;
}

return val;
}

private:
ListNode *cur; // point to next node
stack stk; // save the nested path
};
j**********3

47

D********e

48

【在 s*****r 的大作中提到】
: 俺虽然没仔细看，扫一眼，知道你的面试基本完了
: code不clean，变量太多，用first和second这些是大忌，变量名没有含义。这题有一个
: 变量就OK了
:
: 0,

l******s

49
A validated C# Enumerator solution.

public class EmbeddedList : IEnumerable{
private bool isValue;
private T val;
private IList> ElementList = new List>();
public EmbeddedList() { isValue = false; }
public EmbeddedList(T t) { val = t; isValue = true; }
EmbeddedList newElement = new EmbeddedList(t);
}
private IEnumerable getList(){
if(isValue) yield return val;
foreach (var tList in ElementList)
foreach (var t in tList.getList()) yield return t;
}
public IEnumerator GetEnumerator(){
foreach (var t in getList()) yield return t;
}
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
}
class Program{
static void Main(string[] args){
EmbeddedList el = new EmbeddedList(1);
EmbeddedList el2 = new EmbeddedList(4);
EmbeddedList el3 = new EmbeddedList(6);
EmbeddedList e = new EmbeddedList();
EmbeddedList ee = new EmbeddedList();
//ee: [[[1,2,3,[4,5,[6,7],8],9],10],11]
foreach (int i in ee) Console.WriteLine(i);
//result: 1,2,3,4,5,6,7,8,9,10,11
}
}
j******d

50
class ListNode {
public:
int val;
ListNode *next; // point to the next of self list
ListNode *down; // point to the head of nested list
};
class DeepIterator {
public:

bool hasNext(){
return cur != NULL;
}

int next(){
int val = cur->val;
if (cur->down) {
stk.push(cur);
cur = cur->down;
} else {
while (cur->next == NULL && stk.empty() == false) {
cur = stk.top(); stk.pop();
}
cur = cur->next;
}

return val;
}

private:
ListNode *cur; // point to next node
stack stk; // save the nested path
};

Bloomberg phone interview 面经Leetcode: Symmetric Tree有没有好的iterative的解法？
j**********3

51

r*******g

52

construct ListNode就很困难，不得不引入dummy node，如果不引入dummy node很难
handle这种情况：
{0,{1,2},3,{xxx},{yyy},4}

xxx}右边的括号的时候，一般会把xxx从stack顶端移除，这样当你遇到{yyy}时候，是

【在 j******d 的大作中提到】
: class ListNode {
: public:
: int val;
: ListNode *next; // point to the next of self list
: ListNode *down; // point to the head of nested list
: };
: class DeepIterator {
: public:
:

t*********r

53
sw这哥们又来打嘴炮了

【在 D********e 的大作中提到】
: 听着怎么这么耳熟，有点周星驰食神评价杂碎面的台词, 呵呵
h*******o

54

@interface DeepIterator ()
@property (nonatomic, strong) NSArray *array;
@property (nonatomic, strong) DeepIterator *subInterator;
@property (nonatomic, assign) NSInteger index;
@end
@implementation DeepIterator
- (instancetype)initWithArray:(NSArray *)array
{
self = [super init];
if (self) {
self.array = array;
}
return self;
}
- (BOOL)hasNext
{
if (self.index >= self.array.count) {
return NO;
}
if ([[self.array objectAtIndex:self.index] isKindOfClass:[NSArray class]
]) {
if (self.subInterator == nil) {
DeepIterator *subInterator = [[DeepIterator alloc] initWithArray
:self.array[self.index]];
self.subInterator = subInterator;
}
if ([self.subInterator hasNext]) return YES;
else {
self.subInterator = nil;
self.index ++;
return [self hasNext];
}
}
return self.index < self.array.count;
}
- (id)next
{
if (![self hasNext]) {
return nil;
}
if (self.subInterator) {
return [self.subInterator next];
}
return self.array[self.index ++];
}
@end
x****y

55

public class DeepIterator implements Iterator{
private Stack itStack;

public DeepIterator(List
T******7

56
Mark
c*****m

57

import unittest
class DeepIterator():
def __init__(self, deep_list):
if deep_list == None:
self.iterator_stack = []
else:
self.iterator_stack = [[deep_list, 0]]
self.cur_value = None
def hasNext(self):
#the iterator stack is empty, False
if len(self.iterator_stack) == 0:
return False

#ensure hasNext() can be called many times before next()
if self.cur_value != None:
return True

#peek from iterator stack,
list_object, list_index = self.iterator_stack[-1]
#go through each element of the peek iterator
for i in range(list_index, len(list_object)):
#next time iterate next ele of peek iterator
self.iterator_stack[-1][1] = i + 1
obj = list_object[i]
if type(obj) is int:
#a int
self.cur_value = obj
return True
if type(obj) is list:
#a list
self.iterator_stack.append([obj, 0])
return self.hasNext()

#pop peek iterator
self.iterator_stack.pop()
return self.hasNext()
def next(self):
if self.hasNext():
ret_value = self.cur_value
self.cur_value = None
return ret_value
else:
return None
class TestDeepIterator(unittest.TestCase):
def testHasNextNext(self):
obj_list = [0, [1,2], 3, [], [4,[5,[6,7],8]],[]]
deepIterator = DeepIterator(obj_list)
deepIterator.hasNext()
deepIterator.hasNext()
while deepIterator.hasNext():
print deepIterator.next()
if __name__ == '__main__':
unittest.main()
 1 (共1页)