西雅图2019年初买房安家各种坑分享帖

一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


中国数据智能独角兽企业
坐标杭州 | 个推诚聘
数据/算法/分析/研发等岗位

码农求职神器Triplebyte
不用海投
内推多家公司面试

科技公司如何
用数据分析驱动产品开发
$366 off coupon code: best

深入浅出AB Test
从入门到精通
$366 off coupon code: best

E轮2.5亿美元融资
一起作业诚聘
机器学习/数据/教育等职位
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
123
返回列表 发新帖
楼主: rayluck4
收起左侧

google两轮电面

[复制链接] |试试Instant~
我的人缘0
RainCrush 发表于 2018-11-15 03:31:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (17)
 
 
0% (0)  踩
rayluck4 发表于 2018-11-12 08:29
我是说了一个 N*K*K的算法,也不知道对不对,就当抛块砖来引玉吧。
我忘记说了, 两个list都是已经排好 ...

我感觉既然是follow up, 那么应该很有可能是利用已经之前只有2个人的算法,我感觉应该是这样的(类似merge k lists):
修改2个人的算法使之返回所有可能的区间,然后result[1,2] 和 list3做相同的操作, result[1,2,3] 和list4做相同的操作....最后返回的的结果就是答案.
回复 微信

使用道具 举报

我的人缘0
lovemyisa 发表于 2018-11-21 03:17:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (69)
 
 
4% (3)  踩
我的思路。
[Java] 纯文本查看 复制代码
class Endpoint{
    int time;
    boolean isend;
    List<Integer> range;
    public Endpoint(int time, List<Integer> range){
        this.time = time;
        isend = false;
        this.range = range;
    }
}
class Solution{
    public List<Integer> findMeetingTime(List<List<Integer>> list1, List<List<Integer>> list2, int T){
        List<Integer> res = new ArrayList<>();
        List<Endpoint> list = new ArrayList<>();
        for(List<Integer> ele : list1){
            Endpoint ep1 = new Endpoint(ele.get(0),ele);
            Endpoint ep2 = new Endpoint(ele.get(1),ele);
            ep2.isend = true;
            list.add(ep1);
            list.add(ep2);
        }
        for(List<Integer> ele : list2){
            Endpoint ep1 = new Endpoint(ele.get(0),ele);
            Endpoint ep2 = new Endpoint(ele.get(1),ele);
            ep2.isend = true;
            list.add(ep1);
            list.add(ep2);
        }
        Collections.sort(list, (a, b)->(a.time - b.time));
        int pool = 0;
        Endpoint prev = null;
        for(Endpoint cur : list){
            if(!cur.isend) pool++;
            else{
                pool--;
            }
            if(pool == 2 ){
                int start = Math.max(prev.range.get(0), cur.range.get(0));
                int end = Math.min(prev.range.get(1), cur.range.get(1));
                if(end - start >= T){
                    res.add(start);
                    res.add(end);
                    return res;
                }
            }
            prev = cur;
        }
        return res;
    }
// follow up K 人:
K 个人-> pool size == k
 int i = 0;
 while(i < list.size()){
    int pool = 0;
    int endmin = Integer.MAX_VALUE;
    for(int j = 0; j < k; j++){
        if(!list.get(j).isend) pool++;
        else{
            endmin = Math.min(endmin, list.get(j).time);
            pool--;
        }
        if(pool == k){
            res.add(list.get(j).time);
            res.add(endmin);
            return res;
        }
    }
 }   
   public static void main(String[] args){
        Solution test = new Solution();
        List<List<Integer>> l1 = new ArrayList<>();
        List<Integer> range = new ArrayList<>();
        range.add(1);range.add(3); l1.add(range);
        range = new ArrayList<>(); range.add(6); range.add(9);l1.add(range);
        range = new ArrayList<>(); range.add(12); range.add(15);l1.add(range);
        List<List<Integer>> l2 = new ArrayList<>();
        range = new ArrayList<>();
        range.add(4);range.add(5); l2.add(range);
        range = new ArrayList<>(); range.add(7);range.add(10); l2.add(range);
        range = new ArrayList<>(); range.add(11);range.add(16); l2.add(range);
        List<Integer> res = test.findMeetingTime(l1, l2, 2);
        System.out.println(res.get(0) + " " + res.get(1));

    }
}

评分

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

查看全部评分

回复

使用道具 举报

我的人缘0
Self_Learner 发表于 2018-11-26 06:13:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (121)
 
 
2% (3)  踩
rayluck4 发表于 2018-11-12 08:29
我是说了一个 N*K*K的算法,也不知道对不对,就当抛块砖来引玉吧。
我忘记说了, 两个list都是已经排好 ...

楼主这个思路很好,可以改进的第一是用另一个maxHeap来存放对应的start time,但minEnd - maxStart >= T的时候说明可以找到interval,不然的话,就从两个heap当中pop minEnd 对应的那个人时间,然后插入他的下一个interval,重复比较即可。复杂度是O(N * K * log(K))...这题感觉用indexedPriorityQueue做会很方便,不过java里没有这个数据结构,用普通的priority queue应该也能做,会稍微复杂一点。

另外,楼主follow up 2又啥思路吗?
回复

使用道具 举报

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

本版积分规则

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

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

手机版|小黑屋|一亩三分地

GMT+8, 2019-3-18 21:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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