### Coding Interview Questions set 5

Let's begin with set 5,

Q11)Valid Parentheses problem.

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']',

determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Examples :

a)Input: s = "()"

Output: true

Example 2:

b)Input: s = "()[]{}"

Output: true

Example 3:

c)Input: s = "(]"

Output: false

Solution:

`var isValid = function(s) {   const obj={            "}":"{",            "]":"[",            ")":"(",        },    var stack=[];          for(let i=0;i<s.length;i++){       if(s[i] in obj) {          if(!stack.length || stack[stack.length-1]!==obj[s[i]]) {              return false;           }          else stack.pop();     }else stack.push(s[i]);  } return !stack.length;};`

Logic: We have to use the stack here to solve our problem.

You may also like these articles:

12)Staircase problem.

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps.

In how many distinct ways can you climb to the top?

Examples

a)Input: n = 2

Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step

2. 2 steps

Example 2:

b)Input: n = 3

Output: 3

Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step

2. 1 step + 2 steps

3. 2 steps + 1 step

Solution:

var solution=climbStairs(n) {

// base cases

if(n <= 0) return 0;

if(n == 1) return 1;

if(n == 2) return 2;

int one_step_before = 2;

int two_steps_before = 1;

int all_ways = 0;

for(int i=2; i<n; i++){

all_ways = one_step_before + two_steps_before;

two_steps_before = one_step_before;

one_step_before = all_ways;

}

return all_ways;

}

Logic: Here the pattern is the same as a Fibonacci series.