Amazon Interview Question
Write a function/method with this signature:
bool MyFunc(string term, string input) {}
The method should return true if the search term is found in the input string, even when there are other characters in between.
Examples:
"aba", "bbbbabbxxxxxxbb" returns false
"aba", "bbbbabbxxxxxxab" returns true
Basically, do I see an 'a', then 'b', then another 'a' before I run off the end of the input string?
Interview Answers
static boolean MyFunc(String term, String input) {
int j=0;
for(int i=0;i
static boolean MyFunc(String term, String input) {
int j=0;
for(int i=0;i
complexity: computational=O(n) (actually, Theta(n)); disk=O(1).
public class MyClass {
public static void main(String args[]) {
System.out.println("Found = " + myFunc("aba","bbbbbbabbbbbxxxxxab"));
System.out.println("Found = " + myFunc("aba","bbbbbbababbbbxxxxxab"));
System.out.println("Found = " + myFunc("aba","bbbbbbbbbbabbbbbbbbbbbbbbbaba"));
// add @Tests
}
public static boolean myFunc(String term, String input) {
boolean found=false;
int j=0,i=0;
// Edge cases
if(term.length()>input.length()) return false;
if(term.length()==0) return true;
// O(n): scanning the input
while(i