Yahoo Interview Question
Software Engineer / Developerspublic class outputwords {
@SuppressWarnings("unused")
private String words[];
public outputwords(int InitNum){
words = new String[InitNum];
}
public void addToken(int pos, String Token) {
words[pos-1] = Token;
}
public String toString() {
StringBuffer s = new StringBuffer();
for(int i=0;i<words.length;i++) {
if(words[i] != null) {
s.append(words[i] + " ");
}
}
return s.toString();
}
public static void main (String args[]) throws Exception {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
outputwords mywords = new outputwords(10);
String buffer = reader.readLine();
while(!buffer.equalsIgnoreCase("/output")) {
int period_pos = buffer.indexOf('.');
int pos = Integer.parseInt(buffer.substring(0, period_pos));
mywords.addToken(pos, buffer.substring(period_pos+1));
buffer = reader.readLine();
}
System.out.println(mywords.toString());
}
}//end class
If the count alone is required, Hash table is the solution. Traverse the paragraph once and then display the count accordingly.
If the words need to be displayed. Hashmap<int count, vector words> is enough.
Question is about search. Then a TRIE is the best solution. for the entered words we can search and display if it reaches the end of a word. else proceed searching.
struct trieNode
{
char currentChar;
int endWord;
int endNode;
Vector<trieNode *> childNodes;
};
Initially it will have a dummy Node with possible first letters of the paragraph.
2nd Level will have two letter words
endWord denote the end of a word in the paragraph.
endNode will denote end of the tree depth in this branch.
O(log n) for one search and O(n log n ) for all the words search
Description does not make sense. Task was to display number of 1,2,3,4 lettered words, so example would be
- Alexei January 29, 20115 2
4 1
2 1
where fist number of each row is a number of letters in a word and second is number of words with this many letters in a paragraph.