Amazon Interview Question
Software Engineer InternsCountry: United States
c# implementation.
O(n) time.
O(1) space.
Return values: true - balanced, false - not balanced.
public static bool ValidateBrackets1( string str ) {
const uint n = 0;
// all possible brackets coupled
var dic = new Dictionary<string, uint> { {"{}", n}, {"()", n}, {"[]", n}, {"<>", n} };
// all possible closing brackets
var dic0 = new Dictionary<char, uint> { { '}', n }, { ')', n }, { ']', n }, { '>', n } };
foreach ( char c in str ) {
foreach ( var item in dic ) {
if ( item.Key[ 0 ] == c ) {
dic[ item.Key ]++;
dic0[ item.Key[ 1 ] ] = dic0.Values.Max() + 1;
break;
}
if ( item.Key[ 1 ] == c ) {
if ( dic0[ item.Key[ 1 ] ] != dic0.Values.Max() ) { return false; }
try {
checked { dic[ item.Key ]--; }
dic0[ item.Key[ 1 ] ] = (dic[ item.Key ] == 0)
? 0
: dic0.Values.Where( x => x > 0 ).Min() - 1;
} catch ( OverflowException ) {
return false;
}
break;
}
}
}
return dic.All( item => item.Value == 0 );
}
you are right, thank you.
This check is not performed.
So, looks like using stack with O(n) space is inevitable.
well, actually, O(n) space is not inevitable.
I improved this solution such that it is still O(n) time and O(1) space.
variant #2.
c#.
Time O(n).
Space O(1).
public static bool ValidateBrackets2( string str ) {
const uint n = 0;
// all possible pairs of brackets in forward order
var dic1 = new Dictionary<char, char> { {'{', '}'}, {'(', ')'}, {'[', ']'}, {'<', '>'} };
// all possible pairs of brackets in reverse order
var dic2 = new Dictionary<char, char> { {'}', '{'}, {')', '('}, {']', '['}, {'>', '<'} };
// all possible pairs of brackets coupled
var dic3 = new Dictionary<string, uint> { {"{}", n}, {"()", n}, {"[]", n}, {"<>", n} };
// all possible closing brackets
var dic0 = new Dictionary<char, uint> { { '}', n }, { ')', n }, { ']', n }, { '>', n } };
foreach ( char ch in str ) {
if ( dic1.ContainsKey( ch ) ) {
dic3[ ch.ToString() + dic1[ ch ] ]++;
dic0[ dic1[ ch ] ] = dic0.Values.Max() + 1;
continue;
}
if ( dic2.ContainsKey( ch ) ) {
if ( dic0[ ch ] != dic0.Values.Max() ) { return false; }
try {
checked { dic3[ dic2[ ch ] + ch.ToString() ]--; }
dic0[ ch ] = (dic3[ dic2[ ch ] + ch.ToString() ] == 0)
? 0
: dic0.Values.Where( x => x > 0 ).Min() - 1;
} catch ( OverflowException ) {
return false;
}
}
}
return dic3.All( item => item.Value == 0 );
}
python
time O(m)
space O(1)
import stack
def isBalanced(symString):
stcl = stack.Stack()
balanced = True
i = 0
while i < len(symString) and balanced:
if symString[i] in "{[(":
stck.push(symString[i])
else:
if stck.isEmpty():
balanced =False
else:
top = stck.pop()
if not matches(top, symString[i]):
balanced = False
i += 1
# if after all, symbols are still balanced
if balanced and stck.isEmpty():
return True
return False
def matches(open, close):
pOpen = "{[("
pClose = "}])"
return pOpen.index(open) == pClose.index(close)
C++ solution with example string
#include <iostream>
#include <string>
#include <stack>
using namespace std;
bool isOpen(char c)
{
return c == '(' || c == '{' || c == '[';
}
bool isClose(char c)
{
return c == ')' || c == '}' || c == ']';
}
bool isMatch(char c1, char c2)
{
return (((c1 == '(') && (c2 == ')')) ||
((c1 == '[') && (c2 == ']')) ||
((c1 == '{') && (c2 == '}')) );
}
bool isBalanced(const string& str)
{
stack<char> charStack;
for (unsigned int i = 0; i < str.size(); ++i ) {
if (isOpen(str[i])) {
charStack.push(str[i]);
} else if (isClose(str[i])) {
if (!charStack.empty() && isMatch(charStack.top(), str[i])) {
charStack.pop();
} else {
return 0;
}
}
}
return charStack.empty();
}
int main()
{
string str = "([[(){}]])({})";
cout << str << " : " << isBalanced(str) << endl;
}
Solution in Java
Time : O(n)
Space : O(n)
private static void checkBracketBalancing(String input){
char[] inputArr=input.toCharArray();
Map<Character,Character> charPairs=new HashMap<Character,Character>();
charPairs.put(')', '(');
charPairs.put('}', '{');
charPairs.put(']', '[');
Stack<Character> charst=new Stack<Character>();
for(Character c : inputArr){
if(charPairs.get(c)!=null){
if(!charst.isEmpty() && charPairs.get(c).equals(charst.peek())){
charst.pop();
}else{
System.out.println("Unbalanced");
return;
}
}else{
charst.push(c);
}
}
if(charst.isEmpty()){
System.out.println("Balanced");
}
}
#include <stdio.h>
int arr[][2] = {
{ '{','}'},
{ '[',']'},
{ '(',')'}
/* Keep on adding new set of brackets*/
};
void getvalue(char ch, int *f, int *t){
if (ch == 0) return;
for (int i = *f + 1; i < sizeof(arr) / sizeof(arr[0]); i++){
if (ch == arr[i][0]){
*f = i;
*t = 0;
break;
}
if (ch == arr[i][1]){
*f = i;
*t = 1;
break;
}
}
}
bool fun(char *str){
if (*str == 0) return true;
int f = -1;
int t = 0;
getvalue(*str, &f, &t);
if (f == -1) return true;
else if (t == 0) return (true && fun(str + 1));
else {
int ff = -1;
int tt = 0;
getvalue(*(str - 1), &ff, &tt);
if (ff == f && tt == 0) return true;
else return false;
}
}
int main(){
printf("%d",fun("([{exp[exp]})"));
return 0;
}
it wasn't well tested..
please comment on below.
int arr[][2] = {
{ '{','}'},
{ '[',']'},
{ '(',')'}
/* Keep on adding new set of brackets*/
};
void getvalue(char ch, int *f, int *t){
if (ch == 0) return;
for (int i = *f + 1; i < sizeof(arr) / sizeof(arr[0]); i++){
if (ch == arr[i][0]){
*f = i;
*t = 0;
break;
}
if (ch == arr[i][1]){
*f = i;
*t = 1;
break;
}
}
}
bool fun1(char *str, stack<char> *s){
if (*str == 0){
if (s->empty()) return true;
else return false;
}
int f = 0;
int t = 0;
getvalue(*str, &f, &t);
if (t == 0) s->push(*str);
else{
if (s->empty()) return false;
else{
char ch = s->top();
int ff = 0;
int tt = 0;
getvalue(ch, &ff, &tt);
if (ff == f && tt == 0) {
s->pop();
return fun1(str + 1, s);
}
else return false;
}
}
return (true && fun1(str + 1, s));
}
void fun2(char *str){
int *arr = (int*)calloc(sizeof(int)*128,1);
}
int main(){
stack<char> s;
printf("%d",fun1("(({}[(){}]))",&s));
return 0;
}
boolean validParenthsis(String str) {
Stack<Character> stk = new Stack<>();
for (int i = 0 ; i < str.length ; i++) {
char currChar = str.charAt(i);
if (currChar == '{' || currChar == '[' || currChar == '(' ){
stk.push(currChar);
} else {
if (stk.isEmpty() || stk.pop() != currChar) {
return false;
}
}
}
}
return stk.isEmpty();
}
We can use a data structure stack to solve this problem. My Java code:
Time O(n)
Space O(n)
- techinterviewquestion.com January 31, 2016