电面写的这段代码,过了。
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}, {}}
ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
这句括号内部得到{1,2,3},进入constructor返回的依然是{1,2,3}
al.add(new ArrayList(Arrays.asList(new Integer[]{4, 5})));
这句括号内部是{4,5},加到原来al上于是变成{1,2,3,{4,5}}
al.add(new ArrayList());
这句括号内部是{},加到al上变成{1,2,3,{4,5},{}}
最主要区别是第一句是constructor,不是add。
ArrayList的确应该说明generic的类型为好,不过因为al里既有List又有Integer,实
际上就是ArrayList,注明不注明都没啥区别了。
【在 n****e 的大作中提到】 : 哦,这样啊。我不太熟悉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 DeepIterator {
private Stack stack;
public DeepIterator(List list) {
stack = new Stack();
stack.push(list);
advanceToNext();
}
public boolean hasNext() {
return !stack.isEmpty();
}
public int next() {
if (!hasNext())
throw new RuntimeException("no next");
int result = (Integer) stack.pop();
advanceToNext();
return result;
}
@SuppressWarnings("unchecked")
private void advanceToNext() {
while (!stack.isEmpty() && !(stack.peek() instanceof Integer)) {
Object obj = stack.pop();
if (obj == null)
continue;
List cur = (List) obj;
for (int i = cur.size() - 1; i >= 0; i--)
stack.push(cur.get(i));
}
}
}
l*********h 发帖数: 15
22
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
底下是程序
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();
finalLists.add(0);
ArrayList firstLevelList = new ArrayList();
firstLevelList.add(1);
firstLevelList.add(2);
finalLists.add(firstLevelList);
finalLists.add(3);
firstLevelList = new ArrayList();
firstLevelList.add(4);
ArrayList secondLevelList = new ArrayList();
secondLevelList.add(5);
secondLevelList.add(6);
firstLevelList.add(secondLevelList);
finalLists.add(firstLevelList);
电面写的这段代码,过了。
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 myIterator;
private final Class eleType;
private final Iterator empty = new ArrayList().iterator();
private void checkHead() {
while (!head.hasNext()) { // Handles Empty List
if (myIterator == null || !myIterator.hasNext()) {
break;
}
Object object = myIterator.next();
if (object instanceof List) {
head = new DeepIterator((List) object, eleType); //
} else {
// Better: use Guava style helper: new Iterators.sigletonIterator(
object);
List list = new ArrayList(1);
list.add((T) object); // Talk about validation
head = list.iterator();
}
}
}
@Override
public boolean hasNext() {
checkHead();
return head.hasNext();
}
@Override
public T next() {
checkHead();
return eleType.cast(head.next()); // Why this is better than returning
unchecked.
}
@Override
public void remove() {
throw new UnsupportedOperationException(); // Ask if required. Talk
about ideas.
}
}
哦,这样啊。我不太熟悉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}, {}}
ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
这句括号内部得到{1,2,3},进入constructor返回的依然是{1,2,3}
al.add(new ArrayList(Arrays.asList(new Integer[]{4, 5})));
这句括号内部是{4,5},加到原来al上于是变成{1,2,3,{4,5}}
al.add(new ArrayList());
这句括号内部是{},加到al上变成{1,2,3,{4,5},{}}
最主要区别是第一句是constructor,不是add。
ArrayList的确应该说明generic的类型为好,不过因为al里既有List又有Integer,实
际上就是ArrayList,注明不注明都没啥区别了。
【在 n****e 的大作中提到】 : 哦,这样啊。我不太熟悉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 DeepIterator {
private Stack stack;
public DeepIterator(List list) {
stack = new Stack();
stack.push(list);
advanceToNext();
}
public boolean hasNext() {
return !stack.isEmpty();
}
public int next() {
if (!hasNext())
throw new RuntimeException("no next");
int result = (Integer) stack.pop();
advanceToNext();
return result;
}
@SuppressWarnings("unchecked")
private void advanceToNext() {
while (!stack.isEmpty() && !(stack.peek() instanceof Integer)) {
Object obj = stack.pop();
if (obj == null)
continue;
List cur = (List) obj;
for (int i = cur.size() - 1; i >= 0; i--)
stack.push(cur.get(i));
}
}
}
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) {} :
试着写一个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()