G电面面经：BT的iterator inorder traversal

发信人: sophappylife (sophappylife), 信区: JobHunting
标  题: G电面面经：BT的iterator inorder traversal
发信站: BBS 未名空间站 (Thu Aug  8 15:59:53 2013, 美东)

昨天面的，面试官首先迟到了将近五分钟，上来面试官简单介绍了他自己，然后就直接
进入主题，也没有让我做自我介绍啥的，上来问我有没有用过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<String>, 每次调用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<Integer> {
    private BinaryTreeNode root;

    public InorderIterable(BinaryTreeNode root) {
        this.root = root;
    }

    public BinaryTreeIterator iterator() {
        return new BinaryTreeIterator(root);
    }

    public ArrayList<Integer> traversal() {
        ArrayList<Integer> list = new ArrayList<Integer>();
        BinaryTreeIterator iterator = iterator();
        while (iterator.hasNext()) {
            list.add(iterator.next());
        }
        return list;
    }

    private class BinaryTreeIterator implements Iterator<Integer> {
        BinaryTreeNode current = null;
        ArrayDeque<BinaryTreeNode> stack = new ArrayDeque<BinaryTreeNode>();

        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写出来，但是稍微一变在面试有限的时间内完全做出来对我来说还是难度很大
，看来对这些基础的知识点还是没有理解透彻，需要加强
--

※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 209.]

http://www.mitbbs.com/article_t/JobHunting/32503241.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大