Microsoft Interview Question
Senior Software Development EngineersCountry: India
Interview Type: Phone Interview
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.
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.
- Noobie June 03, 2015