CareerCup

Use a trie to store ip addresses. This is more efficient than a hash. Lookup would be constant time since number of bits in an IP addresss is fixed. For LRU evictions use a linked list apart from the trie such that there is a pointer from an entry in the trie to the list node. If key-value pairs are to be stored, replace the trie with a hash table.

Don't bother about IP Address, focus on a LRU cache with max size. Cache can store any key value pair. IP Address is an example

Here is what i think one should implement the LRU cache
Plese note that, this solution consider <IPAddress, ServerName> mapping, not <ServerName, IPAddress>.
Declare a Node of a trie

public class Node
{
    public Int16 nodeValue; // node will store values from 0 to 9, except root node which will have -1;
    public Node[] child;
    public bool isTerminal;
    public DateTime lastAccessDateTime{get;set;}
    public string serverName{get;set;}
    
    public Node(Int16 value, int childCount,bool isTerminal)
    {
        nodeValue = value;
        child = new Node[childCount];
        isTerminal = isTerminal;
    }
    
    public Node(Int16 value, int childCount)
    {
        nodeValue = value;
        child = new Node[childCount];
        isTerminal = false;
    }
    
    public Node(Int16 value)
    {
        nodeValue = value;
        child = new Node[10];
        isTerminal = false;
    }
}

Define two trie, one is to store datetime, another is to store ipaddress

public class IPAddressTrie
{
    public Node root;
    
    public IPAddressTrie(Int16 value)
    {
        root = new Node(value,3);
    }
    
    public void Insert(string iPAddress, DateTime accessDateTime)
    {
        throw new Exception(); 
    }
    
    public void Delete(string iPAddress)
    {
        throw new Exception(); 
    }
    
    public DateTime Update(string iPAddress, DateTime newAccessDateTime)
    {
        throw new Exception();
    }
    
    public bool Search(string iPAddress, DateTime accessDateTime)
    {
        throw new Exception();
    }
}

public class DateTimeTrie
{
    public Node root;
    public DateTimeTrie(Int16 value)
    {
        root = new Node(value,2);
    }
    
    public void Insert(DateTime lastAccessDateTime, string serverName)
    {
        throw new Exception();
    }
    
    public string Delete(DateTime lastAccessDateTime)
    {
        throw new Exception();
    }

    public void Update(DateTime oldAccessDateTime, DateTime newAccessDateTime)
    {
        var serverName = Delete(oldAccessDateTime);
        Insert(newAccessDateTime, serverName);
    }
    public string DeleteFirstAccussedElement()
    {
        throw new Exception();
    }
}

Here is how you can write your main class

public class IPAddressLRUCache
{

    public static void Main(string[] args)
    {
        DateTimeTrie dTTrie = new DateTimeTrie(-1);
        IPAddressTrie iPATrie = new IPAddressTrie(-1);
        int iPAddressCount = 0;
        while(true)
        {
            string newIPAddress = "temp"; // this is the request generated from the CPU;
            DateTime accessDateTime = DateTime.UtcNow; // cpu can give this as well or we can set it to utcnow;
            if(iPATrie.Search(newIPAddress, accessDateTime))
            {
                // apply mutex lock here
                var oldDateTime = iPATrie.Update(newIPAddress, accessDateTime);
                dTTrie.Update(oldDateTime, accessDateTime);
                // release the lock here
            }
            else // cache miss case
            {
                // aply mutex lock here
                if(iPAddressCount == 1000)
                {
                    var ipaddress = dTTrie.DeleteFirstAccussedElement();
                    iPATrie.Delete(ipaddress);
                    iPAddressCount--;
                }
                else
                {
                    <newIPAddress, server> = Disk.Read();
                    iPATrie.Insert(newIPAddress, accessDateTime);
                    dTTrie.Insert(accessDateTime, server);
                    iPAddressCount++;
                }
                // release mutex here
            }
        }
    }
}

I didn't put much of the thinking for multithreaded main method, so, main may have some issues with multithreading

Complexities

Space : size of the input
	Time : Constant, 2 or 3 multiple of 8.

Okay then..