## Microsoft Interview Question for Software Developers

Team: N/A
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

you can use trie data structure. Time complexity will be O(N) for search.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Inverted index is what the question is about.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is essentially asking for a pattern matching algorithm. Knuth-Morris-Pratt is one popular one.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think I myself have a solution.
Suppose we have to search the phrase "This is".
Then for every occurrence of "This" we will have a node in the trie with the index stored
Then we search for the word "is" in the trie, and hence we can find all the indices in which "is" occur in the large text
Then for each index at which "is" occurs, we can check in O(m+n) time { all the indices at which index of occurrence of "is" - length of("the ") } which matches with the indices at which "the" occurs.
where m,n- number of indices at which "the" , "is" occur respectively.
This approach can be extended to phrases with more than two words in this manner-
For e.g.- we have to search "This is a good approach"
We keep all the indices at which "This is" occurred in a set say S. Then we match all indices at which "a" occurs and match it in the above mentioned manner for all the indices in S and continue so on

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Solution{

private static Node rt=new Node();//Reference to root node of trie.
public static boolean searchWord(String wrd){
if(wrd==null||wrd.length()==0){
return false;
}
for(int i=0;i<wrd.length();i++){
int idx=(int)wrd.charAt(i)-'a';
Node v=rt;
if(v.nextLetters[idx]==null){
return false;
}
v=v.nextLetters[idx];
}
return true;

}

public static boolean searchPhrase(String[] phrase){

Node v=rt;
for(int i=0;i<phrase[0].length();i++){
int idx=(int)phrase[0].charAt(i)-'a';
if(v.nextLetters[idx]==null){
return false;
}
v=v.nextLetters[idx];
}
for(int i=1;i<phrase.length;i++){
String wrd=phrase[i];

//check if the node corresponding to the last letter of the previous word has a pointer to the first letter of the current word
int currChar=(int)wrd.charAt(0)-'a';
if(r.c[currChar]==null || v.nextWordStart[currChar]==null){
return false;
}
v=r.c[currChar];
for(int j=1;j<wrd.length();j++){
currChar=wrd.charAt(j)-'a';
if(v.nextLetter[currChar]==null){
return false;
}
v=v.nextLetter[currChar];
}
}
return true;
}

//represents a letter.
private static class Node{
Node[] nextLetters;//Points to the next character of current word
Node[] nextWordStart;//Points to starting character of next word (if node is the last letter of a word in a phrase).

public Node(){
nextLetters=new Node[26];
nextWordStart=new Node[26];
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Inverted index is what the question is about.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.