## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: Phone Interview

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

The idea here is to use a stack. Since the parenthesis that opens last must close first, last in first out.

Step 1: Begin iterating over the given string character by character.

Step 2: If your current character is an opening parenthesis then push onto the stack.

Step 3: If your current character is a closing parenthesis then pop from the stack and validate if the current character matches appropriately with the popped element.

ex - if currentChar=']' then popped element should be '['. If they don't match or your stack is empty and there is nothing to pop then return false right away.

Step 4: By the end of the string your stack is empty then your string is valid and we return true.

Extension:

Most of the steps would remain the same, except that we could initially save all the values (NOT Keys) of the Map into a Set.

Now we could perform the earlier steps and to identify if the current character is an opening of a parenthesis we simply query the key in the given map & to identify the current character represents the closure of a parenthesis we query from our Set.
I felt the validation in Step 3 was a little tricky.

Time complexity is O(n)
Space complexity is O(m+n)
n - size of the string
m - number of elements in the given map

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

For the extension, along with identifying if it is a opening or closing parenthesis, you would need to identify its pair. for example if you figured out that it's a closing ']' you would need to find its pair in terms of opening '['. So to do it in O(1) time, you would need to keep another map which has closing-opening pair. Isn't it?

Comment hidden because of low score. Click to expand.
0

Yes. The validation in step 3 should be customized accordingly. Which is why I called it tricky :)

Comment hidden because of low score. Click to expand.
0

I don't quite understand the extension. Is the question meaning that the opening and closing parenthesis are no longer standalone. They are wrapped by quotation marks like '(' and ')' so we must see '(' and ')' as a whole. Do I understand it correctly?

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

c++, implement

``````bool verify(string& str) {
stack<char> s;
int i;

for (i = 0; i < str.size(); i++) {
if (str[i] == '<' || str[i] == '[' || str[i] == '(') {
s.push(str[i]);
} else if (str[i] == '>') {
if (s.size() == 0 || s.top() != '<') return false;
s.pop();
} else if (str[i] == ']') {
if (s.size() == 0 || s.top() != '[') return false;
s.pop();
} else if (str[i] == ')') {
if (s.size() == 0 || s.top() != '(') return false;
s.pop();
}
}
if (s.size() > 0) return false;

return true;
}``````

Comment hidden because of low score. Click to expand.
0

Clean code. Accurately solves the first part of the question.

Comment hidden because of low score. Click to expand.
0

You just can do

``return s.size() == 0;``

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

//When using the hashmap. Have two pointers (one at the right end of the string(j), the other at the left end of the string(i)). On, the left end, if you encounter a '(','<','[' ,look up the matching key for i in the hashmap and retreive the corresponding value. See if the character at j matches the retrieved value.

Comment hidden because of low score. Click to expand.
0

What if your string is like - (sasas<sd[qw(1)qw]sd{12}>). above solution will not work.

Comment hidden because of low score. Click to expand.
0

what if your string is like this - "(sasas<sd[qw(1)qw]sd{12}>)" above logic will not work in this case

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

``````import java.util.Stack;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;

public class ValidateParen
{
public static boolean isValid(String s, Map<Character, Character> parens)
{
Set<Character> close = new HashSet<>();
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray())
{
if (parens.containsKey(c))
{
stack.push(parens.get(c));
}
else if (close.contains(c))
{
if (stack.isEmpty() || stack.pop() != c)
{
return false;
}
}
}
return stack.isEmpty();
}
}``````

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

Sample on java (it even will show the position of error)

``````import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class TestParenthesis {

public static void main(String[] args) {
String text = "<sjd>iua[dsds(d]<sa)sa<sasa>>sasasa";
System.out.println(checkSimple(text, '<', '>'));

Map<Character,Character> mp= new HashMap<Character,Character>();
mp.put('<', '>');
mp.put('(', ')');
mp.put('[', ']');
mp.put('{', '}');

System.out.println(checkMap(text, mp));
}

public static boolean checkSimple(String text, char begin, char end) {
char[] textArray = text.toCharArray();
int firstError = -1;
int cnt = 0;
for (int i = 0; i < textArray.length; i++) {
char a = textArray[i];
if (a == begin) {
cnt++;
if (cnt == 1) {
firstError = i;
}
} else if (a == end) {
cnt--;
if (cnt < 0) {
firstError = i;
break;
}
}
}

if (cnt != 0 && firstError >= 0) {
System.out.println("Error at position " + (firstError+1));
return false;
}
return true;
}

public static boolean checkMap(String text, Map<Character, Character> map) {
// making set of ends
Set<Character> ends = new HashSet<Character>();
char[] textArray = text.toCharArray();
// position of error
int firstError = -1;
// here will store ends which we expect
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < textArray.length; i++) {
Character a = map.get(textArray[i]);
if (a != null) {
// pushing into stack expected end
stack.push(a);
if (stack.size() == 1) {
// if this is first element at stack we should keep it's position as suspect for error
firstError = i;
}
} else if (ends.contains(textArray[i])) {
if (stack.isEmpty() || textArray[i] != (char) stack.pop()) {
firstError = i;
break;
}
}
}
if (firstError >= 0) {
System.out.println("Error at position " + (firstError+1));
return false;
}
return true;
}
}``````

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

On Java:

``````import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class TestParenthesis{

public static void main(String[] args) {
String text = "<sjd>iua[dsds(d]<sa)sa<sasa>>sasasa";
System.out.println(checkSimple(text, '<', '>'));

Map<Character,Character> mp= new HashMap<Character,Character>();
mp.put('<', '>');
mp.put('(', ')');
mp.put('[', ']');
mp.put('{', '}');

System.out.println(checkMap(text, mp));
}

public static boolean checkSimple(String text, char begin, char end) {
char[] textArray = text.toCharArray();
int firstError = -1;
int cnt = 0;
for (int i = 0; i < textArray.length; i++) {
char a = textArray[i];
if (a == begin) {
cnt++;
if (cnt == 1) {
firstError = i;
}
} else if (a == end) {
cnt--;
if (cnt < 0) {
firstError = i;
break;
}
}
}

if (cnt != 0 && firstError >= 0) {
System.out.println("Error at position " + (firstError+1));
return false;
}
return true;
}

public static boolean checkMap(String text, Map<Character, Character> map) {
// making set of ends
Set<Character> ends = new HashSet<Character>();
char[] textArray = text.toCharArray();
// position of error
int firstError = -1;
// here will store ends which we expect
Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < textArray.length; i++) {
Character a = map.get(textArray[i]);
if (a != null) {
// pushing into stack expected end
stack.push(a);
if (stack.size() == 1) {
// if this is first element at stack we should keep it's position as suspect for error
firstError = i;
}
} else if (ends.contains(textArray[i])) {
if (stack.isEmpty() || textArray[i] != (char) stack.pop()) {
firstError = i;
break;
}else{
firstError = -1;
}
}
}
if (firstError >= 0) {
System.out.println("Error at position " + (firstError+1));
return false;
}
return true;
}
}``````

Also it will output the error position.

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

``````public static bool ParenthesisValidation(string input)
{
//Program Call
//string input = "<[((kskfhdbh7)";
//var output = ParenthesisValidation(input);
var charToMatch = new List<Tuple<char, char>>()
{
new Tuple<char, char>('(', ')'),
new Tuple<char, char>('<', '>'),
new Tuple<char, char>('[', ']')
};
foreach (var pair in charToMatch)
{
if (input.Contains(pair.Item1) && input.Contains(pair.Item2))
{
var item1Count = input.Where(c => c == pair.Item1).ToList().Count();
var item2Count = input.Where(c => c == pair.Item2).ToList().Count();
if (item1Count != item2Count)
return false;
}
}
return true;
}``````

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

``````public static bool ParenthesisValidation(string input)
{
//Program Call
//string input = "<[((kskfhdbh7)";
//var output = ParenthesisValidation(input);
var charToMatch = new List<Tuple<char, char>>()
{
new Tuple<char, char>('(', ')'),
new Tuple<char, char>('<', '>'),
new Tuple<char, char>('[', ']')
};
foreach (var pair in charToMatch)
{
if (input.Contains(pair.Item1) && input.Contains(pair.Item2))
{
var item1Count = input.Where(c => c == pair.Item1).ToList().Count();
var item2Count = input.Where(c => c == pair.Item2).ToList().Count();
if (item1Count != item2Count)
return false;
}
}
return true;
}``````

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

Is this example valid? "(<str)>"

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

No. That is invalid. (<str>) would be valid.

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

``````/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
public static HashMap<Character,Character> paramMap=new HashMap<Character, Character>();
public static void main (String[] args) throws java.lang.Exception
{

paramMap.put('<','>');
paramMap.put('{','}');
paramMap.put('[',']');
paramMap.put('(',')');
paramMap.put('@','&');

String str="@sasas<sd[qw(1)qw]sd{>&";
checkValidString(str);

}

public static void checkValidString(String str){
char[] strchar=str.toCharArray();
Stack st = new Stack();
for(int i=0;i<str.length();i++){
if(!isAlpha(strchar[i])){
if(paramMap.containsKey(strchar[i]))
st.push(strchar[i]);
else{
char top=(char)st.pop();
if(!paramMap.get(top).equals(strchar[i])){
System.out.println("Invalid");
break;
}

}
}
}
if(st.empty()){
System.out.println("Valid!");
}
}

public static boolean isAlpha(char ch){
if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'))
return true;
return false;
}``````

}

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

``````public class ValidString {
private static final Map<Character, Character> brackets = new HashMap<>();

static {
brackets.put('(', ')');
brackets.put('[', ']');
brackets.put('<', '>');
}

public boolean isValid(String input) {
if (input == null || input.isEmpty()) {
return true;
}

char[] elements = input.toCharArray();
Stack<Character> stack = new Stack<>();
Set<Character> openBrackets = brackets.keySet();
Set<Character> closeBrackets = new HashSet<>(brackets.values());

for(char element : elements) {
if (openBrackets.contains(element)) {
stack.push(element);
} else if (closeBrackets.contains(element)) {
Character openElement;

if (stack.isEmpty() || (openElement = stack.pop()) == null) {
return false; // no valid open bracket
} else {
Character closeElement = brackets.get(openElement);
if (closeElement == null) {
return false; // unknown close bracket
} else if (!closeElement.equals(element)) {
return false;  // unexpected close bracket
}
}
} else {
// do nothing
}
}

return stack.isEmpty();
}

public static void main(String[] args) {
ValidString test = new ValidString();
}
}``````

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

``````bool isValid(string s){

stack<char> st;

for(int i = 0; i < s.length(); i++){
if(s[i] == '<' || s[i] == '(' || s[i] == '['){
st.push(s[i]);
}
else{
if(!st.empty() && ((s[i] == '>' && st.top() == '<') || (s[i] == ')' && st.top() == '(') || (s[i] == ']' && st.top() == '[')))
{
st.pop();
}
else if(isalpha(s[i]) || ispunct(s[i]) || (s[i] >= '0' && s[i] <= '9')){
continue;
}
else{
return false;
}
}
}

return st.empty();
}``````

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

``````import java.util.*;

public class App {

private static Map<Character, Character> map = new HashMap();
public static void main(String[] args) throws Exception {
map.put('[', ']');
map.put('<', '>');
map.put('{', '}');
map.put('(', ')');

System.out.println(isValid("<<[>]>"));
}

public static boolean isValid(String s) {
Stack<Character> stack = new Stack();
for(Character c:s.toCharArray()){
if (map.keySet().contains(c)) {
stack.push(c);
} else {
if (!stack.isEmpty() && c.equals(map.get(stack.peek())))
stack.pop();
else
return false;
}
}
return stack.isEmpty();
}``````

}

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.

### 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.