## Amazon Interview Question for Software Engineer / Developers

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

<a href="http://www.softwareinterviewqna.com/blog/?p=1">The approach to this problem is divide-and-conquer.</a>

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

Suffix Tree

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

I do not think suffix tree can do it.

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

i guess one of the (best)ways assuming hashtables are allowed and the string is not too large, just anagram the string to get all the possible parts (anagrams); throw the anagrams into a hashtable with each anagram as key. now, for any input for a match check, simply check if the input is a key in the hastable in which case you return a true/match else a false/no-match...

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

Why anagrams? I interpreted the problem as doing a substring match with possible typos (hence the 'score' requirement).

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

Use Naive Bayes Algorithm, it will output the probability of the match. It assumes that each word is independent of each other.

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

typedef struct _match {
int position;
int score;
} match;

std::list<match> get_matches(char *sstr, char *input) {
std::list<match> result;
int score = 0;
int position = 0;
char* input_buffer;
char* sstr_buffer;

while(*input) {
score = 0;
input_buffer = input;
sstr_buffer = sstr;
while(*(input++) == *(sstr++)) {
score++;
}
if(score) {
match new_match;
new_match.position = position;
new_match.score = score;
result.push_back(new_match);
}
input = ++input_buffer;
sstr = sstr_buffer;
position++;
}
return result;
}

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

I think this is similar to longest common subsequence problem.

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

i would say..suffix tree...cause it sounds like a substring problem rather than a subsequence problem

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

isnt this simple edit distance(dynamic programming)

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

I believe so

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

check for smith waterman algorithm

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.