聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 12046|回复: 66
收起左侧

facebook onsite

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

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

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

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

x
面的两道题值得说一说, 第一道题意思 大概是这样  相同工作不能在K的时间内重复干 比如工作A 和下一个工作A必须相隔K的时间 。给你一个Arraylist 和K 求出完成所有的最短时间。 时间复杂要求为O(n) 空间为O1;
第二道题是 给个Tree 不一定是平衡的,
游客,本帖隐藏的内容需要积分高于 133 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

大米  ~~~~~

评分

11

查看全部评分

本帖被以下淘专辑推荐:

siren01 发表于 2015-4-3 22:11:15 | 显示全部楼层
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++;. from: 1point3acres
  10.                         }. Waral 博客有更多文章,
  11.                         else{
  12.                                 queue.add(null);
  13.                         }
  14.                         total++;. visit 1point3acres for more.
  15.                         if(queue.size()>coolDown){. from: 1point3acres
  16.                                 queue.poll();
  17.                         }
  18.                 }
  19.                 return total;
  20.         }
复制代码

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

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

献丑写个第二个吧, 水平有限,应该不是最好的解法
class TreeNode
{
        int value;
        TreeNode left;. 牛人云集,一亩三分地
        TreeNode right;
}. Waral 博客有更多文章,
public Result findMinimumNumber(TreeNode root)
{
        if(root == null)
        {
                return new Result();
        }. From 1point 3acres bbs
        if(root.left == null && root.right == null)
        {
                Result r = new Result();. 留学申请论坛-一亩三分地
                r.min = root.value;
                r.list.add(root.value);. 牛人云集,一亩三分地
                return r;
        }. From 1point 3acres bbs
        Result left = findMinimumNumber(root.left);
        Result right = findMinimumNumber(root.right);. 1point 3acres 论坛
        Result r = new Result();
        r.list.add(root.value);
        if(left.min < right.min). from: 1point3acres
        {
                r.list.addAll(left.list);
        }
        else
        { 来源一亩.三分地论坛.
                r.list.addAll(right.list);
        }
        r.min = Math.min(root.value, Math.min(left.min, right.min));
        return r;
}. more info on 1point3acres
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

使用道具 举报

bigbearlake 发表于 2017-4-25 12:43:38 | 显示全部楼层
sonicgu 发表于 2015-4-3 05:47
献丑写个第二个吧, 水平有限,应该不是最好的解法
class TreeNode. 围观我们@1point 3 acres
{

这代码没有考虑树的值可能相同的情况啊
回复 支持 1 反对 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. Waral 博客有更多文章,
第一题见过O(N) space的解法,用hashmap做的,O(1)怎么做呢?LZ能解释一下吗?. Waral 博客有更多文章,
第二题也好难,O(N)的话大 ...

第一题你可以不用考虑空间 后面问的 我没有做出来
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-4-3 02:51:01 | 显示全部楼层
tracywade 发表于 2015-4-3 02:31
先inorder travel一下 ,不用排序 就可以做出来

没太明白,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. visit 1point3acres for more.
第一题见过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
这跟昨天我发的帖子的第一题很像,不过他这个更难。。。

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

使用道具 举报

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)的解法,回家就贴。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 10:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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