## Insertion Sort

```
package random;

import java.util.Arrays;

public class InsertionSort {

public int[] insertionSort(int[] arr){
for(int i = 1; i < arr.length; i++){
for(int j = i; j > 0; j--){//pay attention to this inner for loop, it's decrementing j until it equals to zero
if(arr[j] < arr[j-1]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
return arr;
}

public static void main(String...strings){
int[] arr = new int[]{8, 3, 2, 4, 5, 9, 4, 1, 9, 9};
InsertionSort test = new InsertionSort();
System.out.println(Arrays.toString(test.insertionSort(arr)));
}
}

```

## QuickSort

QuickSort doesn’t require extra space, average time is O(nlgn).

Idea:

1. Pick a pivot and sort all elements in the array that are smaller than the pivot to the left of the chosen pivot, and all that are bigger than the pivot to the right of it
2. recursively sort two sublists
3. Note: the pivot could be chosen in multiple ways:
1. you can pick first element in the array
2. you can pick last element in the array
3. you can pick median element in the array
4. you can pick random element in the array
4. The pivot you pick could result in completely different sorting efficiency under extreme cases: http://stackoverflow.com/questions/2415193/worst-case-for-quicksort-when-can-it-occur

The following partition() method takes the last element as the pivot. In its partition() method: it sets the last element as the pivot, then it keeps an index i = low-1, then use another index j to loop through all elements from low to high-1, when we find any element nums[j] that is smaller than or equal to pivot (i.e. nums[high]), we increment i by 1 first, then we swap nums[j] with nums[i], notice, we swap nums[j] with nums[i], not with nums[high] or anything else, we swap nums[high] after we finish iterating through low to high-1, this is to do this: place all elements that are smaller than the pivot to the left of the pivot, after iterating through from low to high-1, we swap nums[i+1] with nums[high], this is to place nums[high] (i.e. current pivot) to the correct position, then we return i+1 as the pivot as all elements from low to i are sorted already.

I put my partition() function into this site and it’s accepted: http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

```
int[] quickSort_20160628(int[] nums){
quickSort_20160628(nums, 0, nums.length-1);
return nums;
}

void quickSort_20160628(int[] nums, int low, int high) {
if(low < high){
int pi = partition_20160628(nums, low, high);
quickSort_20160628(nums, low, pi-1);
quickSort_20160628(nums, pi+1, high);
}
}

int partition_20160628(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low-1;
for(int j = low; j <= high-1; j++){
if(nums[j] <= pivot){
i++;

int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

int temp = nums[i+1];
nums[i+1] = nums[high];
nums[high] = temp;
return i+1;
}

```

Then, just out of curiosity, I followed the same pattern, implemented the partition() function by picking the first element as the pivot, similar idea in the partition() function: similar to the partition() function in choosing last as pivot where it uses a for loop to find all elements that are smaller than pivot to place them to the left most possible, this partition_pivot_first_20160628I() function uses a for loop to find all elements that are bigger than the chosen pivot and places them to the right most possible.

Cool! I figured this partition method myself by completely understanding it first. Praise the Lord!

Also, don’t forget to put if(low < high){} at the main function!!! Otherwise, it won’t work!

It’s also accepted here: http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

```
int[] quickSort_pivot_first_20160628(int[] nums){
quickSort_pivot_first_20160628(nums, 0, nums.length-1);
return nums;
}

private void quickSort_pivot_first_20160628(int[] nums, int low, int high) {
if (low < high) {
int pi = partition_pivot_first_20160628(nums, low, high);
quickSort_pivot_first_20160628(nums, low, pi - 1);
quickSort_pivot_first_20160628(nums, pi + 1, high);
}
}

private int partition_pivot_first_20160628(int[] nums, int low, int high) {
int pivot = nums[low];
int i = high+1;
for(int j = high; j > low; j--){
if(nums[j] > pivot){
i--;

int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}

int temp = nums[low];
nums[low] = nums[i-1];
nums[i-1] = temp;

return i-1;
}

```

Implement quickSort() that takes median element as the pivot, it’s a bit different from the previous two, just in the way it’s written: it doesn’t use one more help function: partition(), instead, it uses just one function which does both recursion and partition. The fundamental idea behind the three is definitely the same: keep picking one element as pivot, keep placing all elements in the array that are smaller than the pivot to the left of the pivot and those that are bigger to the right.

```
int[] quickSort_pivot_median_20160628(int[] nums){
quickSort_pivot_median_20160628(nums, 0, nums.length-1);
return nums;
}

void quickSort_pivot_median_20160628(int[] nums, int low, int high) {
if(nums == null || nums.length == 0) return ;
if(low >= high) return;

int i = low, j = high, mid = (low+high)/2, pivot = nums[mid];

while(i <= j){
while(nums[i] < pivot) i++;
while(nums[j] > pivot) j--;
if(i <= j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}

if(low < j) quickSort_pivot_median_20160628(nums, low, j);
if(i < high) quickSort_pivot_median_20160628(nums, i, high);
}

```

## SOA – Service Oriented Architecture

https://en.wikipedia.org/wiki/Service-oriented_architecture

“A service-oriented architecture (SOA) is an architectural pattern in computer software design in which application components provide services to other components via a communications protocol, typically over a network. The principles of service-orientation are independent of any vendor, product or technology.

A service is a self-contained unit of functionality, such as retrieving an online bank statement.”

❑ Service Reusability
In SOA, an application is built by assembling small, self-contained, and loosely coupled pieces of functionality. Therefore, the services can be reused in multiple applications independent of their interactions with other services.

❑ Easy Maintainability
Since a service is an independent entity, it can be easily updated or maintained without having to worry about other services. Large, complex applications can thus be managed easily.

❑ Greater Reliability
SOA-based applications are more reliable since small, independent services are easier to test and debug as compared to massive chunks of code.

❑ Location Independence
The services are usually published to a directory where consumers can look them up. This approach allows a service to change its location at any time. However, the consumers are always able to locate their requested service through the directory look up.

❑ Improved Scalability and Availability
Multiple instances of a single service can run on different servers at the same time. This increases scalability and availability of the service.

❑ Improved Software Quality
Since services can be reused, there is no scope for redundant functionality. This helps reduce errors due to inconsistent data, and thereby improves the quality of code.

❑ Platform Independence
SOA facilitates the development of a complex product by integrating different products from different vendors independent of the platform and technology.

❑ Increased Productivity
Developers can reuse existing legacy applications and build additional functionality without having to develop the entire thing from scratch. This increases the developers’ productivity, and at the same time, substantially reduces the cost of developing an application.

Every time a service interacts with another service, complete validation of every input parameter takes place. This increases the response time and machine load, and thereby reduces the overall performance.

❑ Complex Service Management
The service needs to ensure that messages have been delivered in a timely manner. But as services keep exchanging messages to perform tasks, the number of these messages can go into millions even for a single application. This poses a big challenge to manage such a huge population of services.

❑ High Investment Cost
Implementation of SOA requires a large upfront investment by means of technology, development, and human resource.
SOA is not recommended for the following type of applications.

1. Homogenous: Implementing SOA for applications that use the technologies of a single vendor will not be cost-effective. For example, if an application is built in Java, then it would be better to use methods of Java rather than using HTTP for inter-component communications.
2. GUI-Based: SOA would not be suitable for applications with GUI functionality, e.g. a map manipulation application. Such applications require heavy data exchange, which in turn would increase the complexity of the application if SOA is used.
3. Real-time: SOA is not desirable to be used with strictly-enforced response times since the services communicate asynchronously.
4. Stand-alone: It would be futile to invest in SOA for stand-alone non-distributed applications, which do not require request and response-based calls.

The architecture for any software application needs to be selected wisely since it involves factors like investment cost and human effort. Once you are able to understand when and when not to apply the service-oriented architecture, you can make the best use of it in your software development process.

## Inner Join/Left Join/Right Join/Full Join

The INNER JOIN keyword selects all rows from both tables as long as there is a match between the columns in both tables.

The LEFT JOIN keyword returns ALL rows from the left table (table1), with the matching rows in the right table (table2). The result is NULL in the right side when there is no match.

The RIGHT JOIN keyword returns all rows from the right table (table2), with the matching rows in the left table (table1). The result is NULL in the left side when there is no match.

The FULL OUTER JOIN keyword returns all rows from the left table (table1) and from the right table (table2).

The FULL OUTER JOIN keyword combines the result of both LEFT and RIGHT joins.

The SQL UNION operator combines the result of two or more SELECT statements.
The UNION operator is used to combine the result-set of two or more SELECT statements.
Notice that each SELECT statement within the UNION must have the same number of columns.

SQL Aggregate Functions
SQL aggregate functions return a single value, calculated from values in a column.

Useful aggregate functions:

AVG() – Returns the average value
COUNT() – Returns the number of rows
FIRST() – Returns the first value
LAST() – Returns the last value
MAX() – Returns the largest value
MIN() – Returns the smallest value
SUM() – Returns the sum

## Dynamic Programming

As CtCI book points:”A good way to approach DP problem is often to implement it as a normal recursive solution, and then to add the caching part.”

Typical problems include:

Fibonacci sequence;

Climbing Stairs: https://leetcode.com/problems/climbing-stairs/

Robot Moving: https://fishercoder.com/2016/05/30/robot-moving/