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 use the stack here to solve our problem.


You may also like these articles:

 Coding Interview Set 1 

 Coding Interview Set 2.

 


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.


I hope you like this article. Please stay connected for set 6.

You can also follow me on Twitter or Linkedin for the latest updates.

Written By:

Saurabh Joshi

Comments

Popular Posts