# Category: Intermediate

## Find longest Snake sequence in a given matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to find out the snake sequence which has the max­i­mum length. There could be many snake sequence in the matrix, you need to return the one…

## 2D Matrix with Obstructions in it">Dynamic Programming — Count all paths in 2D Matrix with Obstructions in it

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to count all pos­si­ble paths from top left cor­ner to bottom-right cor­ner. You are allowed to move only in two direc­tions, move right OR move down.…

## Dynamic Programming — Count all paths from top left to bottom right of a mXn matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to count all pos­si­ble paths from top left cor­ner to bottom-right cor­ner. You are allowed to move only in two direc­tions, move right OR move down. Example:…

## Print All Diagonals of a given matrix

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to print all the diag­o­nals of matrix. Exam­ple: Approach: We will solve this prob­lem in two parts. first half of diag­o­nals and sec­ond half of diagonals.…

## Dynamic Programming — Maximum Subarray Problem

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum. Exam­ple: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5,…

## Kadane’s Algorithm — Maximum Subarray Problem

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum. Exam­ple: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5,…

## Introduction to Threaded Binary Tree

What is Threaded Binary Tree?? A binary tree is threaded by mak­ing all right child point­ers that would nor­mally be null point to the inorder suc­ces­sor of the node (if it exists), and all left child pointers…

## Swap Nodes in pairs in a Linked List by changing links

Objec­tive: Given a linked list write an algo­rithm to swap nodes in pairs by chang­ing links . Ear­lier we have seen “Swap Every Kth node in a Linked List”, where we have seen how to…

## BST to Greater Sum Tree">Convert BST to Greater Sum Tree

Objec­tive: Given a binary search tree (BST), con­vert it into greater sum tree. What is greater sum tree: Greater sum tree is a tree in which every node con­tains the sum of all the nodes…

## Reverse Alternative ‘k’ nodes in a Linked List.

Objec­tive: Given a linked list and a num­ber ‘k’, write an algo­rithm to reverse alter­nate ‘k’ nodes in the linked list. This prob­lem was asked in the Microsoft and Ama­zon inter­views. Exam­ple: Approach: Recursion…

## Reverse a Linked List in groups of given size ‘K’

Objec­tive: Given a linked list and inte­ger ‘k’, write an algo­rithm to reverse the linked list in groups of size ‘k’. Exam­ple: Approach: Ear­lier we have seen how to reverse a linked list, solu­tion for…

## Generate Maximum revenue by selling K tickets from N windows

Objec­tive: Given ‘N’ win­dows where each win­dow con­tains cer­tain num­ber of tick­ets at each win­dow. Price of a ticket is equal to num­ber of tick­ets remain­ing at that win­dow. Write an algo­rithm to sell…

## Convert binary tree to its Sum tree

Objec­tive: Given a binary tree, write an algo­rithm to con­vert it into its Sum tree. What is Sum tree: Sum tree of a binary tree, is a tree where each node in the con­verted tree…

## Dynamic Programming — Maximum Product Cutting Problem.

Objec­tive: Given a rope of length n meters, write an algo­rithm to cut the rope in such a way that prod­uct of dif­fer­ent lengths of rope is max­i­mum. At least one cut has to…

## Dynamic Programming — Longest Common Substring

Objec­tive: Given two string sequences write an algo­rithm to find, find the length of longest sub­string present in both of them. This prob­lem has been asked in Ama­zon and Microsoft inter­views. Approach to solve this…

## Dynamic Programming — Longest Common Subsequence

Objec­tive: Given two string sequences, write an algo­rithm to find the length of longest sub­se­quence present in both of them. These kind of dynamic pro­gram­ming ques­tions are very famous in the inter­views like Ama­zon, Microsoft,…

## Dynamic Programming — Rod Cutting Problem

Objec­tive: Given a rod of length n inches and a table of prices pi, i=1,2,…,n, write an algo­rithm to find the max­i­mum rev­enue rn obtain­able by cut­ting up the rod and sell­ing the pieces.…

## Dynamic Programming — Coin Change Problem

Objec­tive: Given a set of coins and amount, Write an algo­rithm to find out how many ways we can make the change of the amount using the coins given. This is another prob­lem in which…

## Dynamic Programming — Minimum Cost Path Problem

Objec­tive: Given a 2D-matrix where each cell has a cost to travel. You have to write an algo­rithm to find a path from left-top cor­ner to bottom-right cor­ner with min­i­mum travel cost. You can…

## All N Length Strings from Given String of Length K

Objec­tive: Print All N Length Strings from Given String of Length K where char­ac­ters can appear mul­ti­ple time. Exam­ple: String k = “ALGO” N=2 Result: AA LA GA OA AL LL GL OL AG LG

## Generate Well Ordered Passwords of a Given Length K

Objec­tive: Gen­er­ate Well Ordered Pass­words of a Given Length K. Well ordered means that dig­its should be in increas­ing order in every gen­er­ated pass­word. Exam­ple: K = 7 1234567 1234568 1234569 1234578 1234579 1234589…

## Dynamic Programming — Maximum size square sub-matrix with all 1s

Objec­tive: Given a matrix of 0’s and 1’s (binary matrix). Find out Max­i­mum size square sub-matrix with all 1’s. Exam­ple: Approach: Base Cases: If only one row is given then cells with 1’s will be…

## Dynamic Programming — Longest Increasing Subsequence

Objec­tive: The longest Increas­ing Sub­se­quence (LIS) prob­lem is to find the length of the longest sub­se­quence in a given array such that all ele­ments of the sub­se­quence are sorted in increas­ing order. OR Given a…

## Dynamic Programming — Minimum Coin Change Problem

Objec­tive: Given a amount ‘A’ and n coins,   v1<v2<v3<.….……<vn . Write a pro­gram to find out min­i­mum num­bers of coins required to make the change for the amount ‘A’. Exam­ple: Amount: 5 Coins []…

## Find the Deepest Left Node in a Binary Tree.

Objec­tive: — Given a binary tree, Find the deep­est left node in it. Approach: This approach is very sim­i­lar to “Find the Deep­est Node in a Binary Tree” with lit­tle mod­i­fi­ca­tion. Take two global variable…

## Rearrange the Array of Given Range N, such that A[i]=i

Algo­rithms — Rearrange the Array of Given Range N, such that A[i]=i. Objec­tive: Given a array of length N, in which ele­ments are in the range of 1 to N. All ele­ments may not…

## Print All Paths From Root In a Binary Tree Whose Sum is Equal to a Given Number

Objec­tive: — Given a binary tree and X, Print all the paths start­ing from root so that sum of all the nodes in path equals to a given num­ber. Example:

## Reverse Level Order Traversal

Objec­tive: — Given a binary tree, Do the reverse level order tra­ver­sal. In our ear­lier post we have seen nor­mal Level Order Tra­ver­sal. In reverse level order tra­ver­sal we first need to print the…

## Find the Deepest Node in a Binary Tree.

Objec­tive: — Given a binary tree, Find the deep­est node in it. Approach: Take two global vari­able as “deep­estlevel” and “value”. start­ing with level=0, Do the inorder tra­ver­sal and when­ever you go down one level…

## Find the Height of a tree without Recursion

Objec­tive: — Find the Height of a tree with­out Recur­sion. In our ear­lier post “Height of tree” we had used recur­sion to find it. In this post we will see how to find it…

## Find All the Well Ordered Permutations of a Given String.

Objec­tive: Write an algo­rithm to Print All the Well Ordered Per­mu­ta­tions of a Given String. What is Well Ordered String: When all the alpha­bets in a string occur in the increas­ing order irre­spec­tive of…

## Find Increasing Triplet Sub-sequence

Objec­tive: Given an inte­ger array A[1..n], find an instance of i,j,k where 0 < i < j < k <= n and A[i] < A[j] < A[k]. Exam­ple : int arrA[] = { 10, 9,…

## Track the Maximum Element in a Stack.

Objec­tive: In a Stack, keep track of max­i­mum value in it. It might be the top ele­ment in the stack but once it is poped out, the max­i­mum value should be from the rest…

## Counting Sort

Count­ing Sort is an sort­ing algo­rithm, which sorts the inte­gers( or Objects) given in a spe­cific range. Algo­rithm: Time Com­plex­ity O(n) Take two arrays, Count[] and Result[] and given array is input[]. Count[] will store the…

## Generate All Strings of n bits.

Objec­tive: — Gen­er­ate All Strings of n bits, con­sider A[0..n-1] is an array of size n. Exam­ple : n = 3 Out­put: [0, 0, 0]    [1, 0, 0]    [0, 1, 0]    [1, 1, 0] [0,…

## Implement Queue Using Stacks

Objec­tive: We know that Queue is FIFO (First-in-First-Out) and Stack is LIFO ( Last-in-First-Out). Here our objec­tive is to imple­ment queue using stacks. Approach: Take 2 Stacks, stack1 and stack2. stack1 will be used…

## Alternate Splitting of a given Linked List

Objec­tive: Given a singly linked list, split it into two linked lists. These linked lists will con­tain the alter­nate nodes from the given linked list. Example:

## Reverse The Doubly Linked List

Objec­tive: Reverse The Dou­bly Linked List. Example:

## Swap Kth Node from the front with the Kth Node from the End

Objec­tive: Given a Linked List and a num­ber k, Swap Kth Node from the front with the Kth Node from the End Exam­ple: ->10->20->30->40->50->60->70 Swap­ping 1 Node from the Front and from the End ->70->20->30->40->50->60->10…

## Print the Bottom View of the Binary Tree.

Objec­tive: — Given a binary tree, print it in Bot­tom View of it. What is Bot­tom View: Bot­tom view means when you look the tree from the bot­tom the nodes you will see will be…

## Merge Sort in a Linked list

Objec­tive: Given a Linked List, Sort it using merge sort. Exam­ple: ->9->3->4->2->5->1 Sorted List: ->1->2->3->4->5->9 Approach: Ref­er­ence : Merge Sort in array

## Merge a Linked list into another Linked List at Alternate Positions.

Objec­tive: Given two linked lists, merge one list into another at alter­nate posi­tions, if sec­ond link list has extra nodes, print them as well Exam­ple: 5 -> 10 -> 15 -> 20 ->25 -> null…

## Print The Top View of a Binary Tree

Objec­tive: — Given a binary tree, print it in Top View of it. What is Top View: Top view means when you look the tree from the top the nodes you will see will be…

## Check if Array Contains All Elements Of Some Given Range

Objec­tive: Given an array of unsorted num­bers, check if it con­tains all ele­ments of some given range. Exam­ples: int[] arrA = { 11, 17, 13, 19, 15, 16, 12, 14 }; Range : 12–15 Output:…

## In an Array, find the Contiguous Subarray with Sum to a Given Value.

Objec­tive: Given an array and an inte­ger, find the Sub­ar­ray whose sum is equal to the given inte­ger. Exam­ples: int[] arrA = { 25, 12, 14, 22, 19, 15, 10, 23 }; Integer =…

## In an Array, find the Smallest Subarray with Sum Greater than the Given Value

Objec­tive: Given an array and an inte­ger, find the small­est sub­ar­ray whose sum is greater than the given inte­ger. Exam­ples: arrA[] = { 1, 5, 20, 70, 8} Inte­ger = 97 Out­put : Min…

## Find Kth Smallest or Largest element in an Array.

Objec­tive: Find Kth Small­est or Largest ele­ment in an Array Exam­ple: int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 }; Out­put: The 4th small­est ele­ment is : 8 Approach: Naive…

## Given an array arrA[], find the maximum j – i such that arr[j] > arr[i].

Objec­tive: Given an array arrA[], find the max­i­mum j – i such that arr[j] > arr[i]. Exam­ple: int[] arrA = { 12, 3, 1, 5, 6, 4, 10, 9, 8, 0 }; Out­put: Max(j-i)…

## Search an Element in a Rotated Sorted Array

Input: Rotated Sorted Array. What is Rotated Sorted Array. A sorted array is rotated around some pivot ele­ment. See the Exam­ple Below, array is rotated after 6. Approach:

## Print All The Nodes Which are X distance from the Leaf Nodes

Objec­tive: — Given Binary Tree, Print All The Nodes Which are X dis­tance from the Leaf Nodes Exam­ple : Approach: