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
对 我用的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、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
题目是给一些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自己测 |
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);
}
}
}
- public static int groupFriends(int[][] matrix) {
- UnionFind uf = new UnionFind(matrix);
- int m = matrix.length;
- int n = matrix[0].length;
- for(int i = 0; i < m; i++) {.鏈枃鍘熷垱鑷�1point3acres璁哄潧
- for(int j = 0; j < n; j++) {.1point3acres缃�
- if(matrix[i][j] == 1) {
- uf.union(i, j);. 1point3acres.com/bbs
- }
- }
- }
- return uf.count;
- }
- class UnionFind {
- public int count = 0;
- private int[] id = null;
- public UnionFind(int[][] matrix) {
- count = matrix.length;. 鍥磋鎴戜滑@1point 3 acres
- id = new int[count];
- for(int i = 0; i < id.length; i++) id[i] = i; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
- }
- public int find(int p) {
- while(p != id[p]) {. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
- p = id[p];
- }
- return p;
- }.1point3acres缃�
- public boolean union(int p, int q) {
- p = find(p); 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
- q = find(q);
- if(p == q) return false;
- id[p] = q;
- count--;. more info on 1point3acres.com
- return true;
- }. visit 1point3acres.com for more.
- }
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