Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
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)
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.
#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;
}
#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;
}
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);
}
}
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());
}
}
//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);
}
public static void main(String[] args)
{
try
{
String substring, text;
int count = 0, length, i = 0, index, prevIndex = -1;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
text = br.readLine();
substring = br.readLine();
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();
}
}
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;
}
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);
}
}
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));
}
}
- Sami Alam April 14, 2012static 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; }