一亩三分地论坛

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

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

facebook onsite

[复制链接] |试试Instant~ |关注本帖
tracywade 发表于 2015-4-3 01:58:49 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
面的两道题值得说一说, 第一道题意思 大概是这样  相同工作不能在K的时间内重复干 比如工作A 和下一个工作A必须相隔K的时间 。给你一个Arraylist 和K 求出完成所有的最短时间。 时间复杂要求为O(n) 空间为O1;
第二道题是 给个Tree 不一定是平衡的, 要求 把所有路径排序后  按字符串那样的比较大小方法 找出最小的路径  时间要求线性的。 比如  
          5
       /     \
    10      3
   /   \   /
1    7  8
路径有  5 10 1 ; 5 10 7 ; 5 3 8
排序后  1 5 10 ; 5 7 10 ; 3 5 8;. Waral 鍗氬鏈夋洿澶氭枃绔,
所以按字符串类型排序 为  1 5 10 < 3 5 8 < 5 7 10;
大米  ~~~~~

评分

10

查看全部评分

本帖被以下淘专辑推荐:

sonicgu 发表于 2015-4-3 05:47:01 | 显示全部楼层
siren01 发表于 2015-4-3 05:14
看了您在另一帖子的回复,大神求上代码,祝RP攒齐

献丑写个第二个吧, 水平有限,应该不是最好的解法
class TreeNode
{
        int value;
        TreeNode left;-google 1point3acres
        TreeNode right;
}
public Result findMinimumNumber(TreeNode root). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
{
        if(root == null)
        {
                return new Result();
        }
        if(root.left == null && root.right == null). 1point3acres.com/bbs
        {
                Result r = new Result();
                r.min = root.value;
                r.list.add(root.value);
                return r;
        }
        Result left = findMinimumNumber(root.left);
        Result right = findMinimumNumber(root.right);. more info on 1point3acres.com
        Result r = new Result();.鐣欏璁哄潧-涓浜-涓夊垎鍦
        r.list.add(root.value);
        if(left.min < right.min)
        {
                r.list.addAll(left.list);
        }
        else
        {
                r.list.addAll(right.list);
        }. 鍥磋鎴戜滑@1point 3 acres
        r.min = Math.min(root.value, Math.min(left.min, right.min));
        return r;.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
class Result
{
        int min;
        ArrayList<Integer> list;
        public Result()
        {
                min = Integer.MAX_VALUE;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                list = new ArrayList<Integer>();
        }
}

补充内容 (2015-4-3 05:49):
Result类里面的list保存的就是组成最小数的节点的值

评分

1

查看全部评分

回复 支持 3 反对 0

使用道具 举报

siren01 发表于 2015-4-3 22:11:15 | 显示全部楼层
zengm321 发表于 2015-4-3 13:19
用deque可以实现O(K)space, 等价于O(1). . more info on 1point3acres.com
用一个长度为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{. 1point3acres.com/bbs
  12.                                 queue.add(null);
  13.                         }
  14.                         total++;
  15.                         if(queue.size()>coolDown){
  16.                                 queue.poll();
  17.                         }
  18.                 }
  19.                 return total;
  20.         }
复制代码

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

siren01 发表于 2015-4-3 05:34:56 | 显示全部楼层
crazybadboy 发表于 2015-4-3 05:33
第二题本质上就是每层找最小的数,然后连起来。

上代码吧,应该是每层找左右子树种最小值得数
回复 支持 1 反对 0

使用道具 举报

yuxrose 发表于 2015-4-3 02:27:56 | 显示全部楼层
第一题见过O(N) space的解法,用hashmap做的,O(1)怎么做呢?LZ能解释一下吗?
第二题也好难,O(N)的话大概可以用STACK做DFS,但排序需要nlogn吧?怎么达到O(N)?
回复 支持 反对

使用道具 举报

 楼主| tracywade 发表于 2015-4-3 02:31:52 | 显示全部楼层
yuxrose 发表于 2015-4-3 02:27
第一题见过O(N) space的解法,用hashmap做的,O(1)怎么做呢?LZ能解释一下吗?
第二题也好难,O(N)的话大 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
先inorder travel一下 ,不用排序 就可以做出来
回复 支持 反对

使用道具 举报

 楼主| tracywade 发表于 2015-4-3 02:33:49 | 显示全部楼层
yuxrose 发表于 2015-4-3 02:27
第一题见过O(N) space的解法,用hashmap做的,O(1)怎么做呢?LZ能解释一下吗?
第二题也好难,O(N)的话大 ...

第一题你可以不用考虑空间 后面问的 我没有做出来
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-3 02:51:01 | 显示全部楼层
tracywade 发表于 2015-4-3 02:31. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
先inorder travel一下 ,不用排序 就可以做出来
. From 1point 3acres bbs
没太明白,lz能详细说一下嘛? 比如5 10 7这个path, 先放7, 然后放10的时候和7比较,swap order变成 7 10, 然后放5,因为5最小,要move 7 10的位置放在最前面,有点像insertion sort, 这个还算是O(N)吗?
回复 支持 反对

使用道具 举报

wrbuaa2005 发表于 2015-4-3 02:57:31 | 显示全部楼层
谢楼主,这两题挺难啊,我标记一下回头想
回复 支持 反对

使用道具 举报

 楼主| tracywade 发表于 2015-4-3 03:05:34 | 显示全部楼层
yuxrose 发表于 2015-4-3 02:51
没太明白,lz能详细说一下嘛? 比如5 10 7这个path, 先放7, 然后放10的时候和7比较,swap order变成 7 10 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
开始我也是这么想的 后面你仔细一想 其实inorder就出来了, 因为你知道root 在哪  那肯定就是往左还是往右走的问题了  , 看左边和右边谁小 就往那边走 同样的思路往下一层层走就出来了。。 这个问题很trick
回复 支持 反对

使用道具 举报

1guangnian 发表于 2015-4-3 03:09:36 | 显示全部楼层
楼主,有两条路径,(1,1,5)和(1,10,5),哪个更小呢
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-3 03:40:56 | 显示全部楼层
tracywade 发表于 2015-4-3 03:05
开始我也是这么想的 后面你仔细一想 其实inorder就出来了, 因为你知道root 在哪  那肯定就是往左还是往 ...

恩,这题要是找最小可以这么做,要是把所有可能的数排序输出,那应该要需要用sorting的法子了
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-3 03:52:42 | 显示全部楼层
1guangnian 发表于 2015-4-3 03:09
楼主,有两条路径,(1,1,5)和(1,10,5),哪个更小呢

第一个更小
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-3 03:55:26 | 显示全部楼层
lz第二题这个解法有个小问题,就是当走到一个根的时候,左孩子子树的最小值和右孩子子树的最小值如果一样,那么就无法判断,所以还需要有一个限定条件 就是树内的值没有重复
回复 支持 反对

使用道具 举报

 楼主| tracywade 发表于 2015-4-3 04:02:44 | 显示全部楼层
sonicgu 发表于 2015-4-3 03:55
lz第二题这个解法有个小问题,就是当走到一个根的时候,左孩子子树的最小值和右孩子子树的最小值如果一样, ...

对的  忘记说了
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-3 04:10:56 | 显示全部楼层
yuxrose 发表于 2015-4-3 02:27. 1point 3acres 璁哄潧
第一题见过O(N) space的解法,用hashmap做的,O(1)怎么做呢?LZ能解释一下吗?
第二题也好难,O(N)的话大 ...

第一题的O(n)space的解法哪里有,求链接
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-3 04:18:49 | 显示全部楼层
tracywade 发表于 2015-4-3 04:02
对的  忘记说了

求楼主上第二题代码,是用递归写的?
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-3 04:49:19 | 显示全部楼层
siren01 发表于 2015-4-3 04:18
求楼主上第二题代码,是用递归写的?

这跟昨天我发的帖子的第一题很像,不过他这个更难。。。
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-3 04:53:09 | 显示全部楼层
yuxrose 发表于 2015-4-3 04:49
这跟昨天我发的帖子的第一题很像,不过他这个更难。。。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
恩恩,是的,这个inorder 遍历我还是不能很好的理解,貌似是每次都要知道左右子树的最小值,然后选择小的那个方向走,也就是一开始要递归到最下面计算每个子树的最小值
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-3 04:53:40 | 显示全部楼层
yuxrose 发表于 2015-4-3 04:49. 1point3acres.com/bbs
这跟昨天我发的帖子的第一题很像,不过他这个更难。。。

还有第一题那个冷冻时间的题,我记得我也看到过了, 但是一下子忘记了,求链接呀
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-3 04:55:43 | 显示全部楼层
tracywade 发表于 2015-4-3 04:02
对的  忘记说了

lz好人!跟俺们上个第二题的代码吧!
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-3 04:57:07 | 显示全部楼层
siren01 发表于 2015-4-3 04:53
恩恩,是的,这个inorder 遍历我还是不能很好的理解,貌似是每次都要知道左右子树的最小值,然后选择小的 ...

所以咱们一起呼吁lz上个代码吧!
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-3 04:57:33 | 显示全部楼层
siren01 发表于 2015-4-3 04:53
还有第一题那个冷冻时间的题,我记得我也看到过了, 但是一下子忘记了,求链接呀

我有O(N)的解法,回家就贴。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 20:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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