一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 297|回复: 12
收起左侧

Quora OA 介于版里资源少,最近又有人问我,来补个面经,攒个人品

[复制链接] |试试Instant~ |关注本帖
格格笑 发表于 2016-11-19 06:56:00 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 实习@Quora - 内推 - 在线笔试 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
找了半天截图没找到,
不过版里有新鲜的  大家看题请去这个帖子
http://www.1point3acres.com/bbs/ ... D311%26sortid%3D311
我来上我的代码。。。。带注释 150多行,最大流解    提交最后一刻有个case 过不了,后来交了之后,自己把那个case debug出来了,PS:建议大家自己多列几个corner case
核实一下我的代码再用,免得好心还坑了大家,虽然我应该已经把最后一个case 解决了
好的上代码吧. 鍥磋鎴戜滑@1point 3 acres
第一次上代码 希望格式不乱!. 鍥磋鎴戜滑@1point 3 acres

package liveramp;
import java.util.*;
public class QuoraStackingBox {
        public static void main(String[] args){
//                Scanner scan = new Scanner(System.in);
//        int n = 0;
//        if(scan.hasNextInt()){
//            n = scan.nextInt();
//        }
//        int[][] input = new int[n][2];
//        for(int i = 0; i < n; i++){
//            if(scan.hasNextInt()){
//                input[0] = scan.nextInt();
//            }
//            if(scan.hasNextInt()){
//                input[1] = scan.nextInt();
//            }
//        }
//        System.out.println("");
                QuoraStackingBox solution = new QuoraStackingBox();
                int[][] input = new int[][]{{9,4}, {6,9}, {6,9}, {6,4}, {1,1}};//{2,5},{3,3},{6,6},{7,8}};//,{1,10},{1,1},{1,1},{1,1}};
//                int[][] input = null;
//                int[][] input = new int[][]{};
//                System.out.println(solution.stackingBox(input));
//                test constructDirectedGraph()  PASS!
//                int[][] res = solution.constructDirectedGraph(input);
//                for(int i = 0; i < res.length; i++){
//                        for(int j = 0; j < res.length; j++){
//                                System.out.print(res[j]);
//                        }
//                        System.out.println();
//                }
                System.out.println(solution.stackingBox(input));
               
        }
        public int stackingBox(int[][] box){
                if(box == null || box.length == 0){
                        return 0;
                }
                int[][] graph = constructDirectedGraph(box);
                int s = graph.length - 2;
                int t = graph.length - 1;
                return fordFulkerson(graph, s, t);
        }
       
        //bfs all vertices, if there is a path from source "s" to sink "t" in the residual graph
        //return true; Also the function fills "parentPath[]" to store the path
        public boolean bfs(int graph[][], int s, int t, int[] parentPath){
                //visited array to used to mark the vertices that has been visited
                //if visited: true, else: false
                boolean[] visited = new boolean[graph.length];
                //create a queue, enqueue source vertex and mark it as visited
                Deque<Integer> queue = new LinkedList<Integer>();
                queue.offer(s);
        visited = true;
        parentPath=-1;
        //Standard BFS Loop
                while(!queue.isEmpty()){
                        int curr = queue.poll();
                        for(int i = 0; i < graph.length; i++){
                                if(visited || graph[curr] == 0){
                                        continue;
                                }
                                queue.offer(i);
                                parentPath = curr;
                                visited = true;
                        }
                }
                //if sink "t" has been visited, which means we have reached "t" in
                //BFS starting from source, then we return true; else, return false.
                return visited[t] == true;
        }
        //Ford Fulkerson algorithm to find Max Flow
        //return the maximum flow value from s to t in the given graph
        int fordFulkerson(int[][] graph, int s, int t)
    {
                int[][] residualGraph = new int[graph.length][graph.length];
                for(int i = 0; i < graph.length; i++){
                        for(int j = 0; j < graph.length; j++){
                                residualGraph[j] = graph[j];
                        }
                }
                int maxFlow = 0;
                int parentPath[] = new int[graph.length];
                //test
               
                while(bfs(residualGraph, s, t, parentPath)){
                        //Find minimum residual capacity(min_capacity) of the edges along the path filled by BFS
                        //min_capacity is also the max_Flow on this path
                        int min_capacity = Integer.MAX_VALUE;
                        int v = t;
                        while(parentPath[v] != s){
                                int u = parentPath[v];
                                min_capacity = Math.min(min_capacity, residualGraph[v]);
                                v = u;
                        }
                        //update Residual Graph
                        int vv = t;
                        while(parentPath[vv] != s){
                                int u = parentPath[vv];
                                residualGraph[vv] -=  min_capacity;
                                residualGraph[vv] +=  min_capacity;
                                vv = u;
                        }
                        //add path flow to overall flow
                        maxFlow += min_capacity;
                }
                //return overall flow/ Max Flow
                return maxFlow;
    }
       
        public int[][] constructDirectedGraph(int[][] box){
                //box.length is the number of box
                //graph[j] means the capacity from i to j: could be used to check "if it has out-going arrow"
                int[][] graph = new int[box.length][box.length];
                //counterGraph[j] means the capacity from j to i: : could be used to check "if it has in-going arrow"
                int[][] counterGraph = new int[box.length][box.length];
                for(int i = 0; i < box.length; i++){
                        for(int j = 0; j < box.length; j++){
                                //Then j is bigger than i, j=>i
                                //no need to judge whether it should point to himself
                                if(j == i){
                                        continue;
                                }
                                if(box[j][0] < box[0] && box[j][1] < box[1]){
                                        counterGraph[j] = 1;
                                }
                                if(box[j][0] > box[0] && box[j][1] > box[1]){
                                        graph[j] = 1;
                                }
                        }
                }
                //add s and t: s: superGraph[box.length]  || t: superGraph[box.length + 1]
                //superGraph[j] means the capacity from i to j
                int[][] superGraph = new int[box.length + 2][box.length + 2];
                for(int i = 0; i < box.length; i++){
                        boolean nothingEnter = true;//nothingEnter
                        boolean nothingOut = true;//nothingOut
                        for(int j = 0; j < box.length; j++){
                                if(graph[j] > 0){
                                        nothingOut = false;//it could reach others, so it can not be t
                                }
                                if(counterGraph[j] > 0){
                                        nothingEnter = false;//it can be reached by others, so it can not be s
                                }
                        }
                       
                        if(nothingEnter && nothingOut){
                                superGraph[superGraph.length - 2] = 1;
                                superGraph[superGraph.length - 1] = 1;
                                continue;
                        }
                        //it should be connected by source "s"
                       
                        if(nothingEnter){
                                superGraph[superGraph.length - 2] = 1;
                        }
                        //it should be connected by sink "t"
                        if(nothingOut){
                                superGraph[superGraph.length - 1] = 1000000;
                        }
                       
                }
                //copy original graph/content(the graph without source "s" and sink "t")
                //to superGraph(the graph with source "s" and sink "t"), return it
                for(int i = 0; i < graph.length; i++){
                        for(int j = 0; j < graph.length; j++){
                                superGraph[j] = graph[j];
                        }
                }
                return superGraph;
        }
}



补充内容 (2016-11-21 01:44):
代码清楚的格式 见二楼
 楼主| 格格笑 发表于 2016-11-21 01:41:18 | 显示全部楼层
  1. import java.util.*;
  2. public class QuoraStackingBox {
  3.         public static void main(String[] args){
  4. //                Scanner scan = new Scanner(System.in);
  5. //        int n = 0;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  6. //        if(scan.hasNextInt()){
  7. //            n = scan.nextInt();
  8. //        }
  9. //        int[][] input = new int[n][2];. 1point 3acres 璁哄潧
  10. //        for(int i = 0; i < n; i++){
  11. //            if(scan.hasNextInt()){
  12. //                input[i][0] = scan.nextInt();
  13. //            }
  14. //            if(scan.hasNextInt()){
  15. //                input[i][1] = scan.nextInt();. more info on 1point3acres.com
  16. //            }. 1point 3acres 璁哄潧
  17. //        }
  18. //        System.out.println("");. 鍥磋鎴戜滑@1point 3 acres
  19.                 QuoraStackingBox solution = new QuoraStackingBox();
  20.                 int[][] input = new int[][]{{9,4}, {6,9}, {6,9}, {6,4}, {1,1}};//{2,5},{3,3},{6,6},{7,8}};//,{1,10},{1,1},{1,1},{1,1}};
  21. //                int[][] input = null;
  22. //                int[][] input = new int[][]{};
  23. //                System.out.println(solution.stackingBox(input));
  24. //                test constructDirectedGraph()  PASS!
  25. //                int[][] res = solution.constructDirectedGraph(input);
  26. //                for(int i = 0; i < res.length; i++){. more info on 1point3acres.com
  27. //                        for(int j = 0; j < res.length; j++){
  28. //                                System.out.print(res[i][j]);
  29. //                        }
  30. //                        System.out.println();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  31. //                }. From 1point 3acres bbs
  32.                 System.out.println(solution.stackingBox(input));. 1point3acres.com/bbs
  33.                
  34.         }
  35.         public int stackingBox(int[][] box){
  36.                 if(box == null || box.length == 0){
  37.                         return 0;
  38.                 }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  39.                 int[][] graph = constructDirectedGraph(box);
  40.                 int s = graph.length - 2;
    .1point3acres缃
  41.                 int t = graph.length - 1;
  42.                 return fordFulkerson(graph, s, t);
  43.         }
  44.        
  45.         //bfs all vertices, if there is a path from source "s" to sink "t" in the residual graph
  46.         //return true; Also the function fills "parentPath[]" to store the path
  47.         public boolean bfs(int graph[][], int s, int t, int[] parentPath){
  48.                 //visited array to used to mark the vertices that has been visited
  49.                 //if visited: true, else: false
  50.                 boolean[] visited = new boolean[graph.length];
  51.                 //create a queue, enqueue source vertex and mark it as visited
  52.                 Deque<Integer> queue = new LinkedList<Integer>();
  53.                 queue.offer(s);
  54.         visited[s] = true;
  55.         parentPath[s]=-1;
  56.         //Standard BFS Loop
  57.                 while(!queue.isEmpty()){.1point3acres缃
  58.                         int curr = queue.poll();
  59.                         for(int i = 0; i < graph.length; i++){-google 1point3acres
  60.                                 if(visited[i] || graph[curr][i] == 0){
  61.                                         continue;
  62.                                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  63.                                 queue.offer(i);
  64.                                 parentPath[i] = curr;
  65.                                 visited[i] = true;
  66.                         }
  67.                 }
  68.                 //if sink "t" has been visited, which means we have reached "t" in
  69.                 //BFS starting from source, then we return true; else, return false.
  70.                 return visited[t] == true;
  71.         }
  72.         //Ford Fulkerson algorithm to find Max Flow. from: 1point3acres.com/bbs
  73.         //return the maximum flow value from s to t in the given graph
  74.         int fordFulkerson(int[][] graph, int s, int t). 1point 3acres 璁哄潧
  75.     {
    . from: 1point3acres.com/bbs
  76.                 int[][] residualGraph = new int[graph.length][graph.length];
  77.                 for(int i = 0; i < graph.length; i++){
  78.                         for(int j = 0; j < graph.length; j++){
  79.                                 residualGraph[i][j] = graph[i][j];
  80.                         }
  81.                 }
  82.                 int maxFlow = 0;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  83.                 int parentPath[] = new int[graph.length];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  84.                 //test-google 1point3acres
  85.                
  86.                 while(bfs(residualGraph, s, t, parentPath)){
  87.                         //Find minimum residual capacity(min_capacity) of the edges along the path filled by BFS
  88.                         //min_capacity is also the max_Flow on this path
  89.                         int min_capacity = Integer.MAX_VALUE;. From 1point 3acres bbs
  90.                         int v = t;
  91.                         while(parentPath[v] != s){
  92.                                 int u = parentPath[v];-google 1point3acres
  93.                                 min_capacity = Math.min(min_capacity, residualGraph[u][v]);
  94.                                 v = u; . visit 1point3acres.com for more.
  95.                         }
  96.                         //update Residual Graph
  97.                         int vv = t;
  98.                         while(parentPath[vv] != s){
  99.                                 int u = parentPath[vv];
  100.                                 residualGraph[u][vv] -=  min_capacity;
  101.                                 residualGraph[vv][u] +=  min_capacity;
  102.                                 vv = u;
  103.                         }
  104.                         //add path flow to overall flow
  105.                         maxFlow += min_capacity;
  106.                 }
  107.                 //return overall flow/ Max Flow
  108.                 return maxFlow;. more info on 1point3acres.com
  109.     }
  110.        
  111.         public int[][] constructDirectedGraph(int[][] box){. from: 1point3acres.com/bbs
  112.                 //box.length is the number of box
  113.                 //graph[i][j] means the capacity from i to j: could be used to check "if it has out-going arrow"
  114.                 int[][] graph = new int[box.length][box.length];
  115.                 //counterGraph[i][j] means the capacity from j to i: : could be used to check "if it has in-going arrow"
  116.                 int[][] counterGraph = new int[box.length][box.length];
  117.                 for(int i = 0; i < box.length; i++){
  118.                         for(int j = 0; j < box.length; j++){
  119.                                 //Then j is bigger than i, j=>i
  120.                                 //no need to judge whether it should point to himself
  121.                                 if(j == i){
  122.                                         continue;
  123.                                 }
  124.                                 if(box[j][0] < box[i][0] && box[j][1] < box[i][1]){.1point3acres缃
  125.                                         counterGraph[i][j] = 1;
  126.                                 }
  127.                                 if(box[j][0] > box[i][0] && box[j][1] > box[i][1]){
  128.                                         graph[i][j] = 1;. more info on 1point3acres.com
  129.                                 }
  130.                         }
  131.                 }
  132.                 //add s and t: s: superGraph[box.length]  || t: superGraph[box.length + 1]
  133.                 //superGraph[i][j] means the capacity from i to j. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  134.                 int[][] superGraph = new int[box.length + 2][box.length + 2];
  135.                 for(int i = 0; i < box.length; i++){
  136.                         boolean nothingEnter = true;//nothingEnter
  137.                         boolean nothingOut = true;//nothingOut
  138.                         for(int j = 0; j < box.length; j++){
  139.                                 if(graph[i][j] > 0){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  140.                                         nothingOut = false;//it could reach others, so it can not be t
  141.                                 }
  142.                                 if(counterGraph[i][j] > 0){
  143.                                         nothingEnter = false;//it can be reached by others, so it can not be s
  144.                                 }
  145.                         }
  146.                         . From 1point 3acres bbs
  147.                         if(nothingEnter && nothingOut){
  148.                                 superGraph[superGraph.length - 2][i] = 1;
  149.                                 superGraph[i][superGraph.length - 1] = 1;
  150.                                 continue;
  151.                         }
  152.                         //it should be connected by source "s"
  153.                        
  154.                         if(nothingEnter){. 鍥磋鎴戜滑@1point 3 acres
  155.                                 superGraph[superGraph.length - 2][i] = 1;
  156.                         }
  157.                         //it should be connected by sink "t"
  158.                         if(nothingOut){
  159.                                 superGraph[i][superGraph.length - 1] = 1000000;. Waral 鍗氬鏈夋洿澶氭枃绔,
  160.                         }
  161.                        
    . 1point3acres.com/bbs
  162.                 }
  163.                 //copy original graph/content(the graph without source "s" and sink "t") 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  164.                 //to superGraph(the graph with source "s" and sink "t"), return it
  165.                 for(int i = 0; i < graph.length; i++){
  166.                         for(int j = 0; j < graph.length; j++){
  167.                                 superGraph[i][j] = graph[i][j];
  168.                         }
  169.                 }
  170.                 return superGraph;
  171.         }
  172. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| 格格笑 发表于 2016-11-21 01:43:49 | 显示全部楼层
这道题 看不懂大家要去学一下最大流  里面涉及到 构造有向图,BFS,fordFulkerson 等  自学一下吧,我注释已经写得非常详细了
回复 支持 反对

使用道具 举报

 楼主| 格格笑 发表于 2016-11-21 01:40:08 | 显示全部楼层
小A要当码农 发表于 2016-11-20 13:18
楼主牛逼

补充内容 (2016-11-20 13:21):

你说的是对的因为格式乱了  我查到一个细节 是它把我比如说我要表示 visited[]  他给我把括号弄没了... 我再传一个吧
回复 支持 1 反对 0

使用道具 举报

 楼主| 格格笑 发表于 2016-11-19 06:58:26 | 显示全部楼层
额 好吧 格式乱了~  你们复制粘贴一下  自己看看吧,如果需求大 我再想办法弄的好看一点=.=  不过quora这种招ACM竞赛选手的公司,大家也好好思考一下他在你心中的位置吧~  别误了真正的dream company  就酱
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-19 07:08:10 | 显示全部楼层
话说,楼主哪里找的内推?感觉很难找
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-11-19 07:13:51 | 显示全部楼层
应该给楼主狂加大米
回复 支持 反对

使用道具 举报

mrdanding 发表于 2016-11-19 07:17:16 | 显示全部楼层
我只能说。。好人,一生,平,安。
回复 支持 反对

使用道具 举报

 楼主| 格格笑 发表于 2016-11-19 08:28:19 | 显示全部楼层
wtcupup 发表于 2016-11-19 07:08. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
话说,楼主哪里找的内推?感觉很难找

LinkedIn 上找的~
回复 支持 反对

使用道具 举报

 楼主| 格格笑 发表于 2016-11-21 01:32:41 | 显示全部楼层
编译不过?这是不可能的……等我起床再check一下吧……
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-21 07:14:29 | 显示全部楼层
格格笑 发表于 2016-11-21 01:32
编译不过?这是不可能的……等我起床再check一下吧……

testcase 1/2。。。。。。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 19:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表