Amazon Interview Question Software Engineer / Developers
Country: India
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.
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.
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;
}
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;
}
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
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;
}
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;
}
}
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;
}
}
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;
}
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);
}
}
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;
}
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;
}
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;
}
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 txt = "AABAACAADAABAAABAA";
//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
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) ;
}
}
#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");
}
#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");
}
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" ;
}
else return "Not found";
}
}
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;
}
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;
}
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;
}
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());
}
}
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;
}
}
}
}
Use kmp algorithm to find the starting index of one string in another string.
- Anonymous June 18, 2013