# Category: Expert

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

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

## 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 — 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 — 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 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 — 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 — Search a Word In a Matrix

Objec­tive : Given a 2D matrix of char­ac­ters. Check whether the word exist in the matrix or not. If it exists then print its path. All move­ments are allowed (right, left, up, down and…

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

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

## Provide the Next Siblings Pointers in a Given Binary Tree

Objec­tive: — Given a binary tree with three point­ers left, right and nextSi­b­ling). Write the pro­gram to pro­vide the nextsi­b­ling point­ers. Exam­ple: Approach:

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

## Binary Min — Max Heap

A binary heap is a heap data struc­ture cre­ated using a binary tree. binary tree has two rules — Binary Heap has to be com­plete binary tree at all lev­els except the last level. This…

## 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 Combinations of subset of size K from Given Array

Objec­tive: Given an array of inte­gers of size N, print all the sub­sets of size k. (k<=N) Exam­ple: Gen­er­ate all sub­sets of a fixed size k of a given set [1,2,3…n]. e.g, if n=5…

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

What is Graph: G = (V,E) Graph is a col­lec­tion of nodes or ver­tices (V) and edges(E) between them. We can tra­verse these nodes using the edges. These edges might be weighted or non-weighted. There can…

## AVL Tree — Insertion">AVL Tree — Insertion

What is AVL Tree : AVL tree is widely known as self-balancing binary search tree. It is named after its cre­ator (Georgy Adelson-Velsky and Lan­dis’ tree). In AVL Tree, the heights of child sub­trees at…

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

## Construct a Binary Tree from Given Inorder and Depth-First-Search.

Objec­tive: — Given a inorder and pre­order tra­ver­sal, con­struct a binary tree from that. Input: Inorder tra­ver­sal and Depth-First-Search. Approach: int[] inOrder = { 8, 4, 2, 5, 1, 6, 3, 7, 9 }; int[] DFS

## Inorder Predecessor and Successor in Binary Search Tree

Objec­tive: — Given a Binary Search Tree, Find pre­de­ces­sor and Suc­ces­sor of a given node. What is Pre­de­ces­sor and Suc­ces­sor : When you do the inorder tra­ver­sal of a binary tree, the neigh­bors of given…

## Rearrange Positive and Negative Elements at Alternate Positions in an Array In O(1) Extra Space

Objec­tive: Given an array arrA[] which has neg­a­tive and pos­i­tive ele­ments, rearrange the array in such a man­ner that pos­i­tive and neg­a­tive ele­ments occupy the alter­nate posi­tions and if there are extra pos­i­tive or…

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

## Construct a binary tree from given Inorder and Postorder Traversal

Objec­tive: — Given a inorder and pos­torder tra­ver­sal, write an algo­rithm to con­struct a binary tree from that. This prob­lem was asked in the Microsoft cod­ing com­pe­ti­tion. Input: Inorder and pos­torder tra­ver­sals Sim­i­lar Problems:…

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

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

## Print All The Permutations Of a String

Objec­tive: Given a String, print all the per­mu­ta­tions of it. Input: A String Out­put: Print all the per­mu­ta­tions of a string Exam­ple: Input : abc Out­put: abc acb bac bca cba cab Approach:

## OR Print in Spiral Pattern">Level Order Traversal in Zig Zag pattern OR Print in Spiral Pattern

Objec­tive: Given a binary Tree, Do Level Order Tra­ver­sal in Zig Zag pat­tern OR Print in Spi­ral Input: A Binary Tree Out­put: Order Tra­ver­sal in Zig Zag pat­tern OR Print in Spiral.

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

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

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