candidate number 4 - Round 2 amazon placment august 2013

Amazon placement Round 2 August 2013

Student no 4 - Round 2

Q1. Count the number of inversions in the array, where an inversion is defined as for

i < j and a[i] > a[j]  ( i and j represent pointers to location of the array a[])

for eg.

if a[] = {5, 4, 6, 8, 1}

No. of inversion pairs are 5-  [(5,4) (5,1) (4,1) (6,1) (8,1)] Q2. Find the length of maximum palindromic subsequence in a given string.

for eg.

string  abbbbca

output 6 (abbbba)