Example:
Input: logs = ["1", "user_1", "resource_1"], ["3", "user_2", "resource_2"], ["4", "user_1", "resource_3"], ["7", "user_2", "resource_3"], ["8", "user_1", "resource_3"] Output: [resource_1, resource_3, resource_3]
Approach: If you see this problem is similar to designing data structure with increment, decrement, max and min at constant time. We can mix sliding window approach with it to solve this problem.
Implementation in C#:
private static void PrintMaxOfEvery5Mins(Log[] logs)
{
Array.Sort(logs, (l1, l2) => {
return l1.Timestamp.CompareTo(l2.Timestamp);
});
Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap = new Dictionary<string, LinkedListNode<int>>();
Dictionary<int, HashSet<string>> freqToResourcesMap = new Dictionary<int, HashSet<string>>();
LinkedList<int> frequenciesList = new LinkedList<int>();
Queue<Log> queue = new Queue<Log>();
foreach(var log in logs)
{
if (queue.Count > 0 && log.Timestamp - queue.Peek().Timestamp >= 5)
{
Console.WriteLine(GetMaxOf5Mins(freqToResourcesMap, frequenciesList));
while (queue.Count > 0 && log.Timestamp - queue.Peek().Timestamp >= 5)
{
DecrementCount(queue.Dequeue().Resource, resourceToFreqNodeMap, freqToResourcesMap, frequenciesList);
}
}
queue.Enqueue(log);
IncrementCount(log.Resource, resourceToFreqNodeMap, freqToResourcesMap, frequenciesList);
}
if (queue.Count > 0)
{
Console.WriteLine(GetMaxOf5Mins(freqToResourcesMap, frequenciesList));
}
}
private static void IncrementCount(string resource,
Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap,
Dictionary<int, HashSet<string>> freqToResourcesMap,
LinkedList<int> frequenciesList)
{
if (!resourceToFreqNodeMap.ContainsKey(resource))
{
AddResource(resource, resourceToFreqNodeMap, freqToResourcesMap, frequenciesList);
}
else
{
IncResourceCount(resource, resourceToFreqNodeMap, freqToResourcesMap, frequenciesList);
}
}
private static void AddResource(string resource,
Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap,
Dictionary<int, HashSet<string>> freqToResourcesMap,
LinkedList<int> frequenciesList)
{
if (!freqToResourcesMap.ContainsKey(1))
{
freqToResourcesMap[1] = new HashSet<string>();
frequenciesList.AddFirst(1);
}
freqToResourcesMap[1].Add(resource);
resourceToFreqNodeMap[resource] = frequenciesList.First;
}
private static void IncResourceCount(string resource,
Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap,
Dictionary<int, HashSet<string>> freqToResourcesMap,
LinkedList<int> frequenciesList)
{
var freqNode = resourceToFreqNodeMap[resource];
int currCount = freqNode.Value;
int newCount = currCount + 1;
if (!freqToResourcesMap.ContainsKey(newCount))
{
freqToResourcesMap[newCount] = new HashSet<string>();
frequenciesList.AddAfter(freqNode, newCount);
}
freqToResourcesMap[newCount].Add(resource);
freqToResourcesMap[currCount].Remove(resource);
resourceToFreqNodeMap[resource] = freqNode.Next;
if (freqToResourcesMap[currCount].Count == 0)
{
frequenciesList.Remove(freqNode);
freqToResourcesMap.Remove(currCount);
}
}
private static void DecrementCount(string resource,
Dictionary<string, LinkedListNode<int>> resourceToFreqNodeMap,
Dictionary<int, HashSet<string>> freqToResourcesMap,
LinkedList<int> frequenciesList)
{
var freqNode = resourceToFreqNodeMap[resource];
int currCount = freqNode.Value;
int newCount = currCount - 1;
if (newCount > 0)
{
if (!freqToResourcesMap.ContainsKey(newCount))
{
freqToResourcesMap[newCount] = new HashSet<string>();
frequenciesList.AddBefore(freqNode, newCount);
}
freqToResourcesMap[newCount].Add(resource);
resourceToFreqNodeMap[resource] = freqNode.Previous;
}
freqToResourcesMap[currCount].Remove(resource);
if (freqToResourcesMap[currCount].Count == 0)
{
frequenciesList.Remove(freqNode);
freqToResourcesMap.Remove(currCount);
}
if (newCount == 0)
{
resourceToFreqNodeMap.Remove(resource);
}
}
private static string GetMaxOf5Mins(Dictionary<int, HashSet<string>> freqToResourcesMap,
LinkedList<int> frequenciesList)
{
if (frequenciesList == null)
{
return string.Empty;
}
return freqToResourcesMap[frequenciesList.Last.Value].First();
}
}
class Log
{
public int Timestamp {get; private set;}
public string User {get; private set;}
public string Resource {get; private set;}
public Log(string timestamp, string user, string resource)
{
this.Timestamp = int.Parse(timestamp);
this.User = user;
this.Resource = resource;
}
}
Complexity: O(n)
