Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
int indexof(string & s,string sub)
{
vector<int> T;
T.resize(s.length());
T[0]=-1;
T[1]=0;
int pos=2,cmd=0;
while(pos < s.length())
{
if(s[pos-1] == s[cmd])
{
T[pos] = cmd;
cmd++;
}else
{
if(cmd > 0)
{
cmd = T[cmd];
T[pos] = cmd;
}else
{
cmd = 0;
T[pos]=0;
}
}
pos++;
}
pos = 0;
int i=0;
while(pos < s.length())
{
if(sub[i] == s[pos])
{
i++,pos++;
}else
{
if(pos>0 && i >0)
pos = pos - T[pos];
else
pos++;
i=0;
}
if(i == sub.length())
break;
}
if(i == sub.length())
return pos-i;
else
return -1;
}
package codes.strings;
public class IndexOfImpl {
public static void main(String[] args) {
String str = "utkarsh";
String substr = "kar";
int strLen = str.length();
int subStrLen = substr.length();
int s1 = 0;
int s2 = 0;
int pos = 0;
while(s1<strLen){
if(str.charAt(s1)==substr.charAt(s2)){
s1++;
s2++;
}
else if(str.charAt(s1)!=substr.charAt(s2)){
s1++;
s2=0;
}
if(s2==(subStrLen)){
pos = s1 - s2;
break;
}
}
if(s2==(subStrLen))
System.out.println("Index True, Postion ->"+pos);
else
System.out.println("String Not Found !");
}
}
#include<iostream>
using namespace std;
int main(){
cout<<"hello Inside"<<endl;
string pattern="hellhelloo";
string search="helloo";
int count=search.length();
cout<<count<<endl;
int temp=0;
for(int i=0;i<pattern.length();i++){
for(int j=0;j<count;j++){
if(pattern[i]==search[j]){
//cout<<"pattern"<<pattern[i]<<"search"<<search[i]<<endl;
temp++;
i++;
}
else{
i=i-temp;
temp=0;
}
}
}
if(temp==count)
cout<<"got substr"<<endl;
else
cout<<"sorry"<<endl;
cout<<temp<<endl;
int x;
cin>>x;
}
#include<iostream>
using namespace std;
int main(){
cout<<"hello Inside"<<endl;
string pattern="hellhelloo";
string search="helloo";
int count=search.length();
cout<<count<<endl;
int temp=0;
for(int i=0;i<pattern.length();i++){
for(int j=0;j<count;j++){
if(pattern[i]==search[j]){
//cout<<"pattern"<<pattern[i]<<"search"<<search[i]<<endl;
temp++;
i++;
}
else{
i=i-temp;
temp=0;
}
}
}
if(temp==count)
cout<<"got substr"<<endl;
else
cout<<"sorry"<<endl;
cout<<temp<<endl;
int x;
cin>>x;
}
oops
/*
Implement indexOf function to find a substring from a given string
So, implement indexOf(String str) from index 0
Can use KMP as well for O(n) time complexity...
Salesforce interview question
*/
public static int indexOf(String str, String substring)
{
char[] strArray = str.toCharArray();
char[] subArray = substring.toCharArray();
char first = subArray[0];
int max = (strArray.length - subArray.length);
for (int i = 0; i <= max; i++) {
/* Look for first character of the substring in the original. */
if (strArray[i] != first) {
while (++i <= max && strArray[i] != first);
}
/* Found first character (i is now at the start of substring in original string), now look at the rest of v2
* to make sure the whole substring is in the string */
if (i <= max) {
int j = i + 1;
int end = j + subArray.length - 1; //the end index of the substring in the original string
for (int k = 1; j < end && strArray[j] == subArray[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i;
}
}
}
return -1;
}
Check out KMP Algorithm for string matching.. That will give the answer in O(n).
- Naveen May 09, 2012