Check if one string is Rotation of another string

Objective: Write an algorithm to check if one string is Rotation of another string. This question has been asked in the Amazon interview.

Example:

Input Strings : 'sumitjain' and 'tjainsumi'
Output : true

Input String : 'Jaain' and 'ainJ'
Output: false

Input: Two Strings

Output: True or false based on whether strings are rotation of each other.

Approach:

Read moreCheck if one string is Rotation of another string

String Compression using count of repeated characters – Run Length Encoding

Objective: Write an algorithm to compress the given string by using the count of repeated characters and if new compressed string length is not smaller than the original string then return the original string.

Example:

Input String : ssssuuuummmmmmiiiittttttttttttt
Compressed String : s4u4m6i4t13

Input String : Jaain
Compressed String : Jaain (Since compressed string is length is greater than original string)

Input: A String

Output: either A compressed string or original string whichever us smaller.

Approach:

Read moreString Compression using count of repeated characters – Run Length Encoding

Replace all spaces in a String with ‘%20’

Objective: Write an algorithm to replace all spaces in a given string with ‘%20’. You can consider that string has enough space at the end of the string to hold the extra characters.

Input: A String and true length of a string

Output: Updated string in which each space is replaced by the ‘%20’

Example: 

Input String : I am Sumit Jain    

Output String : I%20am%20Sumit%20Jain

Approach:

Read moreReplace all spaces in a String with ‘%20’

Find Whether Two Strings are Permutation of each other

Objective: Given Two Strings, check whether one string is permutation of other

Input: Two Strings

Output: True or false based on whether strings are permutation of other or not.

Example:

"sumit" and "tiums" are permutations of each other.

"abcd" and bdea" are not permutations of each other.

Approach:

Read moreFind Whether Two Strings are Permutation of each other

Find Intersection Point in Two Linked List

Objective: Given Two linked list, check whether both list intersect each other, if yes then find the starting node of the intersection.

Intersection point means end of one linked list is linked with some node in another linked list and it forms a Y shape.

Input: Two Linked List

Output: Intersection Node or point

Example:

Find Intersection Point in Two Linked List
Find Intersection Point in Two Linked List

Approach:

Read moreFind Intersection Point in Two Linked List

Find the Loop in a Linked list, find its length and Break the Loop

Objective: In a given linked list, check whether it contains the loop in it, if yes then find the Loop length and break the loop.

Loop in a linked list means the last node does not point to the null, instead it points to some node in the list.

Input: A Linked List

Output: Linked list contains loop or not, if yes its length and linked list after breaking the loop.

Example: 

Input : ->10->20->30->40->50->60->30->40->50->60->30->40->50->60->30

here you can see that 30->40->50->60 are repeating ,that means it has a loop
Loop in a Linked List
Loop in a Linked List

Approach:

Read moreFind the Loop in a Linked list, find its length and Break the Loop

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:

Read moreReverse a Linked List

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

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

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 moreRearrange Positive and Negative Numbers of Array On Each Side in O(nlogn)

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

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 moreFind The Longest Sequence Of Prefix Shared By All The Words In A String

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 moreFind a pair of numbers from an array whose sum equals k

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.

Read moreCheck If String has All Unique Characters

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