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 Graph – Detect Cycle in a Directed Graph

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 Snake and Ladder Problem

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 Sliding Window Algorithm (Track the maximum of each subarray of size k)

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 Introduction to Threaded Binary Tree

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 Print All N Length Strings from Given Number K

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 The Word Break Problem

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 Backtracking – Search a Word In a Matrix

Print All Possible Valid Combinations Of Parenthesis of Given ‘N’

Objec­tive: Given “n”, generate all valid parenthesis strings of length “2n”.
Example:

Given n=2

Output:
(())
()()

Approach:

Read morePrint All Possible Valid Combinations Of Parenthesis of Given ‘N’

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 Run This … Read more Reverse The Doubly Linked List

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 Construct a binary tree from given Inorder and Level Order Traversal

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 moreDetermine whether given binary tree is binary search tree(BST) or not