Amazon Interview Question
Technical Support EngineersCountry: India
Interview Type: Written Test
If the program is going to be used only once. What the tip suggests is good enough. Taking O(nm) time, where n is the length of the longer string and m is the length of the shorter one.
If it is going to be used many times for checking different substrings, first build the surffix tree of the long string. Then checking a substring of length m only takes O(m) time.
public static int getSubStringStartingPosition(char[] st1, char[] st2)
{
int pos=0;
boolean flag=false;
int k=0;
for (int i=0; i<=st1.length-1; ++i)
{
if ((k <= st2.length-1) && (st1[i]==st2[k]))
{
//System.out.println("found.."+st2[k]);
if (!flag)
{
pos=i;
}
flag=true;
k++;
}
else
{
System.out.println("not found.."+st1[i]);
if (flag && k <=st2.length-1)
{
System.out.println("found an extra character in the middle..");
pos=-1;
}
}
}
return pos;
}
{{
var indexOf = function(search, target){
for(var k = 0; k < search.length; k++){
if(search[k] = target[0]){
var found = true;
for(var j = 0; j < target.length; j++){
found = found & (search[k + j] == target[j]);
}
if(found){
return k;
}
}
}
return -1;
}
console.log(indexOf('this works','works'));
console.log(indexOf('AAAB','AAB'));
}}
KMP (easy if you know that)
vector<int> BuildPrefixFunction(const string& s) {
vector<int> result(s.length(), 0);
for (int i = 1; i < s.length(); ++i) {
int j = result[i-1];
while (j && s[i] != s[j]) j = result[j-1];
if (s[i] == s[j]) ++j;
result[i] = j;
}
return result;
}
Z function (Google that)
But would prefer hash here. Polynomial hashes would work perfectly here.
KMP (easy if you know that)
vector<int> BuildPrefixFunction(const string& s) {
vector<int> result(s.length(), 0);
for (int i = 1; i < s.length(); ++i) {
int j = result[i-1];
while (j && s[i] != s[j]) j = result[j-1];
if (s[i] == s[j]) ++j;
result[i] = j;
}
return result;
}
Z function (Google that)
But would prefer hash here. Polynomial hashes would work perfectly here.
#include<stdio.h>
#include<string.h>
#define MAX 80
int find();
int main()
{
int n;
n=find();
if (n!=0)
printf("\n First occurence of first string is at %d position of second string", n);
else
printf("\n Not found!");
return(0);
}
int find()
{
char str2[MAX],str1[MAX],*str3;
int len2,i,n=0;
printf("Enter the first string:\n");
gets(str1);
printf("Enter the second string:\n");
gets(str2);
len2=strlen(str2);
for (i=0;i<len2;i++)
{
if (str2[i]==str1[0])
{
str3=strstr(str2,str1);
printf("\n Found...:\t %s", str3);
n=i;
break;
}
else
n=0;
}
return (n);
}
int indexOf(String a, String b) {
if (a == null || a.isEmpty() || b == null || b.isEmpty())
return -1;
if (a.length() > b.length())
return -1;
int max = b.length() - a.length() + 1;
int bx = 0;
while (bx < max) {
if (a.charAt(0) != b.charAt(bx)) {
bx++;
while (bx< max && a.charAt(0) != b.charAt(bx)) {
bx++;
}
} else {
boolean found = true;
for (int i = 1; i < a.length() && bx + i < b.length(); i++) {
if (a.charAt(i) != b.charAt(bx + i)) {
found = false;
break;
}
}
if (found)
return bx;
bx++;
}
}
return -1;
}
int indexOf(String a, String b) {
if (a == null || a.isEmpty() || b == null || b.isEmpty())
return -1;
if (a.length() > b.length())
return -1;
int max = b.length() - a.length() + 1;
int bx = 0;
while (bx < max) {
if (a.charAt(0) != b.charAt(bx)) {
bx++;
while (bx< max && a.charAt(0) != b.charAt(bx)) {
bx++;
}
} else {
boolean found = true;
for (int i = 1; i < a.length() && bx + i < b.length(); i++) {
if (a.charAt(i) != b.charAt(bx + i)) {
found = false;
break;
}
}
if (found)
return bx;
bx++;
}
}
return -1;
}
he easy C++ way to do this is to use std::string::find:
std::string s = "apple";
std::string sub = "ple";
auto index = s.find(sub); //std::string::npos if not found
The way for C would be strstr:
const char *s = "apple";
const char *sub = "ple";
const char *pos = strstr(s, sub); //NULL if not found
Worst case Complexity : O(n)
public class Practice65 {
public static void main(String args[]){
String str1 = "abcdefcde";
String str2 = "de";
int j=0,i=0;
while(i<str1.length()){
if(str2.charAt(j) == str1.charAt(i)){
j++;
i++;
if(j == str2.length()){
System.out.println(i - str2.length());
break;
}
}else{
j=0;
i++;
}
}
}
}
Yeah, I forgot to consider that case. The following code will work for upper case as well.
public class Practice65 {
public static void main(String args[]){
String str1 = "AAAABBAABBAAABAB";
String str2 = "AABBAAA";
int j=0,i=0;
while(i<str1.length()){
if(str2.charAt(j) == str1.charAt(i)){
j++;
i++;
if(j == str2.length()){
System.out.println(i - str2.length());
break;
}
}else{
i = i - j; // Add this piece of code.
j=0;
i++;
}
}
}
}
Once you add that line, the complexity becomes O(mn) with m being the length of the 2nd string. Basically, at i-th position of str1, you check
if (str1.charAt(i+j) == str2.charAt(j))
for j=0 to str2.length()-1. If it passes, you get the answer. But if it fails, you move to the (i+1)-position and start all over again.
Haha. Can you write the code? You have about 20 min for that (time limit for a such question).
It is easier to code Rabin Karp with the same average complexity. It could be done for such time constraints.
- kirotawa January 24, 2014