《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4635|回复: 15
收起左侧

EA电面

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

2016(4-6月) 码农类 硕士 全职@Electronic Arts - 内推 - 技术电面 |Otherfresh 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]]似乎就是反例?.鏈枃鍘熷垱鑷1point3acres璁哄潧
显然最多可安排2个区间,答案是2.
但是按你的想法,2个“线程”就可以放下所有task,那么4-2+1=3这个答案是错的。。。

按end time排序似乎就可以。。。这里的intuition是如果end time确定,不会影响后续的安排。-google 1point3acres
假设现在已经按end time排好序,那么考察当前incoming的区间[s, e],当前总的结束时间为E,如果
1. s >= E,accept [s, e], 可安排会议数+1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
2. s < E,那么[s, e]*至少*会跟一个已经安排好的区间overlap,reject [s, e]即可
因此这样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 | 显示全部楼层
. from: 1point3acres.com/bbs
完全是不同的题=,=
回复 支持 反对

使用道具 举报

 楼主| lqzgz 发表于 2015-10-23 13:40:27 | 显示全部楼层
edly 发表于 2015-10-23 13:30
本质只有O(#Interval)个时间点,把时间点按大小关系离散化就可以了
-google 1point3acres
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)个时间点,把时间点按大小关系离散化就可以了

可否具体讲一下?谢谢了
回复 支持 反对

使用道具 举报

hurtlocker 发表于 2015-10-24 11:25:04 | 显示全部楼层
lqzgz 发表于 2015-10-23 13:40.鏈枃鍘熷垱鑷1point3acres璁哄潧
smart solution

对于楼上的理解,可否具体讲一下?我觉得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. From 1point 3acres bbs
这道题就是求最大的不重叠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>
复制代码
刚才写的,思路大概就是这有



补充内容 (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):. 鍥磋鎴戜滑@1point 3 acres
        return '[%d, %d]' %(self.start, self.end).鏈枃鍘熷垱鑷1point3acres璁哄潧
   
# `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. Waral 鍗氬鏈夋洿澶氭枃绔,
    ongoing_task = None
    . more info on 1point3acres.com
    for task in tasks:
        if task.start < time.start: continue
        if task.end > time.end: break. visit 1point3acres.com for more.
        if not ongoing_task or task.start >= ongoing_task.end:. From 1point 3acres bbs
            rst += 1.1point3acres缃
            ongoing_task = task
   
    print rst. 鍥磋鎴戜滑@1point 3 acres


tasks = [Interval(1,50), Interval(51,100), Interval(1,99)]
time = Interval(1,100)
. 1point3acres.com/bbs
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.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9.     }
  10.     public static int maxTask(Interval[] intervals, Interval total) {
  11.         int res = 0;
    . From 1point 3acres bbs
  12.         // dp[i] - until ith interval, maximum tasks
  13.         List<Integer> dp = new ArrayList<>();. visit 1point3acres.com for more.
  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);
  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);. 鍥磋鎴戜滑@1point 3 acres
  37.         Interval i2 = new Interval(51, 100);
  38.         Interval i3 = new Interval(1, 20);
  39.         Interval i4 = new Interval(30, 40);. from: 1point3acres.com/bbs
  40.         Interval i5 = new Interval(40, 50);
  41.         Interval i6 = new Interval(80, 90);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;. more info on 1point3acres.com
  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>
#include <vector>
#include <utility>
#include <cmath>
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);
        }
}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++){. 鍥磋鎴戜滑@1point 3 acres
                if(vec[i].first >= first && vec[i].second <= second){. 1point 3acres 璁哄潧
                        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++){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if(res[i] > 0){
                        count += 1;
                        Max = max(Max, count);
                }                               
                else{
                        count--;
                }
        }
        return res.size() / 2 - Max + 1;
}

int main(){. 1point 3acres 璁哄潧
        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;
}

.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-20 23:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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