Microsoft Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
Exactly what came to my mind.
You could construct a multiple Trie structure as follows :
The last node of each country in the CountryTrie would contain an object that maintains the count of the visit + another StateTrie object maintaining the states for the country.
And each state in the StateTrie would similarly contain an object maintaining a CityTrie+count.
I'm guessing this would save us a lot of space.
The first thing that comes to mind is a hash table with linked list chaining. You hash the entire dataset on whatever field you want to count hits from. Fields that are filled out the same will hash into the same bucket and the length of the linked list will equal to the number of fields hashed into the bucket.
Since adding to linked lists is pretty crappy in terms of time complexity, it probably makes more sense to use something like a dynamic array instead of a linked list, but the main concept is the same either way. I'm not sure what the best way to handle the size of table, though, since you have to be sure that two fields of the same type can't be hashed into the same slot.
1. Make three strucs
Country { Name; }
State { Country; StateName;}
City { State, CityName)
2. Make BStree Country, State, City
3. When there is any change in city it also add in State and Country also.
4. When any element change System should adjust in BStree so when user get allways get result in order.
Can we use a trie tree to store the # of people visited based on the country/state/city name (suppose their names are unique)
- yingzhong.xu October 27, 2013