|
257. Given a text file and a function getNextWord().....
Microsoft Interview Questions and Answers
(Continued from previous question...)
257. Given a text file and a function getNextWord().....
Question:
Given a text file and a function getNextWord(), which returns a next word read and NULL if EOF is reached. A comparison function to compare two strings bool isEqual(char* str1, char* str2) is also given. Create a link list, which has following node type :
struct Node{
Node* next;
int freq;
char* str;
};
The list must be sorted according to freq and algo must work in less than O(n2).
maybe an answer:
1. For each word, insert it in a self-balanced binary search tree (Red-Black, AVL, etc).
2. If the node exists, increase it's frequency else insert a new node with frequency 1 (the comparison is done using the isEqual function).
3. Re-balance the tree comparing the frequencies of tree nodes.
4. When you are done with all the words(EOF), a simple in-order traversal (compare the frequencies) should do the linked list.
time complexity: O(n * log n): n from scanning the file, log n from insertion and re-balancing.
space complexity: O(n) - for the tree.
(Continued on next question...)
Other Interview Questions
| 