Intermediate

Quick Sort Implementation

by

Objective: Write an algorithm to sort an array in increasing or decreasing order using Quick Sort.

Input:  An Array arrA[]

Output: A sorted array.

Approach:

  • Choose any element from the array and call it as pivot element, Example here we have selected middle element as pivot
  • Place all the elements smaller than pivot in the left side of pivot.
  • Place all the elements greater than pivot in the right side of pivot.
  • Sort left side and right side recursively.

Example:

Read moreQuick Sort Implementation

Valid or Well Formed Parentheses | Part – 1

by

Objective: You have been asked to Write an algorithm to find Whether Given the Sequence of parentheses are 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

Read moreValid or Well Formed Parentheses | Part – 1

Find an Element in 2 dimensional sorted array

by

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 element exists and its location

Approach:

Read moreFind an Element in 2 dimensional sorted array

Merge Sort – Updated – Most Efficient ways to Implement

by

Objective : Write Merge Sort algorithm to sort elements in an array

Input: A unsorted array, arrA[].

Output : A sorted array.

Approach:

Divide and Conquer: In this approach we divide the main problems into smaller problems, solve them and merge the results to get the final result.

How Divide and conquer works in Merge Sort:

We divide the elements into two half’s by middle of the array. We solve the left half and right half recursively and merge the results.

Merging:

Read moreMerge Sort – Updated – Most Efficient ways to Implement