Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
6
of 8 vote

Isn't it same as matching parenthesis?

- Hovercraft May 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Since string builder is specifically ab - won't stack just solve this problem.
If encounter a push inside stack. If encounter b pop out of stack.

If no a in stack and still encounter b - failure
if still a left in stack after run - failure
if no a left in stack after running through input -sucess

- yash May 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The plain recursion is obviously O(2^n) because if the pattern is something like aa and the string is like aaaa at every position you have two valid options, advance in the pattern or recurse it. So, the naive is exponential. Whether you start at the end or beginning doesn't make a difference.Other examples are ababaa with aba... O(m*n) using memoization isn't that bad.

Better will be preprocessing the generator string, finding out which suffix is a common prefix, so you can optimize backtracking. Knuth-Morris-Pratt O(n+m) style algorithm... but in 30 Minutes, assuming you first want to be safe by doing some brute force is tough.

- Chris May 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

@sriram.itech: how about: ababaa with aba as pattern:
A) Replace first (aba)baa -> baa -> false
B) Replace 2nd ab(aba)a -> (aba) -> true
str.replace starts either from start (A) or end .. so it won't work for all productions

Maybe reconsider your solution

- Chris May 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Under the hoods it's actually the parens match problem:

public class IsValidExpression {
    public static void main(String[] args) {
        System.out.println(isValid("aabbab"));
        System.out.println(isValid("abbaab"));
    }

    public static boolean isValid(String expression) {
        if (expression == null || expression.equals("")) {
            return false;
        }
        Stack<Character> opStack = new Stack<>();
        char[] c = expression.toCharArray();

        for (int i = 0; i < c.length; i++) {
            if (c[i] == 'a') {
                opStack.push(c[i]);
            } else if (c[i] == 'b') {
                if (opStack.isEmpty() || opStack.peek() != 'a') {
                    return false;
                }
                opStack.pop();
            }
        }

        if (!opStack.isEmpty()) {
            return false;
        }

        return true;
    }
}

- guilhebl May 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This would take n^2 time. Let me know if you have any other best methods to do

private static boolean isValidGeneration(String str1, String str2){
        if(str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0 || str1.length() % str2.length() != 0)
            return false;
        int prevLen = str1.length();
        while(str1.length() > 0){
            str1 = str1.replace(str2, "");
            if(prevLen == str1.length()){
                return false;
            }
            prevLen = str1.length();
        }
        return true;
    }

- sriram.itech May 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
function checkStack(st) {
if ( st.length >= 2 && st[st.length -1] == 'b' && st[st.length -2] == 'a' ) {
st.pop();
st.pop();
}
}

function isValid(l){
if ( l.length == 0 ) return false;
var st = [];
for ( var i = 0; i < l.length; ++i) {
if ( (i < l.length -l) && [i] == 'a' && l[i+1] == 'b' ) {
++i;
}
else if ( l[i] == 'a' ) {
st.push('a');
}
else if ( l[i] == 'b' ) {
st.push('b');
checkStack(st);
}
else {
return false;
}
};
return i == l.length && st.length == 0;
}

var l = process.argv[2].split('');
console.log(isValid(l));


}}

- Anonymous May 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function checkStack(st) {
    if ( st.length >= 2 && st[st.length -1] == 'b' && st[st.length -2] == 'a' ) {
        st.pop();
        st.pop();
    }
}

function isValid(l){
   if ( l.length == 0 ) return false;
   var st = [];
   for ( var i = 0; i < l.length; ++i) {
       if ( (i < l.length -l) && [i] == 'a' && l[i+1] == 'b' ) {
           ++i;
       }
       else if ( l[i] == 'a' ) {
           st.push('a');
       }
       else if ( l[i] == 'b' ) {
           st.push('b');
           checkStack(st);
       }
       else {
           return false;
       }
   };
   return i == l.length && st.length == 0;
}





var l = process.argv[2].split('');
console.log(isValid(l));

- Anonymous May 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- steve May 25, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* O(n) solution to the problem if generator string is "ab" */
char * findpattern(char *str) {
char *tmp;
if (!str || !(*str)) return NULL;
if (*str == 'b') return str;
tmp = str;
do {
tmp = findpattern(tmp+1);
if (!tmp || !(*tmp)) return NULL;
if (*tmp == 'b') tmp++;
} while(*tmp == 'a');
return tmp;
}

int main(void) {
char *op;
char *string = "abbaab";
op = findpattern(string);
if (!op || *op != 0) {
printf("Invalid string\n");
}
else {
printf("Valid string\n");
}
return 0;
}

- toseef.koliyariwala May 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it can be done in O(n) .At any index i number of 'a's must be >= number of 'b's till index i
Ex : aabb valid
abba invalid

- mahipalsaran May 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the generator string has the property that no two prefix and suffix substrings share a common prefix (e.g. "ab" in the description has this property wheras "aba" does not) then the problem has a simple O(n) solution:

def isValid(s, g):
    if not g:
        return False
    (st, gi) = ([], 0)
    for c in s:
        if c == g[gi]:
            gi += 1
            if gi == len(g):
                gi = st.pop() if st else 0            
        elif c == g[0]:
            st += [gi]
            gi = 1
        else:
            return False
    return not st and gi == 0

print isValid("abcababccabc", "abc")

- adr June 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Actually, problem is simpler than it looks. Can be done in O(n) with using any recursion or stack. For every pair 'a' has to come before 'b'. So if we start with counter = 0, and increment the count every time we see an 'a' and decrement it every time we see 'b'. So if the counter goes below 0 during the scan or end up not being zero, we know the input is not valid.

- Raminder June 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function isStringValid(str) {
    str = str || "aabbabab";
    let foundA = 0;
    for (ch of str.split('')) {
        ch === 'a' ? foundA ++ :foundA --;
        if(foundA < 0) { break; }
    }
    return foundA === 0;
}

- Rishabh Mehan July 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a simple solution in JS

function isStringValid(str) {
    str = str || "aabbabab";
    let foundA = 0;
    for (ch of str.split('')) {
        ch === 'a' ? foundA ++ :foundA --;
        if(foundA < 0) { break; }
    }
    return foundA === 0;
}

- Rishabh Mehan July 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean check(String s,int i,int countA,int countB) {
		
		if(i==s.length()-1 ) {
			if(countA > countB)
				return true;
			else
				return false;
		}
		
		
		else 
			if(s.charAt(i)=='a')
				countA++;
			else
				countB++;
		return check(s,i+1,(countA < countB ? countA: countA++),(countB < countA ? countB: countB++));
		
		
		
		
		
	}

- Anonymous July 19, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More