Daily Archives: June 13, 2014

HeapSort

Posted on by

HeapSort
Heapsort is a O(nlgn) time comparison based sorting algorithm which can sort in-place (swap operations are done on the array itself) but is not stable (i.e. order of element is not maintained). I have discussed general theories behind the idea of building a generic heap data structure in a separate post.

This is a preview of HeapSort. Read the full post (405 words, estimated 1:37 mins reading time)

Print the 2D array in spiral order

Posted on by

Given a 2-dimensional array of integers, print the 2D array in spiral order.

For example:

A = [1,  2,  3,  4,
     5,  6,  7,  8,
     9,  10, 11, 12,
     13, 14, 15, 16]

Then spiral order output should be: [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10].

This is a preview of Print the 2D array in spiral order. Read the full post (441 words, estimated 1:46 mins reading time)

Pairs with a difference of k

Posted on by

Given n numbers , n is very large. Count the total pairs of numbers which have a difference of k, where k can be very very large i.e. k>n . The solution should have as low of a computational time complexity as possible.

This is a preview of Pairs with a difference of k. Read the full post (769 words, estimated 3:05 mins reading time)

linear time string matching using KMP matching algorithm

Posted on by

Given an input string S and a word w. Find the occurrences of the word w in the given string S in linear time. In other words, explain the linear time string matching using KMP matching algorithm.

For example, if S = “ABABAABA” and w = “ABA” then there are 3 occurrences of w in S at {0, 2, 5}.

This is a preview of linear time string matching using KMP matching algorithm. Read the full post (1652 words, 1 image, estimated 6:36 mins reading time)