一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 2498|回复: 10
收起左侧

SnapChat Full-Time 电面

[复制链接] |试试Instant~ |关注本帖
tj474474 发表于 2016-10-20 10:45:47 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Snapchat - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
今天下午的电面是一个国人小哥先聊了15分钟他的组 还有履历上的东西. 鍥磋鎴戜滑@1point 3 acres
然后就做题
Meeting Room ll的变化版. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不是计算最少需要几个meeting room
还要把schedule的结果列出来
例如
Inputs: Meetings, [4, 9], [2, 6], [2, 3], [6, 7]
Outputs:
Room1 : [2, 3], [4, 9]
Room2 : [2, 6], [6, 7]
. from: 1point3acres.com/bbs
我的做法是先把所有的schedule根据start time sort
同时还用了一个PriorityQueue .鏈枃鍘熷垱鑷1point3acres璁哄潧
顺序是根据schedule的end time.

PriorityQueue的Node我还多放了一个该event被存放的roomId. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这样从PrioirtyQueue里面pop出来的时候就可以直接找到需要添加的room
我的面試官挺好的 因為我提出這個做法
他直接就跟我說那你input就用你這個List<Node>吧

不过最后compile有个小bug
因为时间到了没弄完
还是希望有onsite.... 鍥磋鎴戜滑@1point 3 acres
附上代碼
  1. import java.util.*;

  2. class Node {.1point3acres缃
  3.     public int roomId;
  4.     public List<Integer> interview;
  5.     public Node(List<Integer> interview) {
  6.         this.interview = interview;
  7.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8. }
  9. . more info on 1point3acres.com
  10. class Solution {
  11.     static void schedule(List<Node> interviews) {
  12.         List<List<List<Integer>>> result = new ArrayList<>();
  13.         PriorityQueue<Node> pq = new PriorityQueue(1, new Comparator<Node>(){
  14.             @Override
  15.             public int compare(Node a, Node b) {-google 1point3acres
  16.                 return a.interview.get(1) - b.interview.get(1);
  17.             }
  18.         });
  19.         -google 1point3acres
  20.         Collections.sort(interviews, new Comparator<Node>(){
  21.             @Override
  22.             public int compare(Node a, Node b) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.                 return a.interview.get(0) - b.interview.get(0);. 1point 3acres 璁哄潧
  24.             }. 鍥磋鎴戜滑@1point 3 acres
  25.         });. 1point 3acres 璁哄潧
  26.         
  27.         int roomCount = 0;. 鍥磋鎴戜滑@1point 3 acres
  28.         for (Node n : interviews) {
  29.             if (pq.isEmpty()) {
  30.                 n.roomId = roomCount; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  31.                 result.add(new ArrayList<>());
  32.                 result.get(roomCount).add(n.interview);
  33.                 pq.offer(n);
  34.             } else {
  35.                 Node prevNode = pq.peek();
  36.                 if (n.interview.get(0) < prevNode.interview.get(1)) {
  37.                     roomCount++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  38.                     n.roomId = roomCount;
  39.                     result.add(new ArrayList<>());. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  40.                     result.get(roomCount).add(n.interview);. more info on 1point3acres.com
  41.                     pq.offer(n);
  42.                 } else {
  43.                     pq.poll();
  44.                     int prevRoomId = prevNode.roomId;
  45.                     n.roomId = prevRoomId;
  46.                     result.get(prevRoomId).add(n.interview);
  47.                     pq.offer(n);
  48.                 }
  49.             }. 1point 3acres 璁哄潧
  50.         }
  51.         for (int i = 0; i < result.size(); ++i) {
  52.             System.out.print("Room");. visit 1point3acres.com for more.
  53.             System.out.print(i + 1);
  54.             System.out.print(": ");
  55.             for (int j = 0; j < result.get(i).size(); ++j) {
  56.                 System.out.print("[");
  57.                 System.out.print(result.get(i).get(j).get(0));
  58.                 System.out.print(", ");
  59.                 System.out.print(result.get(i).get(j).get(1));. 1point3acres.com/bbs
  60.                 System.out.print("]");. visit 1point3acres.com for more.
  61.                 if (j < result.get(i).size() - 1) {-google 1point3acres
  62.                     System.out.print(", "); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  63.                 } else {. 1point 3acres 璁哄潧
  64.                     System.out.print("\n");
  65.                 }
  66.             }
  67.         }. more info on 1point3acres.com
  68.     }
  69.    
  70.     static public void main(String args[]) {
  71.         //[4, 9], [2, 6], [2, 3], [6, 7]
  72.         Node n1 = new Node(Arrays.asList(4, 9));
  73.         Node n2 = new Node(Arrays.asList(2, 6));
  74.         Node n3 = new Node(Arrays.asList(2, 3));
  75.         Node n4 = new Node(Arrays.asList(6, 7));
  76.         List<Node> input = Arrays.asList(n1, n2, n3, n4);
  77.         schedule(input);
  78.     }   
  79. }
复制代码

评分

2

查看全部评分

本帖被以下淘专辑推荐:

zwcelesta 发表于 2016-10-20 20:44:36 | 显示全部楼层
    public Queue<LinkedList<Interval>> scheduledRooms (List<Interval> meetings) {
        Queue<LinkedList<Interval>> q = new PriorityQueue<>((o1, o2) -> o1.getLast().end - o2.getLast().end);
        Collections.sort(meetings, (o1, o2) -> o1.start == o2.start ? o1.end - o2.end : o1.start - o2.start);
. Waral 鍗氬鏈夋洿澶氭枃绔,        for (Interval meeting : meetings) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
            LinkedList<Interval> room = (q.isEmpty() || meeting.start < q.peek().getLast().end) ? new LinkedList<>() : q.poll();
            room.add(new Interval(meeting.start, meeting.end));
            q.offer(room);
        }
        while (!q.isEmpty()) {
            List<Interval> room = q.poll();
            room.forEach(i -> System.out.print("[" + i.start + "," + i.end + "], "));
            System.out.println(" ");
        }
        return q;
    }
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

1

查看全部评分

回复 支持 4 反对 0

使用道具 举报

edyyy 发表于 2016-10-20 11:43:48 | 显示全部楼层
谢谢楼主分享,祝好运
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-20 22:40:31 | 显示全部楼层
zwcelesta 发表于 2016-10-20 20:44
public Queue scheduledRooms (List meetings) {
        Queue q = new PriorityQueue((o1, o2) -> o ...
. visit 1point3acres.com for more.
好简洁的方法!把LinkedList直接拿来当PriorityQueue的Key
还有Java 8的语法让代码看起来简单多了看来得多学学
回复 支持 反对

使用道具 举报

linweihua0 发表于 2016-10-21 03:02:54 | 显示全部楼层
zwcelesta 发表于 2016-10-20 20:44. visit 1point3acres.com for more.
public Queue scheduledRooms (List meetings) {
        Queue q = new PriorityQueue((o1, o2) -> o ...

这个 你还得考虑merge interval  [1,2] [2,4] -> [1,4]
回复 支持 反对

使用道具 举报

telepathy 发表于 2016-10-31 11:36:17 | 显示全部楼层
楼主我也面倒了这题!可惜没提前看到你的帖子。求问面完多久收到结果啊?
回复 支持 反对

使用道具 举报

pocketnail 发表于 2016-10-31 11:45:46 | 显示全部楼层
我第一轮也是面了这道题,当时也是出了小bug,但也过了,楼主加油!
回复 支持 反对

使用道具 举报

freemail165 发表于 2016-10-31 12:35:41 | 显示全部楼层
linweihua0 发表于 2016-10-21 03:02. 1point3acres.com/bbs
这个 你还得考虑merge interval  [1,2] [2,4] -> [1,4]

题目没要求merge.. from: 1point3acres.com/bbs
上面这个解法的问题是不能按room的使用顺序来输出。

不知道题目是否要求
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-31 12:40:07 | 显示全部楼层
telepathy 发表于 2016-10-31 11:36
楼主我也面倒了这题!可惜没提前看到你的帖子。求问面完多久收到结果啊?

兩天後收到結果 被拒了
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-31 12:40:43 | 显示全部楼层
pocketnail 发表于 2016-10-31 11:45. 1point 3acres 璁哄潧
我第一轮也是面了这道题,当时也是出了小bug,但也过了,楼主加油!

謝謝啦 不過我還是被拒了 可能bug的嚴重程度不一樣吧
回复 支持 反对

使用道具 举报

 楼主| tj474474 发表于 2016-10-31 12:41:03 | 显示全部楼层
freemail165 发表于 2016-10-31 12:35.鐣欏璁哄潧-涓浜-涓夊垎鍦
题目没要求merge.
上面这个解法的问题是不能按room的使用顺序来输出。

題目沒有要求要照順序輸出
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-18 02:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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