最近面试了字节跳动-抖音直播部门的后端开发岗位
记录其中的算法面试题-
有登录日志，计算一天中用户在线的峰值和持续时间
当时没有想出好的解决办法，思路是维护一个最大动态窗口，维护在这个窗口里面的最多的人数，有了这个思路，但是具体细节没有完善，后来想想这个可能不好实现。
看了网上的解决办法，其中之一是开辟一个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;
}
