Microsoft Interview Question
Software ArchitectsCountry: India
Interview Type: Phone Interview
Good one. At each node of the trie, maintain a linked list for the 3-digit numbers.
In order to address the query - 'Count the total number license numbers starting with ABC', you can as well maintain a counter that maintains the size of the linked list and update its value each time the linked list is updated. The query can then be addressed in constant time just by returning the value of that counter.
I don't follow. How can you only allow it three nodes high and consider "ABC" your alpha set? I'm down with the tree. I built this out this weekend to build up my non-existent BST skills. I went through the full factorial of the alpha-digit generation and selected a random 100k set to seed an input file.
I made a balancing BST and can fill and test it in ~1.48ms. But it is no way only three nodes high.
http://casb1.cloudapp.net/1016/8dd68b8687397791471532695a287868/LicensePlateRepo/
Store the data in the following structure:
public class LicensePlate {
private HashMap<String, LinkedList<String>> licensePlates = new HashMap<String, LinkedList<String>>();
public LicensePlate(String[] arr) {
for(String licensePlate : arr) {
String aplhabetPart = licensePlate.split("-")[0];
String numberPart = licensePlate.split("-")[1];
if(licensePlates.containsKey(aplhabetPart)) licensePlates.get(aplhabetPart).add(numberPart);
else {
LinkedList<String> numberList = new LinkedList<String>();
numberList.add(numberPart);
licensePlates.put(aplhabetPart, numberList);
}
}
}
}
For starter, convert each letter to a number between 0-25. Then you can create a 3-dimensional array "LinkedList<Integer> license[][][]", where license[i][j][k] is a list of the 3-digit suffixes for license that starts with ('A'+i)('A'+j)('A'+k). This should support the search quite efficiently and allow you reconstruct all stored data.
Downside is that it takes extra storage because many of the elements might be empty, and so it also takes longer to reconstruct the whole list than needed. An alternative would be to use a multi-level HashMap instead, but the implementation would be slightly more cumbersome.
Maintain a Hash table with "key" as the first 3 characters and the value being a "list" of the last three numbers of all the license plates with the same starting "key". It should be straight forward to get the "List all licenses starting with ‘MMM’ ".
Also mantain a Binary Search Tree where the node value is the "key" above and the "value" is the count of the license plate numbers with that key. Getting the "Count the total number license numbers starting with ABC" can be accomplished by searching for key "ABC" and doing inorder traversal from that node.
For the count of plates for a given prefix "ABC", don't need to traverse the tree or linked-list associated with a hash key. Just keep the count when inserting new elements.
Looks like I misunderstood the statement "Count the total number license numbers starting with ABC". I assumed we want the count of all license plates with keys "starting with ABC" including ABC and beyond such as ACC, MMM etc all the way to the end of the last key tag... and thats why i suggested traversing. But I guess the question asks for the count of plates with just one key.
Thanks @am for pointing it out.
The following structure was defined:
typedef map<string,list<string>,less<string>> Nmap;
where key is of string type represents first 3 characters in the number - letters and list of strins as the value of the dictionary contains all the number plates with this letter-part.
Therefore, the input of the data from text file is:
Nmap* ReadData (ifstream &f)
{
if (!f.is_open())
return 0;
Nmap *numberPlates = new Nmap ();
string str;
while (!f.eof())
{
f >> str;
Nmap::iterator position = numberPlates->find (str.substr(0,3));
if (position != numberPlates->end())
position->second.push_back (str);
else
{
list<string> l(1,str);
numberPlates->insert(make_pair (str.substr(0,3), l));
}
}
return numberPlates;
}
Here is code of searching plates by key. As the result - list of plates:
list<string>* Search (const Nmap *plates, const string key)
{
Nmap::iterator result = const_cast<Nmap*>(plates)->find(key);
if (result !=plates->end())
return &result->second;
else
return 0;
}
And, finally, code, which returns the amount of such plates if the list isn't empty and -1 otherwise:
long SearchCount (const Nmap *plates, const string key)
{
Nmap::iterator result = const_cast<Nmap*>(plates)->find(key);
if (result !=plates->end())
return result->second.size();
else
return -1;
}
And here is the main method:
void main ()
{
ifstream f ("Test.txt");
Nmap* numberPlates = ReadData (f);
list<string> *resultSearch = Search (numberPlates, "ABC");
if (resultSearch !=0)
for (list<string>::iterator itr = resultSearch->begin (); itr != resultSearch->end(); itr++)
cout << *itr <<endl;
long resultCount = SearchCount (numberPlates, "ABC");
if (resultCount >=0)
cout << resultCount << endl;
}
As a first thought, I would create a trie of some special type. The terminal nodes of the trie are the nodes with alpha keys (thus making it at most 3 nodes high - "ABC"), each containing a set of numbers ranging from 000-999.
- ashot madatyan June 30, 2013