## Amazon Interview Question for SDE-3s

Country: United States
Interview Type: Phone Interview

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

You can use a stack to solve the problem with O(n) for memory and time if you are only tracking one type of parenthesis you can promote the stack into a counter and improve the memory cost to O(1) as King@Work mentioned.

``````def is_balanced(a):
parens = []
for x in a:
if x == '(':
parens.append('(')
if x == ')':
if len(parens) == 0 or parens.pop() != '(':
return False
return len(parens) == 0``````

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

O(n) time and O(1) memory

keep a count of open brackets... increment when '(' & decrement when ')'

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

This does not works for "2)(3+4)(5"

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

char str[100];
cout<<"Enter the string : ";
cin>>str;
int flag;
for(int i=0;i<strlen(str)-1;i++)
{
flag =0;
for(int j=0;j<(strlen(str)-1);j++)
{
if(i!=j){
if(str[i]==str[j])
{
flag =1;
continue;
}
}
}
if(flag ==0)
{
cout<<str[i];
break;
}
}

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

``````public class BalancedMathematicalExpressionFinder {

public static boolean isBalancedExpression(String mathematicalExpression) {

return true;
}

public static void main(String[] args) {

String mathematicalExpression = "(1+2";

char[] mathematicalExpressionArray = mathematicalExpression.toCharArray();

ExpressionStack expStack = new ExpressionStack(mathematicalExpressionArray.length);

for(int i=0; i< mathematicalExpressionArray.length;i++){
if(mathematicalExpressionArray[i] == '(') {
expStack.push(mathematicalExpressionArray[i]);
} else if (mathematicalExpressionArray[i] == ')'){
expStack.pop();
}
}
if(expStack.isEmpty()){
System.out.println("Given expression is balanced");
} else {
System.out.println("Given expression is not balanced");
}

}

}

class ExpressionStack {

char[] data;
int maxSize;
int top;

public ExpressionStack(int size){
this.maxSize = size;
this.data = new char[this.maxSize];
this.top = -1;
}

public void push(char c) {
data[++top] =c;
}

public char pop() {
return data[top--];
}

public boolean isEmpty(){
}

}``````

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

``````public static boolean isBalanced(String equation) {
Stack<String> stack = new Stack();
for (int i = 0; i < equation.length(); ++i) {
char c = equation.charAt(i);
if (c == '(')
stack.push("(");
else if (c == ')') {
stack.pop();
}
}
return stack.isEmpty();
}``````

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

``````public static void Main(string[] args)
{
Stack parantheisis = new Stack();
string input = "(7+8(3)";
foreach (var c in input.ToCharArray())
{

if (c == '(')
{
parantheisis.Push(c);
}
if (c == ')')
{
parantheisis.Pop();
}
}
if (parantheisis.Count == 0)
{
Console.WriteLine("Given expression is balanced");
}
else
{
Console.WriteLine("Given expression is not balanced");
}
}``````

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

You need to go through the given string and keep the counter:
1. If you see '(' then you should increment the counter.
2. If you see ')' then you should decrement the counter. If the counter is negative then return false.
At the end of the given string the counter should be zero.

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

``````add first character to the stack

for each character in string
if character is (
if character on top of stack is ), then pop it off, else add your new character to stack
else if character is )
if character on top of stack is (, then pop it off, else add your new character to stack

return true if there are no items in the stack, false otherwise``````

this code will return true for these items: ))((, )()(, ((()))()...
efficiency is O(n)

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

``````class BracesCheck
{
public:
BracesCheck(const std::string &str)
: m_str(str)
, m_opening{ '(', '[', '{', '<' }
, m_closing{ ')', ']', '}', '>' }
{}

bool check()
{
std::stack<char> s;

for (size_t i = 0; i < m_str.size(); i++)
{
if (std::find(m_opening.begin(), m_opening.end(), m_str[i]) != m_opening.end())
{
s.push(m_str[i]);
}
else if (std::find(m_closing.begin(), m_closing.end(), m_str[i]) != m_closing.end())
{
if (s.empty() || !isPair(s.top(), m_str[i])) {
return false;
}

s.pop();
}
}
return s.empty();
}

bool isPair(char opening, char closing)
{
return (opening == m_opening[0] && closing == m_closing[0]) ||
(opening == m_opening[1] && closing == m_closing[1]) ||
(opening == m_opening[2] && closing == m_closing[2]) ||
(opening == m_opening[3] && closing == m_closing[3]);
}

public:
std::string m_str;
const std::vector<char> m_opening;
const std::vector<char> m_closing;
};

TEST(Array, CheckBracesString)
{
EXPECT_FALSE(BracesCheck("{sdfs(dfsfsd)}<1><").check());
EXPECT_TRUE(BracesCheck("{sdfs(dfsfsd)}[(1)]").check());
EXPECT_TRUE(BracesCheck("{}()[]<>").check());
}``````

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.