一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请号
扫码关注留学申请公众号
查看: 1505|回复: 11
收起左侧

肥死不可2020new grad电面跪经

[复制链接] |只看干货 |facebook, 美国面经, 面试经验, 码农类general
我的人缘0

升级   86%


分享帖子到朋友圈
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   98% (268)
 
 
1% (3)    👎

2019(10-12月) 码农类General 硕士 全职@Facebook - 内推 - 技术电面  | Fail/Rej | fresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
个人的肥死不可二进宫,又稳稳得跪了,没办法,准备不充分,小伙伴们一定多刷题,多看面经,做好万全准备。

题目大概就是给定一个任务执行序列,有不同类型的任务,每种任务执行完毕只需要1个时间单位,而相同任务的执行需要至少相隔cooldown个时间单位,求按照给定执行序列执行完所有任务需要花费多长时间。

LC上只找到柳耳药稍微相近一点,但是LC那题是可以随意排序task的,求最少执行时间,而这里是给出了task的执行顺序,求一个确定的总的执行时间。

当时我想这题很快有了思路,不过实现过程坎坎坷坷,因为小细节有点多,“还是我的脑子开始有点乱~”,而且结尾面试官问我能不能优化一下时间复杂度,我一下想不出来怎么优化了,然后就草草收尾了。还是把自己的实现贴在下面,供大家参考:

[hide=50]
// Given a list of task execution order: [1, 1, 2, 1], same number indicates same type of task;
    // Executing any type of task takes only one time slot, while there should be at least a cooldown time cd between executing same type of task
    // Write a function processTasks(int[] order_list, int cooldown) that returns the interval of executing all tasks

    // For example: order_list = [1, 1, 2, 1], cd = 2, then executing situation would be:
    // [1 _ _ 1 2 _ 1], the interval is 7, si processTasks() should return 7

    // Complexity: assume M types of tasks, and N tasks to execute;
    // Time: O(NM), Space: O(M)
    public static int processTasks(int[] orderList, int cooldown){

        int interval = 0;

        int execute_time = 1;

        // key: type, value: cooldown time signal
        Map<Integer, Integer> signalMap = new HashMap<>();
        for(int i=0;i<orderList.length;i++)
            signalMap.putIfAbsent(orderList[i], 0);

        for(int i=0; i<orderList.length;i++
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
execute_time;
                signalMap.put(type, wait_time);

                for(Integer decreaseType : signalMap.keySet())
                    if(decreaseType!=type)
                        signalMap.put(decreaseType, signalMap.get(decreaseType) - wait_time - execute_time);
            }
        }
        return interval;
    }
[\hide]

最后,求米~~

评分

参与人数 5大米 +27 收起 理由
Yuyan + 2 很有用的信息!
Chaoss + 2 楼主加油
清道神君 + 20
pennyyyyy + 2 给你点个赞!
贿贿 + 1 赞一个

查看全部评分


上一篇:Google OA
下一篇:Quora OA
我的人缘0

升级   35.43%

本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   100% (20)
 
 
0% (0)    👎
提供一点小小的想法,请求加点米,看面经谢谢:

public int processTasks(int[] orderList, int cooldown) {
// key is the task Id, value is the recently time it should be put
   Map<Integer, Integer> map = new HashMap<>();
   int time = 0;
   for (int id : orderList) {
     if (map.containsKey(id)) {
       time = Math.max(map.get(id) + cooldown + 1, time);
     }
     map.put(id, time++);
   }
   return time;
}

评分

参与人数 3大米 +7 收起 理由
shikiding + 2 给你点个赞!
Chaoss + 2 给你点个赞!
monaziyi + 3 Smart

查看全部评分

回复

使用道具 举报

我的人缘1

升级   22.14%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   89% (678)
 
 
10% (80)    👎
楼主你好, 这道题是task scheduler 的简化版,因为顺序是固定的,所以直接 顺序遍历,然后记录上一个 char的位置并且如果间隔小于k 就填塞cooldown 即可

评分

参与人数 1大米 +2 收起 理由
bluemapleman + 2 给你点个赞!

查看全部评分

回复

使用道具 举报

我的人缘0

升级   0.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (143)
 
 
4% (7)    👎
Lz啥时候投的。。
回复

使用道具 举报

我的人缘0

升级   86%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (268)
 
 
1% (3)    👎
chiyu 发表于 2019/10/15 03:43:05
Lz啥时候投的。。
大概9月下旬的时候投的
回复

使用道具 举报

我的人缘0

升级   67%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   66% (2)
 
 
33% (1)    👎
那个例子没看太懂,可以麻烦楼主解释一下吗?为什么1_ _ 1要有两个cooldown,但是2_ 1只需要一个?
回复

使用道具 举报

我的人缘0

升级   74.71%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (14)
 
 
6% (1)    👎
yvfub 发表于 2019-10-15 04:57
那个例子没看太懂,可以麻烦楼主解释一下吗?为什么1_ _ 1要有两个cooldown,但是2_ 1只需要一个?

同问。同问。同问。同问。同问。
回复

使用道具 举报

我的人缘0

升级   86%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (268)
 
 
1% (3)    👎
yvfub 发表于 2019-10-15 04:57
那个例子没看太懂,可以麻烦楼主解释一下吗?为什么1_ _ 1要有两个cooldown,但是2_ 1只需要一个?

因为不同类型任务之间不需要考虑cooldown问题,即i类型任务可以在j类型任务的cooldown期间执行,所以1执行完后,2可以立即执行
回复

使用道具 举报

我的人缘0

升级   60.86%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (268)
 
 
2% (6)    👎
本帖最后由 valentin508 于 2019-10-15 08:51 编辑

看一下蠡口叁伍捌,不是陆贰壹
但是蠡口那两道都是可以更改任务序列顺序的,如果固定序列就直接扫一遍,看当前char的index是否出现过并且如果间隔小于k就填充到k。数据结构用hashmap即可,记录某个字符上次出现的位置。这道题最后是让你返回最小的执行时长而不是任务序列本身。所以我们就通过顺序判断需不需要塞cooldown来给原string长度来增加,最后返回这个总长即可
回复

使用道具 举报

我的人缘0

升级   86%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (268)
 
 
1% (3)    👎
zhangzichun 发表于 2019-10-15 05:07
楼主你好, 这道题是task scheduler 的简化版,因为顺序是固定的,所以直接 顺序遍历,然后记录上一个 char ...

谢谢!你的思路很好,我按照这个思路也实现了一次:

// Complexity: assume M types of tasks, and N tasks to execute;
    // Time: O(N), Space: O(M)
    public static int processTasks2(int[] orderList, int cooldown){
        int processTime = 0;
        // Key: Task type , Value: Last appear index
        Map<Integer,Integer> intervalMap = new HashMap<>();
        for(int i=0;i<orderList.length;i++){
            int jobType = orderList;
            if(intervalMap.containsKey(jobType)){ // executed before, need to check cooldown
                int lastAppearIdx = intervalMap.get(jobType); // get its last appear index
                int waitedTime = i - lastAppearIdx; // how many time units the job type has waited for
                if(waitedTime > cooldown)
                    processTime++; // executable, cooldown has finished, execution takes one time unitindex
                else
                    processTime += cooldown + 1 - waitedTime + 1; // wait until executable and execution takes one time unit
            }else  // execuatable (never executed before)
                processTime++;
            intervalMap.put(jobType, i); // update last appear index
        }
        return processTime;
    }

哭了,简化版的都没做出来😂
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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