Arrays

Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

by

Objective: Count all the paths from left top corner to the right bottom corner in two-dimensional array.

Input: Two Dimensional array

Output: No of paths.

Approach :

1. Recursive

The recursive solution to this problem is similar to Print All Paths from Top left to bottom right in Two Dimensional Array

But the Time complexity will be exponential because there will be many sub-problems that will be solved again and again to get the final solution. read this: “Dynamic programming vs Recursion

2. Dynamic Programming (Better Solution)

Create two-dimensional resultCount array to store the number of paths from top left corner.

Read more

Print All Paths from Top left to bottom right in Two Dimensional Array

by

Objective: Print all the paths from left top corner to right bottom corner in two dimensional array.

Input: Two Dimensional array

Output: Print all the paths.

Note: At the End of the article you will know what needs to be included if you want to print the diagonal paths as well.

Example:

Print All Paths - Example

Approach:

As we need to explore all the paths from top left corner to bottom right corner, we will either travel down OR travel right. so every time either we increase the row or column.

Read more

Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn)

by

Objective: Rearrange Positive and Negative Numbers of an Array so that one side you have positive numbers and other side with negative Integers without changing their respective order.

Example

 : Input :  1 -2 3 -4 5 -6 7 -8 9 -10

ReArranged Output :  -2 -4 -6 -8 -10 1 3 5 7 9

Input: An array with positive and negative numbers

Output: Modified array with positive numbers and negative numbers are on each side of the array.

Approach:

Method 1. One naive approach is to have another array of same size and navigate the input array and one scan place all the negative numbers to the new array and in second scan place all the positive numbers to new array. Here the Space complexity will be O(n). We have a better solution which can solve this in O(1) space.

Method 2: Divide and Conquer

Read more

Find The Longest Sequence Of Prefix Shared By All The Words In A String

by

Objective: Write an algorithm to find The Longest Sequence Of Prefix Shared By All The Words In A String. This interesting problem was asked in the Google interview for software engineer. This problem is bit tricky, it looks difficult but actually it is simple problem.

Input: A String

Output: The longest sequence of prefix common in all the words in a string

Example:

“Bedroom BedClock BedTable BedWall” => “Bed”

Approach:

Read more

Print All Elements of Two Dimensional Array in Spiral

by

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

Find a pair of numbers from an array whose sum equals k

by

Objective: Write an algorithm to find out whether in a given array there exists or not two numbers whose sum is exactly equals to a given number. This problem has been asked in Amazon and Microsoft interviews.

Input: An array arrA[], A number k

Output: True or false based upon we have found any two numbers in array arrA[] whose sum is equal to k

Approach:

Method 1: Using Binary Search

Read more

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 more

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

Approach:

Read more

Find Whether Given String is palindrome or Not.

by

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

by

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

by

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

by

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

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:

Once the sorting is done individually on both the half’s, our next task will be merge them. To merge we start with both the arrays at the beginning, pick the smaller one put into array and then compare the next elements and so on.

Read more