Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
I considered a case when everything that inside quotes like "smth." or 'smth.' should be ignored.
So, my solution is:
private final static Map<Character, Character> symbolsPairs = new HashMap<>();
private final static Set<Character> brackets = new HashSet<>();
private final static Set<Character> quotes = new HashSet<>();
static {
// Brackets
brackets.add('<');
brackets.add('>');
brackets.add('{');
brackets.add('}');
brackets.add('[');
brackets.add(']');
brackets.add('(');
brackets.add(')');
// Quotes
quotes.add('\'');
quotes.add('\"');
// Pairs
symbolsPairs.put('(', ')');
symbolsPairs.put('<', '>');
symbolsPairs.put('{', '}');
symbolsPairs.put('[', ']');
}
public static void main(String[] args) {
try (Scanner in = new Scanner(System.in)) {
int T = in.nextInt();
StringBuilder output = new StringBuilder();
for (int t = 0; t < T; t++) {
boolean isBalanced = hasBalancedBracketsAndQuotes(in.next());
output.append(isBalanced ? "Yes" : "No").append(System.lineSeparator());
}
System.out.print(output);
}
}
static boolean hasBalancedBracketsAndQuotes(String s) {
LinkedList<Character> stack = new LinkedList<>();
boolean hasDoubleQuote = false;
boolean hasSingleQuote = false;
for (int i = 0; i < s.length(); i++) {
char b = s.charAt(i);
if (!brackets.contains(b) && !quotes.contains(b)) {
continue;
}
if (hasDoubleQuote && b == '\"') {
hasDoubleQuote = false;
continue;
}
if (hasSingleQuote && b == '\'') {
hasSingleQuote = false;
continue;
}
// to check brackets only we are not inside quotes
if (!hasDoubleQuote && !hasSingleQuote) {
if (symbolsPairs.containsKey(b)) {
stack.addLast(b);
} else if (quotes.contains(b)) {
if (b == '\"') {
hasDoubleQuote = true;
}
if (b == '\'') {
hasSingleQuote = true;
}
} else {
// to check that closed bracket is matched to open bracket
Character o = stack.pollLast();
if (o == null || !symbolsPairs.get(o).equals(b)) {
return false;
}
}
}
}
if (!stack.isEmpty() || hasDoubleQuote || hasSingleQuote) {
return false;
}
return true;
}
Tests are:
a{a{"a{{a"a}a}a - Yes
a{a{'a{{a'a}a}a - Yes
a{a{'a{{a"a}a}a - No
a{a{'a{{a"a}a}a - No
a{a{"a{{a}a"a}a - No
a{a{'a{{a}a'a}a - No
a{[a'a"a'a"a'a"a]a}a - Yes
a{[a'a'a'a"a'a"a]a}a - No
a{[a'a)a'a'a{a'a'a<a'a]a}a - Yes
a - Yes
a{a"a'a"a}a - Yes
a{a"a"a}a - Yes
a{{a'a}}'a}a} - Yes
<a{a(a[a"a}a]a>a)"a]a)a}a> - Yes
<a{a(a[a"a}a]a>a)"a>a}a)a] - No
a"a'a - No
a'a"a - No
public static bool Verify(string input)
{
Dictionary<char, char> OpeningClosing = new Dictionary<char, char>();
OpeningClosing.Add(')', '(');
OpeningClosing.Add('}', '{');
OpeningClosing.Add(']', '[');
Stack<char> stack = new Stack<char>();
int count = 0;
for (int i = 0; i < input.Length; i++)
{
if (OpeningClosing.ContainsValue(input[i]))
{
stack.Push(input[i]);
count = 0;
}
else if (OpeningClosing.ContainsKey(input[i]))
{
if (stack.Count == 0)
{
return false;
}
var closing = stack.Pop();
if (closing != OpeningClosing[input[i]] || count == 0)
{
return false;
}
}
else
{
count++;
}
}
if (stack.Count != 0)
{
return false;
}
return true;
}
module.exports = function (s) {
var S = []
for (var i = 0; i < s.length; ++i) {
var char = s.charAt(i)
var j = S.length - 1
if (char === '\'' || char === '\"') {
if (S[j] === char) {
S.pop()
} else {
S.push(char)
}
continue
}
if (char === '(' || char === '{') {
S.push(char)
}
if (char === ')') {
if (S[j] === '(') {
S.pop()
continue
} else {
return false
}
}
if (char === '}') {
if (S[j] === '{') {
S.pop()
continue
} else {
return false
}
}
}
return S.length === 0
}
var s = '\"A(\'\')B\"'
var solution = module.exports(s)
console.log(solution)
In the above example why is the second string invalid ? Is it invalid because the " and ' don't have a matching closing " or ' ? Or is it invalid because of the empty ()
- RAV January 21, 2017