Find the number of Islands using DFS.

Count total number of Islands OR
The "Island Count" Problem


Given a Ocean in a form of 2D matrix as shown below in which there are few Island present 
(or may not be present).

In a matrix given above, which has only two values ‘1’ and ‘0’. 
1 represents land and 
0 represents water, 
Find the total number of Islands.

Lets understand what is the input and the expected output with few samples.

Sample 1:
Input: 
        int[][] island = new int[][] {
                { 1, 1, 0, 0, 0 },
                { 0, 1, 0, 0, 1 },
                { 1, 0, 0, 1, 1 },
                { 0, 0, 0, 0, 0 },
                { 1, 0, 1, 0, 1 }             
        };
Output: 5

Sample 2:
Input:
        int[][] island = new int[][] {
                {0, 0, 0, 0, 0 },
                {0, 0, 0, 0, 0 },
                {0, 0, 0, 0, 0 },
                {0, 0, 0, 0, 0 },
                {0, 0, 0, 0, 0 }               
        };

Output:0

Sample 3:
Input:
        int[][] island = new int[][] {
                { 1, 0, 0, 0, 0 },
                { 0, 1, 0, 0, 0 },
                { 0, 0, 1, 0, 0 },
                { 0, 0, 0, 0, 0 },
                { 1, 1, 1, 0, 0 }                  
        };

Output:2

Find the number of Islands

Count number of islands where every island is row-wise and column-wise separated


Count total number of islands present in given matrix where every island is separated row-wise and column-wise.

Given a rectangular matrix which has only two values ‘1’ and ‘0’.
1 represents land.
0 represents water.
Islands are all rectangular in shape that is values ‘1’ will always appear in form of rectangular islands and these islands are always row-wise and column-wise separated by at least one line of ‘0’s.

If there is any diagonal island then it will be considered adjacent islands and will be separate.
Count total number of islands in the given matrix.


Lets understand what is the input and the expected output.

Sample 1:
Input: 
        int[][] island = new int[][] {
            { 0,  0,  0 },
            { 1,  1,  0 },
            { 1,  1,  0 },
            { 0,  0,  1 },
            { 0,  0,  1 },
            { 1,  1,  0 }               
        };
Output: 3

Sample 2:
Input:
        int[][] island = new int[][] {
            { 1,  0,  0 },
            { 0,  1,  0 },
            { 0,  0,  1 },
            { 0,  1,  0 },
            { 1,  0,  0 },
            { 0,  1,  0 }               
        };

Output:6

Sample 3:
Input:
        int[][] island = new int[][] {
            { 1,  1,  0 },
            { 1,  1,  0 },
            { 1,  1,  0 },
            { 0,  1,  0 },
            { 0,  0,  1 },
            { 1,  1,  1 }               
        };

Output:3

Stock Buy Sell to Maximize Profit

Maximum difference between two elements such that larger element appears after the smaller number. OR
Stock Buy Sell to Maximize Profit.


We are given an array of N integers representing Stock Prices on a single day.
Find maximum profit that can be earned by performing 1 transaction.


We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay,
such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.


Lets understand what is the input and the expected output.

Sample 1:
Input: [100, 80, 120, 130, 70, 60, 100, 125]
Output: If we buy a stock at 60 and sell at 125 then profit is maximum (65). Sample 2:
Input: [7, 9, 5, 6, 3, 2]

Output: If we buy a stock at 7 and sell at 9 then profit is maximum (2).

Sample 3:
Input: [1, 2, 3, 4, 5, 6]
Output: Prices are in increasing order so there will be no profit as stock prices goes on increasing. So answer is 0.

The Skyline Problem

Skyline Problem In Java.


A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. 
Now suppose you are given the locations and height of all the buildings as shown on a cityscape below. Write a program to output the skyline formed by these buildings collectively.

Lets simplify the problem statement and understand it correctly,
If there are many buildings in a area as shown in below picture, If same buildings is viewed from distance then what we can see is not all the buildings but the skyline that is borders of all buildings.

You can see skyline of buildings if viewed from a side and remove all sections that are not visible/overlapped.
All buildings have common base and every building is represented by 3 points(left, right, height)

‘left': is x coordinate of building left wall.

‘right': is x coordinate of building right wall
‘height': is height of building.


A skyline is a collection of rectangular strips. A rectangular strip is represented as a pair (left, height) where left is x coordinate of building left wall and height is height of building.

Lets understand what is the input and the expected output. INPUT: You are given a building coordinates as shown below,
int[][] skyscraper = { {2,9,10},  {3,6,15},  {5,12,12},  {13,16,10}, {15,17,5} };

OUTPUT: Skyline Coordinates = { {2,10},  {3,15}, {6,12}, {12,0}, {13,10}, {16,5}, {17,0} }


Compress a given string in-place and with constant extra space.

Run-length encoding Program. OR
Given an input string, write a function that returns the Run Length Encoded string for the input string. OR
Compress a given string inplace and with constant extra space.


Compress a given string "aacccddd" to "a2c3d3"
Constraint: Inplace compression, no extra space to be used.
Assumption: Output size will not exceed input size. 

Example: input:"acc" output: "a1c2" buffer overflow, because output size length is 4 and input size length is 3. Such inputs will not be given.

Lets understand what is the input and the expected output.


Type Casting Interview Questions In Java

Type Casting Interview Questions In Java


Type casting helps calling methods of a class using generic reference thereby maintains Polymorphism.


Question 1. We have a requirement to display all the features of a Bird and a class is designed as shown below, how to display all the features of each Bird?

interface Bird{
 void walk();
}

interface Fly{
 void fly();
}

interface Swim{
 void swim();
}

class Duck implements Bird, Fly, Swim{
 @Override
 public void swim() {
  System.out.println("Duck.swim()");
 }

 @Override
 public void fly() {
  System.out.println("Duck.fly()");
 }

 @Override
 public void walk() {
  System.out.println("Duck.walk()");
 }
}

class Pigeon implements Bird, Fly{
 @Override
 public void fly() {
  System.out.println("Pigeon.fly()");
 }

 @Override
 public void walk() {
  System.out.println("Pigeon.walk()");
 }
}

For displaying all the features of Pigeon and Duck, we only need to know what all operations Birds can support like Fly, Swim etc? Based on type checking, we can call particular operation and display all features.
class Zoo{
 public static void main(String[] args) {
  
  Bird bird1 = new Duck();
  bird1.walk();
  if(bird1 instanceof Fly){
   ((Fly)bird1).fly();
  }
  if(bird1 instanceof Swim){
   ((Swim)bird1).swim();
  }
  
  Bird bird2 = new Pigeon();
  bird2.walk();
  if(bird2 instanceof Fly){
   ((Fly)bird2).fly();
  }
  if(bird2 instanceof Swim){
   ((Swim)bird2).swim();
  }
 }
}

Interface typecast helps to achieve this kind of behaviour.


Question 2.
What is the output of below program? will there be any error/exception? if yes then compile time or run time and why?

class SampleClass1 {
    public void test(){}
}
class SampleClass2 {
    public void test(){}
}

class MainTest {

    public void main(String[] args) {
     SampleClass1 sc1 = new SampleClass1();
     SampleClass2 sc2 = (SampleClass2) sc1;
    }
}

It will give Compile Time Error: "Cannot cast from SampleClass1 to SampleClass2".
Casting is possible only if there is Parent-child relationship between classes.


Question 3.
What is the output of below program? will there be any error/exception? if yes then compile time or run time and why?

interface SInterface1 {}

class SampleClass1 {}

class MainTest1 {
 public static void main(String[] args) {
  SampleClass1 sc1 = new SampleClass1();  
  SInterface1 sc2 = (SInterface1) sc1;
 }
}

It will NOT give Compile Time Error but will give Runtime Exception: 
"java.lang.ClassCastException: SampleClass cannot be cast to SInterface1".

Question here is why it didn't gave Compile time error?
Compiler is really not sure here to give compile error because sc1 at runtime can be reference of 
class SampleClass2, say (class SampleClass2 extends SampleClass1 implements SInterface1) in that case typecasting is perfectly valid. So Compiler doesn't give Compile error in this case, but when you run the program it sees that sc1 doesn't point to class that implements SInterface1 and that is why it cannot be typecasted.

Valid typecase possible at runtime,
interface SInterface1 {}
class SampleClass1 {}

class SampleClass2 extends SampleClass1 implements SInterface1{}

class MainTest1 {
 public static void main(String[] args) {
  SampleClass1 sc1 = new SampleClass1(); 
  sc1 = new SampleClass2();
  SInterface1 sc2 = (SInterface1) sc1;
 }
}



Question 4.
What is the output of below program? will there be any error/exception? if yes then compile time or run time and why?

class ClassA{}
class ClassB{}

interface InterfaceI{}

class MainTest11 {
 public static void main(String[] args) {
  InterfaceI i = (InterfaceI)(new ClassA());
  ClassA b = (ClassB)(new ClassA()); 
 }
}

It will give Compile Time Error: "Cannot cast from ClassA to ClassB" at line 9.
It will give Runt Time ClassCastException: "ClassA cannot be cast to InterfaceI" at line 8.

Check below image for better understanding of how Compiler treats casting to 
Reference and Class,


Question 5.
What is the output of below program? will there be any error/exception? if yes then compile time or run time and why?

interface Interface1 { }
interface Interface2 { }
class Class1 implements Interface1 { }

class Test{
 public static void main(){
  Class1 c1 = new Class1();
  String str = new String("Hello"); //OR Integer str = new Integer(1); 

  Interface2 x = (Interface2)c1;  //why compiler does not complain here?
  Interface2 y = (Interface2)str; //why compiler complains here?
 }
}
It will not give Compile time Error at line 10 but gives Compile error at line 11, why?
According to Question 4, which explains rules of typecasting,

Interface2 x = (Interface2) c1;

Compiler will not care what c1 is, it just validates "whether c1 can be object of a Class which is subclass of c1's class type and implements Interface2"? 

For line 10, that is possible because there can be class like,
Class A extends Class1 implements Interface2{}
c1 = new A();
Interface2 x = (Interface2)c1;

For line 9, that is not possible, str can't be object of class,
  1. which extends String class and (This is not possible)
  2. Implements Interface2. (This is possible)
String is as final class, So no class can be subclass of (extends) String class, that is why compiler is sure and gave compile error at line 11.

If we declare Class1 final, then compiler will complain at line 10 as well.

You may also like to see


Important Java Multithreading Interview Questions & Answers

How is ambiguous overloaded method call resolved in java?

Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

 

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.