Thursday, July 31, 2014

再回首,背影已远走。【本科EE硕士自学CS,毕业工作2周年面试回顾】


在美国做程序员2年了,来美国也马上3年了,前两个月跳槽了一次,想把作为new graduate和找第二份工作的面试准备过程和体会总结下来。因为大多数读者都在找第一份工作,所以学校期间的准备比较详细。 2011年8月末,来美国读Cornell只有两学期的水硕士,本科学EE时只上过一门C和一门c++,会一些Matlab。刚来时候听到所有人说CS最容易找工作,于是跟风的选了database,OS和一个用C#做游戏的project。学CS的动力不强,没有找到组织,自己蹲蹲图书馆,学的完全不入流,因为编程基础差作业做的很费力,过了2个月OS扛不住就drop了;database非常挣扎的学完了,编程能力稍微进步了一点。第一学期没认真找工作,唯一的面试是Epic,居然用本科学的c++过了电面,onsite被问各种GRE词汇,跪的彻彻底底。如果Epic给我offer我当时肯定开开心心的去了。

2012年1月,第二学期开始,一下听说好几个同学已经拿到了oracle的offer,瞬间有压力了。同时也找到了中国同学的组织,开始全身心投入的学编程准备面试,旁听了data structure,选了算法(上了2个月精力不够drop了)和web service的课。开始了每天早上8点30出门,晚上12点半回家,除了上课吃饭就在机房编程的生活。很仔细的用2周看了一本讲Data Structure的书 (Data Structures and Algorithms in Java),蛮推荐的,对于没有编程背景的人来说,深入了解数据结构的原理,实现和应用是准备程序员面试的第一步。看完这本书后就基本可以秒杀数据结构的作业。通过学校的网站申请了一些程序员岗位,几个电话面试都跪了。电面中发现会被问一些os和db的概念题,就把课本讲义翻出来看看。之后开始做CC150,题目基本是数据结构作业的延伸,一道道code出来。面试依然在fail,但每天都可以感觉到自己在进步,所以也没有太灰心。身边的更多中国同学拿到oracle,微软 offer,每个offer都击打着自己脆弱的心情。当时安慰自己想:我每天都在进步,拿到offer早的同学都不怎么学了,如果我能毕业时候正好拿到offer,我就学到最多的东西。学校career fair上投的amazon2个月后联系了我,经过2轮的电面我拿到了第二学期的第一个onsite。

2012年5月,毕业典礼,搬去和同学合住了2周。6月初,通过了amazon的onsite。 2014年1月,在amazon干了一年半之后开始痒了,开始刷LeetCode,自己做很多题都不会,一个月做掉了自己能想出来的90题左右,也网申了一些公司。找第二份工作真的比第一份工作容易太多了,只要去申很快就有面试。好朋友也想跳两个人就一起刷,下班去吃碗越南米粉就回到公司开始做题,他很厉害 (也是包子的面试官),教了我好多题目。两个人一起讨论LeetCode效果很好。他对新技术非常有热情,下班后都会去看相关视频,好的就推荐给我看,看这些视频对面试时候的system design题目很有帮助。有天我们一起看了一个讲AWS的基于Twitter Storm的Kinesis的视频,过了两天去Groupon onsite就被问到一模一样的东西。4月拿了Groupon和LinkedIn的offer,被Facebook拒了。好朋友去了Yelp,一起来了湾区。

Sunday, July 27, 2014

那些年我们一起遍历过的树 -- 遍历树,tree traversal



这篇博文想和大家讨论一下tree的traversal有哪些方法。当然我们都很熟悉DFS(InOrder, PreOrder, PostOrder)和BFS,这篇我们想谈一下一些其他方法以及DFS BFS的变种

[可以识辨每层的BFS]

[细节]
在题目中,我们时常需要做BFS并且要区分树的层与层,然后利用这个信息完成任务

[做法]
使用一个queue
初始化queue里插入root和一个分割符(普通node是pointer,因此分割符可选用特殊数字)
pop出root, 像通常BFS一样遍历root的child node,当dequeue分隔符时,在queue里后面插入分隔符
这样遍历完整棵树

[例题]
Populating Next Right Pointers in Each Node --[From Leetcode]
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
  • You may only use constant extra space.
For example,
Given the following binary tree,
       1
      /  \
     2    3
    / \    \
   4   5    7
After calling your function, the tree should look like:
       1 -> NULL
      /  \
     2 -> 3 -> NULL
    / \    \
   4-> 5 -> 7 -> NULL

[代码]
class Solution {
public:
   void connect(TreeLinkNode *root) {
       // BFS Queue
       vector<TreeLinkNode*> bfsq;
       TreeLinkNode*dummy = new TreeLinkNode(0);
       if (root)
       bfsq.push_back(root);
       bfsq.push_back(dummy);

       while (bfsq.size() > 1)
       {
           if (bfsq[1]!=dummy)
           bfsq.front()->next = bfsq[1];
           if (bfsq.front()==dummy)
           {
               bfsq.push_back(dummy);
           }
           else
           {
               if (bfsq.front()->left)
               bfsq.push_back(bfsq.front()->left);
               if (bfsq.front()->right)
               bfsq.push_back(bfsq.front()->right);
           }
           bfsq.erase(bfsq.begin());
       }
       delete(dummy);
   }
};

[不同方向的BFS]

[细节]
例如在第一层中从左向右遍历每个node,第二层就从右向左遍历,第三层向右...

[做法]
使用两个stackS1,S2
初始化把root插入到S1里
然后pop出root, 在遍历root的child node(s)时放入S2里
pop  S2的时候,把child nodes放入S1里
这样轮流使用两个stack,遍历完整棵树

[例题]
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
   3
  / \
 9  20
   /  \
  15   7
return its zigzag level order traversal as:
[
 [3],
 [20,9],
 [15,7]
]

[代码]
/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
   public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
       // Start typing your Java solution below
       // DO NOT write main() function
       ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
       if(root==null) return res;
       boolean order = true;
       ArrayList<TreeNode> toVisit = new ArrayList<TreeNode>();
       toVisit.add(root);
       while(!toVisit.isEmpty()){
           ArrayList<TreeNode> next = new ArrayList<TreeNode>();
           ArrayList<Integer> temp = new ArrayList<Integer>();
           for(TreeNode node:toVisit){
               temp.add(node.val);
           }
           res.add(temp);
           for(int i=toVisit.size()-1;i>=0;i--){
               TreeNode node = toVisit.get(i);
               if(order){
                   if(node.right!=null) next.add(node.right);
                   if(node.left!=null) next.add(node.left);
               }else{
                   if(node.left!=null) next.add(node.left);
                   if(node.right!=null) next.add(node.right);
               }
           }
           order = order?false:true;
           toVisit = new ArrayList<TreeNode>(next);
       }
       return res;
   }
}

[Make use of additional pointers in the Tree for traversal]

[细节]
很多题目在树里提供additional pointers(to parent or to sibling),应该首先考虑使用这些additional pointer做traversal

[例题]
Given a binary tree
  struct TreeLinkNode {
     TreeLinkNode *left;
     TreeLinkNode *right;
     TreeLinkNode *next;
   }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
[代码]
Basic idea is to make use of the next pointer of the current level, iterate through all the nodes on the current level, meanwhile, populate the next pointers of the children below
// the link of level(i) is the queue of level(i+1)
void connect(TreeLinkNode * n) {
   while (n) {
       TreeLinkNode * next = NULL; // the first node of next level
       TreeLinkNode * prev = NULL; // previous node on the same level
       for (; n; n=n->next) {
           if (!next) next = n->left?n->left:n->right;

           if (n->left) {
               if (prev) prev->next = n->left;
               prev = n->left;
           }
           if (n->right) {
               if (prev) prev->next = n->right;
               prev = n->right;
           }
       }
       n = next; // turn to next level
   }
}

[Bottom up traversal of a tree]


[细节]
我们目前看到的绝大多数题都是从一个树的根节点开始遍历,然后逐层到叶结点。很多时候我们也需要从叶结点开始遍历,到根节点。这样做的好处:
1)得到特殊的遍历顺序,可以用于特别的需要,比如按顺序读一个sorted linked list同时构建BST
2)从叶结点得到很多有用讯息,比如一个特定值是否在当前节点为根的子树存在,或者树的深度等等

[做法]
Recursively visit a tree as you do DFS
However, call the recursive function to left child and right child before you ‘visit’ the root

[例题]
Convert Sorted List to Binary Search Tree

[代码]
Bottom up traversal. The key is call recursion call before you do something about the current node, so that the recursion call chain will finally reach leaf node before you handle the subtree root nodes

public class Solution {
   static ListNode head;
   public TreeNode sortedListToBST(ListNode head) {
       if(head == null) return null;
       this.head = head;
        
       // get list length
       int len = 0;
       ListNode ln = head;
       while(ln != null){
           len++;
           ln = ln.next;
       }  
        
       return sortedListToBST(0, len - 1);
   }
    
   // build bottom-to-top
   public TreeNode sortedListToBST(int start, int end) {
       // if finished (root)
       if(start > end) return null;
        
       // get mid val
       int mid = (start + end) / 2;
        
       // build left sub tree
       TreeNode left = sortedListToBST(start, mid - 1);
       // build root node
       TreeNode root = new TreeNode(head.val);
       root.left = left;
       // move to next node to build right sub tree
       head = head.next;
       root.right = sortedListToBST(mid + 1, end);
        
       return root;
   }
}

[References]