## Amazon Interview Question for Software Engineer / Developers

• 0

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

use KMP matching
in each column and each row

Complexity will be O( (m+n)*(m+n))

where matrix is m * m
and n=length of input string

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

anyone knows the answer to this one?

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

@ gautam
yes this i also think about to use kmp here
and complexity will be theta(m*m)
in KMP there are two main steps
FIRST STEP is to make and prefix array PIE
and using this do the searching of pattern in matcher step in step 2
PREFIX FUNCTION
void Prefix(char P[],int m,int PRE[])
{
int q,k=0;
PRE=0;
for(q=2;q<=m;q++)
{
while(k>0 && PRE[k+1]!=PRE[q])
k=PRE[k];
if(P[k+1]=P[q])
k++;
PRE[q]=k;
}}

for matching
void MATCHER(char T[],int n,char P[],int m)
{
in q,k,i,j;
int PRE;
Prefix(P,m,PRE);
q=0;
for(i=1;i<=n;i++)
{
while(q>0 && P[q+1]!=T[i])
q=PRE[q];
if(P[q+1]==T[i])
q++;
if(q==m)
{
printf("the string found at%d",i-m);
q=PRE[q];// for the next match
}

}

}

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.