facebook onsite

请问楼主是几轮面试呀，有没有一轮Design?

zengm321 发表于 2015-4-3 13:19
用deque可以实现O(K)space, 等价于O(1).
用一个长度为K的deque，每次检查的时候就数queue里面有没有出 ...

根据层主思路补了代码，反馈大伙

1. public static int schedule2(List<Character> task){
   
2.                 Queue<Character> queue = new LinkedList<Character>();
   
3.                 int total = 0;
   
4.                 int i = 0;
   
5.                 int coolDown = 2;
   
6.                 while(i<task.size()){
   
7.                         if(queue.isEmpty() || !queue.contains(task.get(i))){
   
8.                                 queue.add(task.get(i));
   
9.                                 i++;
   
10.                         }
    
11.                         else{
    
12.                                 queue.add(null);
    
13.                         }
    
14.                         total++;
    
15.                         if(queue.size()>coolDown){
    
16.                                 queue.poll();
    
17.                         }
    
18.                 }
    
19.                 return total;
    
20.         }

复制代码

ericzeze 发表于 2015-4-3 14:34
请问楼主是几轮面试呀，有没有一轮Design?

没有 只面了三轮

siren01 发表于 2015-4-3 22:11
根据层主思路补了代码，反馈大伙

你是怎么想出来的 太牛了!!

siren01 发表于 2015-4-3 22:11
根据层主思路补了代码，反馈大伙

这个代码很好，不过有个问题就是这个k必须是个常数，否则复杂度不能算O(n)和O(1)

sonicgu 发表于 2015-4-4 00:58
这个代码很好，不过有个问题就是这个k必须是个常数，否则复杂度不能算O(n)和O(1)

是的，看K，实在想不出更好的了

siren01 发表于 2015-4-4 01:47
是的，看K，实在想不出更好的了

米群的siren001是你的账号么？

sonicgu 发表于 2015-4-4 02:12
米群的siren001是你的账号么？

这两个账号都是朋友给的..

siren01 发表于 2015-4-4 02:19
这两个账号都是朋友给的..

了解，面完了等你的面经

感觉每一步都addall好像超过了O(n)？ 先用HashMap 更新最小weight，然后走一遍拿到list。还有感觉是postorder？不知道inorder的思路是如何的。还请指点。

1. import java.util.*;
   
2. import java.lang.*;
   
3. import java.io.*;
   
4. 
   
5. class Ideone {
   
6.         private static class TreeNode {
   
7.                 int val;
   
8.                 TreeNode left;
   
9.                 TreeNode right;
   
10. 
    
11.                 TreeNode(int x) {
    
12.                         val = x;
    
13.                 }
    
14.         }
    
15. 
    
16.         private static HashMap<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>();
    
17. 
    
18.         private static List<Integer> findMinPath(TreeNode root) {
    
19.                 List<Integer> ret = new ArrayList<Integer>();
    
20.                 postOrder(root);
    
21.                 findPath(root, ret);
    
22.                 return ret;
    
23.         }
    
24. 
    
25.         private static void postOrder(TreeNode cur) {
    
26.                 if (cur == null) {
    
27.                         return;
    
28.                 }
    
29.                 int leftMin = cur.val;
    
30.                 if (cur.left != null) {
    
31.                         postOrder(cur.left);
    
32.                         leftMin = weight.get(cur.left);
    
33.                 }
    
34.                 int rightMin = cur.val;
    
35.                 if (cur.right != null) {
    
36.                         postOrder(cur.right);
    
37.                         rightMin = weight.get(cur.right);
    
38.                 }
    
39. 
    
40.                 int curWeight = Math.min(cur.val, Math.min(leftMin, rightMin));
    
41.                 weight.put(cur, curWeight);
    
42.         }
    
43. 
    
44.         private static void findPath(TreeNode cur, List<Integer> list) {
    
45.                 if (cur == null) {
    
46.                         return;
    
47.                 }
    
48.                 list.add(cur.val);
    
49.                 if (cur.left == null) {
    
50.                         findPath(cur.right, list);
    
51.                         return;
    
52.                 }
    
53.                 if (cur.right == null) {
    
54.                         findPath(cur.left, list);
    
55.                         return;
    
56.                 }
    
57.                 int leftWeight = weight.get(cur.left);
    
58.                 int rightWeight = weight.get(cur.right);
    
59. 
    
60.                 if (leftWeight > rightWeight) {
    
61.                         findPath(cur.right, list);
    
62. 
    
63.                 } else {
    
64.                         findPath(cur.left, list);
    
65.                 }
    
66.         }
    
67.         public static void main (String[] args) throws java.lang.Exception
    
68.         {
    
69.                 TreeNode a = new TreeNode(5);
    
70.                 TreeNode b = new TreeNode(7);
    
71.                 TreeNode c = new TreeNode(10);
    
72.                 TreeNode d = new TreeNode(1);
    
73.                 TreeNode e = new TreeNode(3);
    
74.                 TreeNode f = new TreeNode(8);
    
75.                 a.left = c;
    
76.                 a.right = e;
    
77.                 c.left = d;
    
78.                 c.right = b;
    
79.                 e.left = f;
    
80.                 List<Integer> list = findMinPath(a);
    
81.                 for (int k : list) {
    
82.                         System.out.println(k);
    
83.                 }
    
84.         }
    
85. }
    

复制代码