Log in
updated 11:29 AM UTC, May 4, 2016

Write insertion sort algorithm and its implementation. Also explain its time complexity.


Insertion sort is a basic sorting algorithm which works the way people sort a hand of playing cards.
Start with an empty left hand and then remove one card at a time from the deck and insert it into the correct position in your left hand.

lets start with the Pseudo code for Insertion sort algorithm.
input to the algorithm is an array A[1,2,...n] of length n.
Insertion sort is an in-place algorithm , i.e the sorting takes place within the array.

for j = 2 to A.length
    key = A[j]
    i = j - 1
    while (i > 0 and A[i] > key)
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key       



Now , lets see the implementation in Java:

package com.example;

public class Arrays {

	public static int[] insertionSort(int[] array) {
		int key = 0;
		int i = 0;
		for (int j = 1; j < array.length; j++) {
			key = array[j];
			i = j - 1;

			while (i >= 0 && array[i] > key) {
				array[i + 1] = array[i];
				i = i - 1;
			}

			array[i + 1] = key;
		}

		return array;

	}

	public static void main(String[] args) {
		int array[] = { 5, 3, 2, 1, 8, 9, 10 };

		System.out.println("before sorting array = ");
		
		for (int e : array) {
			System.out.print(" " + e);
		}

		System.out.println("\nAfter sorting array = ");

		array = insertionSort(array);

		for (int e : array) {
			System.out.print(" " + e);
		}

	}
}

Output:

before sorting array =
 5 3 2 1 8 9 10
After sorting array =
 1 2 3 5 8 9 10

 

Now, lets look into three cases , best , worst and average case:


Time complexity when array is already sorted (best case) is O(n) because second loop will never run

Worst case time complexity when array is completely unsorted is O(n*n).

Average case is also represented as O(n*n)

 

Similarly , Candidates can also be asked about bubble sort, Selection sort and asked to explain time complexity in best/worst/average case. Be prepared for such kind of questions.

Gud luck.

Add a comment (1)

Check if String has all unique chars.

 

Here is a commonly asked Interview question.

"Implement an algorithm to check if string has all unique chars. Please dont use any extra datastructures other than arrays."

here is a program which does exactly that and which is self explanatory:

package com.example;

public class StringUtilities {

	public static boolean isStringUniqueChars(String word) {

		boolean ret = true;
		int hashArray[] = new int[256];

		for (char e : word.toCharArray()) {

			if (hashArray[e] != 0) {
				ret = false;
				break;
			}
			hashArray[e] += 1;
		}

		return ret;
	}

	public static void main(String[] args) {
		String test = "abcdefghijklmnopqrstuvwxyz";
		System.out.println("Is string \"" + test
				+ "\" a unique chars string = "
				+ (isStringUniqueChars(test) ? "Yes" : "No"));

	}

}

Output:

Is string "abcdefghijklmnopqrstuvwxyz." a unique chars string = Yes

Add a comment (1)

How to convert Integer to Hexadecimal/Octal/Binary in Java

How to convert Integer to Hexadecimal/Octal/Binary in Java.

This is one of the frequently asked Interview questions (converting from One number system to another) even though there are many API's to do it easily , Its quite important to know the logic of converting from One form to another. This also tests the candidates ability to form algorithms to solve logical problems.

Here is a program which converts the Integer to Hexadecimal.

This uses logic to convert rather than using the Java provided API's like Integer.toHexString().

Add a comment (3)

Delete an Item in a Singly linked List

You will be given a reference/pointer to an item in a singly linked list and not its predeccessor, you have to delete that.
This seems tricky if you just concentrate on the item pointer. you have to think in a different way.



Solution:


Concentrate on the content than just on pointer.
Copy the contents of the item.next to item and delete the item.next.


Piece of code (Java based/ try yourself adding it in C)
------------------------
Item.content = item.next.content;
deleteItem = item.next;
item.next = item.next.next;
delete(deleteItem);

Add a comment (1)

delete mth item from the end of singly linked list

Given a singly linked list of size N , how do u delete an element which is M th from the end?

This is a favorite question of the interviewers , try to explain your solution on a sheet of paper and then write a piece of code for the same.

Solution:

Keep two variable's , say var1 and var2.

let the var1 run for m times into the list. then start the var2 from the beginning ,now run var1 and var2 simultaneously in a loop till the var1 becomes null (end of list).

Add a comment (1)

Follow Us on Twitter
Find Us on Facebook
Follow Us on Google
Follow Us on Pinterest