## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

``````static int test1(string str1, string str2)
{
int i = 0;
int j = 0;
int count = 0;
while (i < str1.Length)
{
if (str1[i] == str2[j])
{
j++;
if (j == str2.Length)
{
count++;
j = 0;
}
}
else
{
j = 0;
}
i++;
}

return count;
}``````

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

can only find 1 when compare 'adffuckddfuckdffuck' with 'fuck'

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

One solution which would be useful in case the string is quite large is to use a suffix array
1. Create the suffix array in O(n)
2. Do a binary search on the suffix array for the string in O(lgn)

Due to the suffix array structure, all the suffixes which start with the given substring will be bunched together

So finally the time complexity is O(n)

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

Its a suggestion to u that never take the word "suffix array" or "suffix tree" in an interview until u r confident enough to code it.

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

Can you elaborate on how the get the occurrences of the substring ?

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

can you give a example?
Not quit get the quesiton

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

suppose in amazonam ,how much time am is occur..........not a big deal.

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

you are right!!

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

can be done with KMP

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

One doubt i have is, for ex if we have the String "aaaa" and the subString is "aa", should the final output be 2 or 3

i.e do we need to count chatAt 1,2 as a valid sequence?

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

``````#include<stdio.h>
#include<string.h>
#include<conio.h>
int main()
{char a[50];
char b[50];
int len1,len2,i,j,k;
gets(a);

gets(b);
len1=strlen(a);
len2=strlen(b);
i=0;
while(i<len1)
{          j=0;
if(a[i]==b[j])
{ k=i;
while(a[k]==b[j]&&j<len2&&k<len1)
{k++;j++;continue;}
if(j==len2)
printf("found at %d\n",i+1);
}
i++;

}
getch();
return 0;
}``````

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

The complexity for the above code seems to be o(mn).
In this brute force itself we can put a check to run the loop only till (m-n+1). So complexity can be O((m-n+1).n).

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

``````#include<stdio.h>
#include<string.h>
#include<conio.h>
int main()
{char a[50];
char b[50];
int len1,len2,i,j,k;
gets(a);

gets(b);
len1=strlen(a);
len2=strlen(b);
i=0;
while(i<len1)
{          j=0;
if(a[i]==b[j])
{ k=i;
while(a[k]==b[j]&&j<len2&&k<len1)
{k++;j++;continue;}
if(j==len2)
printf("found at %d\n",i+1);
}
i++;

}
getch();
return 0;
}``````

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

Any better solution ??

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

``````public class SubStringChecker {

int count = 0;

public static void main(String[] args) {

SubStringChecker ssc = new SubStringChecker();
ssc.go();
}

public void go(){

String s1s = "asdbqasdhvasdfasd";
String s2s = "asd";

char[] s1 = s1s.toCharArray();
char[] s2 = s2s.toCharArray();
int length = s2.length;

for(int i=0; i<s1.length; i++){
if(s1[i] == s2[0] && i+length<=s1.length){
if(s1s.substring(i, i + length).equals(s2s)){
count++;
}
}
}
System.out.print(count);
}

}``````

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

Trivial program to write in java...

``````public static void getOccurances (String a, String b) {
int index = a.indexOf(b);
while(index > -1) {
System.out.println("String found at index: "+index);
index = a.indexOf(b, index+b.length());
}
}``````

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

Fails for repeating substrings. getOccurances("aaa","aa") will only print 0. It should also print 1.

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

static int test1(string str1, string str2)
{
int i = 0;
int j = 0;
int count = 0;
while (i < str1.Length)
{
if (str1[i] == str2[j])
{
j++;
if (j == str2.Length)
{
count++;
j = 0;
}
}
else
{
j = 0;
}
i++;
}

return count;
}

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

static int test1(string str1, string str2)
{
int i = 0;
int j = 0;
int count = 0;
while (i < str1.Length)
{
if (str1[i] == str2[j])
{
j++;
if (j == str2.Length)
{
count++;
j = 0;
}
}
else
{
j = 0;
}
i++;
}

return count;
}

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

//complexity n*m
public static void main(String args[]){
String s="ABCAABCDBCEBC";
String sub ="BC";

int m = s.length();
int n = sub.length();
int count=0;
for(int i=0;i<m-n;i++){
int j=0;
while(j<n && s.charAt(i+j)==sub.charAt(j)){
j++;
}
if(j==n){
count++;
}
}
System.out.println("no of occurrence"+count);
}

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

``````public static void main(String[] args)
{
try
{
String substring, text;
int count = 0, length, i = 0, index, prevIndex = -1;
length = text.length();
for(i = 0; i<length; i++)
{
if((index = text.indexOf(substring, i)) != -1)
{
if(index != prevIndex)
count += 1;
prevIndex = index;
}
}
System.out.println(count);
}
catch(Exception e)
{
e.printStackTrace();
}``````

}

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

``````public static int count(String needle, String haystack) {
int length = haystack.length();
int needleLength = needle.length();
int i = 0;
int j = 0;
int count = 0;
while (i < length) {
if (j >= needleLength - 1) {
j = 0;
count++;
}
if (needle.charAt(j) == haystack.charAt(i)) {
j++;
}
i++;
}
return count;
}``````

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

``````public class SubStringChecker {

int count = 0;

public static void main(String[] args) {

SubStringChecker ssc = new SubStringChecker();
ssc.go();
}

public void go(){

String s1s = "asdbqasdhvasdfasd";
String s2s = "asd";

char[] s1 = s1s.toCharArray();
char[] s2 = s2s.toCharArray();
int length = s2.length;

for(int i=0; i<s1.length; i++){
if(s1[i] == s2[0] && i+length<=s1.length){
if(s1s.substring(i, i + length).equals(s2s)){
count++;
}
}
}
System.out.print(count);
}

}``````

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

public class SubStringOccur1 {
int count = 0;
public static void main(String[] args) {
SubStringOccur1 ssc = new SubStringOccur1();
ssc.go();
}
public void go(){
String mainStr="abcghjabcjkdabklabcklabcdab";
String subStr="abc";
boolean s1=mainStr.startsWith(subStr);
boolean s2=mainStr.endsWith(subStr);
int count=0;
String[] abc=mainStr.split(subStr);
if(s1 &&!s2){
count=abc.length-1;
}else{
count=abc.length;
}
System.out.println(Arrays.toString(abc));
System.out.println("occurances=="+(count));
}

}

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

KMP
bayer moore
algoithm's direct implementation

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.