字节后端java面试算法题

最近面试了字节跳动-抖音直播部门的后端开发岗位

记录其中的算法面试题-

bytedance

有登录日志，计算一天中用户在线的峰值和持续时间

当时没有想出好的解决办法，思路是维护一个最大动态窗口，维护在这个窗口里面的最多的人数，有了这个思路，但是具体细节没有完善，后来想想这个可能不好实现。

看了网上的解决办法，其中之一是开辟一个86400的数组，数组中数值代表当前在线人数

步骤：

1. 遍历日志记录

2..遇到登录时间，就在对应时间点+1，遇到退出时间，就在对应时间点-1

3.再开辟一个86400数组，记录当前时间点的在线人数

4.遍历登录记录，更新在线人数数组，维护最大在线人数

实现

private int getMaxOnlineUsers(List<UserLoginRecord> records){

    Calendar cal = Calendar.getInstance();

    cal.set(Calendar.HOUR_OF_DAY, 0);

    cal.set(Calendar.SECOND, 0);

    cal.set(Calendar.MINUTE, 0);

    cal.set(Calendar.MILLISECOND, 0);

    Long startTimeDay = cal.getTimeInMillis()/1000;

    // 登入登出记录

    int[] logRecord =new int[86400];

    // 每一秒钟的在线人数

    int[] onlineUserRecord =new int[86400];

    for (UserLoginRecord record: records) {

        logRecord[(int)(record.getLoginTime()-startTimeDay)]+=1;

        logRecord[(int)(record.getLogoutTime()-startTimeDay)]-=1;

    }

    onlineUserRecord[0] = logRecord[0];

    int maxOnline =0;

    for (int i =1; i <86400; i++) {

        onlineUserRecord[i] = onlineUserRecord[i-1]+logRecord[i];

        maxOnline = Math.max(maxOnline,onlineUserRecord[i]);

    }

    return maxOnline;

}