Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
I would consider it as other way round, as nothing is given about extra noun-verb dict.
Let us define
Set S = {is,am,are,had,have,has}
// I am not sure whether S contains everything we need or not
// as I am not a native English speaker
the words just before any element of S would be considered as noun
and the words just after any element of S would be considered as verb.
We have to watch for special cases of passive voice statements in which
been
is used after has/have. In that case, omit been and consider
word next to it.
Obviously these rules are not sufficient, but its just an idea of mine.
why so ??
well I think because this is how grammar for english is.
It seems more or less a NLP ( natural language processing ) problem to me.
1. Dictionary of all Nouns and verbs:
- Sid June 22, 2013a. make a trie of nouns. let the word in trie end with the word and also add s or es depending on singular or plural property.
b. In case of verb, we will need to have all permutations of verb in the trie i.e. run, running, runs etc so it can be matched
2. Create a Hash table to store the nouns and verbs in the book. for each permutation of noun/verb only store the main word i.e. for running only store run so that the list is complete.
Reason for trie : O(1) search time for word
Reason for Hashtable: O(1) search time