Friday, November 16, 2012

Huge file of parenthesis ( .. ) . Find if they are balanced

The file is huge and you don't want to run out of memory.
Pubblicato da a
Reazioni: 

1 comment:

  1. I failed this to an interview... so stupid!

    I think the solution should look like:

    size_t counter = 0;
    foreach (char c : stream) {
    if ( c == "(" ) ++counter;
    else ( c == ")" ) --counter;

    if ( counter < 0 ) return false;
    }
    if ( counter == 0 ) return true;
    return false;


    O(N) in time and O(1) in space

    ReplyDelete

Subscribe to: Post Comments (Atom)