Graph – Detect Cycle in a Directed Graph

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

Snake and Ladder Problem

Objective – Given a snake and ladder game, write a function that returns the minimum number of jumps to take top or destination position. You can assume the dice you throw results in always favor of you means you can control the dice. Rules: Start from cell 1. Throw the dice and whatever number you … Read more

Sliding Window Algorithm (Track the maximum of each subarray of size k)

Objective: Given an array and integer k, write an algorithm to find the maximum element in each subarray of size k. Example: int [] nums = { 1, 2, 3, 2, 4, 1, 5, 6,1}; Output: 3, 3, 4, 4, 5, 6, 6 Subarrays – [1, 2, 3], max = 3 [2, 3, 2], max … Read more

Introduction to Threaded Binary Tree

What is Threaded Binary Tree?? A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node.    We have the pointers reference the next … Read more

Print All N Length Strings from Given Number K

Objective: Given Number K, Print all the strings of N length. Example: N = 2, K = 3 [1, 1] [2, 1] [3, 1] [1, 2] [2, 2] [3, 2] [1, 3] [2, 3] [3, 3] Approach: This problem is quite similar to Print All Subsets of a given set and Print All Combinations of … Read more

The Word Break Problem

Objective : Given an string and a dictionary of words, find out if the input string can be broken into a space-separated sequence of one or more dictionary words. Example: dictionary = [“I” , “have”, “Jain”, “Sumit”, “am”, “this”, “dog”] String = “IamSumit” Output: “I am Sumit” String =”thisisadog” Output : String can’t be broken … Read more

Backtracking – Search a Word In a Matrix

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

Reverse The Doubly Linked List

Objective: Reverse The Doubly Linked List. Example: Approach: Every Node in a doubly linked list has next and previous pointer. Do the linear traversal of the linked list and keep swapping the next and previous pointers. At the end, make the last pointer as the head of the list. Complete Code:Run This Code public class … Read more

Construct a binary tree from given Inorder and Level Order Traversal

Objective: – Given a inorder and level order traversal, construct a binary tree from that. Input: Inorder and level order traversal Approach: int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 }; int[] levelOrder = { 1, 2, 3, 4, 5, 6, 7 }; First element in the levelorder [] will be the … Read more

Determine whether given binary tree is binary search tree(BST) or not

Objective: Given a Binary tree, find out whether its binary search tree or not.

Input: A Binary Tree.

Output: True or false based on whether tree is BST ot not.

Approach:

Method 1 : If tree doesn’t have duplicates

  • Do the inorder traversal of the given binary tree.
  • check if the previously visited node is less than the current node value.
  • If yes, then return true
  • Else return false.

The above method works only when tree doesn’t have any duplicates.(we can choose that ether duplicates will either go to left OR on the right but we cannot choose it randomly while constructing the tree, we need to decide before we construct the tree and it has to be consistent through out and here we are deciding that duplicates should go to the left subtree.) see figure,

Read more