Stage I: 10 competitive programming problems that cover the stack data structure, ordered by complexity:
1.
Implement a Stack - Implement a stack data
structure that supports push (), pop (), and peek () operations.
|
#include
<iostream> #include
<vector> using namespace std; class Stack { private: vector<int> items; public: void push(int item) { items.push_back(item); } int pop() { if (!is_empty()) { int top = items.back(); items.pop_back(); return top; } } int peek() { if (!is_empty()) { return items.back(); } } bool is_empty() { return items.empty(); } }; Intuition: The intuition behind
this implementation is that a stack is a Last-In-First-Out (LIFO) data structure,
which means that the last item added to the stack will be the first item
removed. Therefore, we can use a vector to store the items in the stack and
manipulate the back of the vector to implement the push(), pop(), and peek()
operations efficiently. Approach: In this
implementation, we use a vector to store the items in the stack. The push()
method appends an item to the end of the vector, while the pop() method
removes and returns the last item in the vector. The peek() method returns
the last item in the vector without removing it. The is empty() method checks
if the vector is empty and returns a boolean value. The time complexity
of push(), pop(), and peek() operations is O(1), as we are only manipulating
the back of the vector. The space complexity is O(n), where n is the number
of items in the stack. This is because we are storing each item in the
vector. |
2.
Balanced Parentheses - Given a string of
parentheses, determine if the parentheses are balanced. For example, the string
"({[]})" is balanced, but the string "({[}])" is not.
|
Intuition
from problem statement: A string of
parentheses is considered balanced if for each opening parenthesis, there is
a corresponding closing parenthesis in the correct order. For example,
"()" is balanced, while ")(" is not. This problem can be
solved using a stack data structure, where we push an opening parenthesis
onto the stack and pop it when we encounter its corresponding closing parenthesis. Approach
of Solution: To solve this
problem, we can iterate through the string and push each opening parenthesis
onto a stack. When we encounter a closing parenthesis, we check if it matches
the top of the stack. If it does, we pop the opening parenthesis from the
stack. If it does not match, we know the string of parentheses is not
balanced. We also need to handle cases where there are extra opening or
closing parentheses. If we have iterated through the entire string and the
stack is empty, then we know the parentheses are balanced. Time and
Space Complexity: The time
complexity of this solution is O(n), where n is the length of the string,
because we iterate through the string once. The space complexity is also
O(n), because in the worst case, we push all the opening parentheses onto the
stack. Solution in
terms of cpp code with best practices and documentation: #include
<iostream> #include
<stack> using
namespace std; /** * Determine if a string of parentheses is
balanced. * @param parentheses the string of parentheses
to check * @return true if the parentheses are
balanced, false otherwise */ bool
is_balanced(string parentheses) { stack<char> s; for (char c : parentheses) { if (c == '(' || c == '{' || c == '[')
{ s.push(c); } else if (c == ')' &&
!s.empty() && s.top() == '(') { s.pop(); } else if (c == '}' &&
!s.empty() && s.top() == '{') { s.pop();
} else if (c == ']' &&
!s.empty() && s.top() == '[') { s.pop(); } else { return false; } } return s.empty(); } int main() { string parentheses1 = "({[]})"; string parentheses2 = "({[}])"; if (is_balanced(parentheses1)) { cout << parentheses1 <<
" is balanced." << endl; } else { cout << parentheses1 <<
" is not balanced." << endl; } if (is_balanced(parentheses2)) { cout << parentheses2 <<
" is balanced." << endl; } else { cout << parentheses2 <<
" is not balanced." << endl; } return 0; } |
3.
Evaluate Postfix Expression - Given a postfix
expression, evaluate the expression using a stack. For example, given the
expression "2 3 + 5 *", the result should be 25.
|
Intuition
from problem statement: A postfix
expression is an expression where the operators come after their operands.
For example, "2 3 +" means "2 plus 3". To evaluate a
postfix expression, we can use a stack data structure to keep track of the
operands. When we encounter an operator, we pop the required number of
operands from the stack, perform the operation, and push the result back onto
the stack. Approach
of Solution: To solve this
problem, we can iterate through the postfix expression and push each operand
onto a stack. When we encounter an operator, we pop the required number of
operands from the stack, perform the operation, and push the result back onto
the stack. After we have iterated through the entire postfix expression, the
result should be the only item remaining on the stack. Time and
Space Complexity: The time
complexity of this solution is O(n), where n is the length of the postfix
expression, because we iterate through the expression once. The space
complexity is also O(n), because in the worst case, we push all the operands
onto the stack. Solution in
terms of cpp code with best practices and documentation: #include <iostream> #include <stack> #include <sstream> using namespace std; #define FORREF #ifndef FORREF /** * Evaluate a
postfix expression. * @param expression
the postfix expression to evaluate * @return the
result of the expression */ int evaluate_postfix(string expression) { stack<int> s; istringstream
iss(expression); string token; while (iss >> token)
{ if (isdigit(token[0])) {
s.push(stoi(token)); } else { int operand2 = s.top();
s.pop(); int operand1 = s.top();
s.pop(); int result; if (token == "+") {
result = operand1 + operand2; } else if (token == "-") {
result = operand1 - operand2; } else if (token == "*") {
result = operand1 * operand2; } else if (token == "/") { if (operand2 == 0) throw new exception();
result = operand1 / operand2; }
s.push(result); } } return s.top(); } int main() { string
expression = "2 3 - 1 *"; try { int result =
evaluate_postfix(expression); cout
<< "The result of " << expression
<< " is " << result << endl; } catch (...) { cout
<< "Exception need to be handled here!!!" << endl; } return 0; } #endif // FORREF |
4.
Next Greater Element - Given an array of
integers, for each element, find the next greater element in the array. For
example, given the array [4, 5, 2, 25], the result should be [5, 25, 25, -1].
5.
Maximum Area of Histogram - Given an array
representing the heights of bars in a histogram, find the maximum area of a
rectangle in the histogram.
6.
Largest Rectangle in a Binary Matrix - Given a
binary matrix, find the largest rectangle of 1's.
7.
Stock Span Problem - Given an array of stock
prices, find the number of consecutive days before the current day when the
stock price was less than or equal to the current day's price.
8.
Infix to Postfix Conversion - Given an infix
expression, convert it to postfix notation.
9.
Minimum Add to Make Parentheses Valid - Given a
string of parentheses, find the minimum number of parentheses that must be
added to make the string valid.
10.
Implement a Queue using Stacks - Implement a
queue data structure using two stacks. The queue should support enqueue (), dequeue
(), and peek () operations.
Stage – II -> 10 advanced competitive programming problems
that involve the stack data structure:
1.
Largest Rectangle in a Histogram - Given an
array representing the heights of bars in a histogram, find the largest
rectangle in the histogram.
2.
Minimum Stack - Implement a stack data structure
that supports push(), pop(), and getMinimum() operations, all with O(1) time
complexity.
3.
Reverse Substrings Between Each Pair of
Parentheses - Given a string containing parentheses, reverse the substrings
between each pair of parentheses.
4.
Maximum Frequency Stack - Implement a stack data
structure that supports push(), pop(), and getMaxFrequency() operations, all
with O(1) time complexity.
5.
Valid Parenthesis String - Given a string
containing the characters '(' , ')' , and '*', determine if the string is
valid.
6.
Score of Parentheses - Given a balanced
parentheses string, compute the score of the string based on the following
rule: () has score 1, AB has score A + B, and (A) has score 2 * A.
7.
Online Stock Span - Write a class StockSpanner
that maintains a daily stock price and returns the span of the stock's price
for the current day. The span of the stock's price today is defined as the
maximum number of consecutive days (starting from today and going backward) for
which the stock price was less than or equal to today's price.
8.
Simplify Path - Given an absolute path for a
file (Unix-style), simplify it. For example, given "/a/./b/../../c/",
return "/c".
9.
Exclusive Time of Functions - Given the logs of
a system, each log is a string that has the following format:
"function_id:start_or_end:timestamp". Return the exclusive time of
each function, i.e., the total time that the function spent during the interval
it was active, without counting time spent in any other function.
10.
Asteroid Collision - Given an array of integers
representing asteroids in a row, simulate the collision of the asteroids. Two
asteroids collide if they are of opposite signs and the absolute value of their
sizes are equal. After the collision, the smaller asteroid disappears and the
larger asteroid may continue moving in the same direction.
Comments
Post a Comment