Some Points about Abstract and Interfaces.

Abstract Classes:

1). A class defined as abstract cannot be instantiated. Meaning, you cannot call just/only new AbstractClass().You need to override all the methods that are marked as abstract as well.(See AbstractMain)

2). Abstract keyword is non access modifier.

3). When a method is marked as abstract, there should not be any implementation for the method.

4). Abstract methods have to be overridden in the sub classes.

5). Abstract classes NEED NOT have abstract methods. Those methods which do not have abstract defined, should be implemented. Meaning there should be a implementation code for this method right in this abstract class method body.

6). If there is at–least one abstract method defined in the whole class, then that class should be declared as abstract.

7). Classes and Methods marked as private cannot be abstract

8). Classes and Methods marked as static cannot be abstract.

9). Classes and Methods marked as final cannot be abstract.

10). Abstract classes can have default and as well as overloaded constructors. When no constructor is defined – a default constructor will be generated by compiler.

11). Constructors of abstract classes are invoked when a subclass object is created. You can call the superclass constructor by calling super().

12). Abstract classes hides the functionality of those methods that are defined as abstract. The actual functionality of the abstract methods are exposed by the implementation classes.

13). Abstract Method Overloading signatures are supported in abstract classes.

14). By making this class as abstract and implementing the methods as well, will not give any compile time error., but gives a run time error after Instantiating the AbstractSubClass.

15).  @Override – Not necessary to provide this annotation, because, Compiler by default takes care of overriding, when it see’s extends keyword.

Interfaces:

1). Interfaces does not have any method implementation.

2). All methods in an interface are public and/or abstract.

3). Any field that is declared, is public and static.

4). There is no multiple inheritance in Java. Which means, any Java class cannot extend more than one class at a time. Instead there is a Multiple Interface Inheritance. Which means, any Java can implement/extends more than one interface.

5). Any Java class that implements any interface, will be having a IS–A relationship, between the Java Class and the interface.

6). If a method deceleration in a interface is abstract, the whole interface need not be declared as abstract, this is unlike abstract classes.

7). Java does not support multiple inheritance, because of the Diamond of Death Problem.

8). Method Overriding is allowed in Interfaces. Each method signature in an interface is unique. Meaning, you can have multiple methods of same name with different arguments.

9). Multiple Interface Inheritance example can extend any number of interfaces.

Ex: public interface MultipleInterfaceImplementation extends InterfaceExample,AnotherInterface

* here InterfaceExample and AnotherInterface are both interfaces.

Source code: https://github.com/chouhan/CoreJavaBasics

Custom Module Loader in Flex

I know it’s too late to post this now, but I just found something which I created in October 2011, when I started cleaning up my hard disk.

package 
{

   import flash.display.DisplayObject;
   import flash.system.ApplicationDomain;
   import flash.utils.ByteArray;
   import flash.utils.Dictionary;
   import mx.controls.Alert;
   import mx.controls.ProgressBar;
   import mx.events.FlexEvent;
   import mx.events.ModuleEvent;
   import mx.modules.IModuleInfo;
   import mx.modules.Module;
   import mx.modules.ModuleLoader;
   import mx.modules.ModuleManager;
   import mx.utils.UIDUtil;

   public class CustomModuleLoader extends ModuleLoader{

        private var ichild:IModuleCommunication;
	private var loadRequested:Boolean = false;
	private var map:Dictionary = new Dictionary();
	private var module:IModuleInfo;
	private var progressBar:ProgressBar = null;
        private var _url:String = null;
        private var _dashBoardChildName:String;

	public function CustomModuleLoader(){
	    super();
	}
	
	public function get dashBoardChildName():String{
	    return _dashBoardChildName;
	}

        public function set dashBoardChildName(value:String):void{
	    _dashBoardChildName = value;
	}
	
	override public function get url():String{
	    return _url;
	}

        override public function set url(value:String):void{
	  if (value == _url){
	     return;
	   }
          if (module){
             unloadModule();
	     return;
	   }
          if (value == null || value == ""){
	     unloadModule();
	     return;
	   }
	_url = value;
	dispatchEvent(new FlexEvent(FlexEvent.URL_CHANGED));
	removeAllChildren();

	if (_url != null && _url != "" && loadRequested){
	   if (!map[_url]){
	      loadModule();
	    }
	    else{
	      child = map[_url];
	      addChild(child);
	     }
	   }
	}

        override public function createComponentsFromDescriptors(recurse:Boolean = true):void{
	   super.createComponentsFromDescriptors(recurse);
	   loadRequested = true;
	}

	override protected function measure():void{
	   super.measure();
	   trace("CustomModuleLoader Width--------------------------------------------- " + this.width);
	   trace("CustomModuleLoader Height--------------------------------------------- " + this.height);
	   this.percentWidth = 100;
	   this.percentHeight = 100;

	   if (progressBar){
	     progressBar.top = 200;
	     progressBar.left = 100;
	     progressBar.x = 200;
	     progressBar.y = 100;
	     progressBar.verticalCenter = 0;
	     trace("progressBar Width--------------------------------------------- " + progressBar.width);
	     trace("progressBar Height--------------------------------------------- " + progressBar.height);
	     trace("progressBar X--------------------------------------------- " + progressBar.x);
	     trace("progressBar Y--------------------------------------------- " + progressBar.y);
             trace("progressBar verticalCenter--------------------------------------------- " +  progressBar.verticalCenter);
             trace("progressBar horizontalCenter--------------------------------------------- " + progressBar.horizontalCenter);
	     trace("progressBar top--------------------------------------------- " + progressBar.top);
 	     trace("progressBar left--------------------------------------------- " + progressBar.left);
	   }
	}

	override public function loadModule(url:String = null, bytes:ByteArray = null):void{
	   if (url != null){
	      _url = url;
	     }
           if (_url == null){
	      return;
	    }
           if (map[_url]){
	      //trace("loadModule() - already created the child");
	      return;
	    }

	   if (module){
	      //trace("loadModule() - load already initiated");
	      return;
	    }
	   showProgressBar();
	   dispatchEvent(new FlexEvent(FlexEvent.LOADING));
	   module = mx.modules.ModuleManager.getModule(_url + '?cacheClear=' + UIDUtil.createUID());
	   module.addEventListener(ModuleEvent.PROGRESS, moduleProgressHandler);
	   module.addEventListener(ModuleEvent.SETUP, moduleSetupHandler);
	   module.addEventListener(ModuleEvent.READY, moduleReadyHandler);
	   module.addEventListener(ModuleEvent.ERROR, moduleErrorHandler);
	   module.addEventListener(ModuleEvent.UNLOAD, moduleUnloadHandler);
	   module.load(ApplicationDomain.currentDomain, null, bytes);
	}

        override public function unloadModule():void{
	  if (map[_url]){
	     delete map[_url];
 	  }
          if (child && contains(child)){
	     ichild.handleDispose();
	     removeChild(child);
	     child = null;
	     ichild = null;
	     _url = null;
	   }
          if (module){
	     module.removeEventListener(ModuleEvent.PROGRESS, moduleProgressHandler);
	     module.removeEventListener(ModuleEvent.SETUP, moduleSetupHandler);
	     module.removeEventListener(ModuleEvent.READY, moduleReadyHandler);
	     module.removeEventListener(ModuleEvent.ERROR, moduleErrorHandler);
	     module.removeEventListener(ModuleEvent.UNLOAD, moduleUnloadHandler);
	     module.release();
	     module.unload();
	     module = null;
	  }
	     applicationDomain = null;
	     removeProgressBar();
	 }

	private function moduleErrorHandler(event:ModuleEvent):void{
	    removeProgressBar();
	    dispatchEvent(event);
	}

	private function moduleProgressHandler(event:ModuleEvent):void{
	    dispatchEvent(event);
	}

	private function moduleReadyHandler(event:ModuleEvent):DisplayObject{
	    removeProgressBar();
            child = module.factory.create() as DisplayObject;
            ichild = child as IModuleCommunication;
            ichild.setModuleParent(this.parentApplication);

	    if (url == "DashboardModule.swf"){
	      ichild.setDashboardChild(dashBoardChildName);
	    }
 	   dispatchEvent(event);
           if (child){
		addChild(child);
		map[url] = child;
	    }
	   return child;
	}

	private function moduleSetupHandler(event:ModuleEvent):void{
	    dispatchEvent(event);
	}

	private function moduleUnloadHandler(event:ModuleEvent):void{
	    removeProgressBar();
	    dispatchEvent(event);
	}

	private function removeProgressBar():void{
	    if (progressBar)
	    {
		removeChild(progressBar);
	        progressBar = null;
	    }
	}

	private function showProgressBar():void{
	 if (!progressBar)
	  {
	    progressBar = new ProgressBar();
	    progressBar.labelPlacement = "top";
	    progressBar.source = module;
	    progressBar.verticalCenter = 0;
	    progressBar.indeterminate = true;
	    addChild(progressBar);
	}
     }
  }
}

Big O, Omega and Theta Notations.

Big O, Omega and Theta Notations are used to describe not only the way an algorithm performs but the way an algorithm scales to produce a output. It measures the efficiency of an algorithm with respect to time it takes for an algorithm to run as a function of a given input. They are used to determine the Worst case complexity, Best case complexity and the Average case complexity.

Big Omega notation describes the best case of a running algorithm. In contrast, Big O notation describes the worst case of a running algorithm.

Big O Notation is denoted as O(n)  also termed as Order of n, or also termed as O of n.

Big Omega Notation is denoted as Ω(n) also termed as Omega of n.

Apart from Big O (O) and Big Omega (Ω), there are Big Theta (Θ), Small O (o) and Small Omega (ω) notations that are used in computer science programming. You can get more information from http://en.wikipedia.org/wiki/Big_O_notation#Big_Omega_notation.

O(1) – Constant Time

This means that the algorithm requires the same fixed number of steps regardless of the size of the task.

Examples:

1). Finding an element in a HashMap is usually a constant time, which is O(1). This is a constant time because, a hashing function is used to find an element, and computing a hash value does not depend on the number of elements in the HashMap.

2). Push and Pop operations for a stack containing n elements.

3). Insert and Remove the operations of a queue.

O(log n) – Logarithmic Time

This means that the algorithm requires the Logarithmic amount of time to perform the task.

Examples:

1). Binary search in a sorted list or Array list of n elements.

2). Insert and Find operations for a binary search tree with n nodes.

3). Insert and Remove operations for a heap with n nodes.

4). Fast insertion, removal and lookup time of a TreeMap (a.k.a balanced tree because a TreeMap maintains key/value objects in a sorted order by using a red black tree) is O(log n)

O(n) – Linear Time

This means that the algorithm requires a number of steps directly proportional to the size of the task.

Examples:

1). Traversal or searching of a list(a linked list or a array) with n elements. This is linear because you will have to search the entire list. This means that if a list is twice as big, searching will take twice as long.

2). Finding the maximum or minimum element in a list, or sequential search in an unsorted list of n elements.

3). Traversal of a tree with n nodes.

4). Calculating iteratively n-factorial, for example finding iteratively the nth Fibonacci number.

O(n log n) – N times Logarithmic time

This means that the algorithm requires N times the Logarithmic time of solving a algorithm.

Examples:

1).  Advanced Sorting Algorithms like quick sort and merge sort.

O(n²) – Quadratic Time

Examples:

1). Simple sorting algorithms, for example a selection sort of n elements.

2). Comparing 2 two dimensional arrays of size n by n.

3). Finding duplicates in an unsorted list of n elements.

Note: If a solution to a problem has one single iteration, in other words, if the solution is achieved by either only one for loop or one while loop or one do-while loop or a single recursive function, then that algorithm is said to perform with O(n) else if the solution is achieved by 2 nested loops, then the algorithm is said to perform with O(n²) and if it is achieved by 3 nested loops, then the algorithm is said to perform with O(n³) and so on..

O(n³) – Polynomial Time

Examples:

1). Given a expression 23n³ + 12n² + 9, and n = large numbers, the execution time for n³ increases drastically which takes O(n³) to perform the operation.

O(aⁿ) for a > 1 – Exponential Time

Examples:

1). Recursive Fibonacci implementation

2). Problem to solve Towers of Hanoi

3). Generating all permutations of n symbols.

Here is the order of execution time, in which the way Big O notations worst case behavior is determined.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) <O(aⁿ)

Constant Time < Logarithmic Time < Linear Time < N times of Logarithmic Time < Quadratic Time < Polynomial Time < Exponential Time.

If algorithm is __ then its performance is __

algorithm	performance
o(n)	< n
O(n)	≤ n
Θ(n)	= n
Ω(n)	≥ n
ω(n)	> n

4 important Big O rules:

1). If you have 2 different steps in your algorithm, add up those steps

Example:

function something() {
    doStep1();	// O(a)
    doStep2();	// O(b)
}

Overall runtime: O(a+b)

2). Drop Constants

function minMax1(array) {
	min, max = null
	for each e in array
		min = MIN(e, min)	//O(n)
	for each e in array
		max = MAX(e, max)	//O(n)
}

Another example:

function minMax2(array){
	min, max = null
	for each e in array
		min = MIN(e, min)
		max = MAX(e, max)	
}

Overall runtime: O(2n)
So dropping the constants overall runtime equals to O(n)

3). Different Arrays is equivalent to (=>) Different Variables.

function getSize(arrayA, arrayB){
	int count = 0;
	for a in arrayA{
		for b in arrayB{
			if(a == b){
				count = count++;
			}
		}
	}
	return count;
}

Overall runtime is NOT O(n^2), but instead it is O(a * b)

Note that, the loops are emulated on 2 different array’s.

4). Drop non dominant terms.

function printSize(array){
	max = null;
	
	// runtime for the below loop is O(n)
	for each a in array{
		max = MAX(a, max);
	}
	
	//runtime for the below nested loop is O(n^2)
	for a in array{
		for b in array{
			print a, b;
		}
	}
}

Overall runtime: O(n + n^2)

However, since O(n) is too small and can be neglected.
In other words,

O(n^2) <= O(n + n^2) <= O(n^2 + n^2)
O(n^2) <= O(n + n^2) <= O(2 * n^2)

Now, dropping the constants based on Rule 2,

O(n^2) <= O(n + n^2) <= O(n^2)

if left and right are equivalent, then center is too..

i.e O(n + n^2) is equivalent to O(n^2)

Hence, overall runtime is O(n^2)

---

Sources:

Click to access BIG-O.pdf

http://bigocheatsheet.com/

This post was more or less taken from the afore mentioned sites, with little or more changes based on my knowledge and observation. I will be adding more examples to one or more above mentioned time analysis Big O notations as and when I come across in the near future of programming career.

Multiplication Table..

package solutions.java;

/**
 * Created by rchouhan on 11/1/14.
 *
 * For Zero iterations
 * O(N) < Olog(N)
 *
 * replace N with 0; and log(0) = 1
 *
 * For N > 0
 *
 * O(N) < Olog(N) < O(Nlog(N)) < O(N + N) (also O(2N)) (or also O(N^2)) < O(N^N)
 */


public class MultiplicationTable {

    public static void main(String[] args){
        multiplicationTable(3);
        multiplicationTableUntil(3);
    }

    // Time Complexity is O(N)
    static void multiplicationTable(int i){

        for(int j=0; j<=10; j++){
            System.out.println(i +" X " + j +" = " + i*j);
        }
    }

    // Time Complexity is O(N^2)
    static void multiplicationTableUntil(int input){
        for(int i=1; i<= input; i++){
            System.out.println("\nMultiplication Table for " + i + "\n");
            for(int j=0; j<=10; j++){
                System.out.println(i +" X " + j +" = " + i*j);
            }
         }
    }
}