Amazon Interview Question Software Engineer / Developers
My solution was...
while(*str)
if(*str=='(')
push('(');
else
if(pop() == STACK_EMPTY)
return FALSE;
str++;
return TRUE;
Dude..according to ur code ... it will accept string like "((((" ....i don't think that is asked in question..let me know if i m wrong!!
i think this would do..
while(*str)
{
if(*str=='(')
push('(');
else
if(pop() == STACK_EMPTY)
return FALSE;
str++;
}
if(pop()==STACK_EMPTY)
return TRUE;
return FALSE;
I do not understand why a stack is needed. It is just to increment a counter whenever meeting '(', and decrement the counter whenever ')'. During the whole process, make sure the counter is non-zero; otherwise, return false.
Hi.
If )( is considered valid, then just do cnt++ for every '(' and cnt-- for every ')'. Otherwise, the running sum should never become <0 and total sum =0.
For checking running sum , either use array or interval trees.
You are right .. if the (()()) is valid, then we can have the code as:
bool isValid(char *p) {
int openB,CloseB,i;
openB=CloseB=i=0;
while (*(p+i)) {
if (*(p + i) != '(')
openB++;
if (*(p + i) != '(')
CloseB++;
if(openB<CloseB)
return false;
}
if(openB==CloseB)
return true;
return false;
}
My attempt for this problem
int func(char* str)
{
int count=0;
// The second condition ensures that ) cannot come before an open (
while(*str!='\0'&& count>=0)
{
if(*str=='(')
count++;
else
count--;
str++;
}
// Equal number of ( and )
if(count==0)
return 1;
else
return -1;
}
seems incorrect to me
))(( will give 0, though its incorrect
should be like
if(string == '('){
count++
else
if(count > 0){
count --;
}
else{
return false;
}
}
/* finally */
if count!= 0{
return false
}
push if you find '(' and if you find ')' do pop. at the end if the stack in empty then string is correct.
- Anonymous May 26, 2010