#stack

Solutions Stack This is a classical problem which requires a stack. Possible C++ Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <stack> #include <map> #include <iostream> using namespace std; static const map<char, char> closedParen { {')', '('}, {']', '[',}, {'}', '{'} }; int main() { int N; cin >> N; string line; while (N--) { stack<char> paren; bool error = false; cin >> line; for (auto c : line) { if (c == '(' || c == '[' || c == '{') paren. [Read More]

You are given an expression in Reverse Polish Notation (RPN) and you have to evaluate it. Input Format Space separated terms of the expression to evaluate (at least one element). Constraints Each numeric element fits an int32. Any other token is either +, -, *, / The result is guaranteed not to go beyond the int32 representation Output Format The result of the expression evaluation, as a single number. Solutions The solution for this excercise would be to use a stack. [Read More]

Solutions Jotting down a brute force solution is easy but inefficient. The problem can be solved efficiently only by implementing a strategy to skip unnecessary checks. One solution uses two stacks and two support arrays: stack memoryL keeps track of the latest elements that are smaller than the current one (from left to right) stack memoryR keeps track of the latest elements that are smaller than the current one (from right to left) array left contains the values of \(Left\) array right contains the values of \(Right\) Think about how to construct the left array. [Read More]

Solutions This is a variation of the classical problem Next greater element we have tackled here. As in that case, the naive solution consists in using two loops: for each element we find the next greater element. This solution is quadratic because for each element we pay a linear search. The worst case is when the array is sorted in decreasing order. Linear online solution based on stack The most common approach to this kind of problems consists in using a stack to store the “candidate” NGE for all the previous elements. [Read More]

Preamble This is a typical challenge where the environment we have to work in is constrained and we have to find a solution under some conditions. Same story when we are not allowed to allocate extra space, or when some basic operation is disabled (e.g. for loop). Why “constrained” challenges make perfect sense Although such challenges could seem senseless, they are instead very useful to improve our ability to adapt. In the real life this skill is generally very important. [Read More]

Solutions This is a classical challenge requiring stacks. A C++ solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include <string> #include <stack> #include <iostream> #include <algorithm> using namespace std; int main() { string S, tmp; //S.reserve(1000000); int Q, op, K; cin >> Q; stack<string> states; while (Q--) { cin >> op; switch(op) { case 1: states. [Read More]

Given an absolute path for a file (Unix-style), simplify it. This challenge simulates an interview problem. As you see, no more information about input constraints are provided. You - probably - have to interact with Marco (who impersonates the interviewer) and ask him some questions to refine your knowledge about the problem. Input Format Only a string is provided. The path always begins with ‘/’ (root directory). Output Format The path simplified. [Read More]

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element \( x \) is the first greater element on the right side of \( x \) in array. Elements for which no greater element exist, consider next greater element as \( -1 \). Input Format You are given \( N \), the number of elements, followed by \( N \) space-separated integer values. [Read More]