Editorial Fitness Freak Coyote

Problem Link

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/fitness-freak-mr-coyote

In this question there are two types of query.

  1. Add number in your data structure
  2. Return number whose rank is floor of n/3

And both query come at any instance of time.

So we can use Balanced Binary Search Tree. But that take O(log n) time complexity in both query.

The better approach is use two heaps.

Create a min heap of size n/3 and create max heap of size 2n/3

So for the second query we give minimum element from the min heap whose rank is floor of n/3

which takes time O(1).

For the first query there can be four cases occur.

-If size of min heap is less than floor of n/3 this is due to increase in n.

in this case we will add that number in the min heap and than compare min of min heap and max of max heap

If max of max heap is greater than min of min heap than we will swap this two elements.

-If size of min heap is equal to floor of n/3

In this case just add it in the max heap.

So the time complexity of this is  O(log n)

Java implementation code

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/fitness-freak-mr-coyote/submissions/code/3618642

Shell Sort

Shell sort is improvement of insertion sort.

Shell sort start comparing elements far apart,then element less apart and finally adjacent to each other.By this stage the elements are sufficiently sorted than the running time is much closer to O(n) than O(n*n).

First it sorts elements which are t distance far away from each other and eventually this distance is decreases and than it becomes one.

example

Array :

9 4 1 2 5 6 8 16 7 3 12 14 15 18 19 10 11 13 17 20

if gap is 4 than

9 4 1 2
5 6 8 16
7 3 12 14
15 18 19 10
11 13 17 20

After sorting elements which are 4 elements away from each other

5 3 1 2
7 4 8 10
9 6 12 14
11 13 17 16
15 18 19 20

and than decreases the distance and make them sorted.

Java implemetation of code

https://ideone.com/v7hJbR

Other resources of the Shell Sort

http://en.wikipedia.org/wiki/Shellsort

http://www.sorting-algorithms.com/shell-sort

KMP string matching algorithm

Problem

Two strings is given to us

  • Text(from where we have to find pattern)
  • pattern

And we have to find from which index we have same pattern in the text.

The simple solution for this is just run two for loops which has time complexity of  O(m*(m-n+1)) where m is the size of pattern string and n is the size of text string

But KMP can do this in O(n+m) where O(m) for preprocessing and O(n) for searching in the text String

KMP algorithm want axillary array of size m for preprocessing of pattern string this will store matches with the pattern so that you should not always start matching from the starting you can do matching from any index depending upon situation the example is given below

For the pattern “AABAACAABAA”, array[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

here we know that if we got mismatch at index 2 than we should start searching from 1st index not from 0 because there are two A are matched in Text string so one A will definitely match.

When we compare pattern[j] with text[i] and see a mismatch, we know that characters pattern[0..j-1] match with text[i-j+1…i-1] so now we will check array[j-1] and we will start matching from pattern[array[j-1]] and text[i] because of the preprocessing so this algorithm will works in O(n)

Java implementation of this algorithm

https://ideone.com/hcT47E

Interpolation Search

Interpolation Search works better than binary search for uniformly distributed and sorted array

binary search always see in the middle of the array but interpolation search calculates a position where the value should be placed according to the distribution of values in the given array so it found the middle index by

mid = low + ((toFind – sortedArray[low]) * (high – low)) / (sortedArray[high] – sortedArray[low]);

Interpolation search on average makes log(log(n)) comparison but its worst case is O(n)

java implementation of the above algorithm

https://ideone.com/4pxceg

Exists Or Not Editorial

Link of question is given below.

https://www.hackerrank.com/contests/codestar-long-programming-contest/challenges/exists-or-not

We will use ASCII number of all the characters so we can make array and store the number of occurrence of each character for particular string.

We will compare two string by comparing occurrence of the same elements which stored in array  because the ordering of the string is not important in this question.

In this problem we have to do two step process.

1)We should take sub string of the given string whose length is same as the second string.

2) We should check whether first string have any letter which is not in the second string because if first string have any letter which is not present in second string than it can’t be a favorable sub string.

Implementation of program

https://ideone.com/f6ZBjg