电面写的这段代码，过了。
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 的大作中提到】 : LinkedIn 的题 : "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 发帖数: 678
9
多谢分享!
【在 p*u 的大作中提到】 : 电面写的这段代码，过了。 : class Collection : { : public: : T next() { : : if (_type == 0) : { : if (_index == 0) : {
这个可能犯规了……
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 = {
val item = content.head
content -= item
item
}
}
J****3 发帖数: 427
12
有大牛给个c++的吗
m*****n 发帖数: 204
13
攒了个段子请大牛点评一下:
// Not thread-safe
// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator
哦，这样啊。我不太熟悉java。 看java oracle document的解释是：Appends the
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 = ...
还有，这里的al，不可能是{1,2,3,{4,5},{}}吧，如果这样的话，arrayList里面的每
个element的type是不一样的。
按照你的写法，这里的ArrayList al应该是： {{1,2,3}, {4, 5}, {}}
电面写的这段代码，过了。
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 的大作中提到】 : LinkedIn 的题 : "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 发帖数: 678
30
多谢分享!
【在 p*u 的大作中提到】 : 电面写的这段代码，过了。 : class Collection : { : public: : T next() { : : if (_type == 0) : { : if (_index == 0) : {
这个可能犯规了……
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 = {
val item = content.head
content -= item
item
}
}
J****3 发帖数: 427
33
有大牛给个c++的吗
m*****n 发帖数: 204
34
攒了个段子请大牛点评一下:
// Not thread-safe
// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator
哦，这样啊。我不太熟悉java。 看java oracle document的解释是：Appends the
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 = ...
还有，这里的al，不可能是{1,2,3,{4,5},{}}吧，如果这样的话，arrayList里面的每
个element的type是不一样的。
按照你的写法，这里的ArrayList al应该是： {{1,2,3}, {4, 5}, {}}
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; }
public void Add(T t){
EmbeddedList newElement = new EmbeddedList(t);
ElementList.Add(newElement);
}
public void Add(EmbeddedList E) { ElementList.Add(E); }
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);
el.Add(2); el.Add(3);
EmbeddedList el2 = new EmbeddedList(4);
el2.Add(5); el.Add(el2);
EmbeddedList el3 = new EmbeddedList(6);
el3.Add(7); el2.Add(el3); el2.Add(8); el.Add(9);
EmbeddedList e = new EmbeddedList();
e.Add(el); e.Add(10);
EmbeddedList ee = new EmbeddedList();
ee.Add(e); ee.Add(11);
//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
Console.ReadKey();
}
}
j******d 发帖数: 2
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:
DeepIterator(ListNode *head) : cur(head) {}
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
};
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; }
public void Add(T t){
EmbeddedList newElement = new EmbeddedList(t);
ElementList.Add(newElement);
}
public void Add(EmbeddedList E) { ElementList.Add(E); }
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);
el.Add(2); el.Add(3);
EmbeddedList el2 = new EmbeddedList(4);
el2.Add(5); el.Add(el2);
EmbeddedList el3 = new EmbeddedList(6);
el3.Add(7); el2.Add(el3); el2.Add(8); el.Add(9);
EmbeddedList e = new EmbeddedList();
e.Add(el); e.Add(10);
EmbeddedList ee = new EmbeddedList();
ee.Add(e); ee.Add(11);
//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
Console.ReadKey();
}
}
j******d 发帖数: 2
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:
DeepIterator(ListNode *head) : cur(head) {}
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******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: : DeepIterator(ListNode *head) : cur(head) {} :
测试了，３重ｌｉｓｔ嵌套。应该是无论多少都可以。
public class DeepIterator implements Iterator{
private Stack itStack;
public DeepIterator(List
T******7 发帖数: 1419
56
Mark
c*****m 发帖数: 271
57
试着写一个python的
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()
