Print All Elements of Two Dimensional Array in Spiral

Objective: This question was asked in Amazon interview for the Software development Engineer position, Write an algorithm to print all the elements of two dimensional array in spiral.
Example :

Print 2D array in Spiral
Print 2D array in Spiral

Input: Two dimensional array

Output: All array elements printed in spiral.

Approach:

Read more

Quick Sort Implementation

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 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 which 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 to a array and using 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

Merge Sort – Updated – Most Efficient ways to Implement

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 more