## Stock Single Sell Problem — O(n) Solution

Objec­tive:  Given an array rep­re­sents cost of a stock on each day. You are allowed to buy and sell the stock only once. Write an algo­rithm to max­i­mize the profit in sin­gle buy and sell. Example:…

## Find the element which appears maximum number of times in the array.

Objec­tive: Given an array of inte­gers, write a algo­rithm to find the ele­ment which appears max­i­mum num­ber of times in the array. Exam­ple: int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8,…

## Find duplicates in an given array in O(n) time and O(1) extra space.

Objec­tive: Given an array of inte­gers, find out dupli­cates in it. Exam­ple: int [] a = {4, 6, 2, 1, 2, 5}; Out­put: Array has dupli­cates : 2 int a [] = {1, 6, 5,…

## Find the last non repeating character in a given string.

Objec­tive: Given a string, write an algo­rithm to find the last non repeat­ing char­ac­ter in it. Exam­ple: String input = “algo­rithms tuto­ri­als” Out­put: ‘u’ String input = “aab­bc­cdd” Out­put: No repeat­ing char­ac­ter found. Approach: Naive…

## Find the last repeating character in a given string.

Objec­tive: Given a string, write an algo­rithm to find the last repeat­ing char­ac­ter in it. Exam­ple: String input = “hori­zon tuto­ri­als” Out­put: ‘i’ String input = “algo­rithms” Out­put: No repeat­ing char­ac­ter found. Approach: Naive approach:…

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

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

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

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

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

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

## Sort Names by their Last Names.

Objec­tive: Given a list of names ( first name and last name), sort the list by their last names. Exam­ple: List [] = {“Daen­erys Tar­garyen”, “Jon Snow”, ” Tyrion Lan­nis­ter”, ” Jof­frey Baratheon”} Out­put: [Joffrey…

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

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

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

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

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

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

## Delete X Nodes After Y Nodes In a Linked List

Objec­tive: Given a Linked List and x and y. Delete x num­ber of nodes after y nodes from the start. Exam­ple: ->10->20->30->40->50->60->70->80->90->100->110->120 Deleted 4 Nodes after 5 Nodes ->10->20->30->40->50->100->110->120 Approach:

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

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

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

## 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 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 Height of a Binary Tree">Find the Maximum Depth OR Height of a Binary Tree

Objec­tive: Given a binary tree, find the height of it Input: A Binary Tree Out­put: Height of a binary tree Exam­ple: Approach: