Amazon Interview Question for Software Engineer Interns


Country: United States




Comment hidden because of low score. Click to expand.
3
of 3 vote

We can use a data structure stack to solve this problem. My Java code:
Time O(n)
Space O(n)

private boolean isValidParenthesis(char[] s) {
    // assume we have a map contains all type of parenthesis
    Map<Character, Character> parenthesisType = new HashMap<Character, Character>();
    parenthesisType.put('{', '}');
    parenthesisType.put('(', ')');
    parenthesisType.put('[', ']');

    // initial a stack
    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length; i++) {
        // if s[i] is a valid open parenthesis, push to stack
        if (parenthesisType.containsKey(s[i])) {
            stack.push(s[i]);
        }
        // if not, this may be a close parenthesis, so
        // check the top of stack, if it's same type
        // with s[i], remove this top open parenthesis
        else if (!stack.empty() && parenthesisType.get(stack.peek()) == s[i]) {
            stack.pop();
        }
        // if this parenthesis not exist or stack is empty, return false
        else {
            return false;
        }
    }

    // if our stack is empty, this mean s is valid parenthesis
    return stack.isEmpty();
}

- techinterviewquestion.com January 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Will your program not return on the first character if it is not a braces?

- nmathur February 05, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi nmathur, my program will return false immediately when it meets an invalid brace because this mean string s will be an invalid parenthesis sequence too.

- techinterviewquestion.com February 06, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 );
}

- zr.roman January 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

does this check for in order as well?
for example {[}]...

- djtrance February 01, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are right, thank you.
This check is not performed.
So, looks like using stack with O(n) space is inevitable.

- zr.roman February 01, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

well, actually, O(n) space is not inevitable.
I improved this solution such that it is still O(n) time and O(1) space.

- zr.roman February 01, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain how it happens in O(1) space?

- Anonymous February 06, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yep.
It's quite obvious. The space is needed only for 2 dictionaries, both of constant size. Constant size means O(1).
That's it.

- zr.roman February 06, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 );
}

- zr.roman January 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do we have also have to keep order into consideration?

Example ')(' would be unbalanced as the order is not right of opening and closing braces?

- Rajdeep January 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- davron.sh.karimov February 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

Would it be possible to explain why this is O(1) space? wouldn't you be pushing potentially n/2 elements on the stack?

- djtrance February 01, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- utkubulkan February 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
        }
    }

- t@_@n February 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- praveen pandit March 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- praveen pandit March 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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();
}

- er.vishalmehta83 January 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You forgot to pop the stack.

- ASDFASDFASDFASDFASDF February 01, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You forgot to pop the stack.

- asdQwspypfmb February 01, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

that, and the fact that '}' is not equal to '{'

- djtrance February 01, 2016 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More