Objective: Given a graph, source vertex and destination vertex. Write an algorithm to count all possible paths between source and destination. Condition: Graph does not contain any cycle. This problem also known as “paths between two nodes” Example: Approach: Use Depth First Search Use DFS but we cannot use visited [] to keep track of … Read more
Objective: Given a directed graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Graph contains cycle if there are any back edges. There are two types of back edges as seen in the example above (marked in red) Edge from a vertex to itself. Self loop. (4-4) Edge from … Read more
Objective: Given undirected graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Earlier we have seen how to find cycles in directed graphs. In this article we will solve it for undirected graph. This problem can be solved in multiple ways, like topological sort, DFS, disjoint sets, in this … Read more
Objective: Given a directed graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Graph contains cycle if there are any back edges. There are two types of back edges as seen in the example above (marked in red) Edge from a vertex to itself. Self loop. (4-4) Edge from … Read more
Objective: Given an array which contains only 0’s and 1’s. write an algorithm to separate 0’s and 1’s. Example int [] arrA = {1,0,1,0,1,1,0,0,0,0,1}; Output: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1] Approach: Counting Count number of 0’s in the array. Say its count. Now in array, put 0 in indexes from … Read more
Objective: Given a string, write an algorithm to find the last repeating character in it. Example: String input = “horizon tutorials” Output: ‘i’ String input = “algorithms” Output: No repeating character found. Approach: Naive approach: This problem can be easily solved using two nested loops from right to left. Take each character from the outer … Read more
Objective: Given two string sequences, write an algorithm to find the length of longest subsequence present in both of them. These kind of dynamic programming questions are very famous in the interviews like Amazon, Microsoft, Oracle and many more. What is Longest Common Subsequence: A longest subsequence is a sequence that appears in the same … Read more
Objective: Given a rod of length n inches and a table of prices pi, i=1,2,…,n, write an algorithm to find the maximum revenue rn obtainable by cutting up the rod and selling the pieces. This is very good basic problem after fibonacci sequence if you are new to Dynamic programming. We will see how the … Read more
Objective: Given a matrix of 0’s and 1’s (binary matrix). Find out Maximum size square sub-matrix with all 1’s. Example: Approach: Base Cases: If only one row is given then cells with 1’s will be the Maximum size square sub-matrix with size = 1. If only one column is given then cells with 1’s will … Read more
Objective : Given a 2D matrix of characters. Check whether the word exist in the matrix or not. If it exists then print its path. All movements are allowed (right, left, up, down and diagonally). Example: Approach: We will show the path as increment counter Create a solution matrix of the same structure as … Read more
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: