## Amazon Interview Question for Computer Scientists

• 0

Country: India
Interview Type: Written Test

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

I have solved it using stack.
Time Complexity - O(n)
Space complexity - O(n)

``````#include<bits/stdc++.h>
using namespace std;

int main()
{

string expression;
cin>>expression;
string s=expression;
stack <int> exp_idx;
bool is_invalid = 0;

/*if while iterating i get a ')' and the top of the stack is '(' the bracket pair is redundant, so we place '\$' signs in those places
*/
for(int i=0;i<expression.length();i++)
{
if(expression[i]==')')
{
if(!exp_idx.empty() and expression[exp_idx.top()]=='(')
{
expression[exp_idx.top()]='\$';
expression[i]='\$';
exp_idx.pop();
}
else
{

while(!exp_idx.empty() and expression[exp_idx.top()]!='(')
exp_idx.pop();
if(exp_idx.empty())
{
i=expression.length();
is_invalid=1;
}
else
{
exp_idx.pop();
}
}

}
else
exp_idx.push(i);

}

//special check for the removal of first and last bracket

int front=0,back=expression.length()-1;

while(front<expression.length() and expression[front]=='\$')
front++;
while(back>=0 and expression[back]=='\$')
back--;

if(front<back and expression[front]=='(' and expression[back]==')')
{
int i=front;
int bracket_balance=0;
while(i<back)
{
if(expression[i]=='(')
bracket_balance++;
else if(expression[i]==')')
{
bracket_balance--;
if(bracket_balance==0)
break;
}
i++;
}
if(i==back)
expression[front]=expression[back]='\$';
}
// special check ends

if(is_invalid)
cout<<"INVALID EXPRESSION";
else
for(auto it:expression)
if(it!='\$') cout<<it;

return 0;
}``````

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

we need to remove parenthesis if complete string enclose with otherwise return same string.

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

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

Comment hidden because of low score. Click to expand.
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;
}

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

private static String removeOuterBraceHelper(String test){

while(validate(test.substring(1, test.length()-1)) && test.startsWith("("))
test = test.substring(1, test.length()-1);

return test;
}

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

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.

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

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

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

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

}
}``````

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

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

}
}``````

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

``````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++;
}
if (statement[i] == ')')
{
closed++;
if (statement[i - 1] != '(' && statement[i - 1] != ')') removeCandidate.RemoveAt(removeCandidate.Count - 1);
}
}

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

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

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

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

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

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

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

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

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

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.