Notes

All these codes are in java

1. CODE COMPILER OUTPUT
2. DATA COLLECTED BY TELECOM COMPANY
3. Remove Duplicates from a sorted doubly linked list
4.Count the Number of Nodes in Circular Linked List
5.Maximum Frequency in a sequence
6. Count frequency of each character
7. Intelligent Code Editor
8. Delete Nodes greater than X
9.Nth Fibonacci number modulo M
10.Delete a Node in Linked list given access to only that Node
11. Given list is circular or not
12.Help Ram to get maximum energy
13.Multi-Level Points Game
14.Total ways to complete the client order
15.Steal Maximum Money
16.Find the severity of the network problem
17.Bitcoin Mining Target
18.Minimum Time To Reach Hometown
19.Install Maximum Mobile Towers
20.Get Maximum Productivity
21.Genetic Engineering
22.No effect after reversal
23.Name for a new company
24.Fair Division Among Friends
25.Maximum Area Square
26.Print all strings of n-bits
27.Print all string of n-bits with condition
28.Aman stuck in a Maze
29.Tom And Permutations
30.Count word in the board
31.Pair with the given sum
32.Viral Infection
33.Relation between the two flowers
34.Try balancing the scale
35.Sort an array of 0s, 1s and 2s
36.Remove Minimum Carriages
37.Solve Sudoku
38.Implement strstr function
39.Tribal Tradition
40.Solve N Queen problem
41.Find all pairs with K difference
42.Count number of ways to cover a distance
43.Rat in a Maze Problem
44. Find the minimum number of edges in a path of a graph
45.Find path in a directed graph
46. Number of Islands
47. .Shortest path in a binary maze
48. .Breadth First Traversal of Graph
49. .Depth First Traversal of Graph
50. .Find the cycle in undirected graph

All these codes are in java

1. Code compiler output

class Result {
static boolean match(char c1, char c2) {
if(c1=='('&&c2==')') {
return true;
} else if (c1=='['&&c2==']') {
return true;
} else if (c1=='{'&&c2=='}') {
return true;
}
return false;
}
static boolean compilerOutput(String code) {
Stack<Character> stack = new Stack<>();
char[] ch = code.toCharArray();
int len = ch.length;
for(char c:ch) {
if(c=='('||c=='['||c=='{') {
if(c=='(') {
stack.push('(');
}
if(c=='[') {
stack.push('[');
}
if(c=='{') {
stack.push('{');
}
} else {
if(c==')'||c==']'||c=='}') {
if(stack.empty()==false) {
if(match(stack.peek(),c)) {
stack.pop();
}
} else {
return false;
}
}
}
}
if(stack.empty()==true) {
return true;
}
return false;
}
}


2. Data Collection By Telecom Company


class Result {
static int collectData(int height[], int n) {
Stack<Integer> stack = new Stack<>();
stack.push(height[0]);
int sum = 0;
for(int i=1;i<n;i++) {
if(stack.empty()==true) {
stack.push(height[i]);
continue;
}
while(stack.empty()==false && stack.peek()<height[i]) {
sum+=height[i];
stack.pop();
}
stack.push(height[i]);
}
while(stack.empty()==false) {
sum = sum-1;
stack.pop();
}
return sum;
}
}


3. Remove Duplicates from a sorted doubly linked list


class Result {
static Node removeDupsDLL(Node head) {
if(head==null||head.next==null) {
return head;
}
Node curr = head;
while(curr!=null && curr.next!=null) {
if(curr.data==curr.next.data) {
curr.next = curr.next.next;
continue;
}
curr = curr.next;
}
return head;
}
}


4. Count the Number of Nodes in Circular Linked List


class Result {
static int countNodes(Node head) {
if(head==null||head.next==null) {
return 0;
}
int count = 1;
Node curr = head.next;
while(curr!=head) {
count++;
curr = curr.next;
}
return count;
}
}



5. Maximum Frequency in a sequence


class Result {
static int maxFrequency(int A[], int n) {
Map<Integer,Integer> map = new HashMap<>();

for(int i:A) {
if(map.containsKey(i)) {
map.put(i,map.get(i)+1);
} else {
map.put(i,1);
}
}

int freq = A[0];
int val = Integer.MIN_VALUE;
for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
if(entry.getValue()>val) {
val = entry.getValue();
freq = entry.getKey();
}
if(entry.getValue()==val) {
if(entry.getKey()<freq) {
freq = entry.getKey();
val = entry.getValue();
}
}
}
return freq;
}
}



6. Count frequency of each character


class Result {
static void countFrequency(String str) {
Map<Character,Integer> hm = new HashMap<>();
char[] ch = str.toCharArray();
int len = ch.length;

for(char c:ch) {
if(hm.containsKey(c)) {
hm.put(c,hm.get(c)+1);
} else {
hm.put(c,1);
}
}

for(char c:ch) {
if(hm.containsKey(c)) {
System.out.print(c+hm.get(c).toString()+" ");
}
hm.remove(c);
}


}
}



7. Intelligent Code Editor

class Result {
static int highlightedBrackets(String expr) {
Stack<Character> stack = new Stack<Character>();
char[] ch = expr.toCharArray();
int sum = 0;
for(char i:ch) {
if(i=='{') {
stack.push('{');
}
if(i=='}') {
if(stack.empty()==false) {
stack.pop();
}
else {
stack.push('{');
sum++;
}
}
}
if(stack.size()%2!=0) {
return -1;
}
return (sum+stack.size()/2);
}
}


8. Delete Nodes greater than X


static Node deleteGreater(Node head, int X) {
if(head==null||head.next==null) {
return head;
}

while(head!=null && head.data>X) {
head = head.next;
}

Node curr = head;
Node prev = head;
while(curr!=null) {
if(curr.data>X) {
prev.next = curr.next;
} else {
prev = curr;
}
curr = curr.next;
}
return head;
}




9. Nth Fibonacci number modulo M


class Result {
static int fibbo(int n, int m) {
if(n==0) {
return 0;
}
if(n==1) {
return 1;
}

int a = 0;
int b = 1;

for(int i=2;i<=n;i++) {
int c = ((a%m)+(b%m))%m;
a = b;
b = c;
}
return b;
}
static int nthFibonacciTerm(int n, int m) {
return fibbo(n,m);
}
}






10. Delete a Node in Linked list given access to only that Node




class Result {
static void deleteNode(Node n1) {
if(n1==null || n1.next==null) {
return;
}
Node next = n1.next.next;
n1.data = n1.next.data;
n1.next = next;
}
}




11. Given list is circular or not




static int isCircular(Node head) {
if(head ==null || head.next==null) {
return 1;
}

Node fast = head;
Node slow = head;

while(fast!=null && fast.next!=null) {
fast = fast.next.next;
slow = slow.next;

if(fast==slow) {
break;
}
}

if(fast==null || fast.next==null) {
return 0;
}

if(fast==slow&&slow==head) {
return 1;
}
return 0;
}



12. Help Ram to get maximum energy


class Result {
static int maxEnergy(int N, int energy[], int time[], int T) {
int dp[][] = new int [N+1][T+1];
for(int i=1;i<=N;i++) {
for(int j=1;j<=T;j++) {
if(j>=time[i-1]) {
int current_energy = energy[i-1] + dp[i-1][j-time[i-1]];
dp[i][j] = Math.max(current_energy, dp[i-1][j]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[N][T];
}
}




13. Multi-Level Points Game


import java.util.Arrays;
class Result {
static int isPossibleToWin(int N, int points[], int P, int K) {
boolean dp[][] = new boolean[N+1][P+1];
dp[0][0] = true;
for(int i=1;i<=N;i++) {
for(int j=0;j<=P;j++) {
dp[i][j] = dp[i-1][j];
if(j >= points[i-1]) {
dp[i][j] = dp[i][j] || dp[i-1][j-points[i-1]];
}
}
}
return dp[N][P-K] ? 1:0;
}
}




14. Total ways to complete the client order

class Result {
static int totalWays(int N) {
// Write your code here
if(N==1){
return 1;
}
if(N==2){
return 2;
}
int [][]dp=new int [2][N+1];
dp[1][1]=1;
dp[1][2]=1;
dp[0][2]=1;
for(int i=3;i<=N;i++){
dp[0][i]=dp[1][i-2];
dp[1][i]=dp[0][i-1]+dp[1][i-1];
}
return dp[0][N]+dp[1][N];
}
}


15. Steal Maximum Money


class Result {
static int getMaxMoney(int house[][], int m, int n) {
int dp[][] = new int[m][n];
dp[m-1][n-1] = house[m-1][n-1];
for(int i=m-2;i>=0;i--) {
dp[i][n-1] = dp[i+1][n-1] + house[i][n-1];
}
for(int j=n-2;j>=0;j--) {
dp[m-1][j] = dp[m-1][j+1] + house[m-1][j];
}
for(int i=m-2;i>=0;i--) {
for(int j=n-2;j>=0;j--) {
int val = Math.max(dp[i+1][j+1] , Math.max(dp[i+1][j], dp[i][j+1]));
dp[i][j] = house[i][j] + val;
}
}
return dp[0][0];
}
}




16. Find the severity of the network problem


class Result {
static int severityLevel(String original_str, String final_str) {
int len1 = original_str.length();
int len2 = final_str.length();
int dp[][] = new int[len1+1][len2+1];
for(int i=1;i<=len1;i++) {
for(int j=1;j<=len2;j++) {
if(original_str.charAt(i-1) == final_str.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
int X = dp[len1][len2];
int SeverityLevel = (len1-X) + (len2-X);
return SeverityLevel;
}
}




17. Bitcoin Mining Target


class Result {
static long bitcoinMining(int Bitcoins[], int N, int K) {
long[] dp = new long[K + 1];
dp[0] = 1;
for(int i=0;i<N;i++) {
for(int j=Bitcoins[i];j<=K;j++) {
dp[j]+=dp[j-Bitcoins[i]];
}
}
return dp[K];
}
}




18. Minimum Time To Reach Hometown


Not done yet ..




19. Install Maximum Mobile Towers


class Result {
static int maxTowers(int heights[], int N) {
int dp[] = new int[N];
dp[0] = 1;
int maxTowers = 0;
for(int i=1;i<N;i++) {
dp[i] = 1;
for(int j=0;j<i;j++) {
if(heights[i] > heights[j]) {
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
maxTowers = Math.max(maxTowers,dp[i]);
}
return maxTowers;
}
}




20. Get Maximum Productivity

class Result {
static int maxProductivity(int productivity[], int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int maxProductivity = 0;
for (int j = 1; j <= i; j++) {
maxProductivity = Math.max(maxProductivity, productivity[j - 1] + dp[i - j]);
}
dp[i] = maxProductivity;
}
return dp[n];
}
}




21. Genetic Engineering


class Result {
// Return the minimum number of operations required to convert virus1 to virus2
static int minOperations(String virus1, String virus2) {
int len1 = virus1.length();
int len2 = virus2.length();
int dp[][] = new int[len1+1][len2+1];
for(int i=0;i<=len1;i++) {
for(int j=0;j<=len2;j++) {
if(i==0) {
dp[i][j] = j;
} else if(j==0) {
dp[i][j] = i;
} else if(virus1.charAt(i-1)==virus2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
} else {
int val = Math.min(dp[i-1][j],dp[i][j-1]);
dp[i][j] = 1 + Math.min(dp[i-1][j-1],val);
}
}
}
return dp[len1][len2];
}
}




22. No effect after reversal


class Result {
static String longestPartWithNoChange(String message) {
int maxLength = 0;
int start = 0;
int n = message.length();
boolean[][] isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
for (int i = 0; i < n - 1; i++) {
if (message.charAt(i) == message.charAt(i + 1)) {
isPalindrome[i][i + 1] = true;
maxLength = 2;
start = i;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (message.charAt(i) == message.charAt(j) && isPalindrome[i + 1][j - 1]) {
isPalindrome[i][j] = true;
if (len > maxLength) {
maxLength = len;
start = i;
}
}
}
}
return message.substring(start, start + maxLength);
}
}
23. Name for a new company




class Result {
// Return the length of new company's name
static int newCompanyNameLen(String company1, String company2) {
int len1 = company1.length();
int len2 = company2.length();
int dp[][] = new int[len1+1][len2+1];
for(int i=1;i<=len1;i++) {
for(int j=1;j<=len2;j++) {
if(company1.charAt(i-1)==company2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] +1;
} else {
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return len1+len2-dp[len1][len2];
}
}




24. Fair Division Among Friends

class Result {
static int fairDivision(int prices[], int n) {
// Write your code here
int totalSum = 0;
for (int i = 0; i < n; i++) {
totalSum += prices[i];
}
int targetSum = totalSum / 2;
int[][] dp = new int[n + 1][targetSum + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= targetSum; j++) {
if (prices[i - 1] <= j) {
dp[i][j] = Math.max(dp[i - 1][j], prices[i - 1] + dp[i - 1][j - prices[i - 1]]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
int sum1 = dp[n][targetSum];
int sum2 = totalSum - sum1;
return Math.abs(sum1 - sum2);
}
}




25. Maximum Area Square


class Result {
public static int maxArea(int mat[][], int m, int n) {
int dp[][] = new int[m][n];
int maxArea = 0;
for (int i = 0; i < m; i++) {
dp[i][0] = mat[i][0];
maxArea = Math.max(maxArea, dp[i][0]);
}
for (int j = 0; j < n; j++) {
dp[0][j] = mat[0][j];
maxArea = Math.max(maxArea, dp[0][j]);
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (mat[i][j] == 1) {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
maxArea = Math.max(maxArea, dp[i][j]);
}
}
}
return maxArea * maxArea;
}
}





26. Print all strings of n-bits

class Solve
{
void generateAllStrings(int n, int i, char currStr[], ArrayList<String> strs){
if(i==n) {
strs.add(new String(currStr));
return;
}
currStr[i] = '0';
generateAllStrings(n,i+1,currStr,strs);
currStr[i] = '1';
generateAllStrings(n,i+1,currStr,strs);
}
}




27. Print all string of n-bits with condition


class Solve
{
void generateAllStrings(int n, int i, int k, char currStr[], ArrayList<String> strs)
{
if (i == n) {
strs.add(new String(currStr));
return;
}
if (i == k) {
currStr[i] = '1';
generateAllStrings(n, i+1, k, currStr, strs);
return;
}
currStr[i] = '0';
generateAllStrings(n, i+1, k, currStr, strs);
currStr[i] = '1';
generateAllStrings(n, i+1, k, currStr, strs);
}
}






28. Aman stuck in a Maze

class pair{
int first;
int second;
pair(int first,int second){
this.first=first;
this.second=second;
}
}
class Result {

public static int solveMaze(int maze[][], int N, int srcRow, int srcCol, int destRow, int destCol) {

int count=0;
boolean[][] vis=new boolean[N][N];
Queue<pair> q=new LinkedList<>();
q.add(new pair(srcRow,srcCol));
vis[srcRow][srcCol]=true;
int[] drow={-1,0};
int[] dcol={0,1};
while(!q.isEmpty()){
int row=q.peek().first;
int col=q.peek().second;
q.poll();
if(row==destRow && col== destCol){
count++;
}
for(int i=0;i<2;i++){
int nrow=row+drow[i];
int ncol=col+dcol[i];
if(ncol>=0 && nrow>=0 && ncol<N && nrow<N && maze[nrow][ncol]==1){
vis[nrow][ncol]=true;
q.add(new pair(nrow,ncol));
}
}
}
return count;
}
}

29. Tom And Permutations


class Solve {
public ArrayList<String> permute(String str) {
ArrayList<String> result = new ArrayList<>();
permuteHelper(str.toCharArray(), 0, result);
return result;
}
private void permuteHelper(char[] arr, int index, ArrayList<String> result) {
if (index == arr.length - 1) {
result.add(String.valueOf(arr));
return;
}
for (int i = index; i < arr.length; i++) {
if (i != index && arr[i] == arr[index]) {
continue;
}
char temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
permuteHelper(arr, index + 1, result);
arr[i] = arr[index];
arr[index] = temp;
}
}
}




30. Count word in the board

class Result {

static int isFound(char board[][],String word,int idx,int srcR,int srcC,int m,int n){
if(srcR>=m || srcC>=n || srcR<0 || srcC<0 || board[srcR][srcC]!=word.charAt(idx) || board[srcR][srcC]=='0')return 0;
if(idx==word.length()-1){
if(board[srcR][srcC]==word.charAt(idx))return 1;
else return 0;
}
char temp=board[srcR][srcC];
board[srcR][srcC]='0';
int count=(isFound(board,word,idx+1,srcR+1,srcC,m,n) + isFound(board,word,idx+1,srcR,srcC+1,m,n) + isFound(board,word,idx+1,srcR-1,srcC,m,n) + isFound(board,word,idx+1,srcR,srcC-1,m,n));
board[srcR][srcC]=temp;
return count;
}
static int countWord(char board[][], String word, int m, int n) {
int count=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(board[i][j]==word.charAt(0)){
count+=isFound(board,word,0,i,j,m,n);
}
}
}
return count;
}
}


31. Pair with the given sum


class Result {
// Return true if a pair with the sum k is found, else return false
static boolean pairSum(int arr[], int n, int k) {
int left = 0;
int right = n-1;
while(left<right) {
if((arr[left]+arr[right])==k) {
return true;
}
else if ((arr[left]+arr[right])<k) {
left++;
}
else {
right--;
}
}
return false;
}
}




32. Viral Infection

class Result {

static class Pair{
int row;
int col;
Pair(int row,int col){
this.row=row;
this.col=col;
}
}
static void viralInfection(int matrix[][], int M, int N, int x, int y) {

Queue<Pair> queue=new LinkedList<>();
int infected=matrix[x][y];
int[][] result=matrix;
Pair p=new Pair(x,y);
queue.add(p);
boolean visited[][]=new boolean[M][N];
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
visited[x][y]=false;
}
}
int[] delRow={0,-1,0,+1};
int delCol[]={-1,0,+1,0};
visited[x][y]=true;
result[x][y]=0;
while(queue.isEmpty()==false){
Pair current=queue.peek();
int row=current.row;
int col=current.col;
queue.remove();
for(int j=0;j<4;j++){
int newRow=row+delRow[j];
int newCol=col+delCol[j];
if(newRow>=0 && newRow<M && newCol>=0 && newCol<N && matrix[newRow][newCol]==infected && visited[newRow][newCol]==false){
result[newRow][newCol]=0;
visited[newRow][newCol]=true;
queue.add(new Pair(newRow,newCol));
}
}
}
matrix= result;
}
}




33. Relation between the two flowers




class Result {
// Return the length of smallest contiguous part from flower1 that contains all genes of flower2
static int findRelation(String flower1, String flower2) {
int left=0;
int right = 0;
int unique = flower2.length();
int minLen = Integer.MAX_VALUE;
int[] count = new int[128];
for(int i:flower2.toCharArray()) {
count[i]++;
}
while(right<flower1.length()) {
if(count[flower1.charAt(right)]>0) {
unique--;
}
count[flower1.charAt(right++)]--;
while(unique==0) {
if(right-left<minLen) {
minLen = right-left;
}
if(count[flower1.charAt(left)]==0) {
unique++;
}
count[flower1.charAt(left++)]++;
}
}
if(minLen==Integer.MAX_VALUE) {
return -1;
}
else{
return minLen;
}
}
}


34.try balancing the scale

class Result {
// Return true if the scale can be balanced, else return false
static boolean balanceScale(int X, int Y, int N, int weights[]) {
// Write your code here
if(X==Y)return true;
HashMap<Integer,Integer> hm=new HashMap<>();
for(int val:weights){
hm.put(val,hm.getOrDefault(val,0)+1);
}
int find=Math.abs(X-Y);
if(hm.containsKey(find))return true;
for(int val:weights){
int cx=X+val;
int cy=Y;
int cfind=Math.abs(cx-cy);
if(cfind==val && hm.getOrDefault(cfind,0)>=2)return true;
else if(cfind!=val && hm.containsKey(cfind))return true;
}
for(int val:weights){
int cx=X;
int cy=Y+val;
int cfind=Math.abs(cx-cy);
if(cfind==val && hm.getOrDefault(cfind,0)>=2)return true;
else if(cfind!=val && hm.containsKey(cfind))return true;
}
return false;
}
}

35. Sort an array of 0s, 1s and 2s




class Result {
// Do not print anything, just sort the given array itself
static void sorting012Array(int a[], int n) {
int zero = 0;
int one = 0;
int two = 0;
for(int i=0;i<n;i++) {
if(a[i]==0) {
zero++;
}
else if(a[i]==1) {
one++;
}
else {
two++;
}
}
int index = 0;
for(int i=0;i<zero;i++) {
a[index] = 0;
index++;
}
for(int i=0;i<one;i++) {
a[index] = 1;
index++;
}
for(int i=0;i<two;i++) {
a[index] = 2;
index++;
}
}
}




36. Remove Minimum Carriages


class Result {
static int removeCarriages(int weight[], int N, int X) {
// Write your code here
int sum=0;
for(int val:weight)sum+=val;
int findSum=sum-X;
if(findSum==0)return N;
else if(findSum<0)return -1;
int max=0;
boolean found=false;
int cSum=0;
int i=0;
int j=0;
while(j<N && i<N){
if(cSum+weight[j]<=findSum){
cSum+=weight[j];
if(cSum==findSum){
found=true;
max=Math.max(max,(j-i+1));
}
j++;
}
else{
cSum-=weight[i];
if(cSum==findSum){
found=true;
max=Math.max(max,(j-i+1));
}
i++;
}
}
return (found)?(N-max):-1;
}
}



37. Solve Sudoku

Not done yet….






38. Implement strstr function


static int strstrCode(String str, String sub) {
int ans = str.indexOf(sub);
if(ans<0) {
return -1;
}
return ans;
}






39. Tribal Tradition


class Result {
// return 1 for YES and 0 for NO
static int followsTradition(String motherName, String childName) {
String join = motherName+motherName;
int len = motherName.length();
for(int i=0;i<len;i++) {
if(join.substring(i,i+len).equals(childName)) {
return 1;
}
}
return 0;
}
}

40. Solve N Queen problem

Not done yet…




41. Find all pairs with K difference




class Result {
static int getPairsCount(int arr[], int n, int k) {
//HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
HashSet<Integer> set = new HashSet<Integer>();
int count = 0;
for(int i=0;i<n;i++) {
set.add(arr[i]);
}
for(int i=0;i<n;i++) {
if(set.contains(arr[i]-k)) {
count++;
}
}
return count;
}
}




42. Count number of ways to cover a distance




class Result
{
static int totalWaysToDistance(int d, int k){
int[] arr = new int[d+1];
arr[0] = 1;
for(int i=1;i<=d;i++) {
for(int j=1;j<=k&&j<=i;j++) {
arr[i]+=arr[i-j];
}
}
return arr[d];
}
}




43. Rat in a Maze Problem




class Result {
public static boolean safe(int x, int y, int[][] maze, int size, boolean[][] vis) {
if (x >= 0 && x < size && y >= 0 && y < size && !vis[x][y] && maze[x][y] == 0) {
return true;
}
return false;
}
public static int solve(int x, int y, int[][] maze, int size, boolean[][] vis, int count) {
if (x == size - 1 && y == size - 1) {
count++;
}
vis[x][y] = true;
if (safe(x, y + 1, maze, size, vis)) {
count = solve(x, y + 1, maze, size, vis, count);
}
if (safe(x + 1, y, maze, size, vis)) {
count = solve(x + 1, y, maze, size, vis, count);
}
vis[x][y] = false;
return count;
}
public static int solveMaze(int[][] maze, int size) {
boolean[][] vis = new boolean[size][size];
int count = 0;
count = solve(0, 0, maze, size, vis, count);
return count;
}
}


44. Find the minimum number of edges in a path of a graph

class Result{
static int number_of_edges(int n){
// Write your code here
return ans(1,n);
}
static int ans(int i,int n){
if(i==n){
return 0;
}
if(i>n){
return Integer.MAX_VALUE;
}
return Math.min(ans(i+1,n),ans(3*i,n))+1;
}
}

45.Find path in a directed graph

import java.util.*;
class Main{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
ArrayList<ArrayList<Integer>> adj=new ArrayList<>();
int V=sc.nextInt();
int E=sc.nextInt();
for(int i=0;i<V;i++){
adj.add(new ArrayList<>());
}
for(int i=0;i<E;i++){
int u=sc.nextInt();
int v=sc.nextInt();
adj.get(u).add(v);
}
int src=sc.nextInt();
int dest=sc.nextInt();
sc.close();
boolean [] vis=new boolean[V];
boolean ans=dfs(src,dest,adj,vis);
if(ans){
System.out.print("YES");
}
else{
System.out.print("NO");
}
}
static boolean dfs(int src, int dest, ArrayList<ArrayList<Integer>> adj,boolean [] vis){
vis[src]=true;
if(src==dest){
return true;
}
for(int it:adj.get(src)){
if(!vis[it]){
if(dfs(it,dest,adj,vis)){
return true;
}
}
}
return false;
}
}

46. Number of Islands
import java.util.*;
class pair{
int first;
int second;
pair(int first,int second){
this.first=first;
this.second=second;
}
}
class Result {
static int countIslands(int mat[][], int m, int n){
// Write your code here
int count=0;
boolean [][] vis=new boolean[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(mat[i][j]==1 && !vis[i][j]){
bfs(i,j,mat,vis,m,n);
count++;
}
}
}
return count;
}
static void bfs(int row , int col ,int [][] mat,boolean[][] vis, int m, int n){
Queue<pair> q=new LinkedList<>();
q.add(new pair(row,col));
int[] drow={-1,0,1,0};
int[] dcol={0,1,0,-1};
vis[row][col]=true;
while(!q.isEmpty()){
int r=q.peek().first;
int c=q.peek().second;
q.remove();
for(int i=0;i<4;i++){
int nrow=r+drow[i];
int ncol=c+dcol[i];
if(nrow>=0 && ncol>=0 && nrow<m && ncol<n && !vis[nrow][ncol] && mat[nrow][ncol]==1){
vis[nrow][ncol]=true;
q.add(new pair(nrow,ncol));
}
}
}
}
}

47.Shortest path in a binary maze

class pair{
int first;
int second;
int time;
pair(int first, int second,int time){
this.first=first;
this.second=second;
this.time=time;
}
}
class Result {
static int shortestPath(int mat[][], int srcR, int srcC, int destR, int destC, int m, int n){
// Write your code here
if(mat[srcR][srcC]==0 || mat[destR][destC]==0){
return -1;
}
boolean[][] vis=new boolean[m][n];
Queue<pair> q=new LinkedList<>();
vis[srcR][srcC]=true;
q.add(new pair(srcR,srcC,0));
int[] drow={-1,0,1,0};
int[] dcol={0,1,0,-1};
int t=Integer.MAX_VALUE;
while(!q.isEmpty()){
int row=q.peek().first;
int col=q.peek().second;
int tim=q.peek().time;
q.remove();
if(row==destR && col==destC){
t=Math.min(t,tim);
}
for(int i=0;i<4;i++){
int nrow=row+drow[i];
int ncol=col+dcol[i];
if(nrow>=0 && ncol>=0 && ncol< n && nrow<m && !vis[nrow][ncol] && mat[nrow][ncol]==1){
vis[nrow][ncol]=true;
q.add(new pair(nrow,ncol,tim+1));
}
}
}
if(t==Integer.MAX_VALUE){
return -1;
}
return t;
}
}

48.Breadth First Traversal of Graph

void BFS(int v)
{
boolean [] vis=new boolean[100];
Queue<Integer> q=new LinkedList<>();
q.add(v);
vis[v]=true;
System.out.print(v+" ");
while(!q.isEmpty()){
int curr=q.poll();
for(Integer node:adjVertices.get(curr)){
if(!vis[node]){
q.add(node);
vis[node]=true;
System.out.print(node+" ");
}
}
}
}

49.Depth First Traversal of Graph


void DFSUtil(int v, boolean vis[])
{
vis[v]=true;
System.out.print(v+" ");
for(int it:adjVertices.get(v)){
if(!vis[it]){
DFSUtil(it,vis);
}
}
}
void DFS(int v)
{
boolean [] vis=new boolean[100];
DFSUtil(v,vis);
}

50.Find the cycle in undirected graph

import java.util.*;
// Add other imports if you want to
// Do NOT change the class name
class pair{
int first;
int second;
pair(int first, int second){
this.first=first;
this.second=second;
}
}
class Main{
public static void main(String[] args)
{
// Write your code here
Scanner sc=new Scanner(System.in);
int V=sc.nextInt();
int E=sc.nextInt();
ArrayList<ArrayList<Integer>> adj=new ArrayList<>();
for(int i=0;i<V;i++){
adj.add(new ArrayList<>());
}
for(int i=0;i<E;i++){
int u=sc.nextInt();
int v=sc.nextInt();
adj.get(u).add(v);
adj.get(v).add(u);
}
sc.close();
boolean ans=bfs(adj,V);
if(ans){
System.out.print("Yes");
}
else{
System.out.print("No");
}
}
static boolean bfs(ArrayList<ArrayList<Integer>> adj,int V){
boolean[] vis=new boolean[V];
for(int i=0;i<V;i++){
if(!vis[i]){
if(bfsUtil(adj,i,vis)){
return true;
}
}
}
return false;
}
static boolean bfsUtil(ArrayList<ArrayList<Integer>> adj, int start,boolean[] vis){
Queue<pair> q=new LinkedList<>();
vis[start]=true;
q.add(new pair(start,-1));
while(!q.isEmpty()){
int node=q.peek().first;
int parent=q.peek().second;
q.remove();
for(int it:adj.get(node)){
if(!vis[it]){
vis[it]=true;
q.add(new pair(it,node));
}
else if(it!=parent){
return true;
}
}
}
return false;
}
}