Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
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
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.
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;
}
}
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.
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;
}
{{
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));
}}
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));
/* 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;
}
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")
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++));
}
Isn't it same as matching parenthesis?
- Hovercraft May 22, 2018