The number of cycles in a given array of integers.

Objective: Given an array of size N which contains integers from range 0 to N-1. (No duplicates). Write a program to find the number of cycles in the array.  Cycles in Array: Since the array is of size N and elements are from 0 to N-1 without any duplicates means all the elements appear exactly … Read more The number of cycles in a given array of integers.

Given an array, find all unique subsets with a given sum with allowed repeated digits.

Objective: Given an array of integers and number N, Write an algorithm to find and print all the unique subsets of array for which sum is equal to N where array elements can be repeated any number of times.  Example: int [] arrA={2,4,3} sum =6 Output: [2, 2, 2] [2, 4] [3, 3] int [] … Read more Given an array, find all unique subsets with a given sum with allowed repeated digits.

Lexicographically next permutation With One swap

Objective: Given an array of integers (in particular order or permutation of a set of numbers), write an algorithm to find the lexicographically next permutation of the given permutation with only one swap.  This problem can also be asked as “Given a permutation of numbers you need to find the next larger permutation OR smallest … Read more Lexicographically next permutation With One swap

Find all subsets of size K from a given number N (1 to N)

Objective: Given two integers N and K, Write an algorithm to find subsets of size K from the numbers 1 to N.  Example: N = 5 K = 3 Output: [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, … Read more Find all subsets of size K from a given number N (1 to N)

Stable Marriage Problem – Gale–Shapley Algorithm – Java

Stable Marriage Given N men and N women and the marriage preference order for each man and woman. Their marriage will be stable when these men and women marry in such a manner so that everyone gets the most desired partner as per the availability( partners in a marriage cannot find anyone else better than … Read more Stable Marriage Problem – Gale–Shapley Algorithm – Java

Given an array, print all unique subsets with a given sum.

Objective: Given an array of integers and number N, Write an algorithm to find and print all the subsets of the array for which sum is equal to N. Example: input [] = {6,2,7,8,2,4,1,3,7,5} Sum = 8 Output: [1, 2, 2, 3] [1, 2, 5] [1, 3, 4] [1, 7] [2, 2, 4] [2, 6] … Read more Given an array, print all unique subsets with a given sum.

Articulation Points OR Cut Vertices in a Graph

Objective: Given a graph, write an algorithm to find all the articulation points or cut vertices. Articulation Points: In a graph, a vertex is called an articulation point if removal of that vertex (along with all the edges associated with that vertex) increases the number of connected components or in other words, removal of that … Read more Articulation Points OR Cut Vertices in a Graph

Find the number of distinct Islands OR connected components.

Objective: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of distinct or unique islands. Island: An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are all surrounded by water. Given such a grid, write an … Read more Find the number of distinct Islands OR connected components.

Print All Paths in Dijkstra’s Shortest Path Algorithm

Objective:  Given a graph and a source vertex write an algorithm to find the shortest path from the source vertex to all the vertices and print the paths all well. Example: We strongly recommend reading the following before continuing to read Graph Representation – Adjacency List Dijkstra’s shortest path algorithm – Priority Queue method We will … Read more Print All Paths in Dijkstra’s Shortest Path Algorithm

Number of Islands using BFS

Objective: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are all surrounded by water. Given such grid, write an algorithm using Breadth-First Search(BFS) to … Read more Number of Islands using BFS

Check if Graph is Bipartite – Adjacency List using Depth-First Search(DFS)

Objective: Given a graph represented by the adjacency List, write a Depth-First Search(DFS) algorithm to check whether the graph is bipartite or not. Earlier we have solved the same problem using Adjacency Matrix (Check if Graph is Bipartite – Adjacency Matrix) with Time complexity: O(V2) where V – No of vertices in the graph. In … Read more Check if Graph is Bipartite – Adjacency List using Depth-First Search(DFS)

Determine the given routing number belong to which bank

Objective: Given the banks and range of routing numbers for each bank. You have given a routing number, write a program to determine which bank it belongs to. Input: Given a list of routing ranges for each bank, with a start number, end number, and bank name. For instance, range = [1001, 1005, BOFA] has … Read more Determine the given routing number belong to which bank

Find all unique combinations of exact K numbers (from 1 to 9 ) with sum to N

Objective: Given two integers N and K. Write an algorithm to find all the combinations of k numbers which sum to N.  Conditions:  All K numbers must be between 1 and 9 and unique. All numbers in K are positive. Example: N= 5 K=2 Output: [1, 4] [2, 3] N =12 K=3 Output: [1, 2, … Read more Find all unique combinations of exact K numbers (from 1 to 9 ) with sum to N

Evaluation of Prefix Expressions (Polish Notation) | Set 2

Earlier we had discussed how to evaluate prefix expression where operands are of single-digit. In this article, we will discuss how to evaluate prefix expression for any number ( not necessarily single digit.) Prefix notation is a notation for writing arithmetic expressions in which the operands appear after their operators. Let’s assume the below Operands … Read more Evaluation of Prefix Expressions (Polish Notation) | Set 2

Evaluation of Prefix Expressions (Polish Notation) | Set 1

Prefix notation is a notation for writing arithmetic expressions in which the operands appear after their operators. There are no precedence rules to learn. Let’s assume the below Operands are real numbers in real digits. (Later we will Enhance the solution for any number) Permitted operators: +,-, *, /, ^(exponentiation) Blanks are NOT permitted in … Read more Evaluation of Prefix Expressions (Polish Notation) | Set 1