### 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.**

## Comments

## Post a Comment