Valid or Well Formed Parentheses | Part – 1

Objective: You have been asked to write an algorithm to find Whether Given the Sequence of parentheses is well-formed. This question was asked in the Amazon Interview.

Input: A String contains a sequence of parentheses

Output: true or false on whether parentheses are well-formed or not

Approach:

  • Idea is to have two counters, one for open parentheses ‘{‘ and one for close ‘}’
  • Read one character at a time and increment one of the counters
  • If any given point of time count of close parentheses is greater than the open one, return false
  • If at the end both counters are equal, return true

Example: { { } { } } – Well-formed

{ { } { = Not well-formed

Code:

Read more

Find an Element in 2 dimensional sorted array

Objective: Write an algorithm to find an element in 2-dimensional array where rows and columns are sorted respectively.

Input: A two dimensional sorted array, arrA[][].

Sorted 2D array

Output: True or false based on whether the element exists and its location

Approach:

Read more

Find Whether Given String is palindrome or Not.

Objective : Write an algorithm to find Whether Given String is palindrome or Not.

Input:  A String,

Output: true or false on whether string is palindrome or not

Approach:

  • Use recursive approach
  • Compare first and last characters if they are not same- return false
  • If they are same make, remove the first and last characters and make a recursive call. 

Example:

Jain niaJ => compare ‘J’ with ‘J’ =>returns true

ain nia => compare ‘a’ with ‘a’ =>returns true

in ni => compare ‘i’ with ‘i’ =>returns true

n n => compare ‘n’ with ‘n’ =>returns true

string length <2 => returns true

Read more

Find a peak element in a Given Array

Objective: In this article, we will discuss an algorithm to Find a peak element in a Given Array. We will see the recursion techniques to solve this problem.

Peak Element: peak element is the element that is greater than or equal to both of its neighbors.

Input:  Array, arrA[] .

Output: A peak element and its index

Approach:

A simple approach is to do a linear scan of an array and using a few variables we can find a peak element. But the Time Complexity will be O(n) but real question is, Can we do better?

The answer is yes, by using Binary Search techniques.

Read more

Find two Missing Numbers in a Sequence of Consecutive Numbers

Objective : Write an algorithm to find two Missing Numbers in a Sequence of Consecutive Numbers

Input:  Array, arrA[] with two missing numbers and Range

Output : Two missing numbers

Approach:

  • Approach is very simple, Add all the given numbers say S
  • Calculate sum of N numbers by formula n(n+1)/2 , say N
  • Find sum of two missing numbers a+b = N-S

Read more

Find a Missing Number From a Sequence of Consecutive Numbers

Objective: You have been asked to write an algorithm to Find a Missing Number From a Sequence of Consecutive Numbers

Input:  Array, arrA[] with a missing number and Range

Output: missing number

Approach:

  • The approach is very simple, Add all the given numbers say S
  • Calculate the sum of N numbers by formula n(n+1)/2, say N
  • Find missing number m = N-S


Example : suppose array given is  {1,2,3,4,5,6,8,9,10} and range is 10.

Read more