Chapter 1 , Core Java by Cay Horstmann

An Introduction To Java

Java is not just a programming language, but an entire platform of libraries, execution environment - security, portability, automatic garbage collection.

Brief history:

1991 : Java founders at Sun Microsystems want to create a language suitable for consumer devices(cable) - so it has to be small and also platform neutral.

1994 : Mosaic browser - need for a language like java. Sun creates HotJava browser to show off java and the craze begins.

1996: Java 1.0 - no print

1997: 1.1 - refelection, GUI event model, inner classes

1998: 1.2 - SE, ME(embedded devices), EE

2000-2002: 1.3-1.4 - libraries, performance

2004: 1.5-> 5 - for each, loops, autoboxing, annotations, enums, static import

2006: 6 - libraries, performance

2009: Oracle buys Sun

2011: 7 - switch string, diamond op

2014: 8 - functional style prog, lambda expressions, streams, interfaces with default methods

2017: 9 - modules

2018: 11- var

2021: 17-records

Buzz words:

Simple : cleaned up C++, small(embedded devices)

Object oriented : data=objects, interfaces to objects

Distributed: access objects across net(HTTP/FTP)

Robust: compile time and run time checks, memory cant be overwritten and corrupted

Secure: secure over a network

Architecture neutral : code compiled to bytecode that can run anywhere

Portable: No implementation dependency, datatypes size doesnt vary as in C++

Interpreted : executes bytecode - fast

High performance: frequently executed bytecode to machine code - hotspots - Just In Time Compiler

Multithreaded: fast and real time

Dynamic: changing libraries without impacting dependent code, adding code to running programs

~

Comparable and Comparator

Java supports sorting on collection in two ways - through Comparable and Comparator(both are functional interfaces with one single abstract method).

Comparable:

To sort collection based on Comparable:

• Elements of the collection must implement Comparable interface and implement it's method "int compareTo(Object o1)".
• Then sorting can be done using Collections.sort(List)

Cons:

• Can't support multiple types of sorting, as one compareTo method can have only one implementation.
• May not have access to the element class, in which case, subclassing the element and implementing compareTo would be the only option.

Code:

public class Dog implements Comparable<Dog>{

      String name;

      String breed;

      public Dog(String name,String breed){

            this.name = name;

            this.breed = breed;

      }

        @Override

public int compareTo(Dog o) {

return name.compareTo(o.name);

}

}

...

List<Dog> dogList = new ArrayList<Dog>();

Collections.sort(dogList);

...

Comparator:

To sort collection based on Comparator:

• A class/anonymous class implements Comparator interface and implements it's method "int compare(Object o1, Object o2). 
• Then sorting can be done by passing the object of the above implmented Comparator - using Collection.sort(List, Comparator).

Pros:

• Can support multiple sorting implementations.
• Don't need to have access to elements of the collection.

Code:

public class DogBreedComparator implements Comparator<Dog> {

@Override

public int compare(Dog o1, Dog o2) {

return o1.breed.compareTo(o2.breed);

}

}

..

Collections.sort(dogList, new DogBreedComparator());

..

Lambda expression:

Collections.sort(dogList, (o1,o2)->o1.breed.compareTo(o2.breed));

..

Both compareTo and compare methods return integer - 

1  : if passed in object is greater than current object

-1: if passed in object is lesser than current object

0: if both are equal

~

Array Rotation - Three Solutions

Array rotation by k places can be done by using extra space of k sized array, by shifting array by one position in loop of k, by shifting array by gcd(array.length, k) in gcd number of sets. Following program has all the implementations:

	package arrays;
	public class ArrayRotation {
	public static void rotateByOne(int[] a) {
	int n = a.length, tmp=a[0];
	for(int i=0;i<n-1;i++) {
	a[i]=a[i+1];
	}
	a[n-1]=tmp;
	print(a);
	}
	public static void rotateByX(int[] a, int init, int x) {
	int n = a.length, tmp=a[init];
	int d =n-x+init;
	for(int i=init;i<d;i=i+x) {
	a[i]=a[i+x];
	}
	a[d]=tmp;
	print(a);
	}
	public static void rotateNoExtraSpace(int[] a,int k) {
	for(int i=0;i<k;i++) {
	rotateByOne(a);
	}
	}
	public static int gcd2(int a,int b) {
	if(a==0)
	return b;
	return gcd2(b%a,a);
	}
	public static void rotateJuggle(int[] a,int k) {
	int n = a.length;
	int g = gcd2(n,k);
	for(int i=0;i<g;i++) {
	rotateByX(a,i,g);
	}
	}
	public static void rotateExtraSpace(int[] a,int k) {
	int n = a.length;
	print(a);
	int[] tmp = new int[k];
	for(int i=0;i<k;i++) {
	tmp[i]=a[i];
	}
	for(int i=0;i<n-k;i++) {
	a[i]=a[i+k];
	}
	int j=0;
	for(int i=n-k;i<n;i++) {
	a[i]=tmp[j++];
	}
	print(a);
	}
	public static void print(int[] a) {
	System.out.println();
	for(int i:a)
	System.out.print("---"+i);
	}
	public static void main(String[] args) {
	int[] a1= {1,2,3,4,5};
	rotateExtraSpace(a1,2);//3,4,5,1,2
	rotateNoExtraSpace(a1,2);
	int[] a2={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
	rotateJuggle(a2,3);
	}
	}

view raw ArrayRotation.java hosted with ❤ by GitHub

Top K Frequent Elements - Hashing Problem

Problem : Get top K frequent elements.

Implementation:

	package hashTables.problems;
	import java.util.ArrayList;
	import java.util.LinkedHashMap;
	import java.util.Map;
	public class TopKFrequentEles {
	static ArrayList<Integer> TopK(int[] arr, int k) {
	//int[] arr = array.stream().mapToInt(i->i).toArray();
	int l1 = arr.length;
	Map<Integer, Integer> countMap = new LinkedHashMap<>();
	for (int i = 0; i < l1; i++) {
	if (countMap.containsKey(arr[i])) {
	countMap.put(arr[i], countMap.get(arr[i]) + 1);
	} else {
	countMap.put(arr[i], 1);
	}
	}
	ArrayList<Integer> result = new ArrayList<Integer>();
	countMap.entrySet().stream().sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed().thenComparing(Map.Entry.<Integer, Integer>comparingByKey().reversed())).forEach(e -> {
	int key = e.getKey();
	int val = e.getValue();
	for (int i = 0; i < val; i++) {
	if(!result.contains(key) && result.size()<k)
	result.add(key);
	else
	break;
	}
	});
	return result;
	}
	public static void main(String[] args) {
	int arr2[]= {8,1,1,2,2,3,3,3,4};
	ArrayList<Integer> result = TopK(arr2,2);
	for(int i: result) {
	System.out.println(i);
	}
	}
	}

view raw TopKFrequentEles.java hosted with ❤ by GitHub

Sort By Frequency - Hashing Problem

Problem : Sort elements by their frequency.

Following is the implementation where we store the frequency in hashmap:

	package hashTables.problems;
	import java.util.ArrayList;
	import java.util.LinkedHashMap;
	import java.util.Map;
	public class SortByFrequency {
	public static ArrayList<Integer> sortByFrequency(int arr[]) {
	int l1 = arr.length;
	Map<Integer, Integer> countMap = new LinkedHashMap<>();
	for (int i = 0; i < l1; i++) {
	if (countMap.containsKey(arr[i])) {
	countMap.put(arr[i], countMap.get(arr[i]) + 1);
	} else {
	countMap.put(arr[i], 1);
	}
	}
	ArrayList<Integer> result = new ArrayList<Integer>();
	countMap.entrySet().stream().sorted(Map.Entry.<Integer, Integer>comparingByValue().reversed().thenComparing(Map.Entry.<Integer, Integer>comparingByKey())).forEach(e -> {
	int key = e.getKey();
	int val = e.getValue();
	for (int i = 0; i < val; i++) {
	result.add(key);
	}
	});
	return result;
	}
	public static void main(String[] args) {
	int arr1[]= {6,6,2,3,1,4,1,5,6,2,8,7,4,2,1,3,4,5,9,6};
	ArrayList<Integer> result = sortByFrequency(arr1);
	for(int i: result) {
	System.out.println(i);
	}
	}
	}

view raw SortByFrequency.java hosted with ❤ by GitHub

Count Distinct Elements In Every Window - Hashing Problem

Problem: Count distinct elements in every window of given K size.

Following is the implementation, which rotates the array window:

	package hashTables.problems;
	import java.util.ArrayList;
	import java.util.HashMap;
	public class CountDistinctElements {
	public static ArrayList<Integer> countDistinct(int arr[], int k) {
	int n = arr.length;
	HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	for (int i = 0; i < k; i++)
	hM.put(arr[i], hM.getOrDefault(arr[i], 0) + 1);
	list.add(hM.size());
	for (int i = k; i < n; i++) {
	if (hM.get(arr[i - k]) == 1) {
	hM.remove(arr[i - k]);
	}else
	hM.put(arr[i - k], hM.get(arr[i - k]) - 1);
	hM.put(arr[i], hM.getOrDefault(arr[i], 0) + 1);
	list.add(hM.size());
	}
	return list;
	}
	public static void main(String[] args) {
	int arr[] = {1,2,1,3,4,2,3};
	int k = 4;
	ArrayList<Integer> list = countDistinct(arr,k);
	for(int i : list) {
	System.out.println(i);
	}
	}
	}

view raw CountDistinctElements.java hosted with ❤ by GitHub

Print Non-repeated Elements - Hashing Problems

Problem : Print the non-repeated elements of an array.

Following is the implementation:

	package hashTables.problems;
	import java.util.ArrayList;
	import java.util.HashMap;
	public class PrintNonRepeated {
	static ArrayList<Integer> printNonRepeated(int arr[]){
	int n = arr.length;
	HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	for(int i=0;i<n;i++) {
	int val = arr[i];
	if(!hM.containsKey(val)) {
	hM.put(val,i);
	list.add(val);
	}else {
	list.remove((Integer)val);
	}
	}
	return list;
	}
	public static void main(String[] args) {
	int arr[]= {1,1,2,2,3,3,4,5,6,7};
	ArrayList<Integer> list = printNonRepeated(arr);
	for(int i:list) {
	System.out.println(i);
	}
	}
	}

view raw PrintNonRepeated.java hosted with ❤ by GitHub