Microsoft Interview Question
Software Engineer / DevelopersI think B+ tree should should be useful in this case.
For a b-order B+ tree with h levels of index:
Inserting a record requires O(log n on base b ) operations
Finding a record requires O(log n on base b) operations
Removing a (previously located) record requires O(log n on base b) operations
Use hash on each word and keep counter on the hash table. Add new item to hash bucket in case of collision
- Tanvir March 09, 2007