Amazon Interview Question
Computer ScientistsCountry: India
Interview Type: Written Test
public static String removeOuterBrace(String test){
if(! validate(test) )
return "INVALID";
return removeOuterBraceHelper(test);
}
private static String removeOuterBraceHelper(String test){
char[] elements = test.toCharArray();
if(elements[0] != '(')
return test;
if(elements[elements.length - 1] != ')')
return test;
int matched = 1;
for (int i = 1; i < elements.length; i++) {
if(elements[i] == '(') {
matched++;
}
else if(elements[i] == ')') {
matched --;
if(i == elements.length - 1 && matched == 0)
if(validate(test.substring(1, test.length()-1)))
return removeOuterBraceHelper(test.substring(1, test.length()-1));
}
}
return test;
}
private static boolean validate(String test) {
char[] elements = test.toCharArray();
int i = 0;
int matchCount = 0;
for (char c:
elements) {
if(c == '(') {
matchCount++;
i++;
}
else if(c == ')') {
matchCount--;
i--;
}
if(matchCount < 0)
return false;
}
return i == 0;
}
}
private static String removeOuterBraceHelper(String test){
char[] elements = test.toCharArray();
if(elements[0] != '(')
return test;
if(elements[elements.length - 1] != ')')
return test;
while(validate(test.substring(1, test.length()-1)) && test.startsWith("("))
test = test.substring(1, test.length()-1);
return test;
}
It is incredibly simple.
1. If the first char and last char are not "(" and ")" - then return the same string.
2. If they are, then,
2.1 get the substring "sub" from position 1 to len-2 (0 based index ).
2.2. Verify if this string has matched parenthesis
2.3 If it has then return the "sub".
2.4 Else return the original string.
package com.company;
public class Main {
public static void main(String[] args) {
String s = "abc(c))";
//O(n)
System.out.println(parseStr(s));
}
static String parseStr(String s) {
//O(n)
if (!stringIsValid(s)) {
return "INVALID";
}
String result = null;
char[] chars = s.toCharArray();
//O(C)
for (int i = 0; i < chars.length; i++) {
int mirroredIndex = chars.length - i;
String validatedString = s.substring(i, mirroredIndex);
//O(n)
boolean valid = checkStringFullyInParethesis(validatedString);
if (!valid) {
result = s.substring(i, mirroredIndex);
break;
}
}
return result;
}
static boolean checkStringFullyInParethesis(String s) {
if (s.indexOf('(') == 0) {
int firstCloseParenthesisIndex = s.indexOf(')');
if (firstCloseParenthesisIndex > 0) {
for (var i = firstCloseParenthesisIndex + 1; i < s.length(); i++) {
char c = s.charAt(i);
if (c != ')' && c != '(') {
return false;
}
}
return true;
}
}
return false;
}
static boolean stringIsValid(String s) {
int countOpenParths = 0;
int countCloseParths = 0;
for (var i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
countOpenParths++;
} else if (s.charAt(i) == ')') {
countCloseParths++;
}
}
return countCloseParths == countOpenParths;
}
}
Complexity - O(n)
1) Verify if String is valid
2) In loop get substring sequentially for first and last element
2.1) Verify if substring is valid and entire fits in parenthesis
2.2) If yes - continue loop for second element, etc..
2.3) if no - exit with current substring
import java.util.*;
/*
Examples:
(((abc))) --> abc
(ab(c)) --> ab(c)
(abc09%(c)) --> abc09%(c)
ab(c) --> ab(c)
(ab)c --> (ab)c
abc(c)) → INVALID
(abc)(def) --> (abc)(def)
(abc)typ(def) --> (abc)typ(def)
((abc)(def)) --> (abc)(def)
*/
class RemoveSmallBrackets {
public static void main(String[] args) {
String[] inputs = new String[]{
"(((abc)))",
"(ab(c))",
"(ab09%(c))",
"ab(c)",
"abc(c))",
"(abc)(def)",
"(abc)typ(def)",
"((abc)typ(def))"
};
char leftChar = '(';
char rightChar = ')';
for(String s : inputs){
char[] ch = s.toCharArray();
System.out.println(String.valueOf(ch)+"->"+String.valueOf(filter(ch,leftChar,rightChar)));
}
}
private static char[] filter(char[] input, char x, char y){
char[] result = null;
if(count(input,x)!=count(input,y))
return new char[]{'I','N','V','A','L','I','D'};
if(input.length>0 && input[0]==x && input[input.length-1]==y){
result = filter(Arrays.copyOfRange(input, 1, input.length-1),x,y);
return (isValidFormat(result,x,y))?result:input;
}
return input;
}
private static boolean isValidFormat(char[] input, char x, char y){
int fx = firstIndexOf(input,x);
int fy = firstIndexOf(input,y);
if((fx==0 && fy==0) || (fx<fy))
return true;
else
return false;
}
private static int count(char[] input, char toBeSearched){
int count = 0;
for(char c: input)
if(c==toBeSearched)
count++;
return count;
}
private static int firstIndexOf(char[] input, char x){
int result = 0;
for(char c: input){
if(c==x)
return result;
result++;
}
return 0;
}
}
import java.util.*;
/*
Examples:
(((abc))) --> abc
(ab(c)) --> ab(c)
(abc09%(c)) --> abc09%(c)
ab(c) --> ab(c)
(ab)c --> (ab)c
abc(c)) → INVALID
(abc)(def) --> (abc)(def)
(abc)typ(def) --> (abc)typ(def)
((abc)(def)) --> (abc)(def)
*/
class RemoveSmallBrackets {
public static void main(String[] args) {
String[] inputs = new String[]{
"(((abc)))",
"(ab(c))",
"(ab09%(c))",
"ab(c)",
"abc(c))",
"(abc)(def)",
"(abc)typ(def)",
"((abc)typ(def))"
};
char leftChar = '(';
char rightChar = ')';
for(String s : inputs){
char[] ch = s.toCharArray();
System.out.println(String.valueOf(ch)+"->"+String.valueOf(filter(ch,leftChar,rightChar)));
}
}
private static char[] filter(char[] input, char x, char y){
char[] result = null;
if(count(input,x)!=count(input,y))
return new char[]{'I','N','V','A','L','I','D'};
if(input.length>0 && input[0]==x && input[input.length-1]==y){
result = filter(Arrays.copyOfRange(input, 1, input.length-1),x,y);
return (isValidFormat(result,x,y))?result:input;
}
return input;
}
private static boolean isValidFormat(char[] input, char x, char y){
int fx = firstIndexOf(input,x);
int fy = firstIndexOf(input,y);
if((fx==0 && fy==0) || (fx<fy))
return true;
else
return false;
}
private static int count(char[] input, char toBeSearched){
int count = 0;
for(char c: input)
if(c==toBeSearched)
count++;
return count;
}
private static int firstIndexOf(char[] input, char x){
int result = 0;
for(char c: input){
if(c==x)
return result;
result++;
}
return 0;
}
}
private static string RemoveParans(string statement)
{
if (statement.Length == 1)
if (statement[0] != '(' && statement[0] != ')') return statement; else return "INVALID";
int opened = 0;
int closed = 0;
var removeCandidate = new List<int>();
for (int i = 0; i < statement.Length; i++)
{
if (closed > opened) return "INVALID";
if (statement[i] == '(')
{
opened++;
removeCandidate.Add(i);
}
if (statement[i] == ')')
{
closed++;
if (statement[i - 1] != '(' && statement[i - 1] != ')') removeCandidate.RemoveAt(removeCandidate.Count - 1);
else removeCandidate.Add(i);
}
}
string result = string.Empty;
for (int i = 0; i < statement.Length; i++)
{
if (!removeCandidate.Contains(i)) result += statement[i];
}
if (result.Length > 2 && result.Substring(1, result.Length - 2).All(c => c != '(' && c != ')')) result = result.Substring(1, result.Length - 2);
return result;
}
public string RemoveOuterParens(string s)
{
var st = new Stack<int>();
int start = 0;
int end = s.Length-1;
int len = s.Length;
for (int i = 0; i < len; i++)
{
if (s[i] == '(')
{
st.Push(len - 1 - i);
}
else if (s[i] == ')')
{
if (st.Count == 0)
{
return "INVALID";
}
else
{
int top = st.Pop();
if (top == i)
{
start++;
end--;
}
}
}
}
return s.Substring(start, end - start + 1);
}
public string RemoveOuterParens(string s)
{
var st = new Stack<int>();
int start = 0;
int end = s.Length-1;
int len = s.Length;
for (int i = 0; i < len; i++)
{
if (s[i] == '(')
{
st.Push(len - 1 - i);
}
else if (s[i] == ')')
{
if (st.Count == 0)
{
return "INVALID";
}
else
{
int top = st.Pop();
if (top == i)
{
start++;
end--;
}
}
}
}
return s.Substring(start, end - start + 1);
}
from collections import deque
def stringParser( pattern ):
stack = deque()
for char in pattern:
if char == "(":
stack.append( ")")
elif char == ")":
if not stack or stack.pop() != char:
return "INVALID"
if stack:
return "INVALID"
leftIdx = 0
rightIdx = len( pattern ) - 1
while leftIdx < rightIdx:
if pattern[ leftIdx ] == "(" and pattern[ rightIdx ] == ")":
leftIdx += 1
rightIdx -= 1
else:
break
subStr = pattern[ leftIdx:rightIdx+1 ]
for char in subStr:
if char in { "(", ")"}:
stack.append( char )
for i in range( 1, len(stack) ):
if stack[i-1] == "(" and stack[i] == ")":
continue
else:
if stack[i-1] == ")" and stack[i] == "(":
subStr = "(" + subStr + ")"
return subStr
def testCast():
test = [ ( "(((abc)))", "abc" ),
( "(ab(c))", "ab(c)" ),
( "(abc09%(c))", "abc09%(c)" ),
( "ab(c)", "ab(c)" ),
( "abc(c))", "INVALID" ),
( "(abc)(def)", "(abc)(def)" ),
( "(abc)typ(def)", "(abc)typ(def)" ),
( "((abc)(def))", "(abc)(def)" ),
]
for inp, expected in test:
output = stringParser( inp )
print( output )
assert( output == expected )
testCast()
from collections import deque
def stringParser( pattern ):
stack = deque()
for char in pattern:
if char == "(":
stack.append( ")")
elif char == ")":
if not stack or stack.pop() != char:
return "INVALID"
if stack:
return "INVALID"
leftIdx = 0
rightIdx = len( pattern ) - 1
while leftIdx < rightIdx:
if pattern[ leftIdx ] == "(" and pattern[ rightIdx ] == ")":
leftIdx += 1
rightIdx -= 1
else:
break
subStr = pattern[ leftIdx:rightIdx+1 ]
for char in subStr:
if char in { "(", ")"}:
stack.append( char )
for i in range( 1, len(stack) ):
if stack[i-1] == "(" and stack[i] == ")":
continue
else:
if stack[i-1] == ")" and stack[i] == "(":
subStr = "(" + subStr + ")"
return subStr
def testCast():
test = [ ( "(((abc)))", "abc" ),
( "(ab(c))", "ab(c)" ),
( "(abc09%(c))", "abc09%(c)" ),
( "ab(c)", "ab(c)" ),
( "abc(c))", "INVALID" ),
( "(abc)(def)", "(abc)(def)" ),
( "(abc)typ(def)", "(abc)typ(def)" ),
( "((abc)(def))", "(abc)(def)" ),
]
for inp, expected in test:
output = stringParser( inp )
print( output )
assert( output == expected )
testCast()
I have solved it using stack.
Time Complexity - O(n)
Space complexity - O(n)
- suvro_coder August 28, 2020