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

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

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

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

## Backtracking — Knight’s Tour Problem

Objec­tive : A knight’s tour is a sequence of moves of a knight on a chess­board such that the knight vis­its every square only once. If the knight ends on a square that is…

## Backtracking — N Queens Problem — Better Solution

Objec­tive : In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen’s prob­lem asks…

## Backtracking — N Queens Problem

Objec­tive : In chess, a queen can move as far as she pleases, hor­i­zon­tally, ver­ti­cally, or diag­o­nally. A chess board has 8 rows and 8 columns. The stan­dard 8 by 8 Queen’s prob­lem asks…

## Backtracking — Rat In A Maze Puzzle

Given a maze, NxN matrix. A rat has to find a path from source to des­ti­na­tion. maze[0][0] (left top corner)is the source and maze[N-1][N-1](right bot­tom cor­ner) is des­ti­na­tion. There are few cells which are…

## SUDOKU Solver">Backtracking — SUDOKU Solver

SUDOKU Puz­zle : The objec­tive is to fill a 9×9 grid with dig­its so that each col­umn, each row, and each of the nine 3×3 sub-grids that com­pose the grid (also called “boxes”, “blocks”,…

## Dynamic Programming — Stairs Climbing Puzzle

Objec­tive: A child is climb­ing up a stair­case with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Imple­ment a method to count how many pos­si­ble ways…

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

## Merge K Sorted Arrays

Objec­tive: Given k sorted array, write an algo­rithm to merge Them into One sorted array. Exam­ple : int[][] A = new int[5][]; A[0] = new int[] { 1, 5, 8, 9 }; A[1] = new…

## Find a Number occurring odd number of times in a Given array

Objec­tive: Given a array of inte­gers, in which every ele­ments occurs even num­ber of times except one num­ber which occurs add num­ber of times. Find out that num­ber. Exam­ple:   int[] A = {…

## Diameter Of a Binary Tree

Objec­tive: — Given a binary tree, find the diam­e­ter of it. What is Diam­e­ter Of a Tree: Diam­e­ter of tree is defined as A longest path or route between any two nodes in a tree.…

## Magic Index — Find Index In Sorted Array Such That A[i] = i.

Objec­tive: Given a sorted array of dis­tinct inte­gers, Find the Magic index or Fixed point in the array. Magic Index or Fixed Point: Magic index or a Fixed point in an array is an index…

## Find numbers which are palindrome in both their decimal and octal Representations

Objec­tive: Given a range of inte­gers, find all the num­bers which are palin­drome when they are rep­re­sented in Dec­i­mal Value( base 10) and in Octal value(base 8). Exam­ple : Num­ber : 373 (Dec­i­mal) and digits…

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

## Colorful Numbers

Objec­tive: Given a num­ber, find out whether its col­or­ful or not. Col­or­ful Num­ber: When in a given num­ber, prod­uct of every digit of a sub-sequence are dif­fer­ent. That num­ber is called Col­or­ful Num­ber. See Example…

## Print All the Subsets of a Given Set (Power Set)

Objec­tive: Given a set of num­bers, print all the poss­si­ble sub­sets of it includ­ing empty set. Power Set: In math­e­mat­ics, Pow­er­Set of any given set S, PS(S) is set of all sub­sets of S including…

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

Objec­tive: — Given “n”, gen­er­ate all valid paren­the­sis strings of length “2n”. Exam­ple: Given n=2 Out­put: (()) ()() Approach:

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

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

## Construct a binary tree from given Inorder and Level Order Traversal

Objec­tive: — Given a inorder and level order tra­ver­sal, con­struct a binary tree from that. Input: Inorder and level order tra­ver­sal Appraoch: int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 }; int[] levelOrder…

## Construct Binary Search Tree from a given Preorder Traversal Using Stack (Without Recursion)

Objec­tive: — Given a pre­order tra­ver­sal, con­struct BST from that, with­out using recur­sion. Input: Pre­order tra­ver­sal Sim­i­lar Prob­lem : This prob­lem is sim­i­lar to the Con­struct Binary Search Tree from a given Pre­order Traversal…

## Construct Binary Search Tree from a given Preorder Traversal using Recursion

Objec­tive: — Given a pre­order tra­ver­sal, con­struct BST from that. Input: Pre­order tra­ver­sal Sim­i­lar Prob­lem : This prob­lem is sim­i­lar to the — Con­struct Binary Search Tree from a given Pre­order Tra­ver­sal Using Stack (Without…

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

## Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number.

Objec­tive: Given an array of size of N and num­ber k. Find all ele­ments in an Array which appears more than N/K times. Input: Array [] and num­ber k. Exam­ple: int[] arrA = { 2, 2,…

## Print All The Nodes Which are X distance from the Given Node

Objec­tive: — Given Binary Tree, Print All The Nodes Which are X dis­tance from the Given Node. Exam­ple : Appraoch: Quite Tricky solu­tion, i will explain using the exam­ple given in the picture.

## Find the Distance between Two Nodes of a Binary Tree.

Objec­tive: — Given nodes in a binary tree, find the dis­tance between them. Exam­ple : Approach:

## Lowest Common Ancestor in a Binary Tree (Not Binary Search Tree).

Objec­tive: — Find the Low­est Com­mon Ances­tor of two given nodes in a Binary Tree What is Low­est Com­mon Ances­tor In a given binary tree, The low­est com­mon ances­tor of two nodes n1 and…

## Lowest Common Ancestor in a Binary Search Tree.

Objec­tive: — Find the Low­est Com­mon Ances­tor of two given nodes in a Binary Search Tree What is Low­est Com­mon Ances­tor In a given binary tree, The low­est com­mon ances­tor of two nodes n1…

## Make a Binary Tree from Given Inorder and Preorder Traveral.

Objec­tive: — Given a inorder and pre­order tra­ver­sal, con­struct a binary tree from that. Input: Inorder and pre­order tra­ver­sals Sim­i­lar Prob­lem: Con­struct a binary tree from given Inorder and Pos­torder Tra­ver­sal Approach: int [] inOrder…

## BST.">Convert a Sorted Doubly Linked List to Balanced BST.

Objec­tive: Given a sorted dou­bly linked list, con­vert it into Bal­anced binary search tree Input: A Dou­bly Linked List Exam­ple: Approach:

## Find the number of occurrences of a number in a given sorted array.

Objec­tive: Given a sorted(ascending order) arrays of inte­gers, find out the num­ber of occurences of a num­ber in that array Input: A sorted array arrA[] and a num­ber x. Out­put: num­ber of occur­rences of ‘x’ in…

## Inorder Successor in Binary Search Tree without Using Parent link

Objec­tive: Given a Binary Search tree, find the inorder suc­ces­sor of a node. What is Inorder Suc­ces­sor: Inorder suc­ces­sor of a node is the next node in the inorder tra­ver­sal of the tree. For the…

## Inorder Successor in Binary Search Tree Using Parent link

Algo­rithms — Inorder Suc­ces­sor in Binary Search Tree Using Par­ent link Objec­tive: Given a Binary Search tree in which every node has a link to its par­ent, find the inorder suc­ces­sor of a node. What is…

## Inorder Successor in Binary Tree

Algo­rithms — Inorder Suc­ces­sor in Binary Tree Objec­tive: Given a Binary tree (Not binary Search Tree ), find the inorder suc­ces­sor of a node. What is Inorder Suc­ces­sor: Inorder suc­ces­sor of a node is the…

## In a Binary Tree, Create Linked Lists of all the nodes at each depth.

Objec­tive: Given a Binary tree cre­ate Linked Lists of all the nodes at each depth , say if the tree has height k then cre­ate k linked lists. NOTE : This prob­lem is very…

## Level Order Traversal, Print each level in separate line.

Objec­tive: Given a Binary tree , Print each level of a tree in sep­a­rate line. NOTE : This prob­lem is very sim­i­lar ” Cre­ate Linked Lists of all the nodes at each depth ” Input:…

## Rearrange Positive and Negative Numbers of Array On Each Side in O(nlogn)

Objec­tive: Rearrange Pos­i­tive and Neg­a­tive Num­bers of an Array so that one side you have pos­i­tive num­bers and other side with neg­a­tive Inte­gers with­out chang­ing their respec­tive order. Exam­ple : Input :  1 –2 3…

## Find The Longest Sequence Of Prefix Shared By All The Words In A String

Objec­tive: Write an algo­rithm to find The Longest Sequence Of Pre­fix Shared By All The Words In A String. This inter­est­ing prob­lem was asked in the Google inter­view for soft­ware engi­neer. This prob­lem is…