找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3987|回复: 5
收起左侧

[Snapchat] Snapchat 电面面经

[复制链接]

11

主题

11

精华

207

积分

高级会员

Rank: 3Rank: 3

积分
207
发表于 10-12-2016 07:08 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

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

x
本帖最后由 Sophia 于 10-13-2016 09:45 AM 编辑 7 D3 Q/ \- H9 v+ x" b
. B! `8 `1 S5 z$ V+ T4 H
大家好,第五次发帖。 但是UP主第四次发的帖写的很详细但是没有被评为精华,感觉很郁闷, 不知道版主看见能不能补评一个精华啊,链接如下:& {* |; O: t- l4 z" b. A* z
http://www.meetqun.com/thread-27874-1-1.html
& F8 z1 a7 ~7 C1 h, O; E* }4 L0 E1 \
第五次发帖给大家分享一个UP主朋友朋友Snapchat的面经, UP主依然强势在外围观电面全过程。 题目就是非常类似于leetcode的上的第253题,meet room, 由于题目带锁,UP主就把题目贴在下面:
6 ^% o! f) T" S% c3 F' f; L$ v7 A" h+ t" O8 L
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
For example,) e3 J' W# n# `6 G, w9 R7 ?
Given [[0, 30],[5, 10],[15, 20]],
; d# B% [* v$ ?3 F5 Breturn 2.

7 t" P+ D0 B$ T1 |0 D4 y- s6 V
据说这题Snapchat已经考过很多次了,但是UP主朋友由于是第一次写,尽管写出来了,但是由于耗时较长,所以并没有拿到onsite。 那么久这道题本身而言, 咱来分析一下。 meet room 的本质就是要计算出在所有interval相交数量的最大值。 那么一个基本的思路就可以是先将所有的interval 按照其起始点来sort一遍。遇见一个起始点,那么room的数量就得+1。 如果碰到一个结束点,那么room的数量就-1,保留一个room的最大值。 这是最基本的思路,但是这题的难点在于对tie的处理,就是在一个会议刚刚结束的时候,另一个会议开始。  话不多说,code如下:
public int minMeetingRooms(Interval[] intervals){
        if(intervals == null) return 0;
        List<EndPoint> list = new ArrayList<EndPoint>();
        for ( interval i : intervals) {
                list.add(new EndPoint(i.start,false));
                list.add(new EndPoint(i.end,true));
        }
' ]. ~6 u9 \9 v# V
        Collections.sort(list);

7 u( h; l1 Z- q  d2 U) W
        int count = 0, max = 0;
        for(EndPoint ep: list){
                if( !ep.isEnd ) count++;
                else count--;

- f8 N' `7 \- E5 m
                max = Math.max(count,max);
        }

* ?6 i1 K: w2 ~" l' C  `
        return max;
}

' f. F! {5 A$ ^3 s( e. X% q2 w
class EndPoint implements Comparable<EndPoint>(
        public int val;
        public boolean isEnd;

6 p0 ^5 j, n9 b( `/ r% M- a
        public EndPoint(int val, boolean isEnd){
                this.val = val;
                this.isEnd = isEnd;
        }

2 m- c& g0 F: J; w9 a& D8 l; i
        public int compareTo(EndPoint ep){
                if ( this.val < ep.val ) return -1;
                else if(this.val > ep.val) return 1;
                else {
                        if(this.isEnd) return -1;
                        else return -1;
                }
        }
)

% m9 y& b* D8 }% B- r! ?) Q! t
望版主把UP的第四,第五篇帖评委精华,UP感激不尽T_T。。。。。
; x  v6 ~2 n) A1 j- `
" g+ Z' f6 H8 x3 s0 F

评分

参与人数 1金钱 +6 收起 理由
Sophia + 6 精华帖子!大赞!

查看全部评分

781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 10-12-2016 07:55 AM | 显示全部楼层
精华帖子!大赞!

0

主题

0

精华

1

积分

新米人

Rank: 1

积分
1
发表于 10-12-2016 04:54 PM 来自美国米群网手机版 | 显示全部楼层
感谢liu452分享~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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