Bloomberg LP Interview Question
InternsCountry: United States
Interview Type: Phone Interview
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Test {
static List<String> validList=new ArrayList<>(Arrays.asList("<",">","{","}","[","]","(",")"));
public static void main(String [] args){
String s="(({[<>]}))";
char [] chars =s.toCharArray();
String b="";
boolean isValid=true;
for(int i=0;i<chars.length/2;i++){
b=Character.toString(chars[i])+Character.toString(chars[chars.length-i-1]);
if(!isValidBracketPair(b)){
isValid=false;
break;
}
}
if(s.length()%2!=0){
char middle=chars[s.length()/2+1];
if(validList.contains(Character.toString(middle))){
isValid=false;
}
}
System.out.println("result of " + s + " "+ isValid);
}
public static boolean isValidBracketPair(String b){
List<String> validList= new ArrayList<>();
validList.add("{}");
validList.add("[]");
validList.add("()");
validList.add("<>");
return validList.contains(b) || isNotBracket(Character.toString(b.charAt(0)),Character.toString(b.charAt(1)));
}
public static boolean isNotBracket(String a, String b){
return ! validList.contains(a) && ! validList.contains(b);
}
}
This is how I'd do it
1 push on (,{,[,<
2 pop on ),},],>
compare popped value
the fail conditions are
1 no opening brace
2 opening brace not matching with closing brace
3 unsatisfied opening braces
the success condition would be all braces matching in the right order
i.e stack empty at end
public class BracketChk {
static Stack<Character> stack = new Stack<>();
public static void main(String[] args) {
System.out.print("Enter the String with brackets : ");
String input = (new Scanner(System.in)).nextLine();
try {
for (int i = 0; i < input.length(); i++) {
System.out.println(stack.toString());
char c = input.charAt(i);
boolean flag = true;
switch (c) {
case '(': case '{': case '[': case '<':
stack.push(c);
break;
case ')': case '}': case ']': case '>':
char o = stack.pop(); // closing brace not having any opening brace
// throws exception
switch (c) {
case ')':
if (o != '(') flag = false;
break;
case '}':
if (o != '{') flag = false;
break;
case ']':
if (o != '[') flag = false;
break;
case '>':
if (o != '<') flag = false;
break;
}
}
if (!flag) throw new EmptyStackException(); // opening and closing brace not matching
}
if (stack.size() > 0) throw new EmptyStackException(); // more opening braces
System.out.println("Successful : Brackets balanced!!"); // all braces match
}
catch (EmptyStackException e) {
System.out.println("Unsuccessful : Brackets not balanced");
}
}
}
Like others mentioned using a stack and a dictionary of open and close characters this is trivial to implement. O(n) Python 3 implementation:
def validate_string(s, brackets_dict):
stack = []
open_bracket = set(brackets_dict.keys())
close_bracket = set(brackets_dict.values())
open = False
for char in s:
if not open:
if char in close_bracket:
return False
open = True
stack.append(brackets_dict[char])
else:
if char in open_bracket:
stack.append(brackets_dict[char])
else:
if not char == stack.pop():
return False
if len(stack) == 0:
open = False
return True
if __name__ == '__main__':
s = '{{[]}}'
validate_string(s, {'{': '}', '[': ']'})
Python - O(n) solution.
def validParentheses(s):
d = {')': '(', '}': '{', ']': '['}
stack = []
for i in s:
if i not in d:
stack.append(i)
else:
if len(stack) > 0:
temp = stack.pop()
else:
temp = '#'
if d[i] != temp:
return False
if len(stack) == 0:
return True
else:
return False
Edit the dictionary for different kinds of opening and closing tags.
Output:
- Diana.Savvatina November 05, 2018