## Amazon Interview Question for Applications Developers

Country: India

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

I can only see exponential solution for this
below is explanation
1) For <i,j>, there are 4 possibilities <i-1,j>,<i+1,j>,<i,j-1>,<i,j+1>
2) Maintain a set for already traversed Pairs, If that alreadu exit dont explore that path
3) Now for each possiblity check if its word print the word and continue, If not word check if it is prefix, if thats true then continue else we ignore that path.

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

I thought of the same solution and thought it was sufficient because I interpreted the words as being English / natural language words. That would make them all relatively short and prevent the number of possibilities, which is exponential in the word length, from getting out of hand.

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

Can you give some pseudo code!

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

I agree, and I think we can just use a modified BFS to do

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

can't understand why it is exponential? for each of the <i,j> pairs(N^2), we need to traverse all N^2 in worst as there are no loops allowed we will not be visiting the alphabets already visited, also characters should be adjacent(within 4 neighbors) to form word Am i wrong at anything ?.

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

What does is_word and is_prefix return?

If they return that word is present in dictionary then or it is a prefix of any word then that can be solved with DP.

DP is the straihght fwd approach for this problem.

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

What is DP? can you please give the example?

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

Yes i guess so! Can you please suggest the solution!

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

``````public void findWords(char[][] m, int i, int j, LinkedList<char> path){
if( IsWord( path.toString + m[i][j])){
System.out.println( path.toString + m[i][j]) );
}
if ( IsPrefix( path.toString + m[i][j]) ){
if ( ! path.contains( m[i-1][j]) ){
findWords( m, i-1, j, path);
}
if ( ! path.contains( m[i+1][j]) ){
findWords( m, i+1, j, path);
}
if ( ! path.contains( m[i][j-1]) ){
findWords( m, i, j-1, path);
}
if ( ! path.contains( m[i][j+1]) ){
findWords( m, i, j+1, path);
}

// Start a new search
findWords( m, i-1, j, newPath);
findWords( m, i+1, j, newPath);
findWords( m, i1, j-1, newPath);
findWords( m, i, j+1, newPath);
}``````

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.