Robbing Houses
Problem Statement: You are given an array that represents the value present inside a house. You need to rob the houses in such a way that no two adjacent houses should be robbed. You need to return with max amount you can rob. Example Input arr = {2, 7, 9, 3, 1} Output: 12 Start […]
Unique Binary Search Trees
Problem Statement: You are given a number “n”. You need to find out structurally unique binary trees that are possible. Example Input: n = 3 Output: 5 Solution We can solve this problem with the help of DP 1. Top Down Approach 2. Bottom Up Approach First we will see some examples: Below are the […]
Get the least number of perfect squares
Problem Statement: You are given a number “n”. You need to return the least number of perfect square number that sum to n. A number os called as perfect square, if an integer is the square of another integer. Example: 1, 4, 9, 16 Example Example 1: Input: n = 12 Output: 3 Because, 12 […]
Get the nth Fibonacci Number
Problem Statement: You are given a number, you need to find the sum of the 2 preceding Fibonacci sequence. F(n) = F(n-1) + F (n-2) Example Input : n = 2 Output: 1 F(2) = F(1) + F(0) = 1 + 0 = 1 Solution We can solve this problem by: 1. Recursion 2. Top […]
Count the ways to decode a digit sequence
Problem Statement: You are given an digit sequence, you need to count the number of possible decoding of the given digit sequence. Example Input: “121” Output: 3 The possible ways to decode are “ABA”, “AU”, “LA” Solution We can solve this problem by using: 1. Recursion 2. Top Down memoization 3. Bottom Up tabulation 1. […]
Climb the stairs with minimum cost
Problem Statement: You are given an array with the cost. Where the cost[i] represents the cost of ith step of the stairs. If you step on the stair, you will pay the cost and you can either climb one or two steps. Your task is to climb the stairs with minimum cost to reach the […]
Dice Sum Problem
Problem Statement: You are given a number “n”. You need to count the number of ways to construct the sum by throwing a dice one or more times. Each throw produces a number between 1 and 6. Example n = 3 There are 4 ways to construct the sum: 1 + 1 + 1 1 […]
Check if a graph is a strongly connected using Kosaraju DFS algorithm
Problem Statement: You are given a directed graph, you need to find out if the graph is strongly connected or not. A strongly connected garph if there is a path between any two pair of vertices. Solution Step 1: Take an array to hold if a vertex has been visited or not. Step 2: Do […]
Find if there is a path between 2 nodes in an undirected graph
Problem Statement: You are given an undirected graph along with 2 nodes. You need to check if there is a path between the 2 nodes. Solution We can solve this problem by using Floyd Warshall Algorithm. For that we will create an adjacent matrix and we need to fill all the intermediate paths as: 1. […]
Get the unique lengths of connected components of an undirected graph.
Problem Statement: You are given an undirected graph with connected components. Then you need to provide output of the unique length of connected components. Example The count of edges from the connected components are {2, 3, 2} The unique count is 2. Solution Solution is very simple. You need to do a DFS traversal to […]