facebook onsite

面的两道题值得说一说， 第一道题意思 大概是这样  相同工作不能在K的时间内重复干 比如工作A 和下一个工作A必须相隔K的时间 。给你一个Arraylist 和K 求出完成所有的最短时间。 时间复杂要求为O（n) 空间为O1；
第二道题是 给个Tree 不一定是平衡的，

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

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

求大米  ~~~~~

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.         }

复制代码

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

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

sonicgu 发表于 2015-4-3 05:47
献丑写个第二个吧, 水平有限，应该不是最好的解法
class TreeNode
{

这代码没有考虑树的值可能相同的情况啊

第一题见过O(N) space的解法，用hashmap做的，O(1)怎么做呢？LZ能解释一下吗？
第二题也好难，O(N)的话大概可以用STACK做DFS，但排序需要nlogn吧？怎么达到O(N)?

yuxrose 发表于 2015-4-3 02:27
第一题见过O(N) space的解法，用hashmap做的，O(1)怎么做呢？LZ能解释一下吗？
第二题也好难，O(N)的话大 ...

先inorder travel一下 ，不用排序 就可以做出来

yuxrose 发表于 2015-4-3 02:27
第一题见过O(N) space的解法，用hashmap做的，O(1)怎么做呢？LZ能解释一下吗？
第二题也好难，O(N)的话大 ...

第一题你可以不用考虑空间 后面问的 我没有做出来

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

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

谢楼主，这两题挺难啊，我标记一下回头想

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

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

楼主，有两条路径，（1，1，5）和（1，10，5），哪个更小呢

tracywade 发表于 2015-4-3 03:05
开始我也是这么想的 后面你仔细一想 其实inorder就出来了， 因为你知道root 在哪  那肯定就是往左还是往 ...

恩，这题要是找最小可以这么做，要是把所有可能的数排序输出，那应该要需要用sorting的法子了

1guangnian 发表于 2015-4-3 03:09
楼主，有两条路径，（1，1，5）和（1，10，5），哪个更小呢

第一个更小