# Postfix Notation Evaluation - Amazon Top Interview Questions

### Problem Statement :

```Postfix notation is a way to represent an expression where the operator comes after the operands.

For example, ["2", "2", "+", "6", "*"] would be equal to 24, since we have (2 + 2) * 6 = 24.

Given a list of strings exp, representing a postfix notation consisting of integers and operators ("+", "-", "*", "/"), evaluate the expression. "/" is integer division.

Example 1

Input

exp = ["9", "3", "+", "2", "/"]

Output

6

Explanation

(9 + 3) / 2 = 6

Example 2

Input

exp = ["3", "9", "-", "4", "/"]

Output

-1

Explanation

(3 - 9) / 4 = -1```

### Solution :

```                        ```Solution in C++ :

#define long long long
long cal(long first, string& op, long second) {
if (op == "*") return first * second;
if (op == "-") return first - second;
if (op == "+") return first + second;
return first / second;
}

int solve(vector<string>& exp) {
stack<long> st;
for (int i = 0; i < exp.size(); i++) {
if (exp[i] == "+" or exp[i] == "-" or exp[i] == "/" or exp[i] == "*") {
long a = st.top();
st.pop();

long b = st.top();
st.pop();

long res = cal(b, exp[i], a);
st.push(res);

continue;
}

long d = stol(exp[i]);
st.push(d);
}

return st.top();
}```
```

```                        ```Solution in Python :

OPERATIONS = {"+": add, "-": sub, "*": mul, "/": lambda a, b: int(a / b)}

class Solution:
def solve(self, exp):
stack = []

for x in exp:
if x in OPERATIONS:
b, a = stack.pop(), stack.pop()
stack.append(OPERATIONS[x](a, b))
else:
stack.append(int(x))

return stack[-1]```
```

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty