## Amazon Interview Question for Software Engineer / Developers

Country: India

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

Use kmp algorithm to find the starting index of one string in another string.

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

Its complexity would be n^2 i guess..... Need to give most optimal solution.

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

@Rahul KMP is Θ(n)

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

public static int mySubStringIndex(String main, String sub) {
int charPos = -1;
boolean firstCharFound = false;
for (int i = 0; i < main.length(); i++) {
if( main.charAt(i) == sub.charAt(0)) {
firstCharFound = true;
charPos = i;
} // end-if

if(firstCharFound) {
for (int j = 1; j < sub.length(); j++) {
if (main.charAt(++i) != sub.charAt(j))
return -1;
}
break;
}
}
return charPos;
}

Disclaimer:
1) The function makes use of only charAt.
2) Have not done input argument validation.

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

``````public static int mySubStringIndex(String main, String sub) {
int charPos = -1;
boolean firstCharFound = false;
for (int i = 0; i < main.length(); i++) {
if( main.charAt(i) == sub.charAt(0)) {
firstCharFound = true;
charPos = i;
} // end-if

if(firstCharFound) {
for (int j = 1; j < sub.length(); j++) {
if (main.charAt(++i) != sub.charAt(j))
return -1;
}
break;
}
}
return charPos;
}``````

Disclaimer:
1) The function makes use of only charAt.
2) Have not done input argument validation.

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

traverse the input array, when you find the start of the target arrray, start comparing,
If you found the whole target array, return the currentindex - target.Length as the starting index.
At any time If the input array has fewer letters than those in the target array, return -1

``````public static int IsSubstring(string input, string target)
{
if (input.Length < target.Length || target.Length ==0)
return -1;
int targetPointer = 0;
for (int inputIndex = 0; inputIndex < input.Length; inputIndex++)
{
// you finished matching all the target array characters against the input , and it worked

if (targetPointer == target.Length)
{
return inputIndex - target.Length;
}
if (input[inputIndex] == target[targetPointer])
{
targetPointer++;
}
else
{
// reset the target pointer for next matching chance (when you find the first letter again)
targetPointer = 0;
}
}
return -1;
}``````

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

not correct

try this
input = "nns"
target = "ns"

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

``````void KMPSearch(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);

// create lps[] that will hold the longest prefix suffix values for pattern
int *lps = (int *)malloc(sizeof(int)*M);
int j  = 0;  // index for pat[]

// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);

int i = 0;  // index for txt[]
while(i < N)
{
if(pat[j] == txt[i])
{
j++;
i++;
}

if (j == M)
{
printf("Found pattern at index %d \n", i-j);
j = lps[j-1];
}

// mismatch after j matches
else if(pat[j] != txt[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if(j != 0)
j = lps[j-1];
else
i = i+1;
}
}
free(lps); // to avoid memory leak
}

void computeLPSArray(char *pat, int M, int *lps)
{
int len = 0;  // lenght of the previous longest prefix suffix
int i;

lps[0] = 0; // lps[0] is always 0
i = 1;

// the loop calculates lps[i] for i = 1 to M-1
while(i < M)
{
if(pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if( len != 0 )
{
// This is tricky. Consider the example AAACAAAA and i = 7.
len = lps[len-1];

// Also, note that we do not increment i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}

// Driver program to test above function
int main()
{
char *txt = "ABABDABACDABABCABAB";
char *pat = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}``````

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

Yes Kmp algorithm will give us the result in O(n) as it keeps track of the previously encountered characters. If during matching a character occurs that has already been matched earlier in the pattern then it skips the match of this particular character.

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

The main story of matching two strings ..

1. Consider corner case(s) like length, second string exactly same length or less than first string
2. scan character one by one
3. If first character matches then start matching with second string, if second string exists with same length
3.1 Use a binary Algorithm to find match between strings

1. Match first and last character
2. Match middle then if found then again first last and then middle
3. Continue recursive call until scan all characters

Here if full match found then complexity O(N), N length of two strings
This algorithm shows better performance in case of mismatch

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

We can improve the algo like, while doing substring match then we can maintain a stack which indicates next possible match index ;)

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

Just traverse throughout the length of Input string once while checking for occurrence of target string in it along the way as follows. Since I am relatively inexperienced in calculating complexity, can anyone tell be the complexity of the solution i provided?.

``````private int stringSearchUsingLogic(String A, String B) {
int indexPositionOfBinA = -1;
Boolean sensedPresence = Boolean.FALSE;
if ((A != null) && (B != null) && (A.length() > B.length())) {
char a[] = A.toCharArray();
char b[] = B.toCharArray();
int aSize = A.length();
int bSize = B.length();
int bPosition = 0;
char aChar, bChar;
// Loop through each and every characters of A string
for (int aPosition = 0; aPosition < aSize; aPosition++) {
aChar = a[aPosition];
// getting bChar at a particular index position
bChar = getBChar(b, bPosition);
if (bChar == '\u0000') {
// B string is present in A, since its is traversed fully
break;
}
if (aChar == bChar) {
if (!sensedPresence) {
// apparent start position is found
sensedPresence = Boolean.TRUE;
indexPositionOfBinA = aPosition;
}
bPosition++;
continue;
} else {
// if the number of remaining characters in A string is less
// than length of B string
if (aSize - (aPosition + 1) < bSize) {
break;
}
sensedPresence = Boolean.FALSE;
bPosition = 0;
indexPositionOfBinA = -1;
}
}
}
return indexPositionOfBinA;
}

private char getBChar(char b[], int position) {
char bChar = '\u0000';
if (b.length > position) {
bChar = b[position];
}
return bChar;
}``````

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

public static int searchh(String str1,String target){
int strlen;
int targetlen;
String[] parts1=str1.split("");
String[] parts2=target.split("");
strlen=str1.length();
targetlen=target.length();
int count = 0;
int pos = 0;

for(int i=1;i<=strlen ;i++){

pos=i;
for(int j=1;j<=targetlen && pos<=strlen;j++){

if(parts1[pos].equals(parts2[j])) {

count+=1;

}
pos+=1;
}

if(count==targetlen)
{
return i;
}
else{
count=0;
}
}

return -1;
}
}

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

public static void findindex(string str1, string str2)
{
Regex r = new Regex(str2, RegexOptions.IgnoreCase);
Match m = r.Match(str1);
Console.Write(m.Index);
}

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

``````public class KMP {

/**
* @param args
*/
public static void main(String[] args) {
System.out.println(KMPSearching("ABABBABABC", "BBAB"));
}

public static int KMPSearching(String target, String pattern){
int[] prefixArray = prefix(pattern);
int length = target.length();
int lengthP = pattern.length();
int num = 0;
for(int i = 0; i<length; i++){
while(num > 0 && target.charAt(i) != pattern.charAt(num) ){
num = prefixArray[num-1];
}
if(target.charAt(i) == pattern.charAt(num)){
num++;
}
if(num == lengthP){
return i- lengthP+1;

}
}
return -1;
}

public static int[] prefix(String pattern){
int length = pattern.length();
int[] prefix = new int[length];
prefix[0] = 0;
for(int i = 1; i < length; i++){
int k = prefix[i-1];
while((pattern.charAt(i) != pattern.charAt(k)) &&(k!=0)){
k = prefix[k-1];
}
if(pattern.charAt(i) == pattern.charAt(k)) prefix[i] = k+1;
else prefix[i] = 0;
}

return prefix;
}

}``````

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

``````int size(char *s)
{
int i =0;
for( i =0; s[i]!='\0'; i++);
return i;
}
int Search(char *str1, char *str2)
{
int i=0,j=0;
int count1=0,count2=0;
int size1 = 0;
int size2 = 0;
size1 = size(str1);
size2 = size(str2);
printf("The size of the strings are %d,%d\n",size1,size2);
for( j = 0; j <size2 ; j++)
{
if( str1[i] == str2[j])
{
i++;
count1++;
}
else
{
i = 0;
count1 = 0;
count2++;
}
if ( i==size1 )
{
printf("The string is found.\n");
return (j-(count1-1));
}
if ( j == size2)
return -1;
}
}

int main()
{
int val;
char *txt = "iamdrshmindmanarsh";
char *pat = "mindman";
val = Search(pat, txt);
printf("The index is :%d",val);

return 0;``````

}

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

class mano
{
public static int substring(String s1,String s2)
{
int m=s1.length();
int n=s2.length();
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(s1.charAt(i)==s2.charAt(j))
{
System.out.println(i);
//break;
}
}
}
return -1;
}
public static void main(String args[])
{
String s1="cbaca";
String s2="a";
substring(s1,s2);
}
}

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

cssd

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

``````int FindString(char* target, int targetLen, char* str, int strLen)
{
if(!target || !str || targetLen <= 0 || strLen <= 0)
{
return -1;
}

int stringStart = -1;
bool foundFullString = false;
int targetProgress = 0;
for(int i = 0; i < strLen; i++)
{
if(*(str + i) == *(target + targetProgress))
{
if(targetProgress == 0)
{
stringStart = i;
}

targetProgress++;

if(targetProgress == targetLen)
{
foundFullString = true;
break;
}
}
else
{
stringStart = -1;
targetProgress = 0;
}
}

if(!foundFullString)
{
stringStart = -1;
}

return stringStart;
}``````

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

``````static int Substring(string input, string searchStr)
{
int pos = -1;

if (searchStr.Length == 0 || input.Length< searchStr.Length)
return pos;

for (int i = 0; i < input.Length - 1; i++)
{
if (input[i] == searchStr[0])
{
int j = 0;
for (; j < searchStr.Length; j++)
{
if (input[i + j] != searchStr[j])
break;
}

if (j == searchStr.Length)
return i;
}
}

return pos;
}``````

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

Logic is correct working fine minor corrections in the code Biranchi w.r.t syntax

``````static int SubString(String input, String searchStr)
{
int pos = -1;

if (searchStr.length() == 0 || input.length() < searchStr.length())
return pos;

for (int i = 0; i < input.length() - 1; i++)
{
if (input.charAt(i) == searchStr.charAt(0))
{
int j = 0;
for (; j < searchStr.length(); j++)
{
if (input.charAt(i + j) != searchStr.charAt(j))
break;
}

if (j == searchStr.length())
return i;
}
}

return pos;
}``````

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

I think this logic does not work when both input and searstr indices are 1. Ex : Ipnut :"a" and searchstr : "a.

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

``````private static int stringContainIndex(String first, String second) {
for(int i = 0; i < first.length(); i++){
int k = i;
for(int j = 0; j < second.length(); j++){
if(first.charAt(k) == second.charAt(j)){
k++;
}else{
break;
}
}
if(k-i == second.length()){
return i;
}
}
return -1;``````

}

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

The KMP should do the work in O(N). Implemented below with sample output provided.

``````#include <stdio.h>
#include <string>
#include <vector>

using std::string;
using std::vector;

typedef vector<int> ivec;

void print_fail_func(const ivec& idx)
{
for (ivec::size_type i = 0; i < idx.size(); ++i){
printf("idx: %-2d len: %-2d\n", i, idx[i]);
}
}

vector<int> compute_prefix_function(const string& s)
{
int len = s.length();
vector<int> p(len);
p[0] = 0;

int k = 0;
for(int i = 1; i < len; i++) {
while ( (k > 0) && (s[k] != s[i]) )
k = p[k-1];
if (s[k] == s[i])
k++;
p[i] = k;
}
return p;
}

void do_kmp_search(const string& txt, const string& pat, const ivec& idx)
{
int i = 0, j = 0, m = 0;
int ls = txt.length();
int lp = pat.length();
int cmpcount = 0;

while(i < ls){
if (txt[i] == pat[m]) {
++i;
++m;

++cmpcount;

// check if we have a match here
if (m == lp) {
printf("MATCH at: %d\n", i - lp);
m = 0;
continue;
}
}
else { // the current chars do not match
int shft = 0;
if (m > 0)
shft = idx[m - 1];

if (shft > 0) { // we have previous shorter matching prefix of the pattern
m = shft + 0;
}
else { // no previous prefix of pattern matching the string
++i;
m = 0; // reset the pattern index to its beginning
}
}
}

printf("Count of comparisons: %d\n", cmpcount);
}

int main(int argc, char* argv[])
{
string txt = "abc abcdab abcdabcdabde abcdabdu";
string pat = "abcdabd";

//string pat = "AABA";

ivec idx;

printf("TEXT   : %-40s LEN: %d\n", txt.data(), txt.length());
printf("PATTERN: %-40s LEN: %d\n\n", pat.data(), pat.length());

idx = compute_prefix_function(pat);
print_fail_func(idx);
printf("\n");
do_kmp_search(txt, pat, idx);
return 0;
}``````

OUTPUT:

``````TEXT   : abc abcdab abcdabcdabde abcdabdu         LEN: 32
PATTERN: abcdabd                                  LEN: 7

idx: 0  len: 0
idx: 1  len: 0
idx: 2  len: 0
idx: 3  len: 0
idx: 4  len: 1
idx: 5  len: 2
idx: 6  len: 0

MATCH at: 15
MATCH at: 24
Count of comparisons: 27``````

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

1) compare text with length n with first n characters of the main string.
2) if all characters matches then return 0
3) else increment index by 1 and recursively search main string from the next position to end of the main string until match is found.

``````String mainText = "who am i? Spiderman Or Superman";
String searchText = "Spiderman";
public int contains(String mainText, String searchText){

if(mainText.length() < searchText.length()){
return -1
}

if( mainText.subString(0, searchText.length()).equals(searchText)){
return 0;
}else{
return 1 + contains( mainText.subString(1, mainText.length()), searchText) ;
}

}``````

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

public static int containsIN(String one, String two) {

if(one.contains(two))
return one.indexOf(two);
if(two.contains(one))
return two.indexOf(one);
else
return -1;
}

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

#include <stdio.h>
#include <string.h>

int match(char str1[],char str2[],int index,int len)
{
int i=0;
while(i!=len-1)
{
if(str1[++index] != str2[++i])
return -1;
}
return 1;
}

main()
{
char str1[100] = "amimamion";
char str2[100]="mioh";
int len,i,j,k;

len =strlen(str2);

i=0;

while(str1[i]!='\0')
{
if(str1[i] == str2[0])
{
k = match(str1,str2,i,len);
if(k==1)
{
printf("true");
return;
}
}

i++;
}

printf("false");

}

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

#include <stdio.h>
#include <string.h>

int match(char str1[],char str2[],int index,int len)
{
int i=0;
while(i!=len-1)
{
if(str1[++index] != str2[++i])
return -1;
}
return 1;
}

main()
{
char str1[100] = "amimamion";
char str2[100]="mioh";
int len,i,j,k;

len =strlen(str2);

i=0;

while(str1[i]!='\0')
{
if(str1[i] == str2[0])
{
k = match(str1,str2,i,len);
if(k==1)
{
printf("true");
return;
}
}

i++;
}

printf("false");

}

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

class MatchString
{
public static void main(String[] args)
{
System.out.println("Matching string and return index");
String original="hi this is my string";
String key="strig";
MatchString ms=new MatchString();
System.out.println(ms.matchString(original,key));
}

public String matchString(String s,String k)
{
int len1=s.length();
int len2=k.length();
char coriginal[]=s.toCharArray();
char ckey[]=k.toCharArray();
int count=0;
int m=0;
int i,loc=0;
for(i=0;i<len1;i++)

{

if(coriginal[i]==ckey[m])
{
count++;
m++;
if(count==len2){break;}
}

else
{
count=0;
m=0;
}

}

if(count==len2)
{
return "String found in index "+(i=(i-(len2-1)+1))+"th "+ "to "+(i+len2-1)+"th" ;
}

}

}

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

Here is the code in C--

``````int substr(char str[],char str1[])
{
int i=0,j=0;
int l=strlen(str1);
for(i=0;i<strlen(str);i++)
{
if(str[i]==str1[0])
{
for(j=1;j<l;i++)
{
if(str[j+i]!=str[i])
break;
}
if(j=l-1)
{
printf("match found at index %d",i);
return i;
}
}
}
return -1;
}``````

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

Use this is main
//search for target string in string. return index where target is found.
int indexval = findtargetString("","");

Here are the main methods

bool checkwithTarget(int ind, string str, string target)
{
int j = 0;
while (ind < str.length() && j < target.length())
{
if (str[ind] == target[j])
{
j++;
ind++;
}
else{
return false;
}

}
return true;
}

int findtargetString(string str, string target)
{
str = "sanggeetha";
target = "geet";
vector<int> possibleIndices;
for (int i = 0; i < str.length(); i++)
{
if (str[i] == target[0])
{
possibleIndices.push_back(i);
}
}
for (int i = 0; i < str.length(); i++)
{
try {
cout << "Element " << i << ": " << possibleIndices.at(i) << endl;
if(checkwithTarget(possibleIndices.at(i), str, target))
return (possibleIndices.at(i));
}
catch (exception& e) {
cout << "Element " << i << ": index exceeds vector dimensions." << endl;
}
}
return -1;
}

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

if

``source.IndexOf(target);``

is not the option :)

``````private int inString(string source, string target)
{
int index = -1;

if (string.IsNullOrWhiteSpace(source) || string.IsNullOrWhiteSpace(target) || target.Length > source.Length)
{
return index;
}

for (int i = 0; i < source.Length; i++)
{
if (source[i] == target[0])
{
index = i;
for (int j = 0; j < target.Length; j++)
{
if (source.Length - 1 < i + j ||
target[j] != source[i + j])
{

index = -1;
break;
}
}
}
}

return index;
}``````

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

``````public static boolean stringsMatch(String str1,String str2){

if(str1==null || str2==null)
return false;

int len1=str1.length();
int len2=str2.length();

for(int i=0;i<len1-len2;i++){
int j=0;
for(j=0;j<len2;j++){
if(str1.charAt(i+j)!=str2.charAt(j)){
break;
}
}
if(j==len2){
//full pattern matched.
return true;
}
}
return false;
}``````

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

public class position_of_a_string_in_another_string
{

StringBuilder output = new StringBuilder();
public static void main(String []args)
{
position_of_a_string_in_another_string obj = new position_of_a_string_in_another_string ();
System.out.println(obj.findTheCommonSubstringWithPosition("careerstack","stack"));
}

private int findTheCommonSubstringWithPosition(String str1, String str2)
{
int dynamic_array[][] = new int [str1.length()+1][str2.length()+1];

for(int i=0;i<str1.length();i++)
{
for(int j=0;j<str2.length();j++)
{
if(str1.charAt(i) == str2.charAt(j))
{
dynamic_array[i+1][j+1] = dynamic_array[i][j] + 1;
}

else
{
dynamic_array[i+1][j+1] = Math.max(dynamic_array[i][j+1], dynamic_array[i+1][j]);
}
}
}

for(int x = str1.length() , y = str2.length() ; x!=0 && y!=0 ;)
{
if(dynamic_array[x][y] == dynamic_array[x-1][y])
{
x--;
}

else if(dynamic_array[x][y] == dynamic_array[x][y-1])
{
y--;
}

else
{
output.append(str1.charAt(x-1));
x--;
y--;
}
}

output = output.reverse();
return str1.indexOf(output.toString());
}
}

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

public class SearchStringPosition
{
public static void main(String[] args)
{
//Example
String abc = "indiabgh";
String cdg = "bgh";
int j= cdg.length();
//System.out.println(j);
for(int i=0;i<abc.length();i++,j++)
{
String chg = abc.substring(i,j);
System.out.println(chg);
if(chg.equals(cdg))
{
System.out.println("found");
System.out.println(i);
break;

}
}

}

}

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

This is amazon question dude......
Need to write you methods to find.

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.