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));
}
}

Mobikwik Interview Experience |( OffCampus Drive Quality Assurance SDET-I)

MobiKwik is an Indian company founded in 2009 that provides a mobile phone based payment system and digital wallet. Customers add money to an online wallet that can be used for payments.

A couple of days back(22nd July,2019) MobiKwik hire as Quality Assurance Engineer SDET-I for passout 2019 batch.
Selection process go thru various round let's discuss about that.

Round 1:- Offline Wriiten Coding and MCQ and Test Cases   

This round was 40 minuts and contains 15 MCQ which was technical,aptitude ,Data Structure and 2 Coding Questions,and 1 Test Case writting.

Coding 1:-  Given a string find all permutaions of given string in lexicographical order.

Coding 2:-  Given an array remove duplicate elements from the array.

ex:-  a[]={1,2 3,1,2,3,1,2}

Output:-   {1,2,3,0,0,0,0,0}

Round 2:-  Technical Interview-I

After written test almost 34 students got selected for next round and I was one of them.
In this round Interviewer came and ask me tell me something about yourself. I was very nervous but interviewer was very cool and after introduction he asked me 3 coding problem.
 1. Given an array sort array using recursion.
 2. Given string print all the string that accure more than one times in the given string.
     ex:  my name is sushil mall my name is.

     Output:-   my name is
 3. Find Second highest element in the array.

after asking coding he asked me some puzzles, databases queries and testing related questions.

Round 3:- Technical Interview-II

I was very happy to clear the first round and in the second round interviewer came and asked me tell me something about yourself. she was very cool and very friendy.
she asked me a coding question and write code about the given question. queastion was given a array find second minimum element in the gievn array.after that she asked me puzzles and queries.

Round 3:- Testing interviews-III

Again i was very happy because I have clear the second technical round and on left testing and was last round.Interviewer came and asked me why should we hire you convince me.I explain but he was not convinced. I was very nervous because he was not friendy and his attitude was very dangrous.then after discussion at leas 10 minut on why should we hire you. he said me to write test case of wallet transaction. again I was fear and nervous because he was not friendly and everyone knows that 'fear is not good for fair' I write some test cases he said think something and write some another test cases. and then he asked me to write Test cases of shoes I write but he gave me time limit and said to write 50 test cases. Finaly result announce and I was not selected only 4 student got selected.But when I was going to my house HR call me and said that come tomarrow with some preperation about testing.

 Round 4:- Technical Interview-IV

Next day I went again Mobikwik office for last interview. Then inetrviewer came and asked my why you did not select previuos day. I explain all about previous day then he gave me a coding problem to solve and write the code. problem was given a 2-D n*n matrix rotate it 90 degree. I wrote code firstly and explain him. He said write test case of every steps of given problem I wrote he was very happy. he asked me to write test case of lift I wrote and tell him but he want to know more test cases. then he asked me how much companies you have already give Interviews then last hes asked me a puzlle and said if you will solve this puzzle then you will got selected today otherwise some difficulties will got. and you have infinite time and you can try many time. I solve that with in 10 min with 5th tery he becomy happy and handshake with me congratulate me. then HR came and asked about my family and said congratulation and we are going to hire you said your family.
I was very happy to get a offer from Mobikwik. Thanks a lot Mobikwik and their Team.

*******************************Enjoy ********************************************