Given an array of integers, you are allowed to swap only adjacent elements in the array. write a program to find the minimum number of swaps to sort the given array. Example: Input : [2, 20, 15, 6, 10] Minimums adjacent swaps required sort the array: 5 Input : [10, 3, 4, 2, 5, 7, … Read more Minimum number of adjacent swaps to sort the given array
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.
Problem: There is N number of items that need to be transferred from one place to another by a robot. Each item has a specific weight. The robot can carry maximum weight K in one trip. You need to come up with an algorithm to find out the minimum number of trips that the robot … Read more Efficient Robot Problem – Find Minimum Trips
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
Objective: Given a graph represented by the adjacency List, write a Breadth-First Search(BFS) algorithm to check whether the graph is bipartite or not. Earlier we have solved the same problem using Depth-First Search (DFS). In this article, we will solve it using Breadth-First Search(BFS). Before we proceed, if you are new to Bipartite graphs, lets … Read more Check if Graph is Bipartite – Adjacency List using Breadth-First Search(BFS)
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
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.
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
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)
Objective: Given a stack of integers, write an algorithm to sort the stack using recursion. Example: Original Stack: [14, 9, 67, 91, 101, 25] Sorted Stack: [9, 14, 25, 67, 91, 101] Original Stack: [4, 9, 6, 8, 10, 5] Sorted Stack is:[10, 9, 8, 6, 5, 4] Approach: In this solution, we need two … Read more Sort a given stack – Using Recursion
Given: There are N people in a social network and there are friends group. Each person can be part of a friend group of a specific size. Number of people in the social network – N An array of size N specifying group size for each person. – (g0, g2, g3,….., gn). The first person … Read more Social Network Problem
Objective: Given a graph represented by the adjacency matrix, write a Depth-First Search(DFS) algorithm to check whether the graph is bipartite or not. Bipartite Graphs OR Bigraphs is a graph whose vertices can be divided into two independent groups or sets so that for every edge in the graph, each end of the edge belongs … Read more Check if Graph is Bipartite – Adjacency Matrix using Depth-First Search(DFS)
Problem Statement: When customers book an Airbnb the total price, which includes base price + service fee + cleaning fee. all these prices are in decimals. Write an algorithm to round each price such that the sum of the prices equals the round of the total sum of all decimal prices and minimize the rounding. … Read more Round Price Problem
Objective: Given a number with N digits, write a program to get the smallest number possible after removing k digits from number N. OR Implement a method that returns the lowest possible number that could be generated after removing n characters from a string of digits. Example: N = 1453287, k = 3 Output: 1287 … Read more Smallest Number after Removing K digits
Objective: Given a Stack, write an algorithm to reverse the stack. Example: Original Stack: [14, 9, 67, 91, 101, 25] Reversed Stack: [25, 101, 91, 67, 9, 14] Approach: Use Recursion In this solution, we need two recursive functions. reverse() and insert_at_bottom(). reverse() – this function will be called by the driver. In this function, … Read more Reverse a Stack using recursion – In Place (Without using extra memory)