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

找了半天截图没找到，
不过版里有新鲜的  大家看题请去这个帖子

我来上我的代码。。。。带注释 150多行，最大流解    提交最后一刻有个case 过不了，后来交了之后，自己把那个case debug出来了，PS:建议大家自己多列几个corner case
核实一下我的代码再用，免得好心还坑了大家，虽然我应该已经把最后一个case 解决了
好的上代码吧
第一次上代码 希望格式不乱！

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[i][0] = scan.nextInt();

//            }

//            if(scan.hasNextInt()){

//                input[i][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[i][j]);

//                        }

//                        System.out.println();

//                }

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

t can not be s

                                }

                        }

                       

                        if(nothingEnter && nothingOut){

                                superGraph[superGraph.length - 2][i] = 1;

                                superGraph[i][superGraph.length - 1] = 1;

                                continue;

                        }

                        //it should be connected by source "s"

                       

                        if(nothingEnter){

                                superGraph[superGraph.length - 2][i] = 1;

                        }

                        //it should be connected by sink "t"

                        if(nothingOut){

                                superGraph[i][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[i][j] = graph[i][j];

                        }

                }

                return superGraph;

        }

}

补充内容 (2016-11-21 01:44):
代码清楚的格式 见二楼

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];
   
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();
    
16. //            }
    
17. //        }
    
18. //        System.out.println("");
    
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++){
    
27. //                        for(int j = 0; j < res.length; j++){
    
28. //                                System.out.print(res[i][j]);
    
29. //                        }
    
30. //                        System.out.println();
    
31. //                }
    
32.                 System.out.println(solution.stackingBox(input));
    
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;
    
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()){
    
58.                         int curr = queue.poll();
    
59.                         for(int i = 0; i < graph.length; i++){
    
60.                                 if(visited[i] || graph[curr][i] == 0){
    
61.                                         continue;
    
62.                                 }
    
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
    
73.         //return the maximum flow value from s to t in the given graph
    
74.         int fordFulkerson(int[][] graph, int s, int t)
    
75.     {
    
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];
    
84.                 //test
    
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;
    
90.                         int v = t;
    
91.                         while(parentPath[v] != s){
    
92.                                 int u = parentPath[v];
    
93.                                 min_capacity = Math.min(min_capacity, residualGraph[u][v]);
    
94.                                 v = u;
    
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;
     
109.     }
     
110.        
     
111.         public int[][] constructDirectedGraph(int[][] box){
     
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]){
     
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;
     
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.                        
     
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){
     
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;
     
160.                         }
     
161.                        
     
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. }

复制代码

这道题 看不懂大家要去学一下最大流  里面涉及到 构造有向图，BFS，fordFulkerson 等  自学一下吧，我注释已经写得非常详细了

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

小A要当码农 发表于 2016-11-20 13:18
楼主牛逼

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

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

额 好吧 格式乱了~  你们复制粘贴一下  自己看看吧，如果需求大 我再想办法弄的好看一点=.=  不过quora这种招ACM竞赛选手的公司，大家也好好思考一下他在你心中的位置吧~  别误了真正的dream company  就酱

话说，楼主哪里找的内推？感觉很难找

我只能说。。好人，一生，平，安。

wtcupup 发表于 2016-11-19 07:08
话说，楼主哪里找的内推？感觉很难找

LinkedIn 上找的~

牛逼啊。。

楼主牛逼

补充内容 (2016-11-20 13:21):
楼主你的代码编译不过啊。。 感觉看不懂。。

编译不过？这是不可能的……等我起床再check一下吧……