Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
We both agreed on your point. But he just wanted to see if I can come up with a divide and conquer type algorithm to do this. We did this with an assumption of having unlimited number of processors and the parenthesis check might be replaces with a more processor intensive code block that will defeat the overhead of thread setup.
@msramachandran: which location you given interview in amazon and for what position exactly?
@msramachandran: one more question, you said you told the interviewer that you knew the question beforehand. What was the response from the interviewer? Should we tell them that I know the question already?
Well. I take interviews all the time. I can figure out if the candidate already knew the question and tries to fake it. And I am a little extra honest always :). So I don't telling him that I knew the solution already. It also cuts the crap and may be I will get a new question that I can break my head on.
He reacted saying "ok. but can you tell me the answer". For the second question, I told him that i knew the question and answer before he explained 25% of the question. Save a lot of time for both of us and it gave him a good opinion of myself.
int isValidParenthesis(char *str, int len) {
int count = 0, i;
for(i = 0; i < len; i++) {
if (str[i] == '[') {
count++;
}
else if (str[i] == ']') {
count--;
}
if (count < 0) {
return FALSE;
}
}
if (count > 0) {
return FALSE;
}
return TRUE;
}
// Function returns a pointer to end of string if its balanced
// Otherwise, string is imbalanced at next to the return pointer
char* check_balance( char *p )
{
if( *p == '\0' || *p == ')' )
return p;
else if( *p == '(' )
{
p = check_balance(p+1);
if( *p != ')' )
return --p;
}
return check_balance(p+1);
}
// Function returns a pointer to end of string if its balanced
// Otherwise, string is imbalanced at next to the return pointer
char* check_balance( char *p )
{
if( *p == '\0' || *p == ')' )
return p;
else if( *p == '(' )
{
p = check_balance(p+1);
if( *p != ')' )
return --p;
}
return check_balance(p+1);
}
Just plain bogus..
- Anonymous October 20, 2011The overhead of setting up threads to do this in parallel will be too much. If you string is so big that it actually improves performance that you are probably doing something wrong.