Here Interview Question Software Developers
Country: United States
Interview Type: In-Person
A simple approach is to use a stack with push-pop to solve.
But given the interviewer specifically said 'stream' 'thread' 'distributed', he is specifically looking at scale here.
Use a main thread to receive the stream head, and use child threads to maintain stacks and do processing(push/pop). The stacks would have fixed sizes; so use some flags to notify, when they get full or empty.
Keep one count say cnt. If you encounter '(' increment counter by one. If you encounter ')' decrement by one. Perform increment or decrement in synchronized method. if counter is negative it means that parantesis dont match.
public class Matcher{
private Integer counter;
private boolean synchronized isValid(String symbol){
if(symbol.equals("(")){
counter++;
}else if(symbol.equals(")")){
counter--;
}
if(counter<0){
throws new Exception("paranthesis do not match") ;
}
}
}
Will this work for ')()('? The sum at the end is -1 + 1 - 1 + 1 = 0. Will this detect properly nested format?
@Yev: Adding a check after incrementing/decrementing the counter should fix this. Basicaaly, the counter should never be negative, and at the end of the string should be 0. If the counter becomes negative t any point, then nomatter what the restof the string is, the parantheses will not match.
You can push open paranthesis into stack and pop the closing paranthesis and ignore other characters in the string. After parsing the entire string, if your stack should be empty for correctly paired string
- riya July 16, 2015