Microsoft Interview Question for Software Architects


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
3
of 3 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 votes

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.

- Murali Mohan July 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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/

- ajamrozek October 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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);
			}
		}
	}
}

- subahjit June 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Sunny June 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- whatevva' June 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- am July 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- whatevva' July 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Alex July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would store it in one long bitmask.
AAA-ZZZ range gives us 17576 permutations, 000-999 range in each, divided by 8 (1 bit per plate) is ~2 Mb file.

It's pretty trivial to calculate offsets and make queries in such a file.

- vk October 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

build an array of arrays for eg in php

$array['abc']=array('123'=>'somevalue');
to find this value
$array['abc']['123']
to find all vaues in mmm
$array['mmm']

- Anonymous November 19, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More