### How to nail your Coding Interview

Here are some tips while giving your coding interviews. 1. Never try to jump to…

May 11, 2019

Its a kind of incremental insertion technique, where the algorithm build up sorting by first sorting n-1 items.

Or, we can say that we pick an element on n-1 items, and insert in a position where all items on the left side are less than or equal to this number.

The algorithm works in two loops, where outer most loop iterate over complete array. To be more precise, We iterate from index-1 to end of array. Leaving index-0 to be used by inner loop.

In inner loop, the loop variable takes the index from outer loop index variable. It takes a backup of the value present on that index, and go backward toward 0-index. It shift previous elements to next position unless they are greater than the value for which we have taken backup.

In short, inner loop tries to sort the n-1 part of array by shifting any bigger element to right. And, **insert** the element to the final position.

See the code here:

```
public void sort(int[] arr) {
int len = arr.length;
for (int i=1; i<len; i++) {
int key = arr[i];
int j = i-1;
while (j >= 0 && key < arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
```

- It does not use extra memory. And, is in-place algorithm.
- Its stable, as it does not change order of same value elements.
- It is more efficient in practice than Bubble Sort and Selection Sort
- It is well suited for small data sets.

The algorithm runs on O(n^2) in worst case.

Here are some tips while giving your coding interviews. 1. Never try to jump to…

Big-O notation In simpler terms, its kind of a unit to measure how efficient an…

Problem Statement You are given two non-empty linked lists representing two non…

Problem Statement Given a linked list, remove the n-th node from the end of list…

Problem Statement Write a function to find the longest common prefix string…

Problem Statement Given an array nums of n integers, are there elements a, b, c…

Introduction In this post we will see following: How to schedule a job on cron…

Introduction There are some cases, where I need another git repository while…

Introduction In this post, we will see how to fetch multiple credentials and…

Introduction I have an automation script, that I want to run on different…

Introduction I had to write a CICD system for one of our project. I had to…

Introduction Java log4j has many ways to initialize and append the desired…