Redian新闻
>
小弟求问LinkedIn那道Deep Iterator的题
avatar
小弟求问LinkedIn那道Deep Iterator的题# JobHunting - 待字闺中
l*h
1
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);

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() + " --> ");
}
}
}
程序能出来,有个疑问,因为Integer 和 ArrayList 类型不同 所以只能用Object 代
替,ArrayList也没控制类型,Eclipse里面一片黄,真正面过这个题的是不是像
Composite Pattern 似的 有一个 Item 的 interface, singleItem 和 listItem
实现这个interface, 这样就解决类型的问题了?
avatar
s*r
2
俺虽然没仔细看,扫一眼,知道你的面试基本完了
code不clean,变量太多,用first和second这些是大忌,变量名没有含义。这题有一个
变量就OK了

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
: 底下是程序

avatar
l*n
3
arraylist没有控制类型是什么意思?java是可以check list类型的,到了最后的
integer层的时候,instanceof (ArrayList)就是false了。
if (x instanceof Collection){
}

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
: 底下是程序

avatar
l*h
4

谢了,学习了,自己用Java用的还是不熟

【在 l*n 的大作中提到】
: arraylist没有控制类型是什么意思?java是可以check list类型的,到了最后的
: integer层的时候,instanceof (ArrayList)就是false了。
: if (x instanceof Collection){
: }
:
: 0,

avatar
l*h
5

嗯,好的,学习了,着急写一个例子测试就搞的有点乱。。。

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

avatar
P*r
6
这道题目好像有好几个版本,你确认可以直接拿ArrayList的Iterator吗?
好像见过一个Generic的 linked list,每个Node 有 down 和 next.
不过基本上用到Stack是必须的。

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
: 底下是程序

avatar
n*e
7
L家要求这么高啊?正在准备L家on site。前辈有什么建议。
前辈能否贴个此题的标答,让我们好知道L家的标准。

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

avatar
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 的大作中提到】
: 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
: 底下是程序

avatar
n*e
9
多谢分享!

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

avatar
J*3
10
有大牛给个c++的吗
avatar
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 = {
val item = content.head
content -= item
item
}
}
avatar
J*3
12
有大牛给个c++的吗
avatar
m*n
13
攒了个段子请大牛点评一下:
// 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 Iterator head = empty;

DeepIterator(List list, Class eleType) {
this.myIterator = list.iterator();
this.eleType = eleType;
}

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.
}
}

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

avatar
n*e
14
仔细看了一下code,
有几个问题:
1, Collection只能遍历一边,第二次遍历就出错了。
2, 这里没有iterator的 implementation。 如何用c++实现iterator

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

avatar
D*T
15
想了一下,这个问题好像不是那么容易。楼主的code如果末尾有个空的List会出错。我
不太懂C++所以pdu的只是半懂,不过感觉我的想法和ta估计差不多。moridin的code很
神奇,我实在看不太懂。
下面是我的code,搞ArrayList还成,搞LinkedList可能就惨了。另外remove好像是ok
的。
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();
stack.add(new ArrayPosition(al));
}
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}));
al.add(new ArrayList(Arrays.asList(new Integer[]{4, 5})));
al.add(new ArrayList());
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);
}
}
}
avatar
n*e
16
多谢回复。
ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
al.add(new ArrayList(Arrays.asList(new Integer[]{4, 5})));
al.add(new ArrayList());
上面这段codes中,al依然只是一般的ArrayList。 不是DeepIterator所对应的list吧?
DeepIterator所对应的list是:{1, {2, 3, {4, 5}, 6}, 7}。 应该是类似这种的。

ok

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

avatar
D*T
17
这个应该没错。这样al搞出来的是{1,2,3,{4,5},{}}。我用debugger跟进去了,应该是
没问题的。

吧?

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

avatar
n*e
18
哦,这样啊。我不太熟悉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}, {}}

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

avatar
D*T
19
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}, {}}

avatar
n*e
20
恩,弄明白了。 多谢你的回复。你的code应该是对的。

【在 D*T 的大作中提到】
: 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,注明不注明都没啥区别了。

avatar
b*6
21
我也被问过这个问题,当时没写好,现在再写一个:
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));
}
}
}
avatar
l*h
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);

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() + " --> ");
}
}
}
程序能出来,有个疑问,因为Integer 和 ArrayList 类型不同 所以只能用Object 代
替,ArrayList也没控制类型,Eclipse里面一片黄,真正面过这个题的是不是像
Composite Pattern 似的 有一个 Item 的 interface, singleItem 和 listItem
实现这个interface, 这样就解决类型的问题了?
avatar
s*r
23
俺虽然没仔细看,扫一眼,知道你的面试基本完了
code不clean,变量太多,用first和second这些是大忌,变量名没有含义。这题有一个
变量就OK了

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
: 底下是程序

avatar
l*n
24
arraylist没有控制类型是什么意思?java是可以check list类型的,到了最后的
integer层的时候,instanceof (ArrayList)就是false了。
if (x instanceof Collection){
}

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
: 底下是程序

avatar
l*h
25

谢了,学习了,自己用Java用的还是不熟

【在 l*n 的大作中提到】
: arraylist没有控制类型是什么意思?java是可以check list类型的,到了最后的
: integer层的时候,instanceof (ArrayList)就是false了。
: if (x instanceof Collection){
: }
:
: 0,

avatar
l*h
26

嗯,好的,学习了,着急写一个例子测试就搞的有点乱。。。

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

avatar
P*r
27
这道题目好像有好几个版本,你确认可以直接拿ArrayList的Iterator吗?
好像见过一个Generic的 linked list,每个Node 有 down 和 next.
不过基本上用到Stack是必须的。

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
: 底下是程序

avatar
n*e
28
L家要求这么高啊?正在准备L家on site。前辈有什么建议。
前辈能否贴个此题的标答,让我们好知道L家的标准。

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

avatar
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 的大作中提到】
: 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
: 底下是程序

avatar
n*e
30
多谢分享!

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

avatar
J*3
31
有大牛给个c++的吗
avatar
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 = {
val item = content.head
content -= item
item
}
}
avatar
J*3
33
有大牛给个c++的吗
avatar
m*n
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 Iterator head = empty;

DeepIterator(List list, Class eleType) {
this.myIterator = list.iterator();
this.eleType = eleType;
}

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.
}
}

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

avatar
n*e
35
仔细看了一下code,
有几个问题:
1, Collection只能遍历一边,第二次遍历就出错了。
2, 这里没有iterator的 implementation。 如何用c++实现iterator

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

avatar
D*T
36
想了一下,这个问题好像不是那么容易。楼主的code如果末尾有个空的List会出错。我
不太懂C++所以pdu的只是半懂,不过感觉我的想法和ta估计差不多。moridin的code很
神奇,我实在看不太懂。
下面是我的code,搞ArrayList还成,搞LinkedList可能就惨了。另外remove好像是ok
的。
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();
stack.add(new ArrayPosition(al));
}
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}));
al.add(new ArrayList(Arrays.asList(new Integer[]{4, 5})));
al.add(new ArrayList());
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);
}
}
}
avatar
n*e
37
多谢回复。
ArrayList al = new ArrayList(Arrays.asList(new Integer[]{1,2,3}));
al.add(new ArrayList(Arrays.asList(new Integer[]{4, 5})));
al.add(new ArrayList());
上面这段codes中,al依然只是一般的ArrayList。 不是DeepIterator所对应的list吧?
DeepIterator所对应的list是:{1, {2, 3, {4, 5}, 6}, 7}。 应该是类似这种的。

ok

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

avatar
D*T
38
这个应该没错。这样al搞出来的是{1,2,3,{4,5},{}}。我用debugger跟进去了,应该是
没问题的。

吧?

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

avatar
n*e
39
哦,这样啊。我不太熟悉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}, {}}

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

avatar
D*T
40
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}, {}}

avatar
n*e
41
恩,弄明白了。 多谢你的回复。你的code应该是对的。

【在 D*T 的大作中提到】
: 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,注明不注明都没啥区别了。

avatar
b*6
42
我也被问过这个问题,当时没写好,现在再写一个:
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));
}
}
}
avatar
x*g
43
这个有没有大牛贴个c++版本的啊,
多谢多谢,大概意思理解了,只是c++里怎么表示那个object的iterator?
avatar
D*e
44
听着怎么这么耳熟,有点周星驰食神评价杂碎面的台词, 呵呵

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

avatar
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; }
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();
}
}
avatar
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:
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
};
avatar
j*3
47
先mark了再看
avatar
D*e
48
听着怎么这么耳熟,有点周星驰食神评价杂碎面的台词, 呵呵

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

avatar
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; }
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();
}
}
avatar
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:
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
};
avatar
j*3
51
先mark了再看
avatar
r*g
52
今晚写了下,c++把人都要写死了
construct ListNode就很困难,不得不引入dummy node,如果不引入dummy node很难
handle这种情况:
{0,{1,2},3,{xxx},{yyy},4}
这种情况下3->next=4, 那么3->down是什么呢,到底是xxx还是yyy,如果3->down=xxx,
然后xxx->next=yyy?这样的话从逻辑上讲是对的,但是实际上很难维护,因为你遇到{
xxx}右边的括号的时候,一般会把xxx从stack顶端移除,这样当你遇到{yyy}时候,是
很难知道是从3指向{yyy}还是从{xxx}指向{yyy}。
总之就是c++写死人。

【在 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) {}
:

avatar
t*r
53
sw这哥们又来打嘴炮了

【在 D********e 的大作中提到】
: 听着怎么这么耳熟,有点周星驰食神评价杂碎面的台词, 呵呵
avatar
h*o
54
这题规定必须用stack做么?保存一个sub deepiterator递归也行吧。
小众的ObjC代码:
@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
avatar
x*y
55
测试了,3重list嵌套。应该是无论多少都可以。
public class DeepIterator implements Iterator{
private Stack itStack;

public DeepIterator(List list){
if(list ==null || list.isEmpty()){
itStack=null;
return;
}
itStack=new Stack();
itStack.push(list.iterator());
}

@Override
public boolean hasNext() {
if(itStack ==null || itStack.isEmpty()){
  return false;
}
Iterator it=itStack.peek();
while(!it.hasNext()){
itStack.pop();
if(itStack.isEmpty()){
return false;
}
it=itStack.peek();
}
return true;

}
@Override
public Object next() {
Iterator it= itStack.peek();
Object curObj=it.next();

while(curObj instanceof List){
it= ((List)curObj).iterator();
itStack.push(it);
curObj=it.next();
}

return curObj;
}
}
avatar
T*7
56
Mark
avatar
c*m
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()

#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()
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。