Barclays Capital Interview Question
Software Engineer / DevelopersInterview Type: In-Person
To add other characters like '{' and '}', all you need to do is modify the closing function, nothing else needs to change!
Sorry for the unformatted code. It goes like this:
public boolean isLeft(char c){
return c == '(' || c == '[';
}
public boolean isMatch(char l, char r){
return l == '(' && r == ')' ||
l == '[' && r == ']' ;
}
public boolean isValid(CharStream in){
if(!in.hasNext()) return true; //it's only at the start that empty sequence is legal
char c = in.next();
return isLeft(c) && isValid(1, c, in); //legal sequence should start with a left bracket
}
public boolean isValid(int level, char left, CharStream in){
if(!in.hasNext()) return false; //it's empty, then left can not be matched, so it's illegal
char c = in.next();
if(!isLeft(c) && isMatch(left, c) ||
isLeft(c) && isValid(level+1, c, in) && in.hasNext() && isMatch(left, in.next()))
{
if(level == 1) return isValid(in); //this indicates that the sequence may be divided into two fully matched part
else return true; //this is not the first level, need to return to last level first
}
else return false; //left can not be matched, so it's illegal
}
C++ version. Used a stack to check for matching open/close brackets and parenthesis.
#include <iostream>
#include <deque>
#include <stack>
class char_stream {
public:
char_stream(const std::string& data) : data_(data.begin(), data.end()) { }
bool has_next() const { return !data_.empty(); }
char next() { char n = data_.front(); data_.pop_front(); return n; }
private:
std::deque<char> data_;
};
bool is_valid(char_stream& s) {
std::stack<char> st;
while (s.has_next()) {
char next = s.next();
switch (next) {
case '[':
case '(':
st.push(next);
break;
case ']':
if (st.top() != '[')
return false;
st.pop();
break;
case ')':
if (st.top() != '(')
return false;
st.pop();
break;
default:
std::cout << "unknown char: " + next << std::endl;
return false;
}
}
return st.empty();
}
int main() {
std::cout << std::boolalpha;
char_stream good("()(([]))");
std::cout << is_valid(good) << std::endl;
char_stream bad("(]");
std::cout << is_valid(bad) << std::endl;
char_stream bad2("([)]");
std::cout << is_valid(bad2) << std::endl;
return 0;
}
You need a stack too keep track of the order of brackets.
public class CheckBracketConsistency {
public static boolean Validate(CharStream cs) {
Stack<Character> stack = new Stack<Character>();
Integer position = 0;
Character expected = 0;
while (cs.hasNext()) {
switch (cs.next()) {
case '(':
stack.push(')');
break;
case ')':
expected = stack.pop();
if (expected.compareTo(')') != 0) {
System.out.print("Expected " + expected.toString() + " at index " + position.toString() + ".");
return false;
}
break;
case '[':
stack.push(']');
break;
case ']':
expected = stack.pop();
if (expected.compareTo(']') != 0) {
System.out.print("Expected " + expected.toString() + " at index " + position.toString() + ".");
return false;
}
break;
default:
// Unknown character
return false;
}
position++;
}
return stack.empty();
}
}
Sample running code:
public class CareerCup {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
CharSequence[] cs = new CharSequence[3];
cs[0] = new CharSequence("(([]([]))");
cs[1] = new CharSequence("([)]");
cs[2] = new CharSequence("()(([]))([()])");
for (int i = 0; i < 3; i++) {
System.out.print("Checking sequence " + Integer.toString(i) + "...\n");
if (! CheckBracketConsistency.Validate(cs[i]))
System.out.println("The input sequence is invalid. Might have left some paranthesis open.");
else
System.out.println("The input sequence is valid.");
}
}
}
Output:
Checking sequence 0...
The input sequence is invalid. Might have left some paranthesis open.
Checking sequence 1...
Expected ] at index 2.The input sequence is invalid. Might have left some paranthesis open.
Checking sequence 2...
The input sequence is valid.
BUILD SUCCESSFUL (total time: 0 seconds)
public boolean isValid(CharStream in){
if(in.hasNext()){
if(in.next()=="(" or in.next=="["){
stack.push(in.next());
b //The 'in' parameter is in's substring from in'start+1 to in'length
//Suppose:this operation is done by 'next()';
isValid(in);
}
if((in.next()==")" and stack.get(stack.size-1)=="(") or (in.next()=="]" and statck.get(stack.size-1)=="[")){
stack.pop();
isValid(in);
}else{
return false;
}
}else{
//This sentence is from the first
return stack.size()==0;
}
}
I ignored recursion is requirement here is sample code
boolean isvalid( char c, CharStream input)
{
if( stream.hasNext() )
{
x = stream.getNext()
if( x == '(' || x == '[' || x == '{' )
return isvalid(x, input);
else if( x == ')' && c == '(' || x == ']' && c == '[' || x == '}' && c == '{] )
return true;
else if( isalphanumeric(x) )
continue
else
return false;
}
else if( c != '\0' )
return false;
return true;
}
call as isValid('\0', istream);
bool check_balance(CharStream *in, stack < char > *brackets)
{
if (in->hasNext)
{
char current = in->next();
if (current == ‘(‘ || current == ‘[‘)
{
brackets->push(c);
return check_balance(in, brackets);
}
else
{
if (brackets->empty())
return false;
char last = brackets->top();
if (last == ‘[‘ && current == ‘)’)
return false;
if (last == ‘(‘ && current == ‘]’)
return false;
return check_balance(in, brackets);
}
}
else
return brackets->empty();
}
bool isValid(const CharStream &in)
{
std::stack brackets;
return check_balance(CharStream &in, stack < char > &brakets);
}
public boolean isValid(CharStream in) {
return isValidImpl(in, 0, 0);
}
public boolean isValidImpl(CharStream in, int parenthesesIndex, int bracketsIndex)
{
if (!in.hasNext())
return parenthesesIndex == 0 && bracketsIndex == 0;
if (parenthesesIndex < 0 || bracketsIndex < 0)
return false;
char ch = in.next();
if (ch == '(') return isValidImpl(in, parenthesesIndex + 1, bracketsIndex);
if (ch == ')') return isValidImpl(in, parenthesesIndex - 1, bracketsIndex);
if (ch == '[') return isValidImpl(in, parenthesesIndex, bracketsIndex + 1);
if (ch == ']') return isValidImpl(in, parenthesesIndex, bracketsIndex - 1);
return isValidImpl(in, parenthesesIndex, bracketsIndex);
}
public boolean isValid(CharStream in) {
return isValidImpl(in, 0, 0);
}
public boolean isValidImpl(CharStream in, int parenthesesIndex, int bracketsIndex)
{
if (!in.hasNext())
return parenthesesIndex == 0 && bracketsIndex == 0;
if (parenthesesIndex < 0 || bracketsIndex < 0)
return false;
char ch = in.next();
if (ch == '(') return isValidImpl(in, parenthesesIndex+1, bracketsIndex);
if (ch == ')') return isValidImpl(in, parenthesesIndex-1, bracketsIndex);
if (ch == '[') return isValidImpl(in, parenthesesIndex, bracketsIndex+1);
if (ch == ']') return isValidImpl(in, parenthesesIndex, bracketsIndex-1);
return isValidImpl(in, parenthesesIndex, bracketsIndex);
}
The problem is easy solve with a container used, just as above has shown, while it could be a challenge to nail it completely recursively with just one function whose signature is given. The following is my code. It's also easy to add '{' and '}'.
public boolean isLeft(char c){
return c == '(' || c == '[';
}
public boolean isMatch(char l, char r){
return l == '(' && r == ')' ||
l == '[' && r == ']' ;
}
public boolean isValid(CharStream in){
if(!in.hasNext()) return true; //it's only at the start that empty sequence is legal
char c = in.next();
return isLeft(c) && isValid(1, c, in); //legal sequence should start with a left bracket
}
public boolean isValid(int level, char left, CharStream in){
if(!in.hasNext()) return false; //it's empty, then left can not be matched, so it's illegal
char c = in.next();
if(!isLeft(c) && isMatch(left, c) ||
isLeft(c) && isValid(level+1, c, in) && in.hasNext() && isMatch(left, in.next()))
{
if(level == 1) return isValid(in); //this indicates that the sequence may be divided into two fully matched part
else return true; //this is not the first level, need to return to last level first
}
else return false; //left can not be matched, so it's illegal
Here is the full implementation, one based on Stack and another one on recursion approache.
class CharStream
{
int _pos = 0;
char[] _stream = new char[0];
public CharStream()
{
}
public CharStream(string stream)
{
SetStream(stream);
}
public void SetStream(string stream)
{
if (string.IsNullOrEmpty(stream))
throw new ArgumentNullException();
_stream = stream.ToCharArray();
_pos = 0;
}
public bool HasNext
{
get
{
return _pos < _stream.Length;
}
}
public char Next()
{
if (!HasNext)
throw new ArgumentException();
return _stream[_pos++];
}
public string Stream
{
get { return new string(_stream); }
set { SetStream(value); }
}
public void Reset()
{
_pos = 0;
}
}
static bool ParentesisCorrect(CharStream stream)
{
Stack<char> stack = new Stack<char>();
while (stream.HasNext)
{
char nextValue = stream.Next();
if (nextValue == '[' || nextValue == '(')
stack.Push(nextValue);
else
{
if (stack.Count == 0)
return false;
char stackValue = stack.Pop();
if (nextValue == '[' && stackValue != ']' ||
nextValue == '(' && stackValue != ')' ||
nextValue == ')' && stackValue != '(' ||
nextValue == ']' && stackValue != '[')
return false;
}
}
return stack.Count == 0 ? true : false;
}
static bool recCor(CharStream stream)
{
bool result = true;
while (stream.HasNext)
{
result &= RecursiveParentesisCorrect(stream.Next(), stream, 0);
}
return result;
}
static bool OpenBracket(char c)
{
return c == '[' || c == '(';
}
static bool CloseBracket(char c)
{
return c == ')' || c == ']';
}
static bool RecursiveParentesisCorrect(char prevChar, CharStream stream, int depth)
{
char streamValue = stream.HasNext ? stream.Next() : 'x';
if (OpenBracket(streamValue))
{
if (!RecursiveParentesisCorrect(streamValue, stream, ++depth))
return false;
else
{
return depth != 0 && stream.HasNext ?
RecursiveParentesisCorrect(prevChar, stream, --depth) : false;
}
}
else
{
return (OpenBracket(prevChar) && CloseBracket(streamValue));
}
}
and a test method
static void TestBrackets()
{
CharStream cs = new CharStream("([][()])[][()]");
Console.WriteLine("{0} is {1} correct", cs.Stream, ParentesisCorrect(cs) ? "" : "NOT");
cs.Reset();
Console.WriteLine("{0} is {1} correct", cs.Stream, recCor(cs) ? "" : "NOT");
Console.ReadKey();
}
Iterative approch:
import java.util.Stack;
import java.util.EmptyStackException;
public class BracketValidatorIterative{
public boolean isValid(CharStream in){
final String openBrackets = "{[(";
final String closeBrackets = "}])";
Stack<Character> stack = new Stack<Character>();
while(in.hasNext()){
char c = in.next();
int index = -1;
if((index=containsBracket(openBrackets,c))>-1){
stack.push(c);
}else if((index=containsBracket(closeBrackets,c))>-1){
try{
char openCh = stack.pop();
if(openCh!=openBrackets.charAt(index))
return false;
}
catch(EmptyStackException e){
return false;
}
}
}
return stack.empty();
}
private int containsBracket(String str, char ch){
return str.indexOf(ch);
}
}
Recursive approach:
import java.util.Stack;
import java.util.EmptyStackException;
public class BracketValidatorRecursive{
final String openBrackets = "{[(";
final String closeBrackets = "}])";
public boolean isValid(CharStream in){
return isValid(in,new Stack<Character>());
}
private boolean isValid(CharStream in, Stack<Character> stack){
if(!in.hasNext()){
return true;
}else{
char c = in.next();
int index = -1;
if((index=containsBracket(openBrackets,c))>-1){
stack.push(c);
}else if((index=containsBracket(closeBrackets,c))>-1){
try{
char openCh = stack.pop();
if(openCh!=openBrackets.charAt(index))
return false;
}
catch(EmptyStackException e){
return false;
}
}
return true && isValid(in,stack);
}
}
private int containsBracket(String str, char ch){
return str.indexOf(ch);
}
}
How about this?
public class CharStreamTest {
public boolean isValid(CharStream in) {
// your code here
while (in.hasNext()) {
char c = in.next();
if (!isOpen(c)) {
return false;
}
if (!isValidSub(in, c)) {
return false;
}
}
return true;
}
private boolean isValidSub(CharStream in, char open) {
String before_in = in.toString();
char first = in.next();
if (!isOpen(first)) {
return isMatch(open, first);
}
if (!isValidSub(in, first)) {
return false;
}
return in.hasNext() && isMatch(open, in.next());
}
public boolean isMatch(char open, char close) {
return open == '(' && close == ')' || open == '[' && close == ']';
}
public boolean isOpen(char c) {
return c == '(' || c == '[';
}
public static void main(String[] s) {
CharStreamTest checker = new CharStreamTest();
System.out.println(checker.isValid(new CharStreamImpl("()")));
System.out.println(checker.isValid(new CharStreamImpl("([])")));
System.out.println(checker.isValid(new CharStreamImpl("()(([]))")));
System.out.println(checker.isValid(new CharStreamImpl("()(([])")));
System.out.println(checker.isValid(new CharStreamImpl("()(([])))")));
System.out.println(checker.isValid(new CharStreamImpl("()(([(]))")));
}
}
interface CharStream {
boolean hasNext();
char next();
}
class CharStreamImpl implements CharStream {
int index = 0;
int len;
String string;
public CharStreamImpl(String s) {
string = s;
len = s.length();
}
public boolean hasNext() {
return index < len;
}
public char next() {
return string.charAt(index++);
}
public String toString() {
return index + " / " + len;
}
}
Here's my python code for a recursive function without a helper:
def isValid(strm, tmp=[]):
if not strm.hasnext():
return len(tmp)==0
if len(tmp) == 0:
a = strm.next()
else:
a = tmp.pop()
b = strm.next()
if not ((x == '(' and y ==')') or (x == '[' and y ==']')):
tmp.append(a)
tmp.append(b)
return isValid(strm, tmp)
Would anyone care to comment if they would say this is not following the signature?
(The second argument has a default value)
public class CheckValidity {
int counter;
boolean isValid(CharStream in) {
if (in.hasNext()) {
char currChar = in.next();
if (currChar == '(' || currChar == '[') {
++counter;
} else if (currChar == ')' || currChar == ']') {
--counter;
}
} else {
return (counter == 0);
}
return isValid(in) || (counter == 0);
}
public static void main(String[] args) {
System.out.println(new CheckValidity().isValid(new CupCharStream("(xyz)".toCharArray())));
System.out.println(new CheckValidity().isValid(new CupCharStream("(xyz".toCharArray())));
System.out.println(new CheckValidity().isValid(new CupCharStream("xyz)".toCharArray())));
System.out.println(new CheckValidity().isValid(new CupCharStream("((x)y(z))".toCharArray())));
System.out.println(new CheckValidity().isValid(new CupCharStream("([[xyz])".toCharArray())));
}
}
How about this ?
public class CheckValidity {
int counter;
boolean isValid(CharStream in) {
if (in.hasNext()) {
char currChar = in.next();
if (currChar == '(' || currChar == '[') {
++counter;
} else if (currChar == ')' || currChar == ']') {
--counter;
}
} else {
return (counter == 0);
}
return isValid(in) || (counter == 0);
}
public static void main(String[] args) {
System.out.println(new CheckValidity().isValid(new CupCharStream("(xyz)".toCharArray())));
System.out.println(new CheckValidity().isValid(new CupCharStream("(xyz".toCharArray())));
System.out.println(new CheckValidity().isValid(new CupCharStream("xyz)".toCharArray())));
System.out.println(new CheckValidity().isValid(new CupCharStream("((x)y(z))".toCharArray())));
System.out.println(new CheckValidity().isValid(new CupCharStream("([[xyz])".toCharArray())));
}
}
interface CharStream
{
bool hasNext();
char? next();
}
public class Prackests: CharStream
{
string _s;
int index = 0;
public Prackests(string s)
{
_s = s;
}
public bool hasNext()
{
return index < _s.Length;
}
public char? next()
{
if (index < _s.Length)
{
return _s[index++];
}
return null;
}
}
public static void Main()
{
Console.WriteLine(IsValid(new Prackests("(})")));
}
static char? closingChar(char c)
{
switch (c)
{
case '[':
return ']';
case '{':
return '}';
case '(':
return ')';
default:
return null;
}
}
static bool IsValid(Prackests s)
{
if (s == null) return true;
return IsValidHelper(s.next(), s);
}
static bool IsValidHelper(char? c, Prackests s)
{
//if (c == null) return true;
var e = s.next();
if (closingChar(c.Value) == e) return true;
return s.hasNext() && IsValidHelper(e, s) && closingChar(c.Value) == s.next();
}
public boolean isValid(CharStream in) {
while (in.hasNext()){
char c=in.next();
if (c=='('||c=='['){
stack.push(c);
} else if (c==')'){
if (stack.get(stack.size()-1)=='('){
stack.pop();
}
} else if (c==']') {
if (stack.get(stack.size()-1)=='['){
stack.pop();
}
}
}
return stack.size()==0;
}
Recursion is very powerful if used correctly.
For instance, in this case, the code is quite simplified.
public boolean isValid (CharStream in) {
while (in.hasNext()) {
Char c = in.next();
Char expected = ' ';
switch(c) {
case '(': expected = ')'; break;
case '[': expected = ']'; break;
case '{': expected = '}'; break;
default: return false;
}
if (!isValid(in)) return false;
if (!in.hasNext()) return false;
if (in.next() != expected) return false;
}
return true;
}
Here is a purely recursive version in python (iteration is not exactly hasNext, next). I was not able to stick to the signature and needed a helper function, though (my earlier attempt was trying to stick to the signature, and use no helper functions).
Add the below for a complete program and some test cases.
- Subbu. November 29, 2013