How to check Palindrome

Check if a string is palindrome or not is one of most common question we encountered during our basic days.

Let's Solve this problem with a Naive but efficient approach in this case.

Pseudocode :

1. i=0, j=n
2. while i < j:
3.    check if i'th element is not equal to j'th
4.      then return False 
5.   else i++,j--
6. loop end
7. return True

Array Aptitude

Divide array in two part such that sum of array left to partition index i  is equal to sum of array right to partition index i.

That is A[0]+A[1]...+A[i-1]=A[i+1]+....+A[n]

This is slightly tricky question but very easy to solve and code ,if you find the trick.

Algorithm:

• Find the cumulative sum at each index of array
• loop through array and check  A[i-1]==A[n]-A[i] , If condition Satisfy for any index i, means array can be partition in two group with this condition,So print "YES" else "NO"
• Use special case if array has only 1 element then print YES
• if array has only two element then print "NO"

Quick Select -Finding K'th Largest

Quick select is one of very popular algorithm used to find k'th largest element in a list. It can be use to find median or finding k'th smallest element etc.

Finding K'th largest element looks easy , we just need to sort & get K'th largest . But here we are dealing with time so we need fastest way to do this

 Time complexity of Quick Select (average case) =O(n)

 Quick Select is basically modified version of Quick sort. In Quick Sort we need to sort all element but Quick select just want to know pivot value that divide array in given ratio.

Quick sort 

let a example we have 10 different number in array  & we want to find 3rd largest element.(we  assume 0..9 index array) then in sorted array its position should be (10-3)th Index.

ANALYSIS OF SORTING ALGORITHMS

We know
(i)Bubble Sort,
(ii)Selection Sort,
(iii)Insertion Sort,
(iv)Quick Sort
Here are my observation of
The asymptotic behavior of each of the sorting algorithms for each of the data types
(i) Random data,
(ii) Reverse Ordered Data,
(iii) Almost Sorted Data
(iv) Highly Repetitive Data

I am Using Matlab for Simulation