Maximum depth of left node in Binary Tree

Given a Binary tree, print the maximum depth of a left node.( the node needs to be a left child ) (if the node is right child of the left child of the root node then it wont count as a left node)

import java.io.*;
class Node
{
    int data;
    Node left,right;
    Node(int data)
    {
        this.data=data;
        left=right=null;
    }
}
class TreeQuestion {
    Node root;
    static int max=0;
    void maxDepth(Node root,int direction,int depth)
    {
        if(root==null)
          return;
        if(direction==1)
        {
            max=Math.max(max,depth);
        }
        maxDepth(root.left,1,depth+1);
        maxDepth(root.right,2,depth+1);
    }
    public static void main (String[] args) {
        TreeQuestion tree=new TreeQuestion();
        tree.root=new Node(1);
        tree.root.left=new Node(2);
        tree.root.left.left=new Node(3);
        tree.root.left.left.left=new Node(4);
        tree.maxDepth(tree.root,1,0);
        System.out.println(max+1);
       
    }
}

Balanced Binary Tree

Given a binary tree, determine whether or not it is height-balanced. A height-balanced binary tree can be defined as one in which the heights of the two subtrees of any node never differ by more than one.

Algorithm:-

 import java.util.*;
class Node
{
    int data;
    Node left,right;
    Node(int data)
    {
        this.data=data;
        left=right=null;
    }
}
class CheckBT {
    Node root;
    boolean isBalanced(Node root)
    {
        if(root==null)
          return true;
        int l,r;
        l=height(root.left);
        r=height(root.right);
        if(Math.abs(l-r)<=1&&isBalanced(root.left)&&isBalanced(root.right))
             return true;      
      return false;       
    }
    int height(Node node)
    {
        if(node==null)
         return 0;
        return 1+Math.max(height(node.left),height(node.right));
    }
    public static void main (String[] args) {
        CheckBT tree=new CheckBT();
        tree.root=new Node(1);
        tree.root.left=new Node(2);
        tree.root.left.left=new Node(3);
        if(tree.isBalanced(tree.root))
           System.out.println("Balanced");
         else
           System.out.println("Not Balanced");
    }
}

Absolute Path Coding Problem with Solution

Given an absolute pathname that may have . or .. as part of it, return the shortest standardized path.

For example, given "/usr/bin/../bin/./scripts/../", return "/usr/bin/".

import java.util.*;
class GFG {
    static String getAbsolutePath(String s)
    {
        String path[]=s.split("/");
        ArrayList<String>al=new ArrayList<>();
        for(int i=0;i<path.length;i++)
        {
            if(path[i].equals("."))
              continue;
            else if(path[i].equals(".."))
              {
                  if(al.size()>0)
                   al.remove(al.size()-1);
              }
              else
              al.add("/"+path[i]);
        }
        if(al.size()>0)
          al.add("/");
        s="";
       for(int i=1;i<al.size();i++)
         s+=al.get(i);
       return s;        
    }
    public static void main (String[] args) {
            Scanner sc=new Scanner(System.in);
            String s=sc.next();
            System.out.println(getAbsolutePath(s));
    }
}

Finding sum of digits of a number until sum becomes single digit

Given a number n we need to find the sum of it's digit until it becomes single digit and expected time complexity O(1).

Input:-  12345

Output-   6


Solution 1:- Brute Force

import java.util.*;

class GFG {
    static int getSum(int n)
    {
        int sum=0;
        while(n>0||sum>9)
        {
            if(n==0)
            {
                n=sum;
                sum=0;
            }
           
                sum+=n%10;
                n=n/10;
           
        }
        return sum;
    }
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(getSum(n));
    }
}


Solution 2:- Best Way


import java.util.*;
class GFG {
    static int getSum(int n)
    {
        if(n==0)
          return n;
        return (n%9==0?9:n%9); 
    }
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(getSum(n));
    }
}

Time Complexity- O(1)

Samsung Noida R&D Coding Round Question minimum distance between source and destination

There is dedicated Samsung software for coding test the question is given below:
There is one spaceship. X and Y co-odinate of source of spaceship and destination spaceship is given. There are N number of warmholes each warmhole has 5 values.
First 2 values are starting co-ordinate of warmhole and after that value no. 3 and 4 represents ending co-ordinate of warmhole and last 5th value is represents cost to pass through this warmhole. Now these warmholes are bi-direction.
Now the to go from (x1,y1) to (x2,y2) is abs(x1-x2)+abs(y1-y2).
The main problem here is to find minimum distance to reach spaceship from source to destination co-ordinate using any number of warm-hole. It is ok if you wont use any warmhole.


Solution: 

import java.util.Scanner;

class Samsung{
    static int ans=Integer.MAX_VALUE;
    static int distance(int sx,int sy,int dx,int dy)
    {
        return Math.abs(sx-dx)+Math.abs(sy-dy);
    }
    static void calCulateUtil(int mat[][],int n,int sx,int sy,int dx,int dy,int dis,boolean visited[])
    {
        ans=Math.min(ans,distance(sx,sy,dx,dy)+dis);
        for(int i=0;i<n;i++)
        {
            if(visited[i]==false)
            {
                visited[i]=true;
                int temp=distance(sx,sy,mat[i][0],mat[i][1])+dis+mat[i][4];
                calCulateUtil(mat,n,mat[i][2],mat[i][3],dx,dy,temp,visited);
                temp=distance(sx,sy,mat[i][2],mat[i][3])+dis+mat[i][4];
                 calCulateUtil(mat,n,mat[i][0],mat[i][1],dx,dy,temp,visited);
                 visited[i]=false;
            }
        }
    }
    static int calCulate(int mat[][],int n,int sx,int sy,int dx,int dy,boolean visited[])
    {
        calCulateUtil(mat,n,sx,sy,dx,dy,0,visited);
        return ans;
    }
    public static void main (String[] args) {
          Scanner sc=new Scanner(System.in);
          int t=sc.nextInt();
          while(t-->0)
          {
              int n=sc.nextInt();
              int sx=sc.nextInt();
              int sy=sc.nextInt();
              int dx=sc.nextInt();
              int dy=sc.nextInt();
              int mat[][]=new int[n][5];
              boolean visited[]=new boolean[n];
              for(int i=0;i<n;i++)
              {
                  for(int j=0;j<5;j++)
                  {
                      mat[i][j]=sc.nextInt();
                  }
              }
              System.out.println(calCulate(mat,n,sx,sy,dx,dy,visited));
          }
    }
}

Shortest Path between source to destination in matrix

Given a Boolean 2D matrix (0-based index), find whether there is a path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. Moves are possible in only four directions i.e. up, down, left and right. The path can only be created out of a cell if its value is 1.



Solution:-

BFS traversal of matrix will give us minimum distance from source to destination in matrix.

Idea behind Solution:-  Step1:-  make a boolean matrix of same dimention and assign true every 1 and false at every 0 on the basis of given matrix.

step2:- start from source and do BFS traversal of matrix and every step increase the distance by 1.

step3:- when we reach destination then return the distance.



import java.util.Scanner;
class Point
{
    int x,y,d;
    Point(int x,int y,int d)
    {
        this.x=x;
        this.y=y;
        this.d=d;
    }
}
class Queue
{
    Point p[]=new Point[10000];
    int front=-1,end=-1;
    void add(int x,int y,int d)
    {
        if(front==-1)
            front=0;
        if(end<9999)
        {
            p[++end]=new Point(x,y,d);
        }
    }
    Point poll()
    {
        Point x=p[front++];
        return x;
    }
    boolean isEmpty()
    {
        if(front>end)
          return true;
        if(front==-1||end==-1)
          return true;
      return false;     
    }

}
class GFG {
    static int getMinValue(int mat[][],int n,int m,int sx,int sy,int dx,int dy)
    {
        boolean visited[][]=new boolean[n][m];
          for(int i=0;i<n;i++)
          {
              for(int j=0;j<m;j++)
              {
                  if(mat[i][j]==0)
                  visited[i][j]=true;
                  else
                  visited[i][j]=false;
              }
          }
          
          visited[sx][sy]=true;
          visited[dx][dy]=false;
          //Point p=new Point(sx,sy,0);
          Queue q=new Queue();
          q.add(sx,sy,0);
          while(!q.isEmpty())
          {
              Point p=q.poll();
              if(p.x==dx&&p.y==dy)
                return p.d;
            //left
              if(p.y-1>=0&&visited[p.x][p.y-1]==false)
              {
                  visited[p.x][p.y-1]=true;
                  q.add(p.x,p.y-1,p.d+1);
              }
              //right
              if(p.y+1<m&&visited[p.x][p.y+1]==false)
              {
                  visited[p.x][p.y+1]=true;
                  q.add(p.x,p.y+1,p.d+1);
              }
              //up
              if(p.x-1>=0&&visited[p.x-1][p.y]==false)
              {
                  visited[p.x-1][p.y]=true;
                  q.add(p.x-1,p.y,p.d+1);
              }
              //down
              if(p.x+1<n&&visited[p.x+1][p.y]==false)
              {
                  visited[p.x+1][p.y]=true;
                  q.add(p.x+1,p.y,p.d+1);
              }
             
          }
          return -1;
         
    }
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int mat[][]=new int[n][m];
          for(int i=0;i<n;i++)
          {
              for(int j=0;j<m;j++)
              {
                  mat[i][j]=sc.nextInt();
              }
          }
        int sx=sc.nextInt();
        int sy=sc.nextInt();
        int dx=sc.nextInt();
        int dy=sc.nextInt();
        System.out.println(getMinValue(mat,n,m,sx,sy,dx,dy));
    }
}



 https://ide.geeksforgeeks.org/pqvGANXWLT

Find whether there is path between two cells in matrix

Solution:-

import java.util.*;
class Point
{
    int x,y;
    Point(int x,int y)
    {
        this.x=x;
        this.y=y;
    }
}
class Queue
{
    Point p[]=new Point[10000];
    int front=-1,end=-1;
    void add(int x,int y)
    {
        if(front==-1)
            front=0;
        if(end<9999)
        {
            p[++end]=new Point(x,y);
        }
    }
    Point poll()
    {
        Point x=p[front++];
        return x;
    }
    boolean isEmpty()
    {
        if(front>end)
          return true;
        if(front==-1||end==-1)
          return true;
      return false;     
    }
}

class GFG {
    static String check(int mat[][],int n,int m)
    {
        boolean visited[][]=new boolean[n][m];
        Point p=new Point(0,0);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(mat[i][j]==1)
                {
                    p.x=i;
                    p.y=j;
                }
                else if(mat[i][j]==0)
                 visited[i][j]=true;
                 else
                 visited[i][j]=false;
            }
        }
        Queue q=new Queue();
        q.add(p.x,p.y);
        visited[p.x][p.y]=true;
        while(!q.isEmpty())
        {
            p=q.poll();
            if(mat[p.x][p.y]==2)
             return "YES";
             //left
            if(p.y-1>=0&&visited[p.x][p.y-1]==false)
            {
                q.add(p.x,p.y-1);
                visited[p.x][p.y-1]=true;
            }
            //right
             if(p.y+1<m&&visited[p.x][p.y+1]==false)
            {
                q.add(p.x,p.y+1);
                visited[p.x][p.y+1]=true;
            }
            //bottom
             if(p.x+1<n&&visited[p.x+1][p.y]==false)
            {
                q.add(p.x+1,p.y);
                visited[p.x+1][p.y]=true;
            }
            //top
             if(p.x-1>=0&&visited[p.x-1][p.y]==false)
            {
                q.add(p.x-1,p.y);
                visited[p.x-1][p.y]=true;
            }
        }
        return "NO";
    }
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int mat[][]=new int[n][m];
for(int i=0;i<n;i++)
{
    for(int j=0;j<m;j++)
    {
        mat[i][j]=sc.nextInt();
    }
}
System.out.println(check(mat,n,m));
}
}