Functional interface in Java

Function interface in Java

We discussed interfaces and abstract class in earlier, let’s discuss specific type of interface called functional interface. A functional interface is an interface with only one abstract method. This abstract method is implemented by class. Below is example of a functional interface, interface CustomFunctionalInterface has only one abstract method abstractMethod.

@FunctionalInterface
public interface CustomFunctionalInterface {
	public boolean abstractMethod(Integer a);
}

Notice that there is special annotation @FunctionalInterface added in Java 8 to help compile type check, if you add another abstract method in functional interface, it will throw an error.

What happens when another interface inherit functional interface? If there is no other abstract method defined in child interface, it automatically become functional interface. Child interface can have default methods and still be functional.

It’s not that the functional interfaces came in Java 8, they preexisted, example being Runnable interface mentioned above. However there are many functional interfaces like Predicate are introduced in Java 8. By virtue of their ability to pass around functionality(i.e. behavior), functional interfaces primarily enable behavior parameterization.

Functional interface and anonymous class

Anonymous class is a class without a name. Anonymous classes are created and instantiated using functional interfaces. One of the most common example is instantiating Runnable class.

public class AnonymousInnerClassTest {
	public static void main(String[] args) {
		new Thread(new Runnable() {
			@Override
			public void run() {
				System.out.println("A thread created and running");
			}
		}).start();
	}
}

This does not mean that anonymous classes can only be created using functional interface, but it is less clumsy and  more understandable when using one. Notice how anonymous class is created, 

The anonymous class expression consists of the following:

  • The new operator
  • The name of an interface to implement or a class to extend. In this example, the anonymous class is implementing the interface Runnable.
  • Parentheses that contain the arguments to a constructor, just like a normal class instance creation expression. Note: When you implement an interface, there is no constructor, so you use an empty pair of parentheses, as in this example.
  • A body, which is a class declaration body. More specifically, in the body, method declarations are allowed but statements are not

Let’s see an example where we are using functional interfaces.

Please share if there is something is missing or wrong. If you want to contribute to website, please reach out to us on [email protected]

Default methods in interface In Java 8

Default methods in interface

Before understanding default methods in interface, first understand what in an interface. An interface is the contract an object exposes to the outside world. An interface is a reference type in Java. It is a collection of abstract methods which are implemented by class.

In plain terms, let’s say you are developing a program which interact with multiple TV sets. These TV sets will have different types of remote operating them. Now, if you implement version of our program for each type of TV and remote available in market, it will be a nightmare.
That’s why we expose an interface or contract which all TV set implementation adhere to and all remotes can use that interface to operate desired functionality.
Here advantage is that no matter what internal implementation of TV is as far as it follows the same interface, remote will work.

	interface TV { 
		public boolean switchOn();
		public boolean switchOff();
		public int changeChannel();
		public int volumeDown();
		public int volumeUp()
	} 

We can implement these methods in any which way we like on different TV sets (objects) without having to change remotes (outside world implementation).

public class SamsungTV implements TV {
	public boolean switchOn() {
		// implementation
	}

	public boolean switchOff() {
		// implementation
	}

	public int volumeDown() {
		// implementation
	}

	public int volumeUp() {
		// implementation
	}
}

As you noticed that interface only contains abstract function and does not give any implementation of any function. However, with Java 8 that has changed. An interface can have default implementation of a function.

	public interface InterfaceExample {
		// to be implemented by class
		void abstractMethod(String str);
	
		default void defaultMethod(String str){
			System.out.println("logging::"+str);
		}
	}

Why was that required? Imagine a case where you defined an interface and whole lot of classes implemented it in whatever way they wanted to. Now, at certain time in your project, you decided to add another method to the interface. It will need update of all classes which implement interface. 
How about a default implementation of new function and classes can implement it if they want different behavior? One of the major reason for introducing default methods in interfaces is to enhance the Collections API in Java 8 to support lambda expressions.

As you know, Java does no allow multiple inheritance, that is to inherit more than one class, because that leads to “diamond problem. However, which interfaces having default implementation, and classes can implement multiple interfaces, “diamond problem” is bound happen. If two interface implement same function which function should be used by class object? 
To solve this problem, it is mandatory to provide implementation of common default methods of interfaces by class else compiler will throw errors.

	public interface InterfaceExample1 {
		// to be implemented by class
		void abstractMethod1(String str);
	
		default void defaultMethod(String str){
			System.out.println("logging::"+str);
		}
	}		
	public interface InterfaceExample2 {
		// to be implemented by class
		void abstractMethod2(String str);
	
		default void defaultMethod(String str){
			System.out.println("logging::"+str);
		}
	}		
public class ExampleClass implements InterfaceExample1, InterfaceExample2 {

	@Override
	public void abstractMethod1() {
	}

	@Override
	public void abstractMethod2(String str) {
	}

	@Override
	public void log(String str){
		System.out.println("MyClass logging::"+str);
	}
}

Default methods in interfaces actually bridges the gap between abstract classes and interfaces in Java. Also, it safeguards again breaking of code in case interfaces are modified. 

Please share if there is something wrong or missing. If you want to contribute to website, please reach out to us on [email protected]

Abstract class Vs Interface

Difference between abstract class and interface

To understand difference between abstract class and interface, first, we have to understand what is an abstract class and an interface and what are the similarities.

Abstract class in plain terms is a class which contains one more abstract methods. Abstract method has no implementation, just a declaration. Sub-classes of abstract class are responsible for providing implementation of such methods. Example of an abstract class as follows

package Examples;

/**
 * Created by sangar on 22.10.17.
 */
public abstract class AbstractBicycle {
    //member fields
    protected int gears;
    protected int topSpeed;
    protected int serviceCost;

    public int getGears(){
        return this.gears;
    }

    public abstract void service();
}

 

On the other hand, interfaces are like contracts which are honored by every class which implements them. It does not matter how a class implement the contract, as far as it implements it. For example, Television box can have may functionalities like changing channels, volume control, records, selection of source etc. TV manufacturers defined this industry standard interfaces, so that remotes can be build to call these behaviors on TV sets. It does not matter how different models of TV implement these interface, as far as they implement it.

Interface is again just like a class, which contains all abstract methods.  Implementation of those methods is left to class  which implements interface. Interface can contain constants too which are by default final. Example of declaration of an interface be

package Examples;

/**
 * Created by sangar on 22.10.17.
 */
interface IBicycle {

    void changeGear(int newValue);

    void speedUp(int increment);

    void applyBrakes(int decrement);
}

So, what’s the difference between abstract class and interface then? There are very subtle differences as follows

  1. Abstract class is object oriented in nature as it defines hierarchy between classes, on the other hand interfaces are functional in nature as they define what a class has to implement to satisfy this interface.
  2. Methods and fields in abstract class can have individual access specifiers like private, public or protected, where as in interfaces, everything has to be public. Sub-class implementing abstract methods from abstract class can keep visibility same or reduce it, whereas class implementing interface has to keep visibility same which is public.
  3. A sub-class or child can only extend single abstract class, whereas a class can implement multiple interfaces.
  4. By definition, abstract class can have default implementation of some methods, where as interface just has definition of all methods. This is not true from Java 8 default method signatures in interface. Refer here for more details.
  5. Sub-class uses extends to use abstract class where implements to implement an interface.
  6. Abstract classes can have constructors but interfaces can’t have constructors.

Abstract class Vs Interface : When to use what?

Now, when to use what? When to use abstract class and when to go to interfaces.

Consider using abstract classes if any of these statements apply to your situation:

  • You want to share implementation among several closely related classes.
  • You expect that classes that extend your abstract class have many common methods or fields, or require access modifiers other than public (such as protected and private).
  • You want to declare non-static or non-final fields. This enables you to define methods that can access and modify the state of the object to which they belong.

Consider using interfaces if any of these statements apply to your situation:

  •  If unrelated classes would implement your interface.
  • Specify the behavior of a particular data type, but not concerned about who  implements its behavior.
  • You want to take advantage of multiple inheritance of type.

Reference : Oracle documentation

In short, abstract class provides is-a kind of relationship between class and concrete sub-classes whereas interface provides has-a capability between unrelated classes.

This post clarifies difference between abstract class and interface and explains when to use what. Hope it helped you!

Please share if there is something wrong or missing. If you want to contribute to website, please reach out to us through contact form or drop a mail to [email protected]

 

Median of integers stream

Median of integers stream

We solve two problems which involved streams, first was to find first non repeated character in stream and second was LRU cache. Let’s discuss another problem which is to find median of integers stream. Problem statement is like this: Given continuous stream of integers, find median of integers stream received till given point of time. Median can be asked at multiple times.

To understand problem better, ask yourself, what is a median?

The median is the value separating the higher half from the lower half of a data sample. For a data set, it may be thought of as the “middle” value.

Wikipedia

For example, in the data set {1, 3, 3, 6, 7, 8, 9}, the median is 6, the fourth largest, and also the fourth smallest, number in the sample.

Median of sorted array of integers is element at middle index of array if size of array is odd and average of elements at mid and mid +1 elements if size of array is even.

Now, that we understood the definition of median. let’s go back to our problem and take an example to understand it further. Problem is that we get integers from a stream, one by one and at any given point of time, we have to return median of set of integers received till now. 
First, stream throws 12, then 7 and then 8. What will be the median now? It will be 8, because if we arrange 12,7,8 in sorted order, 8 is element at middle. What if we get 11 next? Well, now sorted order looks like 7,8,11,12. As size of set is even, we take average of mid and mid+1 element which is 9.5.

Median of integers stream : thoughts

What will be the brute force solution? As integers are processed from stream, store them in an array. Can we store element randomly? If yes, to find median, we have to sort array every time. Complexity of this method to find median in stream of integers will be O(n log n) dominated by the sorting algorithm.
How about we insert element in array in sorted order. This will make complexity of processing integer from stream O(n2), as we have to move n elements to right in worst case.
Another underlying problem in using array here is that we do not know how many integers will come out of stream, so it will be very difficult to pre-allocate memory for it. Linked list can solve that problem, however, it does not reduce complexity of processing, at the same increases the complexity of finding median to O(n) from O(1).

Think of this, do we need completely sorted set of  integers before we can calculate the median? Actually, we need kth smallest element of array if size of set is odd and average of kth and k+1th element if size of set is even, k will be n/2. 

However, we do not have pre-processed array with us. What is the property of the median? Median is greater than all elements on left of it and less than all elements on the right side of it, where the number of elements on both groups is equal or differs by 1.

Median of integers stream : Heaps

How about we split the incoming integers into two halves. Whenever median is asked, we can get the maximum of one half and return it as median, if the size of two halves differ by 1 or return of average of the max of one half and minimum of other halves if the size of two halves is equal.

What data structure is best to find min and max in constant time? Heap it is. In this case, we will need two heaps, one max and another min heap. Max heap will store all the elements on the left side of median and min heap will store all the elements on the right side of the median.

How to balance the size difference between the two heaps? Insert new processed integer into the max heap,  if the size of the max heap is 2 more than min heap, extract the maximum element from the max heap and put it in min heap.

Also, maintain the property that all the elements on the max heap should be less than elements on the min heap. So, whenever the root of the max heap greater than the root of min heap, it should be removed from the max heap and added to the min heap.

Let’s take an example and understand the method first and the make concrete algorithm out of it. We have the first number from the stream as 12, what should we do? We decided to put every number on the max heap to start with.

median of integer stream
Add the integer to max heap as both heaps are empty at this point of time

Now, comes the integer 7. First of all, we add a new integer to the max heap. This will create a difference in size of the min and max heap more than one. In that case, we will take out the max from the max heap and put it into the min heap.

median of integers stream
7 is added to the max heap, which makes size difference of more than 1.
So, the root of the max heap (12) is moved to min heap

Next integer is 18, what happens now. We add into the max heap. Difference between sizes is not more than 1, However, the root of the max heap (18) is greater than the root of min heap (12). In this case, too, we take the root of the max heap and move it to the min heap. At this point, if the median of integers stream is asked, return the root of min heap which is 12.

18 is added to max heap, however now the root of max heap is more than the root of the min heap, so it should be removed from the max heap
median of stream
18 is removed from the max heap and added to the min heap.

Come the integer 10, it goes into the max heap, does not create any size difference and the root of the max heap is less than the root of the min heap. At this point, the median of the stream of integers till now is 11 ((10+12)/2).

median of stream of integers
10 is added to the max heap.

.New integer from the stream is 11. As usual, add the new integer to the max heap, size difference remains less than 2 and 11 is less than the root of the min heap (12).
What should be the median now? At this point, the size of the max heap is more than the min heap, hence we will return the root of the max heap (11)

median of integer stream
11 is added to max heap

Median of a stream of integers: Algorithm

  1. Process integer from the stream and add it to the max heap.
  2. If the root of max heap greater than the root of the min heap:
    1. Delete the root from the max heap
    2. Add removed integer from the max heap to the min heap
  3. If the size difference between the two heaps is more than 2:
    1. Remove the root of the heap which has more elements.
    2. Add removed node to another heap.
  4. To calculate the median:
    1. If the size of both heaps equal, return average of their roots.
    2. Else, return the root of the heap with more elements.

Median of integers stream : Implementation

Implementation involves priority queue in Java, refer to Stack Overflow question on how to use priority queue as a max heap.

package com.company;

import java.util.Collections;
import java.util.PriorityQueue;

/**
 * Created by sangar on 18.10.18.
 */
public class MedianOfIntegerStream {
    private PriorityQueue maxHeap;
    private PriorityQueue minHeap;

    public MedianOfIntegerStream(){
        maxHeap = new PriorityQueue(Collections.reverseOrder());
        minHeap = new PriorityQueue();
    }

    public double getMedian(){
        if(maxHeap.size() == minHeap.size())
            return (double)((int)maxHeap.peek() + (int)minHeap.peek())/2;

        if(maxHeap.size() > minHeap.size())
            return (double)(int)maxHeap.peek();

        return (double)(int)minHeap.peek();

    }

    public void processInteger(int data){
        maxHeap.add(data);

        if(maxHeap.size() - minHeap.size() > 1
                || ( minHeap.size() > 0 
				&& (int)maxHeap.peek() > (int)minHeap.peek())){
            minHeap.add(maxHeap.poll());
        }

        if(minHeap.size() - maxHeap.size() > 1){
            maxHeap.add(minHeap.poll());
        }
    }
}

Test cases for median in integers stream

package test;

import com.company.MedianOfIntegerStream;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class MedianOfIntegerStreamTest {

    MedianOfIntegerStream tester = new MedianOfIntegerStream();

    @Test
    public void baseTest() {

        tester.processInteger(12);
        tester.processInteger(7);

        assertEquals(9.5, tester.getMedian() );
    }

    @Test
    public void maxHeapWithMoreElementsTest() {

        tester.processInteger(12);
        tester.processInteger(7);
        tester.processInteger(9);

        assertEquals(9, tester.getMedian() );
    }

    @Test
    public void minHeapWithMoreElementsTest() {

        tester.processInteger(12);
        tester.processInteger(7);
        tester.processInteger(9);
        tester.processInteger(13);
        tester.processInteger(15);

        assertEquals(12, tester.getMedian() );
    }

    @Test
    public void minHeapSizeMoreThanTwoDifferenceTest() {

        tester.processInteger(12);
        tester.processInteger(7);
        tester.processInteger(9);
        tester.processInteger(13);
        tester.processInteger(15);
        tester.processInteger(17);
        tester.processInteger(19);

        assertEquals(13, tester.getMedian() );
    }

    @Test
    public void maxHeapGetsTheElementTest() {

        tester.processInteger(12);
        tester.processInteger(7);
        tester.processInteger(9);
        tester.processInteger(13);
        tester.processInteger(15);
        tester.processInteger(17);
        tester.processInteger(5);
        assertEquals(12, tester.getMedian() );
    }
}

Complexity of processing is O(log n) to insert an element into any heap. However, fetching median in stream of integers at any given time is O(1).

Please share if there is something wrong or missing. Please signup if you want to receive curated interview material for your preparation.