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

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

Input: Two Dimensional array

Output: No of paths.

Approach :

1. Recursive

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 which will be solved again and again to get the final solution. read this : “Dynamic programming vs Recursion

2. Dynamic Programming (Better Solution)

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

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

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:

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

Merge or Combine Two Sorted Linked Lists

Objective: Given two sorted linked lists, objective is to merge both the lists in sorted order.

Input: Two sorted linked list List a, List b.

Example: 

List a : ->2->6->18

Listb: ->1->3->17->19

Merged List: ->1->2->3->6->17->18->19

Approach:

Read moreMerge or Combine Two Sorted Linked Lists

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 morePrint All Elements of Two Dimensional Array in Spiral

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 moreQuick Sort Implementation

Valid or Well Formed Parentheses | Part – 1

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

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

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