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...
Category: Top Companies
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...
Longest substring with at most K unique characters
Objective: Given a string, write an algorithm to find the longest substring with at most K characters. Example: Input: aabbaacdeeeeddded, K = 3 Output: Longest substring with 3 most unique characters is: cdeeeeddded with...
Collatz Conjecture – Maximum Steps takes to transform (1, N) to 1.
Objective: Given a number N, write an algorithm to find the maximum number of steps it takes to transform (1, N) to 1 using Collatz Conjecture. The Collatz conjecture is a conjecture in mathematics...
Sort a given stack – Using Recursion
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:...
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...
Check if interval is covered in given coordinates
Objective: Given 1-D list of coordinates, (x1, x2), (x3, x4), , , ,(xn-1, xn)and interval (a, b). Write an algorithm to determine if interval (a,b) is covered in the list of coordinates. Example: Coordinates...
Lexicographically previous 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 previous permutation of the given permutation with only one swap. This...
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....
Print all subsets of an array with a sum equal to zero
Objective: Given an array of integers write an algorithm to find all the subsets for which sum is equal to zero. The array contains both positive and negative integers. Example: Given Array: [8, 3,...
Social Network Problem
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...
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...
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...
Minimum Boats Required to rescue people
Objective: Given N people need to be rescued by crossing the river by boat. Each boat can carry a maximum weight of given limit K. Each boat carries at most 2 people at the...
Number of Islands
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...