## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

Isn't it same as matching parenthesis?

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

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.

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

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;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 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.

Comment hidden because of low score. Click to expand.
1
of 1 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;
}``````

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;
}``````

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));

}}

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));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

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

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")``````

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;
}``````

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++));

}``````

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.

### 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.