Sorting Techniques

Background

This post summarises various sorting techniques.

Sorting Techniques

I have written posts over time to show the implementation of some of the sorting techniques. Following are links to the same -

• Bubble Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Counting Sort
• HeapSort

Related Links

• http://bigocheatsheet.com/
• Sort a stack using recursion in Java(OSFG)

What is transient keyword in Java?

Background

In one of my earlier post, I had covered what serialization in Java is and how transient keyword can be used in that context. You can take a look at that post -

• Serialization in Java

We saw that in serialization context, instance variables marked as transient will not be serialized and on deserialization, they get the default values. In this post, we will see some more details about transient keyword with an example.

Transient use cases

• The transient keyword should be used when you do not want to serialize your instance variables. Eg.
• An instance of Logger class. There is no state associated with a logger instance, so we do not need to serialize it.
• Similarly, any secure data like passwords, which you may not want to serialize.
• You cannot use any classes in the JDK that does not implement Serializable as references in your class that is Serializable. It needs to be marked transient. Else it will throw “java.io.NotSerializableException” exception.

The transient and final keyword

Transient treats final keyword a bit differently. So let's take an example to understand this,

//final field 1
public final transient String myName = "Aniket";
//final field 2
public final transient Logger myLogger = LoggerFactory.getLogger(MyClass.class.getName());

If you consider above fields in a class, by our above logic they should not be serialized since they are marked as transient. However, if any final variable is evaluated as a "constant expression" like in case of myName above, it will be serialized. So in above case myName is serialized and myLogger is not.

On the side note, recall serialVersionUID which is static and final. It is the only static variable that gets serialized. static instances do not form the state of the object, so by very definition of serialization, it is not serialized.

Use of transient keyword in HashMap.

If you see HashMap implementation you can see the array that backs it is marked as transient.

      /**
      * The table, resized as necessary. Length MUST Always be a power of two.
  */
      transient Entry[] table;

If this array is not serialized, how does it get deserialized back to restore instance state? Class does implement serializable -

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {


    private static final long serialVersionUID = 362498820763181265L;

Reason for this is that two instances of same class do not generate the same hashcode (unless of course, you override the hashcode method to do so). The native implementation uses the objects memory location which will be different for the object before serialization and after deserialization. So it is not guaranteed that the objects will be in the same bucket and in the same location as that of hashmap that was serialized. This is why the array itself is not serialized by marking it as transient. So how is the instance state restored? 

For this in HashMap implementation, they override writeObject and readObject method. In the writeObject method, all entries from the entry array are read in a sequence and serialized. Similarly, in readObject for deserialization, it is read in the same order and then stored in its own internal entry table array. So the buckets and position are dynamically calculated during deserialization with the same data.

PS: This is a good interview question :)

Related Links

• Serialization in Java(OSFG)

How to print odd and even numbers in order with two threads

Background

Let us say you have two threads - one thread prints even numbers and other one prints odd numbers. You need to design this in such a way that all the numbers are printed in the natural order i.e 1,2,3,4 etc. 

This is more of a synchronization questions rather than a data structure question. You need to understand how threads, synchronization works in order to be able to solve this question. 

How to print odd and even numbers in order with two threads

We can do this two ways -

1. Using Sempahores
2. Using wait and notify

Let us see how we can do this using semaphores -

public static void withSemaphores() throws InterruptedException, ExecutionException {

 Semaphore oddLock = new Semaphore(1);
 Semaphore evenLock = new Semaphore(0);

 Runnable printOdd = () -> {
  for (int i = 1; i < 10; i = i + 2) {
   try {
    oddLock.acquire();
   } catch (Exception e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
   ;
   System.out.println(i);
   evenLock.release();
  }
 };

 Runnable printEven = () -> {
  for (int i = 2; i < 10; i = i + 2) {
   try {
    evenLock.acquire();
   } catch (Exception e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
   System.out.println(i);
   oddLock.release();

  }
 };

 new Thread(printOdd).start();
 new Thread(printEven).start();
}

Before we see how this is actually working you need to understand how semaphores work. They essentially are like permits. You can initialize the semaphore with the initial permits. Let us say semaphore has 2 permits, to begin with. In this case, 2 threads can acquire these permits. The 3rd thread which comes has to wait till one of the 2 permits become available again. Threads that have acquired the permits can release them once they are done. Permits are acquired by acquire() method and released by release() method. To read more about Semaphores you can refer a post I had written earlier -

• Counting Semaphore, CountDownLatch, CyclicBarrier - synchronization methods for concurrency

Also, note I have used Java 8 lambda syntax in the code above. You can read more about lambds -

• Using Lambda Expressions from Java 8

Now with this understanding let's see how the above logic works.

printOdd runnable is responsible for printing odd numbers whereas printEven prints even number. For loop is designed in such a way and it increments by 2 to continue printing respective numbers. We need to start with 1 which is odd, so old thread starts first. Notice we have 2 semaphores - one for odd and one for even. Odd semaphore has 1 permit whereas even semaphore has 0, to begin with. The odd thread can get the permit from an odd semaphore and print the odd value which is 1. Meanwhile, the even thread will get blocked since no permits are available for even semaphore. Only when an odd thread releases even semaphore permit, even thread will go ahead and print 2. That's how each thread locks each other till numbers are printed in sequence.

You can do the same with the wait and notify. You can see both of the above methods on my GitHub repository on data structures - https://github.com/aniket91/DataStructures/blob/master/src/com/osfg/questions/PrintOddEven.java 

Related Links

• Counting Semaphore, CountDownLatch, CyclicBarrier - synchronization methods for concurrency(OSFG)
• Using Lambda Expressions from Java 8(OSFG)
• https://github.com/aniket91/DataStructures

How to use Callable interface with Threads in Java?

Background

In one of the previous posts on Creating Threads with Executor service, we saw an interface called Callable. Executor has a method called submit that took Callable object and returned a future object which had the results. Unlike the Runnable interface, we can use Callable interface to return the result or throw checked Exceptions. In this post, we will see how to use Callable interface with plain Thread construct.

How to use Callable interface with Threads in Java?

We know that Thread takes Runnable interface only. No surprises there. So we cannot directly use objects implementing the Callable interface. Also to get the result we need Future object as we saw in Executors. Remember any design pattern that suits this use case? yes, it is Adapter Pattern. Java provides a class called FutureTask which implements Runnable and Future, combining both functionalities conveniently. Let's see an example of how we can do this -

package com.osfg;

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.FutureTask;

public class Test {
 public static void main(String args[]) throws InterruptedException, ExecutionException {

  Callable<String> callable = () -> {
   Thread.sleep(5000);
   return "Hello!";
  };

  FutureTask<String> futureTask = new FutureTask<>(callable);
  Thread t = new Thread(futureTask);
  t.start();

  while (!futureTask.isDone()) {
   System.out.println("Task not done yet!");
   Thread.sleep(1000);
  }

  System.out.println(futureTask.get());
 }

}

You can see here that our Callable waits for 5 seconds and returns the results. And in the main thread, we do a check every 1 second to see if the result is available in the FutureTask. So if you run above code you will get -

Task not done yet!

Task not done yet!

Task not done yet!

Task not done yet!

Task not done yet!

Hello!

FutureTask has following methods -

• public boolean cancel(boolean mayInterrupt): Used to stop the task. It stops the task if it has not started. If it has started, it interrupts the task only if mayInterrupt is true.
• public Object get() throws InterruptedException, ExecutionException: Used to get the result of the task. If the task is complete, it returns the result immediately, otherwise, it waits until the task is complete and then returns the result.
• public boolean isDone(): Returns true if the task is complete and false otherwise

Related Links

• Creating Threads with Executor service(OSFG)
• Adapter and Facade Design Patterns in Java(OSFG)

How to write your own attribute directive in Angular?

Background

In the last post, we saw how to use structural directives like *ngIf and *ngFor that can be used to modify DOM elements. 

• Using structural directives in Angular

Attribute directives can change the appearance or behavior of an element, component, or another directive. In this post, I am going to show you how to write your own attribute directives in Angular.

For this, we are going to create a directive which on single click will enlarge our text and on double click get it back to original size. 

How to write your own attribute directive in Angular?

Let's start by writing our directive class file. Under the app folder create a new file called enlarge.directive.ts.  In this file add following code -

import { Directive, ElementRef, HostListener, Input, Renderer2 } from '@angular/core';
@Directive({
  selector: '[appEnlarge]'
})
export class EnlargeDirective {


  constructor(private el: ElementRef, private renderer: Renderer2) { }


  @Input('appEnlarge') appEnlargeSize: string;


  @HostListener('click') onclick() {
    this.enlarge( this.appEnlargeSize || '100px');
  }


  @HostListener('dblclick') ondblclick() {
    this.enlarge('50px');
  }


  private enlarge(enlargeSize: string) {
    this.renderer.setStyle(this.el.nativeElement, 'font-size', enlargeSize);
  }
}

Let's go over this code and try to understand what we are doing here.  1st line has a couple of imports that we will understand as we go ahead. Next line has an annotation called @Directive which states that this class is a directive and its selector is appEnlarge. So you could use this directive as follows -

• <p appEnlarge>Directive applied for this content!</p>

We will see this in action in some time. Next, we have a constructor where we have access to the native element and the renderer. We can use APIs from renderer or Native element to actually make changes to the element.

Next, we have an input called appEnlargeSize. Here the user can specify how much the context needs to be enlarged. Notice how we have used an alias here in the bracket. This is so that we could specify input and directive in the same binding as below -

• <p [appEnlarge]="'120px'">Directive applied for this content!</p>

Then we are using HostListener APIs for single and double click to actually do our transformation - which is increasing the font size. You can see all HostListener APIs here -

• https://angular.io/api/core/HostListener

 Notice how in enlarge function we have used renderer API of setStyle to apply our desired style. You can see all renderer2 APIs here -

• https://angular.io/api/core/Renderer2

Now that your directive is done let's import it and declare it in our main module. Go to app.module.ts  and import it. Also, add it in the declaration section. Your app module should look like below -

import { BrowserModule } from '@angular/platform-browser';
import { NgModule } from '@angular/core';


import { AppRoutingModule } from './app-routing.module';
import { AppComponent } from './app.component';
import {EnlargeDirective} from './enlarge.directive'

@NgModule({
  declarations: [
    AppComponent,
    EnlargeDirective
  ],
  imports: [
    BrowserModule,
    AppRoutingModule
  ],
  providers: [],
  bootstrap: [AppComponent],
})
export class AppModule { }

And that's it. Save all your changes and start your angular app using -

• ng serve

Go to http://localhost:4200/ and see your changes.

Single click on the text to enlarge it and double click it to bring it to its original size.

This is not a great example with perfect CSS and animation but I hope this gives you an idea of how you can write custom directives in angular.  These are very powerful techniques to change the appearance of your components. Let me know if you have any questions. Thanks.


This is the last post of the year 2018 :). So wishing all a very happy new year! Hoping coming year would be more awesome with a lot of more learning and sharing!

Related Links

• https://angular.io/guide/attribute-directives
• Angular Hello World example(OSFG)
• Understanding angular application folder structure(OSFG)
• Routing and navigation in Angular(OSFG)
• Building nested components in Angular (OSFG)
• Passing data between the nested component in Angular(OSFG)
• How to customize build configuration with custom webpack config in Angular CLI 6(OSFG)
• How to write your own webpack plugin?(OSFG)
• How to dynamically create a component in Angular?(OSFG)