Graph – Detect Cycle in a Directed Graph

Objective: Given a directed graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Graph contains cycle if there are any back edges. There are two types of back edges as seen in the example above (marked in red) Edge from a vertex to itself. Self loop. (4-4) Edge from … Read more Graph – Detect Cycle in a Directed Graph

Graph – Software Installation Problem

Objective: Given a list of software’s which you need to install in a computer. Few software’s has dependency on other software’s in the list, means these software can be installed only when all of its dependent software’s are installed. Write an algorithm to print the sequence in which all the software’s in the list can … Read more Graph – Software Installation Problem

Sliding Window Algorithm (Track the maximum of each subarray of size k)

Objective: Given an array and integer k, write an algorithm to find the maximum element in each subarray of size k. Example: int [] nums = { 1, 2, 3, 2, 4, 1, 5, 6,1}; Output: 3, 3, 4, 4, 5, 6, 6 Subarrays – [1, 2, 3], max = 3 [2, 3, 2], max … Read more Sliding Window Algorithm (Track the maximum of each subarray of size k)

Print all sub sequences of a given array

Objec­tive:  Given an array write an algorithm to print all the possible sub subsequences. Example: int [] a = {1, 2, 3}; Output: Possible sub sequences – {Empty}, {1}, {2}, {3}, {1, 2} ,{1,3}, {2, 3}, {1, 2, 3} Approach: The approach will be similar to as discussed here Gen­er­ate All Strings of n bits If … Read more Print all sub sequences of a given array

Remove Duplicates from a string

Objective:  Given a string, write an algorithm to remove the duplicate characters in that string. Example: Input: tutorialhorizon Output: tuorialhzn Approaches: There are multiple approaches to solve this problem- Use Sorting – (Will change the order of the characters) Use Hash Set – (Will change the order of the characters). Use Linked HashMap – (Will retain … Read more Remove Duplicates from a string

Dynamic programming – Minimum Jumps to reach to end

Objective:  Given an array of non negative integers, start from the first element and reach the last by jumping. The jump length can be at most the value at the current position in the array. Optimum result is when you reach the goal in minimum number of jumps. Example: Given array A = {2,3,1,1,4} possible ways … Read more Dynamic programming – Minimum Jumps to reach to end

Number of bit to be flipped to convert one number to another.

Bit Manipulation

Objec­tive:  Given two numbers x and y. write an algorithm to find the number of bits which are to be flipped to convert number x to y. Example x = 10, Y = 20 x = 0 1 0 1 0, y = 1 0 1 0 0 So if we need to convert x to … Read more Number of bit to be flipped to convert one number to another.

Separate 0’s and 1’s in a given array

Objec­tive:  Given an array which contains only 0’s and 1’s. write an algorithm to separate 0’s and 1’s. Example int [] arrA = {1,0,1,0,1,1,0,0,0,0,1}; Output: [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1] Approach: Counting Count number of 0’s in the array. Say its count. Now in array, put 0 in indexes from … Read more Separate 0’s and 1’s in a given array

Find three elements in an array that sum to a given value

Objec­tive:  Given an array of integer write an algorithm to find 3 elements that sum to a given number k. In short a+b+c = k. Example: int a [] = { 3,1,7,4,5,9,10} , k = 21;Output: Elements are 7 4 10 int a [] = { 3,1,7,4,5,9,10} , k = 55;Output: Did not find 3 elements whose … Read more Find three elements in an array that sum to a given value

Majority Element- Boyer–Moore majority vote algorithm

Objec­tive:  Given an array of integer write an algorithm to find the majority element in it (if exist). Majority Element: If an element appears more than n/2 times in array where n is the size of the array. Example: int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; … Read more Majority Element- Boyer–Moore majority vote algorithm

Majority Element – Part 1

Objective:  Given an array of integer write an algorithm to find the majority element in it (if exist). Majority Element: If an element appears more than n/2 times in array where n is the size of the array. Example: int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; … Read more Majority Element – Part 1

Find the Index from which 0 starts

Objec­tive:  Given an array of integer which 1’s followed by 0’s. Find the starting index of 0. Example: int [] a = {1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0}; First Index from where 0 starts: 10 int [] a = {1,1,1};  //No 0 is present output: Array does not have 0 int [] a = {0,0,0};  //Only 0’s. return the first index … Read more Find the Index from which 0 starts

Find the only element in array which appears only once

Bit Manipulation

Objec­tive: Given an array of integers, all the elements are appear twice but one element which appears only once. Write an algorithm to find that element. Example: int [] a = { 1,5,6,2,1,6,4,3,2,5,3}; output: 4 Approach: Brute Force: Use nested loops and compare each element in array with all other elements and track the element … Read more Find the only element in array which appears only once

Algorithm to calculate power(k,n).

Objective:  Given two numbers ‘k’ and ‘n’. Write an algorithm to calculate kn. Example: k = 4, n = 5 kn = 45 = 1024 k = 2, n = 3 kn = 23 = 8 Approach: Method 1: Brute Force Use for loop to iterate from 1 to n and do k*k for each iteration. … Read more Algorithm to calculate power(k,n).

Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer

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, 4}; Output: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6. Approach: Ear­lier we have seen how to … Read more Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer