在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

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

EA电面

[复制链接] |试试Instant~ |关注本帖
lqzgz 发表于 2015-10-23 12:57:36 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类General 硕士 全职@Electronic Arts - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
游客,本帖隐藏的内容需要积分高于 1 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


祝大家offer多多!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

hurtlocker 发表于 2017-2-9 14:02:34 | 显示全部楼层
shiloh00 发表于 2017-2-1 06:12
这个题想到一个o(n)的方法 其实就是和meetingroom一样但是是逆向思维 我们不妨看如果想让所有的task都run的 ...

这个有sort了至少是nlgn吧。。。
. 牛人云集,一亩三分地
代码没仔细看,但是按照你叙述的思路,[[1,5], [6,10], [2, 7], [8, 12]]似乎就是反例?
显然最多可安排2个区间,答案是2.
但是按你的想法,2个“线程”就可以放下所有task,那么4-2+1=3这个答案是错的。。。

按end time排序似乎就可以。。。这里的intuition是如果end time确定,不会影响后续的安排。
假设现在已经按end time排好序,那么考察当前incoming的区间[s, e],当前总的结束时间为E,如果
1. s >= E,accept [s, e], 可安排会议数+1
2. s < E,那么[s, e]*至少*会跟一个已经安排好的区间overlap,reject [s, e]即可. 1point 3acres 论坛
因此这样iterate并且安排区间,从头到尾是“不会亏”的
回复 支持 1 反对 0

使用道具 举报

小柯西 发表于 2015-10-23 13:20:49 | 显示全部楼层
leetcode meeting rooms
回复 支持 反对

使用道具 举报

edly 发表于 2015-10-23 13:30:55 | 显示全部楼层
本质只有O(#Interval)个时间点,把时间点按大小关系离散化就可以了
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-23 13:34:52 | 显示全部楼层

完全是不同的题=,=
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-23 13:40:27 | 显示全部楼层
edly 发表于 2015-10-23 13:30. 牛人云集,一亩三分地
本质只有O(#Interval)个时间点,把时间点按大小关系离散化就可以了

smart solution
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2015-10-24 11:22:54 | 显示全部楼层
dp[task.end] = dp[0..(task.start - 1)] + 1。。。这里task.end是时间点吗?dp[task.end]是不是就是dp[0..task.end]?
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2015-10-24 11:24:17 | 显示全部楼层
edly 发表于 2015-10-23 13:30
本质只有O(#Interval)个时间点,把时间点按大小关系离散化就可以了

可否具体讲一下?谢谢了
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2015-10-24 11:25:04 | 显示全部楼层

对于楼上的理解,可否具体讲一下?我觉得lz您提的followup解法就不错啊
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-24 12:00:56 | 显示全部楼层
lqzgz 发表于 2015-10-23 13:34. from: 1point3acres
完全是不同的题=,=

这道题就是求最大的不重叠interval数量啊,算法导论上讲greedy的那一章专门有说过,和meeting rooms是同一个模型。只不过这题多加了个区间限制,[1, 100],不过也很好办,在每个iterration里都判断下当前检查的interval是否已经超出限制区间就行了。
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-24 12:34:08 | 显示全部楼层
小柯西 发表于 2015-10-24 12:00
这道题就是求最大的不重叠interval数量啊,算法导论上讲greedy的那一章专门有说过,和meeting rooms是同 ...

alright,算法导论没好好看过。。。
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-24 12:54:38 | 显示全部楼层
  1. </blockquote><div class="blockcode"><blockquote><blockquote>class Interval(object):
  2.     def __init__(self, start, end):. 1point 3acres 论坛
  3.     <span style="line-height: 1.5;">   </span><span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">self.start = start</span>
复制代码
刚才写的,思路大概就是这有



补充内容 (2015-10-24 12:55):
卧槽。怎么变成这样
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-24 12:55:27 | 显示全部楼层
class Interval(object):. 牛人云集,一亩三分地
    def __init__(self, start, end):. 1point3acres
        self.start = start
        self.end = end. 1point3acres
   
    def __repr__(self):
        return '[%d, %d]' %(self.start, self.end)
   
# `intervals` is a list of intervals.
# `time` is a interval.
# return the max num of tasks that can be done in the given time.. 1point 3acres 论坛
def maxTaskNum(tasks, time):. 牛人云集,一亩三分地
    tasks.sort(key=lambda i: i.end)
   
    rst = 0
    ongoing_task = None
   
    for task in tasks:. from: 1point3acres
        if task.start < time.start: continue
        if task.end > time.end: break
        if not ongoing_task or task.start >= ongoing_task.end:
            rst += 1. visit 1point3acres for more.
            ongoing_task = task
   
    print rst

. 一亩-三分-地,独家发布
tasks = [Interval(1,50), Interval(51,100), Interval(1,99)]
time = Interval(1,100)
.留学论坛-一亩-三分地
maxTaskNum(tasks, time)
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-24 13:33:25 | 显示全部楼层
  1. tasks.sort(key=lambda i: i.end)
复制代码
机智,受教了
回复 支持 反对

使用道具 举报

liqingfd 发表于 2017-1-20 09:35:11 | 显示全部楼层
dp的做法试了一下,自己跑了几个testcase感觉没什么问题,如果小伙伴们发现有错误,欢迎指出:)
  1. public class test {
  2.     static class Interval {. 1point 3acres 论坛
  3.         int start;
  4.         int end;
  5.         public Interval(int start, int end) {
  6.             this.start = start;
  7.             this.end = end;.本文原创自1point3acres论坛
  8.         }
  9.     }
  10.     public static int maxTask(Interval[] intervals, Interval total) {
  11.         int res = 0;.本文原创自1point3acres论坛
  12.         // dp[i] - until ith interval, maximum tasks
  13.         List<Integer> dp = new ArrayList<>();. from: 1point3acres
  14.         Arrays.sort(intervals, new Comparator<Interval>() {. 围观我们@1point 3 acres
  15.             @Override
  16.             public int compare(Interval a, Interval b) {
  17.                 if (a.start != b.start)     return a.start - b.start;
  18.                 else    return a.end - b.end;
  19.             }
  20.         });
  21.         dp.add(1);
  22.         for (int i = 1; i < intervals.length && intervals[i].end <= total.end; i++) {
  23.             dp.add(0);
  24.             for (int j = 0; j < i; j++) {
  25.                 if (intervals[j].end <= intervals[i].start) {. 围观我们@1point 3 acres
  26.                     if (dp.get(j) + 1 > dp.get(i)) {
  27.                         dp.set(i, dp.get(j) + 1);
  28.                         res = Math.max(res, dp.get(i));
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.         return res;
  34.     }
  35.     public static void main(String args[]){
  36.         Interval i1 = new Interval(1, 50);
  37.         Interval i2 = new Interval(51, 100);
  38.         Interval i3 = new Interval(1, 20);.1point3acres网
  39.         Interval i4 = new Interval(30, 40);
  40.         Interval i5 = new Interval(40, 50);
  41.         Interval i6 = new Interval(80, 90);. 留学申请论坛-一亩三分地
  42.         Interval i7 = new Interval(95, 110);
  43.         Interval[] is = new Interval[7];
  44.         is[0] = i1;
  45.         is[1] = i2;
  46.         is[2] = i3;
  47.         is[3] = i4;
  48.         is[4] = i5;
  49.         is[5] = i6;
  50.         is[6] = i7;
  51.         System.out.print(maxTask(is, new Interval(1, 100)));
  52.     }
  53. }
复制代码
回复 支持 反对

使用道具 举报

shiloh00 发表于 2017-2-1 06:12:28 | 显示全部楼层
这个题想到一个o(n)的方法 其实就是和meetingroom一样但是是逆向思维 我们不妨看如果想让所有的task都run的话 最少需要多少个线程 那么把总得个数减去最小的线程数再➕1就是最后要的结果了 代码如下:


#include <iostream>. Waral 博客有更多文章,
#include <vector>
#include <utility>
#include <cmath>
using namespace std;.本文原创自1point3acres论坛
struct cmp{. 留学申请论坛-一亩三分地
        bool operator()(int a, int b){
                if(abs(a) == abs(b))
                        return a < b;
                else
                        return abs(a) < abs(b);
        }
}comparator;
int find_max(vector<pair<int, int>>& vec, pair<int, int>& bar){
        vector<int> res;
        int first = bar.first;. 牛人云集,一亩三分地
        int second = bar.second;. 牛人云集,一亩三分地
        for(int i = 0; i < vec.size(); i++){. From 1point 3acres bbs
                if(vec[i].first >= first && vec[i].second <= second){
                        res.push_back(vec[i].first);
                        res.push_back(vec[i].second * (-1));
                }
        }.1point3acres网
//        cout << res.size() << endl;
        sort(res.begin(), res.end(), comparator);
        int Max = INT_MIN;. 一亩-三分-地,独家发布
        int count = 0;. Waral 博客有更多文章,
        for(int i = 0; i < res.size(); i++){
                if(res[i] > 0){.本文原创自1point3acres论坛
                        count += 1;
                        Max = max(Max, count);
                }                               
                else{
                        count--;. 一亩-三分-地,独家发布
                }. visit 1point3acres for more.
        }.本文原创自1point3acres论坛
        return res.size() / 2 - Max + 1;
}

int main(){
        vector<pair<int, int>> res;
        res.push_back(make_pair(1, 20));
        res.push_back(make_pair(21, 40));
        res.push_back(make_pair(1, 99));
        res.push_back(make_pair(45, 60));
        res.push_back(make_pair(70, 80));
        res.push_back(make_pair(2, 65));
        res.push_back(make_pair(1, 101));
        pair<int, int> p = make_pair(1, 100);
        int r = find_max(res, p);
        cout << r << endl;
}


回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-23 11:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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