推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4363|回复: 15
收起左侧

EA电面

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

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

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

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

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


祝大家offer多多!
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

1

查看全部评分

本帖被以下淘专辑推荐:

小柯西 发表于 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)个时间点,把时间点按大小关系离散化就可以了
. 1point 3acres 璁哄潧
可否具体讲一下?谢谢了
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

这道题就是求最大的不重叠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):
  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>
复制代码
刚才写的,思路大概就是这有
. From 1point 3acres bbs


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

使用道具 举报

小柯西 发表于 2015-10-24 12:55:27 | 显示全部楼层
class Interval(object):
    def __init__(self, start, end): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        self.start = start
        self.end = end
   
    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.
def maxTaskNum(tasks, time):
    tasks.sort(key=lambda i: i.end)
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    rst = 0
    ongoing_task = None. more info on 1point3acres.com
   
    for task in tasks:
        if task.start < time.start: continue. From 1point 3acres bbs
        if task.end > time.end: break
        if not ongoing_task or task.start >= ongoing_task.end:
            rst += 1
            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感觉没什么问题,如果小伙伴们发现有错误,欢迎指出:). from: 1point3acres.com/bbs
  1. public class test {
  2.     static class Interval {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  3.         int start;
  4.         int end;
  5.         public Interval(int start, int end) {
  6.             this.start = start;
  7.             this.end = end;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.         }. From 1point 3acres bbs
  9.     }
  10.     public static int maxTask(Interval[] intervals, Interval total) {
  11.         int res = 0; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.         // dp[i] - until ith interval, maximum tasks
  13.         List<Integer> dp = new ArrayList<>();
  14.         Arrays.sort(intervals, new Comparator<Interval>() {
  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) {
  26.                     if (dp.get(j) + 1 > dp.get(i)) {
  27.                         dp.set(i, dp.get(j) + 1);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.                         res = Math.max(res, dp.get(i));
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.         return res;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.     }
  35.     public static void main(String args[]){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  36.         Interval i1 = new Interval(1, 50);. 1point3acres.com/bbs
  37.         Interval i2 = new Interval(51, 100);
  38.         Interval i3 = new Interval(1, 20);
  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);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  43.         Interval[] is = new Interval[7];. more info on 1point3acres.com
  44.         is[0] = i1;
  45.         is[1] = i2;
  46.         is[2] = i3;
  47.         is[3] = i4;
  48.         is[4] = i5;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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就是最后要的结果了 代码如下:

. From 1point 3acres bbs
#include <iostream>
#include <vector> 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
#include <utility>
#include <cmath>. From 1point 3acres bbs
using namespace std;
struct cmp{.鐣欏璁哄潧-涓浜-涓夊垎鍦
        bool operator()(int a, int b){
                if(abs(a) == abs(b))
                        return a < b;
鏉ユ簮涓浜.涓夊垎鍦拌鍧.                 else
                        return abs(a) < abs(b);
        }. Waral 鍗氬鏈夋洿澶氭枃绔,
}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++){
                if(vec[i].first >= first && vec[i].second <= second){
                        res.push_back(vec[i].first);
                        res.push_back(vec[i].second * (-1));
                }
        }
//        cout << res.size() << endl;
        sort(res.begin(), res.end(), comparator);
        int Max = INT_MIN;
        int count = 0;
        for(int i = 0; i < res.size(); i++){
                if(res[i] > 0){.1point3acres缃
                        count += 1;
                        Max = max(Max, count);
                }                               
                else{
. From 1point 3acres bbs                        count--;
                }
        }.鏈枃鍘熷垱鑷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);-google 1point3acres
        cout << r << endl;
}. visit 1point3acres.com for more.

-google 1point3acres
回复 支持 反对

使用道具 举报

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

这个有sort了至少是nlgn吧。。。. more info on 1point3acres.com

代码没仔细看,但是按照你叙述的思路,[[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]即可
因此这样iterate并且安排区间,从头到尾是“不会亏”的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-18 03:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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