Amazon Interview Question for Computer Scientists


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

- suvro_coder August 28, 2020 | Flag Reply
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.

- kamal suthar August 26, 2020 | Flag Reply
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;
}
}

- nooreddin August 26, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nooreddin August 26, 2020 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- nooreddin August 26, 2020 | Flag
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.

- NoOne August 29, 2020 | Flag Reply
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

- artem.shustov August 31, 2020 | Flag Reply
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;	
				
	}
}

- KritarthD September 03, 2020 | Flag Reply
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;	
				
	}
}

- KritarthD September 03, 2020 | Flag Reply
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++;
                    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;
        }

- Hassan Kachal September 12, 2020 | Flag Reply
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);
        }

- coolbro October 15, 2020 | Flag Reply
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);
        }

- coolbro October 15, 2020 | Flag Reply
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()

- Anonymous July 25, 2021 | Flag Reply
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()

- walid July 25, 2021 | Flag Reply


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