/*

Suppose we have an unsorted log file of accesses to web resources. Each log entry consists of an access time, the ID of the user making the access, and the resource ID. 

​

The access time is represented as seconds since 00:00:00, and all times are assumed to be in the same day.

​

Example:

logs1 = [

    ["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"],

]

​

Example 2:

logs2 = [

    ["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"]

]

​

Example 3:

logs3 = [

    ["300", "user_10", "resource_5"]

]

​

Write a function that takes the logs and returns the resource with the highest number of accesses in any 5 minute window, together with how many accesses it saw.

​

Expected Output:

most_requested_resource(logs1) # => ('resource_3', 3)

Reason: resource_3 is accessed at 53760, 54001, and 54060

​

most_requested_resource(logs2) # => ('resource_3', 4)

Reason: resource_3 is accessed at 1199, 1200, 1201, and 1202

​

most_requested_resource(logs3) # => ('resource_5', 1)

Reason: resource_5 is accessed at 300

​

Complexity analysis variables:

​

n: number of logs in the input

*/

using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    class Entry

    {

        public int timestamp;

        public string user;

        public string resource;

        public Entry(int t, string u, string r)

        {

            timestamp = t;

            user = u;

            resource = r;

        }

    }

​

    static Tuple<string, int> getHighest(Dictionary<string, int> dict)

    {

        int maxSoFar = Int32.MinValue;

        string maxKeySoFar = "";

        foreach (string key in dict.Keys)

        {

            if (dict[key] > maxSoFar)

            {

                maxKeySoFar = key;

                maxSoFar = dict[key];

            }

        }

​

        return Tuple.Create(maxKeySoFar, maxSoFar);

    }

​

    static Tuple<string, int> calculate(string[][] logs)

    {

        Dictionary<string, int> dict = new Dictionary<string, int>();

        int low = 0;

        int high = 0;

        List<Entry> entries = new List<Entry>();

        foreach (var log in logs)

        {

            Entry entry = new Entry(int.Parse(log[0]), log[1], log[2]);

            entries.Add(entry);

        }

​

        entries = entries.OrderBy(e => e.timestamp).ToList();

//      entries.ForEach(t => Console.WriteLine("{0} {1}", t.timestamp, t.resource));

​

        int n = entries.Count;

        if (!dict.ContainsKey(entries[low].resource))

            dict.Add(entries[low].resource, 0);

        dict[entries[low].resource] += 1;

        while (high + 1 < n && entries[high + 1].timestamp <= entries[low].timestamp + 300)

        {

            high += 1;

            if (!dict.ContainsKey(entries[high].resource))

                dict.Add(entries[high].resource, 0);

            dict[entries[high].resource] += 1;

        }

​

//      Console.WriteLine("High now at: {0}", high);

//      foreach(string key in dict.Keys) {

//          Console.WriteLine("{0}: {1}", key, dict[key]);

//      }

        int totalMaxSoFar = Int32.MinValue;

        string totalMaxKeySoFar = "";

        Tuple<string, int> result = getHighest(dict);

        if (result.Item2 > totalMaxSoFar)

        {

            totalMaxKeySoFar = result.Item1;

            totalMaxSoFar = result.Item2;

        }

​

        while (high + 1 < n)

        {

            dict[entries[low].resource] -= 1;

            low += 1;

//          Console.WriteLine("low {0}: {1}", low, entries[low].timestamp);

            while (high + 1 < n && entries[high + 1].timestamp <= entries[low].timestamp + 300)

            {

//              Console.WriteLine("entries[high + 1].timestamp {0}: entries[low].timestamp {1}", entries[high + 1].timestamp, entries[low].timestamp);

                high++;

                if (!dict.ContainsKey(entries[high].resource))

                    dict.Add(entries[high].resource, 0);

                dict[entries[high].resource] += 1;

            //Console.WriteLine("high {0}: {1}", high, entries[high].resource);

            }

//          foreach(string key in dict.Keys) {

//              Console.WriteLine("{0}: {1}", key, dict[key]);

//          }

            result = getHighest(dict);

            if (result.Item2 > totalMaxSoFar)

            {

                totalMaxKeySoFar = result.Item1;

                totalMaxSoFar = result.Item2;

            }

        }

​

        return Tuple.Create(totalMaxKeySoFar, totalMaxSoFar);

    }

​

    public static void Main(String[] args)

    {

        string[][] logs1 = new string[][]{new[]{"58523", "user_1", "resource_1"}, new[]{"62314", "user_2", "resource_2"}, new[]{"54001", "user_1", "resource_3"}, new[]{"200", "user_6", "resource_5"}, new[]{"215", "user_6", "resource_4"}, new[]{"54060", "user_2", "resource_3"}, new[]{"53760", "user_3", "resource_3"}, new[]{"58522", "user_22", "resource_1"}, new[]{"53651", "user_5", "resource_3"}, new[]{"2", "user_6", "resource_1"}, new[]{"100", "user_6", "resource_6"}, new[]{"400", "user_7", "resource_2"}, new[]{"100", "user_8", "resource_6"}, new[]{"54359", "user_1", "resource_3"}, };

        string[][] logs2 = new string[][]{

            new[]{"300", "user_1", "resource_3"}, 

            new[]{"599", "user_1", "resource_3"}, 

            new[]{"900", "user_1", "resource_3"}, 

            new[]{"1199", "user_1", "resource_3"}, 

            new[]{"1200", "user_1", "resource_3"}, 

            new[]{"1201", "user_1", "resource_3"}, 

            new[]{"1202", "user_1", "resource_3"}};

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

        var result = calculate(logs1);

        Console.WriteLine("logs 1 {0}: {1}", result.Item1, result.Item2);

        result = calculate(logs2);

        Console.WriteLine("logs 2 {0}: {1}", result.Item1, result.Item2);

        result = calculate(logs3);

        Console.WriteLine("logs 3 {0}: {1}", result.Item1, result.Item2);

    }

}