Snapchat Interview Misc

http://www.1point3acres.com/bbs/thread-198209-1-1.html
题目是给一些tasks，每个tasks有一些dependencies，要求输出task 的执行顺序，每个task只执行一次，并且所有dependencies执行完了之后再执行当前任务. 1point3acres.com/bbs
就是很简单的拓扑排序，然而我并没有写熟练. 1point 3acres 璁哄潧
而且小哥不会写C++，而我只会写C++，先把他给的java interface转成C++的struct……我本来对java就不怎么熟，这中间解释了半天

边写边涂改。他面试用的东西是一个online judge一样的，可以跑程序，然后可以写输入。他让我test的时候，我以为要从stdin读入。我想 这尼玛还得建好图。在那犹豫了一会儿，他说 你可以hard coding。我才接着写test cases，然后测试了一下。
想出的几个test cases都跑过了，结果正确。

最后他问了个问题说如果tasks太多无法fit in memory怎么办，我就思密达了

每个task里面有两个Method 一个是execute 另一个是getDependencies() 就是返回它所依赖的task的List
http://www.1point3acres.com/bbs/thread-186745-1-1.html

给一个int的matrix，里面只有0和1，matrix[i][j]表示i和j是朋友，如果是0表示两人不是朋友， 是朋友的分成一个组，问能分几组。比如1和2是朋友，3和他们都不是朋友，那么就是2组， return 2就可以。自己写test自己测

对 我用的union find 当时没多想还有什么别的解法 面完2天给的消息

Number of island 1 是必须要连在一起在算一组 但是这个比如1和2，1和5是朋友 这样他们是一组的 我觉得如果你用BFS的话 应该就不行 因为1和2连着 但是中间是0就走不到5 但是如果用union find的话 就是一样的方法了 没什么差别

这题BFS，DFS都可以做，和number of Island 1的区别在于，比如对于friend i, 不是对上下左右四个点做进一步的搜索，而是对i的所在的那一行进行搜索。当然，要加visited set进行判断已经搜过的friend 例如dfs:
public static void dfs(int[][] matrix, HashSet<Integer> visited, int curr){
    visited.add(curr);
    int n = matrix.length;
    for(int i=0;i<n;i++){
        if(matrix[curr][i]==1 && i!=curr && !visited.contains(i)){
            dfs(matrix,visited,i);
        }
    }
}

1.         public static int groupFriends(int[][] matrix) {
2.                 UnionFind uf = new UnionFind(matrix);
3.                 int m = matrix.length;
4.                 int n = matrix[0].length;
5.                 for(int i = 0; i < m; i++) {.鏈枃鍘熷垱鑷�1point3acres璁哄潧
6.                         for(int j = 0; j < n; j++) {.1point3acres缃�
7.                                 if(matrix[i][j] == 1) {
8.                                         uf.union(i, j);. 1point3acres.com/bbs
9.                                 }
10.                         }
11.                 }
12.                 return uf.count;
13.         }
14. class UnionFind {
15.         public int count = 0;
16.         private int[] id = null;
17.         public UnionFind(int[][] matrix) {
18.                 count = matrix.length;. 鍥磋鎴戜滑@1point 3 acres
19.                 id = new int[count];
20.                 for(int i = 0; i < id.length; i++) id[i] = i; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
21.         }
22.         
23.         public int find(int p) {
24.                 while(p != id[p]) {. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
25.                         p = id[p];
26.                 }
27.                 return p;
28.         }.1point3acres缃�
29.         
30.         public boolean union(int p, int q) {
31.                 p = find(p); 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
32.                 q = find(q);
33.                 if(p == q) return false;
34.                 id[p] = q;
35.                 count--;. more info on 1point3acres.com
36.                 return true;
37.         }. visit 1point3acres.com for more.
38. }

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=154918&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
1、word ladder II 2、给一个整数数组表示一列整数并定义这样一个游戏：两个玩家A和B分别轮流从数组的两端取一个数字，并在游戏结束之后计算自己的
收益（取得的整数的总和）。假定玩家A可以先取，求在玩家B采取贪心策略和最优策略这两种情况下，玩家A所能获得的最大收益。

3、首先给出一个树节点的定义方式，一个用Java写的例子如下 class Node {   public char label;   public Node
left, right;   Node(char label) {     this.label = label   } }
然后以此为基础输入给定一个DAG（Directed Acyclic
Graph），这个DAG的每一个节点都是一个树节点，并且这个DAG有且只有一个根节点（没有incoming edges）。如果从根节点执行中序遍历算法，要求推导出最坏情况下遍历结果有多长。并且要求写代码，输出这个遍历中第k个节点。

当时没有跟面试官确认left和right指针都指向同一个节点的case会不会发生，根据讨论我猜是不会发生的。但其实也没有本质区别。 . more info on 1point3acres.com 中序遍历就是标准的二叉树中序遍历的算法。

4、XML Parser