s**********e
发帖数: 326 | 1 昨天面的，面试官首先迟到了将近五分钟，上来面试官简单介绍了他自己，然后就直接
进入主题，也没有让我做自我介绍啥的，上来问我有没有用过java iterator pattern,
我给听成intepreter, 回答没用过，他不相信，又问了一遍，恍然大悟，赶紧说用过
用过，用过很多，然后他还说用java的人不可能没用过
然后问为什么用iterator, 有啥好处
答了之后接着问java里面有几种list, 答arraylist和linkedlist
又问实现这两种不同list的iterator有什么不同，到此为止都是对答如流，问他我答的
是不是他想要的答案，他说exactly
答完以后开始出题，先是写个data structure, 让我guess这是什么data structure,
class N {
private N l; // can be null
private N r; // can be null
private String data;
}
一紧张说成linkedlist, 赶紧改口说是tree,
然后就是描述问题，要求写一个Iterator, 每次调用next都是按in order顺序
返回BT里面某node的value，例子如下
root.data = “m”;
root.l.data=”g”;
root.r.data= “q”;
m
g q
a h p s
z
Iterates in this sequence: a, g, h, m, p, q, s, z
首先给了个naive的解法，先in order 遍历树，把得到的结果存到array里面，然后每
次调用next都从array里面取，同时也说了这个解不好，因为需要额外内存，应该有更
好的解我还没想出来
面试官表示同意，然后就开始给hint,首先问我in order traversal要用什么数据结构,
答stack, 然后提示说每次pop的时候就可以理解为取出一个元素来，恍然大悟，开始写
代码，写代码的时间总共20分钟，最后勉强写完，但是N多bug,惨不忍睹，估计要挂了
今天静下心来重新写了一遍，用我的这个Iterator run了一遍leetcode上面的in order
binary tree traversal, 结果都正确，求各位大仙批评指正
public class BinaryTreeNode {
public BinaryTreeNode left;
public BinaryTreeNode right;
public int val;
public BinaryTreeNode(int val){
this.val = val;
}
}
public class InorderIterable implements Iterable {
private BinaryTreeNode root;
public InorderIterable(BinaryTreeNode root) {
this.root = root;
}
public BinaryTreeIterator iterator() {
return new BinaryTreeIterator(root);
}
public ArrayList traversal() {
ArrayList list = new ArrayList();
BinaryTreeIterator iterator = iterator();
while (iterator.hasNext()) {
list.add(iterator.next());
}
return list;
}
private class BinaryTreeIterator implements Iterator {
BinaryTreeNode current = null;
ArrayDeque stack = new ArrayDeque();
public BinaryTreeIterator(BinaryTreeNode root) {
current = root;
}
public boolean hasNext() {
if (current == null && stack.isEmpty()) return false;
return true;
}
public Integer next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
if (current != null) {
while (current != null) {
stack.push(current);
current = current.left;
}
}
BinaryTreeNode result = stack.pop();
current = result;
if (current.right != null) {
current = current.right;
} else {
current = null;
}
return result.val;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
}
经验教训： 这道题其实就是binary tree inorder iterative traversal的变种， 感
觉自己还是基础知识不扎实，尽管in/pre/post order的iterative traversal都能基本
bug free写出来，但是稍微一变在面试有限的时间内完全做出来对我来说还是难度很大
，看来对这些基础的知识点还是没有理解透彻，需要加强 |
f*******b
发帖数: 520 | |
r*******e
发帖数: 7583 | 3 这是常见题吧，本版的面经出现过多次的
pattern,
构,
order
);
【在 s**********e 的大作中提到】
: 昨天面的，面试官首先迟到了将近五分钟，上来面试官简单介绍了他自己，然后就直接
: 进入主题，也没有让我做自我介绍啥的，上来问我有没有用过java iterator pattern,
: 我给听成intepreter, 回答没用过，他不相信，又问了一遍，恍然大悟，赶紧说用过
: 用过，用过很多，然后他还说用java的人不可能没用过
: 然后问为什么用iterator, 有啥好处
: 答了之后接着问java里面有几种list, 答arraylist和linkedlist
: 又问实现这两种不同list的iterator有什么不同，到此为止都是对答如流，问他我答的
: 是不是他想要的答案，他说exactly
: 答完以后开始出题，先是写个data structure, 让我guess这是什么data structure,
: class N {
|
u*****o
发帖数: 1224 | 4 弱问LZ，面试官说一定要用iterator了是吗？ in order traversal用threaded trees
不是更好吗，不用stack. 还是他就说要考察iterator的使用？ |
s**********e
发帖数: 326 | 5 是的，这道题考察的就是如何设计iterator, 悲催的是iterator on binary tree, 而
且要求iterate的顺序必须是inorder. 设计iterator on array, linkedlist之类的要
比这个简单一些。即使iterate on binary tree in level order也要简单一些，对我
来说。应该算是一道集design和算法为一体的一道题吧。我面试之前是没有见到过这道
题，不知道是不是常见题。
trees
【在 u*****o 的大作中提到】
: 弱问LZ，面试官说一定要用iterator了是吗？ in order traversal用threaded trees
: 不是更好吗，不用stack. 还是他就说要考察iterator的使用？
|
u*****o
发帖数: 1224 | 6 你已经好厉害了啊。。当场写iterator很难的啊。。。我看懂别人的答案都费牛劲，更
别说当场写了。。。加油！offer不远了!!
【在 s**********e 的大作中提到】
: 是的，这道题考察的就是如何设计iterator, 悲催的是iterator on binary tree, 而
: 且要求iterate的顺序必须是inorder. 设计iterator on array, linkedlist之类的要
: 比这个简单一些。即使iterate on binary tree in level order也要简单一些，对我
: 来说。应该算是一道集design和算法为一体的一道题吧。我面试之前是没有见到过这道
: 题，不知道是不是常见题。
:
: trees
|
s*******n
发帖数: 305 | 7 之前用array+list实现hashtable的时候写过一个相应的iterator, 这方面实在是基础
很差．．．， 最后是在hashtable 定义了一个方法， 把所有数据都放到一个
arraylist里面（类似于楼主的traversal())， 然后再由Iterator get 到， 怎么都感
觉象是个伪Iterator...
要是面试碰到楼主这个题， 肯定跪了， 楼主的解法很精妙, mark.
祝楼主好运， 拿到onsite |
r*******e
发帖数: 7583 | 8 本版讨论过好几次的
http://www.mitbbs.com/article_t1/JobHunting/32198853_0_3.html
http://www.mitbbs.com/article_t/JobHunting/32479009.html
【在 s**********e 的大作中提到】
: 是的，这道题考察的就是如何设计iterator, 悲催的是iterator on binary tree, 而
: 且要求iterate的顺序必须是inorder. 设计iterator on array, linkedlist之类的要
: 比这个简单一些。即使iterate on binary tree in level order也要简单一些，对我
: 来说。应该算是一道集design和算法为一体的一道题吧。我面试之前是没有见到过这道
: 题，不知道是不是常见题。
:
: trees
|
u*****o
发帖数: 1224 | 9 LZ，想问问你当时面试官要求可以加PARENT POINTER吗？ 有parent pointer的话也好
写一些。唯独这个case是一堆case中最麻烦的
【在 s**********e 的大作中提到】
: 是的，这道题考察的就是如何设计iterator, 悲催的是iterator on binary tree, 而
: 且要求iterate的顺序必须是inorder. 设计iterator on array, linkedlist之类的要
: 比这个简单一些。即使iterate on binary tree in level order也要简单一些，对我
: 来说。应该算是一道集design和算法为一体的一道题吧。我面试之前是没有见到过这道
: 题，不知道是不是常见题。
:
: trees
|
w******j
发帖数: 185 | 10 这个是常见题来的......
要准备啊...
顺便再看看preoder/postorder |
|
|
f********x
发帖数: 2086 | |
s**********e
发帖数: 326 | 12 BT的data structure是面试官定义好的，没有parent pointer。
【在 u*****o 的大作中提到】
: LZ，想问问你当时面试官要求可以加PARENT POINTER吗？ 有parent pointer的话也好
: 写一些。唯独这个case是一堆case中最麻烦的
|
s**********e
发帖数: 326 | 13 咳，带娃大妈骑驴找马没有那么多时间看面经啊
【在 w******j 的大作中提到】
: 这个是常见题来的......
: 要准备啊...
: 顺便再看看preoder/postorder
|
w******j
发帖数: 185 | 14 来个java的吧，带parent pointer和不带的，preorder和inorder的
import java.util.NoSuchElementException;
import java.util.Stack;
public class BST {
private Node root;
private static class Node {
int key;
Node left, right, parent;
Node(int key) {
this.key = key;
}
}
public BST(){
}
public BSTIterator inorderIterator() {
return new InorderIterator();
}
public BSTIterator preorderIterator() {
return new PreorderIterator();
}
public BSTIterator postorderIterator() {
return new PostorderIterator();
}
public BSTIterator preorderIterator1() {
return new Preorder();
}
public BSTIterator inorderIterator1() {
return new Inorder();
}
private class Inorder implements BSTIterator {
Stack stack = new Stack();
Inorder() {
Node leftmost = root;
while (leftmost != null){
stack.push(leftmost);
leftmost = leftmost.left;
}
}
public boolean hasNext() {
return !stack.isEmpty();
}
public int next() {
if (!hasNext())
throw new NoSuchElementException();
Node x = stack.pop();
int key = x.key;
if (x.right != null){
stack.push(x.right);
Node left = x.right.left;
while(left != null)
{
stack.push(left);
left = left.left;
}
}
return key;
}
}
private class Preorder implements BSTIterator {
Stack stack = new Stack();
Preorder() {
if (root != null)
stack.push(root);
}
public boolean hasNext() {
return !stack.isEmpty();
}
public int next() {
if (!hasNext())
throw new NoSuchElementException();
Node x = stack.pop();
int key = x.key;
if (x.right != null)
stack.push(x.right);
if (x.left != null)
stack.push(x.left);
return key;
}
}
private class InorderIterator implements BSTIterator {
private Node nextNode;
private InorderIterator() {
// The traversal starts with the smallest node
Node leftmost = root;
while(leftmost != null && leftmost.left != null)
leftmost = leftmost.left;
nextNode = leftmost;
}
public boolean hasNext() {
return (nextNode != null);
}
public int next() {
if (nextNode == null)
throw new NoSuchElementException();
// Store a copy of the key to be returned.
int key = nextNode.key;
if(nextNode.right != null)
{
nextNode = nextNode.right;
while(nextNode.left != null)
nextNode = nextNode.left;
}
else
{
Node child = nextNode;
Node parent = nextNode.parent;
while(parent != null && parent.right == child)
{
child = parent;
parent = parent.parent;
}
if (parent == null)
nextNode = null; // the traversal is complete
else
nextNode = parent;
}
return key;
}
}
/*** inner class for a preorder iterator ***/
private class PreorderIterator implements BSTIterator {
private Node nextNode;
private PreorderIterator() {
// The traversal starts with the root node.
nextNode = root;
}
public boolean hasNext() {
return (nextNode != null);
}
public int next() {
if (nextNode == null)
throw new NoSuchElementException();
// Store a copy of the key to be returned.
int key = nextNode.key;
// Advance nextNode.
if (nextNode.left != null)
nextNode = nextNode.left;
else if (nextNode.right != null)
nextNode = nextNode.right;
else {
// We've just visited a leaf node.
// Go back up the tree until we find a node
// with a right child that we haven't seen yet.
Node parent = nextNode.parent;
Node child = nextNode;
while (parent != null
&& (parent.right == child || parent.right == null)) {
child = parent;
parent = parent.parent;
}
if (parent == null)
nextNode = null; // the traversal is complete
else
nextNode = parent.right;
}
return key;
}
}
public static void main(String[] args) {
BST bst = new BST();
bst.root = new Node(15);
bst.root.left = new Node(12);
bst.root.left.parent = bst.root;
bst.root.left.left = new Node(6);
bst.root.left.left.parent = bst.root.left;
bst.root.left.right = new Node(14);
bst.root.left.right.parent = bst.root.left;
bst.root.left.left.right = new Node(10);
bst.root.left.left.right.parent = bst.root.left.left;
bst.root.left.left.right.left = new Node(9);
bst.root.left.left.right.left.parent = bst.root.left.left.right;
bst.root.right = new Node(18);
bst.root.right.parent = bst.root;
bst.root.right.right = new Node(25);
bst.root.right.right.parent = bst.root.right;
bst.root.right.right.left = new Node(21);
bst.root.right.right.left.parent = bst.root.right.right;
BSTIterator preorder = bst.preorderIterator();
BSTIterator preorder1 = bst.preorderIterator1();
while(preorder.hasNext())
System.out.print(preorder.next() + " ");
System.out.println();
while(preorder1.hasNext())
System.out.print(preorder1.next() + " ");
System.out.println();
BSTIterator inorder = bst.inorderIterator();
while(inorder.hasNext())
System.out.print(inorder.next() + " ");
System.out.println();
BSTIterator inorder1 = bst.inorderIterator1();
while(inorder1.hasNext())
System.out.print(inorder1.next() + " ");
System.out.println();
}
}
public interface BSTIterator {
boolean hasNext();
int next();
} |
c********p
发帖数: 1969 | 15 iteration有啥比recursion的好处？ |
u*****o
发帖数: 1224 | 16 你是说iterative solution比起recursion的好处吗？
主要是比较经济。recursion会存一个whole activation stack --> large memory
overhead, not efficient
但这个题是implement iterators, 和传统的iterative solution还不一样。iterator
的好处主要是flexible，container independent,还有就是support random access.可
以想象成每个node排成一行，可以move forward, backward for element access。
【在 c********p 的大作中提到】
: iteration有啥比recursion的好处？
|
c********p
发帖数: 1969 | 17 遍历不是要用个stack 么？
iterator
【在 u*****o 的大作中提到】
: 你是说iterative solution比起recursion的好处吗？
: 主要是比较经济。recursion会存一个whole activation stack --> large memory
: overhead, not efficient
: 但这个题是implement iterators, 和传统的iterative solution还不一样。iterator
: 的好处主要是flexible，container independent,还有就是support random access.可
: 以想象成每个node排成一行，可以move forward, backward for element access。
|
