讨论Bloomberg onsite OOD题目

Job Hunting Interview
, , ,
1

设计地铁系统，每张地铁卡有一个ID，然后有很多不同的站，设计一个class求两站之间平均travel的时间，问了一些类似于万一刷卡进站了但是没有刷卡出站的话怎么办之类的问题。

2

首先看下这个class该有哪些field，即属性

3

可以入群讨论

mmqrcode1553360092802
mmqrcode1553360092802.png1080×1592 146 KB

4

这个感觉不需要某个用户的地铁卡就可以算吧

5

大概是这样，不知道理解得对不对， 定义一个MetroSystem class 和 一个 MetroStation class。MetroStation 用两个map in, out 分别存储出入站的时间。MetroSystem 包含若干MetroStation ， 统计扫描出站人数，及出入站时间差总和，得到平均travel时间。

public class MetroSystem {
    private List<MetroStation> stations = new LinkedList<>();

    public void buildAndAddStation(MetroStation station) {
        stations.add(station);
    }

    public long getAverageTravelTime(MetroStation source, MetroStation destination) {
        long usedTime = 0;
        Set<Integer> exitIds = destination.getExitIds();
        if (exitIds.isEmpty()) {
            return 0;
        }
        for (int id : exitIds) {
            usedTime += destination.getExitTimestamp(id) - source.getEnterTimestamp(id);
        }
        return usedTime / exitIds.size();
    }
}

public class MetroStation {
    private int stationId;
    private String stationName;
    private Map<Integer, Long> in = new HashMap<>(); // card id -> enter timestamp
    private Map<Integer, Long> out = new HashMap<>(); // card id -> exit timestamp

    public MetroStation(int stationId, String stationName) {
        this.stationId = stationId;
        this.stationName = stationName;
    }

    public void enter(int id) throws AlreadyEnteredException {
        if (in.containsKey(id)) {
            throw new AlreadyEnteredException("Already entered the station");
        }
        in.put(id, System.currentTimeMillis());
    }

    public void exit(int id) throws Exception {
        if (in.containsKey(id)) {
            throw new AlreadyEnteredException("Can not exit the station because you didn't enter");
        }
        out.put(id, System.currentTimeMillis());
    }

    public Set<Integer> getEnterIds() {
        return in.keySet();
    }
    public Set<Integer> getExitIds() {
        return out.keySet();
    }
    public long getEnterTimestamp(int id) {
        return in.get(id);
    }
    public long getExitTimestamp(int id) {
        return out.get(id);
    }
}
6

Bloomberg OOD题目 微信群上的聊天记录如下，请查收。

————— 2019-03-23 —————

A 11:07

Travel时间应该是指行人所用的时间 要包括入站 等车之类的时间吧

L. 11:07

这个面经的问题不是很清楚，感觉是这个人坐一次坐多久？

X 11:07

题意确实不清

A 11:07

高峰时段和闲时应该是不一样的travel时间 让算平均 不是车跑几站的时间

X 11:08

从use case来说，只能记录入站和出站时间吧

B 11:08

看到过类似的面经，就是要实现进站出站和计算两站之间average的travel时间

B 11:09

用一两个hashmap就可以了

Kevin 19:03

用Map<Integer,TreeSet>按id記下所有start和end event的時間。然後filter掉不完整的event，然後按每一個完整的start-end pair, 計算距離/時間；最後整合出結果

X 19:04

你还得记录站吧，要计算某个站的数据吧

Kevin 19:08

Event裡包括了location了

Kevin 19:09

要不然怎能計算距離

X 19:12

不光是距离吧，题目貌似要每个站之间的耗时

C 19:13

应该只需要算时间/站数就行了

C 19:13

不需要距离吧

C 19:14

每张票有一个平均时间，然后统合起来所有的票，求总共的平均时间

7

有 destination.getExitTimestamp(id) 的一定有对应 source 的 id 进入吗？

MetroStation source, MetroStation destination => 你要筛选掉 一些 id 不在 source 入站的吧