resource Access with in 5 min

http://202.79.172.224/id/880895

给了 list of <usr_id, resource_id, time_stamp>

问每个 resource 被访问了多少

follow up 返回那个5分钟内被访问最多的resource id 和次数

--请问 follow-up， 是把每个resource的ts先sort, 然后for loop 每个ts, 利用binary search找到五分钟内的最大index，然后求得此时的个数, 最后依次update max吗？

--用 queue 然后每次append的时候 check head 根据情况pop

----------------------------------------------------------------------------------------------

有一些资源的使用记录 比如 [{"ts": xxx, "user": xxx, "resource": xxx}. {"ts": xxx, "user": xxx, "resource": xxx}. {"ts": xxx, "user": xxx, "resource": xxx}. ] 然后目标是找到每一个resource 一定时间长度内 最多被使用了多少次 比如 我们有 r1: 10 11 12 20 25 r2: 5 10 15 20 21 22 然后让找5个ts内的 那么 r1: 3 (10-11-12) r2: 3 (20-21-22)

第二题同样的data 要返回 一个图一样的结构，大概是 reource： 到可能别的reso‍‍‌‌‍‌‍‌‍‌‍‍‌‍‍‌‍‌‌‍urce的可能性,这个是根据user来算的，基本就是一个反向bfs这样，时间不够了没做出来

--------------------------------------------------------------------------------------------------

输入是一串<时间(秒)，用户id，资源id>，返回时间窗口为5分钟的被访问次数最多的资源。题目不难，但是有两个坑：输入是没有按照时间排序的；五分钟的定义是：0-300 秒，N‍‍‌‍‌‍‌‌‍‍‌‍‌‌‍‌‍‌‍‍OT 0-299秒。我掉到第一个坑里，有个测试案例没通过，时间结束了才意识到。

------------------------------------------------------------

https://leetcode.com/discuss/interview-question/1695307/wayfair-karat-userlogsearliestandlatestaccesstime-java-and-javascript-coding-question

public class Solution {
public static void main(String[] args) {
    String[][] logs1 = new String[][] {
            { "58523", "user_1", "resource_1" },
            { "62314", "user_2", "resource_2" },
            { "54001", "user_1", "resource_3" },
            { "200", "user_6", "resource_5" },
            { "215", "user_6", "resource_4" },
            { "54060", "user_2", "resource_3" },
            { "53760", "user_3", "resource_3" },
            { "58522", "user_22", "resource_1" },
            { "53651", "user_5", "resource_3" },
            { "2", "user_6", "resource_1" },
            { "100", "user_6", "resource_6" },
            { "400", "user_7", "resource_2" },
            { "100", "user_8", "resource_6" },
            { "54359", "user_1", "resource_3"},
            };
   String[][] logs2 = new String[][] {
            {"300", "user_1", "resource_3"},
            {"599", "user_1", "resource_3"},
            {"900", "user_1", "resource_3"},
            {"1199", "user_1", "resource_3"},
            {"1200", "user_1", "resource_3"},
            {"1201", "user_1", "resource_3"},
            {"1202", "user_1", "resource_3"}
    };

    String[][] logs3 = new String[][] {
            {"300", "user_10", "resource_5"}
    };

    System.out.println(mostRequestedResource(logs1));
    System.out.println(mostRequestedResource(logs2));
    System.out.println(mostRequestedResource(logs3));

}

private static List<String> mostRequestedResource(String[][] logs) {
    Map<String,ArrayList<Integer>> accessMap = new HashMap<>();
    for (String[] entry : logs) {
        Integer accessTime = Integer.parseInt(entry[0]);
        String resourceId = entry[2];
        if (accessMap.containsKey(resourceId)) {
            var exList = accessMap.get(resourceId);
            exList.add(accessTime);
            accessMap.put(resourceId, exList);
        } else {
            ArrayList<Integer> newList = new ArrayList<>();
            newList.add(accessTime);
            accessMap.put(resourceId, newList);
        }
    }
    String maxResource = "";
    Integer maxWindowTime = 0;
    for (var entry : accessMap.entrySet()) {
        Integer entryTime = windowCount(entry.getValue(), 300);
        if (entryTime > maxWindowTime) {
            maxResource = entry.getKey();
            maxWindowTime = entryTime;
        }
    }
    List<String> result = new ArrayList<>();
    result.add(maxResource);
    result.add(maxWindowTime.toString());
    return result;
}

private static Integer windowCount(ArrayList<Integer> accessTimes, Integer window) {
    Collections.sort(accessTimes);
    int maxWindowTime = 0;
    for (Integer testVal : accessTimes) {
        List<Integer> timesInWindow = accessTimes.stream()
                .filter(val -> val >= testVal)
                .filter(val -> val <= (testVal + window)).toList();
        int testWindowTime = timesInWindow.size();
        maxWindowTime = Integer.max(maxWindowTime, testWindowTime);
    }
    return maxWindowTime;
}

Version 2:

    static Response getMaximumAccesses(String[][] logs) {

        Arrays.sort(logs, Comparator.comparing(arr -> Long.valueOf(arr[0])));
        int max = Integer.MIN_VALUE;
        Response res = null;
        for (int i = 0; i < logs.length; i++) {
            Map<String, Integer> count = new HashMap<>();
            String[] prevLogs = logs[i];
            long prevTime = Long.parseLong(prevLogs[0]);
            count.put(prevLogs[2], 1);
            res = (res == null) ? new Response(prevLogs[2], 1) : res;
            for (int j = i + 1; j < logs.length; j++) {
                String[] curLogs = logs[j];
                long curTime = Long.parseLong(curLogs[0]);
                if (curTime <= prevTime + 300) {
                    int curCount = count.getOrDefault(curLogs[2], 0) + 1;
                    count.put(curLogs[2], curCount);
                    if (curCount > max) {
                        max = curCount;
                        res = new Response(curLogs[2], max);
                    }
                } else {
                    break;
                }
            }
        }
        return res;
    }


}


class Response {
    String resource;
    int accesses;

    Response(String resource, int accesses) {
        this.accesses = accesses;
        this.resource = resource;
    }

    @Override
    public String toString() {
        return "Response{" +
                "resource='" + resource + '\'' +
                ", accesses=" + accesses +
                '}';
    }
}