Reverse a Linked List

Objective: Reverse the given linked list.

Input: A Linked List

Output: Reversed Linked List

Example:

Input : ->30->25->20->15->10->5

Reversed : ->5->10->15->20->25->30

NOTE : Click Reverse a Linked List – Part 2 to see the another implementation of this problem.

Approach:

Iterative:

Read more

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 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

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

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:

Without Recursion:

Read more

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

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

Check If String has All Unique Characters

Objective: Write an algorithm to find out whether in a given string contains all the unique characters. This question has been asked in the Amazon and Microsoft interviews.

Input:  A String

Output: True or false based upon whether string contains all the unique characters or not.

Approach:

Method 1.

When characters are not ASCII but could be anything alphabets or special characters

Read more

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