Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Good solution, add to that the cases like (a+b) having redundant brackets and a+(b) having redundant brackets
This is the perfect solution, We can modify a bit if we get a expression we can append () in Expression Explicitly though it's not needed but still.
so if you get a+(e+(b*c)) ==> (a+(e+(b*c)))
I will take stack as horizontal.
Stack ==> ( a ( e ( b top
when first ")" encountered value should be on the top. yes it is. so remove up to first "(".
Stack ==>
( a ( e
top
now encountered new ")"
if you don't encounter any "value" on the top of Stack then there is a redundant Brackets.
like
((a))
( ( a
after first encounter
left Stack ==> (
second encounter ")"
no value on the top. Error got it.
for every pair of parenthesis there needs to be an operator between them.
int check(char s[])
{
char c;
int i=0;
while(s[i]!='\0')
{
if(s[i]=='+' || s[i]=='-' || s[i]=='*' || s[i]=='/' || s[i]=='(')
push(s[i]);
if(s[i]==')')
{
c=pop();
if(c=='(' || c==')')
return 1;
pop();
}
i++;
}
if(ind!=0)
return 0;
return 1;
}
Extended to return false if invalid expression with unmatched open/close parens. Code in C#.
protected bool IsWellFormedExpression(string expression)
{
List<char> chars = new List<char>();
for (int i = 0; i < expression.Length; i++)
{
// Pop
if (expression[i] == ')')
{
// If preceding char is an open paren, then redundant
if (chars.Count > 0 && chars[chars.Count - 1] == '(')
return false;
// pop chars till we hit the open paren
bool foundOpenParen = false;
while (chars.Count > 0 && !foundOpenParen) {
foundOpenParen = (chars[chars.Count - 1] == '(');
chars.RemoveAt(chars.Count-1);
}
// Expression is not valid : close parens > open parens
if (!foundOpenParen)
return false;
}
// Push
else
{
chars.Add(expression[i]);
}
}
// Expression potentially not valid : open parens > close parens
return (!chars.Contains('('));
}
Here is a ruby solution with a few quick test cases:
def is_value(char)
/[A-Za-z0-9]+/ =~ char
end
def is_operator(char)
/[+\-*\/~?&^!]+/ =~ char
end
def redundant_parens?(string_in)
raise ArgumentError, "Input string cannot be nil" if string_in.nil?
# special cases
return true if string_in[0] == '(' && string_in[string_in.length-1] == ')'
stack = []
string_in.each_char do |char|
#puts "#{stack}"
if char == ")"
raise ArgumentError, "Malformed input string" if stack.size.zero?
if stack.size.zero? || !is_value(stack.last)
return true
end
stack.pop while stack.last != "("
stack.pop
elsif char == "("
stack.push char
elsif is_value char
next if !stack.length.zero? && is_value(stack.last)
stack.push char
elsif is_operator char
end
end
return false
end
test_ar = [
{string_in: "a+(b*c)", bool_out: false},
{string_in: "a+((b*c))", bool_out: true},
{string_in: "a+((b*c)+d)", bool_out: false},
{string_in: "a+(e+(b*c)+d)", bool_out: false},
{string_in: "a+(e+(b*c))", bool_out: false},
{string_in: "(a+(b*c))", bool_out: true},
{string_in: nil, bool_out: 'ArgumentError'},
{string_in: "", bool_out: false},
]
test_ar.each do |test|
begin
out = redundant_parens?(test[:string_in])
puts "\"#{test[:string_in]}\" returns #{out} of class #{out.class}"
if out != test[:bool_out]
puts "Test failed with value: #{out}, but should be #{test[:bool_out]}"
else
puts "Success!"
end
rescue ArgumentError => e
puts "\"#{test[:string_in]}\" has failed with exception #{e}"
if test[:bool_out] != "ArgumentError"
puts "Test failed with value: \"ArgumentError\", but should be #{test[:bool_out]}"
else
puts "Success!"
end
end
end
scan the string char by char
1, if the char is not ')' push it to stack, otherwise pop until you have a '(', pop that '('.
2, if the char is ')' and the top of stack is '(', then it contains redundant.
bool check(const std::string& s)
{
std::stack<char> stk;
int l = s.length();
for (int i = 0; i < l; ++i)
{
char c = s[i];
if (c != ')')
stk.push(c);
else
{
if (stk.top() == '(')
return false;
while (stk.top() != '(')
{
stk.pop();
}
if (!stk.empty())
stk.pop();
}
}
return true;
}
private static int testExpr(String s) {
char c;
int i = 0;
while (i < s.length()) {
if (s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*'
|| s.charAt(i) == '/')
push(s.charAt(i));
else if (s.charAt(i) == '(') {
if (!isEmpty() && top() == s.charAt(i) )
return 1;
else
push(s.charAt(i));
} else if (s.charAt(i) == ')') {
c = pop();
if (c == '(' || c == ')')
return 1;
//pop();
}
i++;
}
if (!isEmpty())
return 0;
return 1;
}
Ignoring BODMAS rule i think the problem is mainly based on fact that for each pair of paranthesis there should be one operator
hence Solution would be maintain 2 stack. one for brackets and one for operator
scan from left to right
push each opening bracket in stack1.
push each operator in stack 2
on encountaring a closing bracket 1) check if proper opening bracket is in stack 1, pop opening bracket 2) check if atleast one operator is present in the stack 2.
the stack 2 may be non empty in last.
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int redundant(char* exp,int length)
{
int content[100] = {0};
char b;
stack <char> expstack;
stack <char> paran;
for(int i=0;i<length;i++)
{
b = exp[i];
if(b==')')
{
paran.push(b);
}
else
{
expstack.push(b);
}
}
int j=-1;
int length2 = paran.size();
while(!paran.empty())
{
paran.pop();
char val = expstack.top();
++j;
while(val!='(' && !expstack.empty())
{
content[j]++;
expstack.pop();
val = expstack.top();
}
expstack.pop();
}
for(int i=0;i<length2;i++)
if(content[i]==0)
return 1;
return 0;
}
int main()
{
char a[] = {'a','+','(','(','b','*','c',')',')'};
char b[] = {'(','a',')'};
char c[] = "a+(e+(b*c))";
int l = sizeof(c)/sizeof(c[0]);
int res = redundant(c,l);
cout<<(res?"true":"false")<<endl;
}
What is wrong with this code?
private static boolean isRedundant(String str) {
int acount = 0;
int bcount = 0;
for (int i = 0; i < str.length(); i++) {
if(str.charAt(i) == '('){
if(i+1<str.length() && str.charAt(i+1) == '('){
acount=acount+1;i++;
}
}
if(str.charAt(i) == ')'){
if(i+1<str.length() && str.charAt(i+1) == ')'){
bcount=bcount+1;
i++;
}
}
if(acount>0 && acount == bcount){
return true;
}
}
return false;
}
What is wrong in this code?
private static boolean isRedundant(String str) {
int acount = 0;
int bcount = 0;
for (int i = 0; i < str.length(); i++) {
if(str.charAt(i) == '('){
if(i+1<str.length() && str.charAt(i+1) == '('){
acount=acount+1;i++;
}
}
if(str.charAt(i) == ')'){
if(i+1<str.length() && str.charAt(i+1) == ')'){
bcount=bcount+1;
i++;
}
}
if(acount>0 && acount == bcount){
return true;
}
}
return false;
}
What is the problem with this code
private static boolean isRedundant(String str) {
int acount = 0;
int bcount = 0;
for (int i = 0; i < str.length(); i++) {
if(str.charAt(i) == '('){
if(i+1<str.length() && str.charAt(i+1) == '('){
acount=acount+1;i++;
}
}
if(str.charAt(i) == ')'){
if(i+1<str.length() && str.charAt(i+1) == ')'){
bcount=bcount+1;
i++;
}
}
if(acount>0 && acount == bcount){
return true;
}
}
return false;
}
bool checkRedundancy(string str)
{
int len = str.length();
stack<char> st;
int optr = 0;
for(int i=0;i<len;i++)
{
if(str[i] == '(')
st.push(')');
else if(str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
optr++;
else if(str[i] == ')')
{
if(!optr)
return true;
optr--;
st.pop();
}
}
if(!st.empty() && !optr)
return true;
return false;
}
1. Take a variable to keep track of number of operator, initialize to 0 (optr).
2. Keep pushing "(".
3. If operator found, increment it.
4. If ")" found, pop once from stack and decrement optr by 1.
5. Keep doing this till end of input.
6. For no redundancy stack should be empty with optr = 0.
Hope it explains.
Done using stack with explaination.
onestopinterviewprep.blogspot.com/2014/03/detect-duplicate-parentheses-in.html
No, It's to help others. As long as someone is getting value out of it. It shdn bother you. I am sorry I din wanna be rude to u.
No. You are not helping at all.
This site is for first-hand interview experiences.
Not some ridiculous hear-say nonsense.
Go post on the forum.
Interesting problem.
We maintain a stack. We traverse the expression, and we push either a bracket, or a value. If the top of stack contains a value, we don't push another value, just leave it as is. If we encounter a right bracket, we expect a value on top to pop. We then pop the value and pop a bracket. If we don't get a value on top when we encounter a right bracket, then we have redundant brackets.
We ignore operators.
code would look something like
- Sandra's Bollocks. March 30, 2014stack <Token> s; TokenStream stream = new Lexer(input_expression); foreach token in stream { if (token.Type == Operator) continue; // Ignore them. if (token.Type == Value) { if (!s.Empty() && s.Top().Type == Value) continue; s.Push(token); } if (token.Type == Left) { // Left bracket s.Push(token); } if (token.Type == Right) { if (s.Empty()) throw IllegalExpressionException; if (s.Peek().Type != Value) return false; s.Pop(); if (s.Empty() || s.Top.Type() != Left) throw IllegalExpressionException; } } if (!s.Empty()) throw IllegalExpressionException; return true;