由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 求指点一道G家Iterator的题目
相关主题
讨论一个题目G电面面经:BT的iterator inorder traversal
[google面试]iterator访问小弟求问LinkedIn那道Deep Iterator的题
Linkedin这道题用非递归该怎么写啊?发个g的电面
刷了半天题Bloomberg phone interview 面经
问一个Linkedin经典题贴一个C++ nested Iterator的code,求讨论和指正。
binary tree的in-order iterator怎么写?L家面试题 iterator for nested integer求讨论
问一道题问一道facebook的面试题
bst中序遍历c++ class iteratorPure Storage面经
相关话题的讨论汇总
话题: nestedinteger话题: iterator话题: node话题: integer话题: return
1 (共1页)
W**********2
发帖数: 30
1
题目就是 Nested Iterator
Program an iterator for a List which may include nodes or List
{0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
求java的做法。
感觉这道题关键是怎么设计这个既保存单个item,又保存list的结构, 这个结构设计
好了,用java iterator应该就不难了。不知道对不对, 求指点。 先谢谢啦 :)
j******o
发帖数: 4219
2
这题拿递归就能做吧
f*y
发帖数: 876
3
用两个Queue,
Queue // the NestList of the next element
Queue // the index of the next element
d******o
发帖数: 13
4
Stack + 递归
之前面Twitter也被问到过,但是迷迷糊糊没想清楚。。。
需要一个 helper class: Pair(NestedList list, int position) 定义当前所在的位
置.
Iterator 需要实现 hasNext() 和 next()
hasNext 检查还有没有值,检查栈顶的Pair,如果当前所指的是Node,直接输出 true
即可。如果是List,就new 一个 Pair(curList, 0), push到stack上。然后递归的
call hasNext 进行检查。如果 栈顶的position 已经超出 当前list 的范围,说明已
经遍历完当前list, pop 掉当前元素,然后对新的栈顶元素(如果有的话)的
position + 1, 之后同样 递归的 call hasNext 继续进行检查。
至于next,上面的 hasNext 保证了 如果还有值,会让栈顶的Pair指到一个Node,所以
直接输出即可,并将 position + 1.
d******o
发帖数: 13
5
Stack + 递归
stack中存储的是iterate 时,当前所处的 List 及 position,可能指向的是Node,可
能是List,可能当前的position == list.size() 也可能 stack 已为空。
分别对以上情况做处理即可。
f*******r
发帖数: 976
6
Mark

【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item,又保存list的结构, 这个结构设计
: 好了,用java iterator应该就不难了。不知道对不对, 求指点。 先谢谢啦 :)

S********t
发帖数: 3431
7
list个毛线,直接说nary tree嘛。
tree怎么做iterator不是基础知识吗?

【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item,又保存list的结构, 这个结构设计
: 好了,用java iterator应该就不难了。不知道对不对, 求指点。 先谢谢啦 :)

g*****i
发帖数: 91
g*****i
发帖数: 91
f*********s
发帖数: 1881
10
mark

【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item,又保存list的结构, 这个结构设计
: 好了,用java iterator应该就不难了。不知道对不对, 求指点。 先谢谢啦 :)

相关主题
binary tree的in-order iterator怎么写?G电面面经:BT的iterator inorder traversal
问一道题小弟求问LinkedIn那道Deep Iterator的题
bst中序遍历c++ class iterator发个g的电面
W**********2
发帖数: 30
11
题目就是 Nested Iterator
Program an iterator for a List which may include nodes or List
{0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
求java的做法。
感觉这道题关键是怎么设计这个既保存单个item,又保存list的结构, 这个结构设计
好了,用java iterator应该就不难了。不知道对不对, 求指点。 先谢谢啦 :)
j******o
发帖数: 4219
12
这题拿递归就能做吧
f*y
发帖数: 876
13
用两个Queue,
Queue // the NestList of the next element
Queue // the index of the next element
d******o
发帖数: 13
14
Stack + 递归
之前面Twitter也被问到过,但是迷迷糊糊没想清楚。。。
需要一个 helper class: Pair(NestedList list, int position) 定义当前所在的位
置.
Iterator 需要实现 hasNext() 和 next()
hasNext 检查还有没有值,检查栈顶的Pair,如果当前所指的是Node,直接输出 true
即可。如果是List,就new 一个 Pair(curList, 0), push到stack上。然后递归的
call hasNext 进行检查。如果 栈顶的position 已经超出 当前list 的范围,说明已
经遍历完当前list, pop 掉当前元素,然后对新的栈顶元素(如果有的话)的
position + 1, 之后同样 递归的 call hasNext 继续进行检查。
至于next,上面的 hasNext 保证了 如果还有值,会让栈顶的Pair指到一个Node,所以
直接输出即可,并将 position + 1.
d******o
发帖数: 13
15
Stack + 递归
stack中存储的是iterate 时,当前所处的 List 及 position,可能指向的是Node,可
能是List,可能当前的position == list.size() 也可能 stack 已为空。
分别对以上情况做处理即可。
f*******r
发帖数: 976
16
Mark

【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item,又保存list的结构, 这个结构设计
: 好了,用java iterator应该就不难了。不知道对不对, 求指点。 先谢谢啦 :)

S********t
发帖数: 3431
17
list个毛线,直接说nary tree嘛。
tree怎么做iterator不是基础知识吗?

【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item,又保存list的结构, 这个结构设计
: 好了,用java iterator应该就不难了。不知道对不对, 求指点。 先谢谢啦 :)

g*****i
发帖数: 91
g*****i
发帖数: 91
f*********s
发帖数: 1881
20
mark

【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item,又保存list的结构, 这个结构设计
: 好了,用java iterator应该就不难了。不知道对不对, 求指点。 先谢谢啦 :)

相关主题
Bloomberg phone interview 面经问一道facebook的面试题
贴一个C++ nested Iterator的code,求讨论和指正。Pure Storage面经
L家面试题 iterator for nested integer求讨论求教一道经典面题的解法
y*******5
发帖数: 887
21
用composition pattern:
1:---
package NestedIterator;
public interface NestedNodeList extends Iterable {
}
2:---
package NestedIterator;
import java.util.Iterator;
public class Node implements NestedNodeList {
private E val;
public Node(E val) {
this.val = val;
}
@Override
public Iterator iterator() {
return new NodeIterator();
}
private class NodeIterator implements Iterator {
private boolean iterated = false;
@Override
public boolean hasNext() {
return !iterated;
}
@Override
public E next() {
if (hasNext()) {
iterated = true;
return val;
}
return null;
}
}
}
3.---
package NestedIterator;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class NodeList implements NestedNodeList {
private List> nodeList;
public NodeList() {
this.nodeList = new ArrayList<>();
}
@Override
public Iterator iterator() {
return new NodeListIterator();
}
public void add(NestedNodeList nodes) {
nodeList.add(nodes);
}
private class NodeListIterator implements Iterator {
private int idx = 0;
Iterator iter;
@Override
public boolean hasNext() {
if (idx >= nodeList.size())
return false;
if (iter == null)
iter = nodeList.get(idx).iterator();
if (iter.hasNext())
return true;
idx += 1;
if (idx >= nodeList.size())
return false;
iter = nodeList.get(idx).iterator();
return iter.hasNext();
}
@Override
public E next() {
if (hasNext()) {
return iter.next();
}
return null;
}
}
public static final void main(String[] args) {
NodeList list0 = new NodeList<>();
NodeList list1 = new NodeList<>();
NodeList list2 = new NodeList<>();
NodeList list3 = new NodeList<>();
Node node0 = new Node<>(0);
Node node1 = new Node<>(1);
Node node2 = new Node<>(2);
Node node3 = new Node<>(3);
Node node4 = new Node<>(4);
Node node5 = new Node<>(5);
Node node6 = new Node<>(6);
list3.add(node5);
list3.add(node6);
list2.add(node4);
list2.add(list3);
list2.add(node4);
list2.add(list3);
list1.add(node1);
list1.add(node2);
list0.add(node0);
list0.add(list1);
list0.add(node3);
list0.add(list2);
for (int i : list0) {
System.out.println(i);
}
}
}
定义一个interface, 把node 和 list of node 定义在同一个interface下
这个interface里面只有一个method 就是 iterator
Interface NestedNodeList
然后,node的类型的iterator的实现是:
iterator里面有个bool变量
如果这个node已经取过了,就是true,没有取过就是false
node iterator 的 hasnext()方法就是用这个bool来判断
next()的方法就返回 node的值并把这个bool的状态更新
然后NodeList 用一个private 的list 放入 NestedNodeList 为interface的类型
所以既可以放入node, 也可以放入里一个nested Nodelist本身
然后NodeList的iterator就是 深度优先 dfs 的遍历这个list
recursive的call list里面的每个iterator

【在 W**********2 的大作中提到】
: 题目就是 Nested Iterator
: Program an iterator for a List which may include nodes or List
: {0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
: 求java的做法。
: 感觉这道题关键是怎么设计这个既保存单个item,又保存list的结构, 这个结构设计
: 好了,用java iterator应该就不难了。不知道对不对, 求指点。 先谢谢啦 :)

m********r
发帖数: 29
22
leetcode付费题 2d vector
r********g
发帖数: 219
23
大体这样(java):
public class SuperIterator {
Stack iterators = new Stack<>();
public SuperIterator(Iterator topIterator) {
iterators.push(topIterator);
}

public boolean hasNext() {
if (iterators.isEmpty()) {
return false;
}

Iterator topIterator = iterators.pop();
while (!topIterator.hasNext()) {
if (!iterators.isEmpty()) {
topIterator = iterators.pop();
} else {
return false;
}
}
iterators.push(topIterator);
return true;
]
// 以此类推 写出 next()
}
a******f
发帖数: 9
24
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
class NestedInteger {
public:
NestedInteger(int i) : integer(i), isInt(true) {}
NestedInteger(vector l) : nestedList(l), isInt(false) {}

// Return true if this NestedInteger holds a single integer, rather than
a nested list.
bool isInteger() {
return isInt;
}

// Return the single integer that this NestedInteger holds, if it holds
a single integer
// The result is undefined if this NestedInteger holds a nested list
int getInteger() {
return integer;
}
// Return the nested list that this NestedInteger holds, if it holds a
nested list
// The result is undefined if this NestedInteger holds a single integer
vector &getList() {
return nestedList;
}
bool isInt;
int integer;
vector nestedList;
};
class NestedIntegerIterator {
public:
NestedIntegerIterator(vector &nestedList) {
s.push({nestedList.begin(), nestedList.end()});
}

int next() {
return (s.top()[0]++)->getInteger();
}

bool hasNext() {
while (!s.empty()) {
while (!s.empty() && s.top()[0] == s.top()[1]) {
s.pop();
if (!s.empty())
++s.top()[0];
}

if (!s.empty() && s.top()[0]->isInteger())
return true;

while (!s.empty() && !s.top()[0]->isInteger())
s.push({s.top()[0]->getList().begin(), s.top()[0]->getList()
.end()});
}
return false;
}
private:
stack::iterator>> s;
};
int main()
{
{
vector l = {NestedInteger(0), NestedInteger({
NestedInteger(1), NestedInteger(2)}), NestedInteger(3), NestedInteger({
NestedInteger(4), NestedInteger({NestedInteger(5), NestedInteger(6)})})};
NestedIntegerIterator ni(l);
while (ni.hasNext())
cout << ni.next() << endl;
}
return 0;
}
1 (共1页)
相关主题
Pure Storage面经问一个Linkedin经典题
求教一道经典面题的解法binary tree的in-order iterator怎么写?
问个题问一道题
iterator 实现 如何 peek(),pop()?bst中序遍历c++ class iterator
讨论一个题目G电面面经:BT的iterator inorder traversal
[google面试]iterator访问小弟求问LinkedIn那道Deep Iterator的题
Linkedin这道题用非递归该怎么写啊?发个g的电面
刷了半天题Bloomberg phone interview 面经
相关话题的讨论汇总
话题: nestedinteger话题: iterator话题: node话题: integer话题: return