# Author: SJ

## k-Nearest Neighbors

This arti­cle is con­tribute by Anto­nis Maroniko­lakis Objec­tive: We are given a data set con­tain­ing items, with numeric val­ues, cat­e­go­rized into classes. We are also given a new item, with­out a class. We want…

## 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:…

## Reverse the given Array without using built in function

Objec­tive: Given a array, write an algo­rithm to reverse the array. Exam­ple: int a[] = {1, 2, 3, 4, 5} Out­put: {5, 4, 3, 2, 1} Approach: It’s obvi­ous that you can­not use any built-in…

## 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 — Edit Distance Problem

Objec­tive: Given two strings, s1 and s2 and edit oper­a­tions (given below). Write an algo­rithm to find min­i­mum num­ber oper­a­tions required to con­vert string s1 into s2. Allowed Oper­a­tions: Inser­tion — Insert a new character.…

## Dynamic Programming — Coin In a Line Game Problem

Objec­tive: In this game, which we will call the coins-in-a-line game, an even num­ber, n, of coins, of var­i­ous denom­i­na­tions from var­i­ous coun­tries, are placed in a line. Two play­ers, who we will call…

## Dynamic Programming — Box Stacking Problem

Objec­tive: You are given a set of n types of rec­tan­gu­lar 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real num­bers). You want to cre­ate a stack…

## Dynamic Programming — Split the String into Minimum number of Palindromes.

Objec­tive: You are given a large string. You need to cut the string into chunks such that each sub­string that you get is a palin­drome. Remem­ber that each 1 length string is always a…

## Dynamic Programming — Highway Billboard Problem

Objec­tive:  Sup­pose you’re man­ag­ing con­struc­tion of bill­boards on the Rocky & Bull­win­kle Memo­r­ial High­way, a heav­ily trav­eled stretch of road that runs west-east for M miles. The pos­si­ble sites for bill­boards are given by…

## 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,…

## Convert Binary Tree into Threaded Binary Tree

Objec­tive: Given a binary tree write an algo­rithm to con­vert it into threaded binary tree. Note: Tree node has extra Boolean field to be used. In ear­lier arti­cle “Intro­duc­tion to Threaded Binary Tree” we have…

## Double Threaded Binary Tree Complete Implementation

In ear­lier arti­cle “Intro­duc­tion to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advan­tages it has over nor­mal binary tree. In this arti­cle we will see…

## Single Threaded Binary Tree Complete Implementation

In ear­lier arti­cle “Intro­duc­tion to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advan­tages it has over nor­mal binary tree. In this arti­cle we will see…

## 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…

## Implement Stack Using Linked List

Objec­tive: Write an algo­rithm to imple­ment Stack using Linked List. If you do not know about then for starters its abstract data type in which fol­lows the prin­ci­ple of LIFO (Last-In-First-Out) which means the…

## Doubly Linked List Complete Implementation

In this arti­cle we will see what is dou­bly linked list, how it is dif­fer­ent from other linked list and how to imple­ment it. Ear­lier we have seen what is Singly Linked List and Circular…

## Circular Linked List Complete Implementation

Ear­lier we have seen what is Singly Linked List and How to imple­ment it. In a way you say that it’s an exten­sion of singly linked list. I would sug­gest that if you do…

## 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…

## Shortest Range in K-sorted Lists

Objec­tive: You have k lists of sorted inte­gers. Find the small­est range that includes at least one num­ber from each of the k lists. This is very nice and tricky solu­tion, This prob­lem was asked in…

## 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…

## Get the Sum of all left leaves in a Binary tree

Objec­tive: Given a binary tree, find the sum of all the nodes which are left as well as leaves nodes. Exam­ple:     Approach: Approach is quite sim­ple. Do the inorder tra­ver­sal check if…

## 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…

## Binary Tree-Postorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for pos­torder tra­ver­sal. Exam­ple: Ear­lier we have seen “What is pos­torder tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will…

## Binary Tree — Preorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for pre­order tra­ver­sal. Exam­ple: Ear­lier we have seen “What is pre­order tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will…

## Binary Tree-Inorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for Inorder tra­ver­sal. Exam­ple: Ear­lier we have seen “What is Inorder tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will…

## Delete the Binary Tree

Objec­tive: Given a binary tree, write an algo­rithm to delete it. This is one of the basic prob­lem in trees. if you are new to trees then this prob­lem will help you build your…

## Search the Element in a binary tree — With and Without Recursion

Objec­tive: Given a binary tree and a given num­ber x, Write an recur­sive algo­rithm to search the ele­ment in the tree. This is one of the very basic prob­lems of tree. If you are new…

## Tree Traversals

There are mul­ti­ple ways to in which you can tra­verse a tree. In this arti­cle we will see these tra­ver­sals in detail. If you are new to trees then I would rec­om­mend that you…

## Find the Size of a Binary Tree without Recursion

Objec­tive: Given a binary tree, Write an non-recursive algo­rithm to find the size of the tree. Note : Size of the tree is num­ber of nodes in the tree Approach: In our ear­lier post (link) we…

## Dynamic Programming — Longest Palindromic Subsequence

Objec­tive: Given a string, find a longest palin­dromic sub­se­quence in it. What is Longest Palin­dromic Sub­se­quence: A longest palin­dromic sub­se­quence is a sequence that appears in the same rel­a­tive order, but not nec­es­sar­ily contiguous(not substring)…

## 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 — Minimum Numbers are Required Whose Square Sum is Equal To a Given Number

Objec­tive: Given a num­ber, Write an algo­rithm to find out min­i­mum num­bers required whose square is equal to the num­ber. This ques­tion has been asked in the Google Inter­view for Soft­ware Devel­oper posi­tion.This is…

## 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…

## Print All N Length Strings from Given Number K

Objec­tive: Given Num­ber K, Print all the strings of N length. Exam­ple: N = 2, K = 3 [1, 1] [2, 1] [3, 1] [1, 2] [2, 2] [3, 2] [1, 3] [2, 3]…

## Print All Possible Subsets with Sum equal to a given Number

Objec­tive: Given a num­ber N, Write an algo­rithm to print all pos­si­ble sub­sets with Sum equal to N In this prob­lem you will see the power of recur­sion. This ques­tion has been asked in the…

## 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 — Subset Sum Problem

Objec­tive: Given a set of pos­i­tive inte­gers, and a value sum S, find out if there exist a sub­set in array whose sum is equal to given sum S. Exam­ple: int[] A = {…

## The Word Break Problem

Objec­tive : Given an string and a dic­tio­nary of words, find out if the input string can be bro­ken into a space-separated sequence of one or more dic­tio­nary words. Exam­ple: dic­tio­nary = [“I” , “have”,…