找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

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

[Snapchat] Snapchat 电面面经

[复制链接]

11

主题

11

精华

207

积分

高级会员

Rank: 3Rank: 3

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

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

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

x
本帖最后由 Sophia 于 10-13-2016 09:45 AM 编辑 ( J' s$ g+ e. |& Y+ U# k
" v# Y& d1 z2 L/ Z7 G+ o  j
大家好,第五次发帖。 但是UP主第四次发的帖写的很详细但是没有被评为精华,感觉很郁闷, 不知道版主看见能不能补评一个精华啊,链接如下:8 b. _5 ?, H/ t
http://www.meetqun.com/thread-27874-1-1.html  Z+ Y  U( z$ c, T) o$ m
  b  x4 }: o1 u% {" A( k  K
第五次发帖给大家分享一个UP主朋友朋友Snapchat的面经, UP主依然强势在外围观电面全过程。 题目就是非常类似于leetcode的上的第253题,meet room, 由于题目带锁,UP主就把题目贴在下面:
- q! n( U% g) T7 d! w# W% m* A. p* i& o1 c* x" `- \
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,* E) o! c% }: c! @: O
Given [[0, 30],[5, 10],[15, 20]],* N" l- w8 [! ?* K& S
return 2.
9 u+ Y6 B1 _- P0 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));
        }

+ d& c; [2 B" L. e& R+ a: P% l6 |
        Collections.sort(list);

4 p4 H5 G0 t5 e! `" @7 j- |4 o
        int count = 0, max = 0;
        for(EndPoint ep: list){
                if( !ep.isEnd ) count++;
                else count--;
8 u" D9 d2 i7 O, V3 R8 q5 L
                max = Math.max(count,max);
        }
7 q0 z9 F6 Y* L+ X% {7 N0 O$ c
        return max;
}
$ J# H, `; p8 n
class EndPoint implements Comparable<EndPoint>(
        public int val;
        public boolean isEnd;
8 l+ }! B$ \2 m3 ]% Z: _
        public EndPoint(int val, boolean isEnd){
                this.val = val;
                this.isEnd = isEnd;
        }
  z: h9 T$ A; B0 P$ ]6 t
        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;
                }
        }
)
" Q" T9 B2 N7 O. j1 |5 v/ o  K: T
望版主把UP的第四,第五篇帖评委精华,UP感激不尽T_T。。。。。
- Y5 v. Y) i, {% L- l6 G5 a' m" x
" y' Y: n& |% w$ g% Y

评分

参与人数 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分享~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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