G onsite 2015/02/09

yapingchen1990 发表于 2015-2-11 09:01
楼主。刚才想了下。如果input是1,2,3,4,四个integer的话， 这道题的意思是这四个数必须按顺序么。因为如 ...

是按顺序……

谁能讲下第三题怎么做吗？谢谢了

sunfish 发表于 2015-2-11 13:09
谁能讲下第三题怎么做吗？谢谢了

终于有人问这个了……我觉得这道题我当时写了好久，现在没人问，是不是我水平太低了……
我就直接贴代码吧。

1. class Entry {
   
2.         public String funcName;
   
3.         public int timeStamp;
   
4.         public boolean isStart;
   
5.         public Entry(String funcName, int timeStamp, boolean isStart) {
   
6.                 super();
   
7.                 this.funcName = funcName;
   
8.                 this.timeStamp = timeStamp;
   
9.                 this.isStart = isStart;
   
10.         }
    
11. }
    
12. class Node {
    
13.         public String funcName;
    
14.         public int start;
    
15.         public int end;
    
16.         public int indentLevel;
    
17.         public Node(String funcName, int indentLevel) {
    
18.                 super();
    
19.                 this.funcName = funcName;
    
20.                 this.indentLevel = indentLevel;
    
21.         }
    
22. }
    
23. public class ProgramProfile {
    
24.         public static void printProfile(List<Entry> input) {
    
25.                 Stack<Node> stack = new Stack<Node>();
    
26.                 List<Node> res = new LinkedList<Node>();
    
27.                 for (int i = 0; i < input.size(); i++) {
    
28.                         Entry curr = input.get(i);
    
29.                         if (curr.isStart) {
    
30.                                 Node node = new Node(curr.funcName, stack.size());
    
31.                                 node.start = curr.timeStamp;
    
32.                                 stack.push(node);
    
33.                                 res.add(node);
    
34.                         } else {
    
35.                                 Node node = stack.pop();
    
36.                                 node.end = curr.timeStamp;
    
37.                         }
    
38.                 }
    
39.                
    
40.                 for (Node node : res) {
    
41.                         for (int i = 0; i < node.indentLevel * 4; i++) {
    
42.                                 System.out.print(" ");
    
43.                         }
    
44.                         System.out.println(node.funcName + "    " + (node.end - node.start));
    
45.                 }
    
46.         }
    
47.         /**
    
48.          * @param args
    
49.          */
    
50.         public static void main(String[] args) {
    
51.                 // TODO Auto-generated method stub
    
52.                 List<Entry> input = new ArrayList<Entry>();
    
53.                 input.add(new Entry("main", 0, true));
    
54.                 input.add(new Entry("foo", 5, true));
    
55.                 input.add(new Entry("g", 10, true));
    
56.                 input.add(new Entry("g", 20, false));
    
57.                 input.add(new Entry("foo", 50, false));
    
58.                 input.add(new Entry("bar", 60, true));
    
59.                 input.add(new Entry("main", 90, false));
    
60.                 input.add(new Entry("main", 100, false));
    
61.                 ProgramProfile.printProfile(input);
    
62.         }
    
63. 
    
64. }

复制代码

tianyangche 发表于 2015-2-11 06:46
我刚开始想错了，后来经他提示想出了解法。用分治法来做。for循环从0开始，每次分成左右两边，左边的结果 ...

嗯，不过分治法需要你对每个过程保存一个结果集，然后这些对结果集进行Cross式的合并，这种方式程序比较清晰但空间复杂度容易很高。我想了个纯粹的DFS方法，就是直接往原序列里插入运算符，N个数需要插满N-1个操作符（中止条件），最后计算形成的逆波兰式，如果等于目标数就直接返回

补充内容 (2015-2-11 16:36):
PS：Google对楼主的考验比较严峻，这题能现场都做出来很不错了。第三题用flood spread算法比较容易，第四题纯粹考数学啊

CrossTheWall 发表于 2015-2-11 16:31
嗯，不过分治法需要你对每个过程保存一个结果集，然后这些对结果集进行Cross式的合并，这种方式程序比较 ...

不明觉厉~没太懂什么意思，求代码啊大神~

tianyangche 发表于 2015-2-11 16:34
不明觉厉~没太懂什么意思，求代码啊大神~

代码没写呢，抽空过来贴上。
是这样的：
比如 1234，你DFS的过程往第二个数之后的序列插入运算符（N-1个）， 比如12+34*-，该逆波兰式等于（1+2）-（3*4）； 如果是1234+-/, 那就等于1/(2-（3+4）)。
这样深搜就不用保存中间运算结果集合了！

CrossTheWall 发表于 2015-2-11 16:31
嗯，不过分治法需要你对每个过程保存一个结果集，然后这些对结果集进行Cross式的合并，这种方式程序比较 ...

求大神明示什么叫flood spread方法？我没听说过，也没找见~求大神发个链接啥的看看~

第三题能用stack做比较简单吧

第二题是用graph的adjacency list求connected component BFS和DFS都可以吧

tianyangche 发表于 2015-2-11 16:46
求大神明示什么叫flood spread方法？我没听说过，也没找见~求大神发个链接啥的看看~

你可以去google 一下“flood fill”，就是说“只要有通路，洪水就可以蔓延”。不过这个题需要稍微改
动下，就是用hash map遍历原来集合里所有的Pair，得到每个Node的邻居，比如 1-2， 2-3， 2-4， 1-4，
5-6， 1 的邻居就是（2, 4）， 2的邻居是（3,4）.....； flood fill之后，就变成两个集合：{1， 2，
3， 4}, {5, 6}
其实你做这个题的思路就类似于flood fill的