Amazon Interview Question
SDE-3sCountry: United States
Interview Type: Phone Interview
O(n) time and O(1) memory
keep a count of open brackets... increment when '(' & decrement when ')'
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(){
return top == -1;
}
}
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");
}
Console.ReadKey();
}
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)
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());
}
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.
- Fernando May 25, 2017