Next largest palindrome

Q: A number is given as a palindrome, write a function to return the next largest palindrome.

Algorithm:

Case I: The given number is a palindrome..ex: 1234321 then simply increment the centre digit by 1 i.e the answer is 1235321

Case II: The given number is not a palindrome:

Subcase 1: The number to the left of the middle digit is greater than the number on the right ex:2194135 (here 219 > 135) then,reverse the left side numbers and replace the right side numbers with them, therefore the answer will be 2194912.

Subcase 2:The number to the right of the middle digit is greater than the number on the left ex:1354219 then,
then increment the middle digit by 1 and then reverse the left side numbers and replace the right side numbers with them. Therefore the answer would be 135 5(middle digit incremented) 531(reversed), resulting in 1355531, which is the next palindrome.
Note: in case the middle digit is 9 then incrementing it would make it 10, so put 0 instead of 9 and increment the first right and left neighbouring digit of 9 by 1.

Subsets that match a given sum in an array

Q: Find subsets that match a given sum in an array

Common Element in a binary search tree

Q: Given two BST's A, B, Find All elements of A which are present in B

OR

You are given the root nodes of two BST and you have to print the common elements in them.

Max loss of the stock

Given an array of stock prices from day 0 to N-1 of a company X, we have to find the max loss that is possible. Loss occurs if stock is bought at higher price and sold at lower price.
Ex: 1 2 3 7 5 8 9 4 6 10 12
Max Loss is 9 - 4 = 5 (Possible losses are 8-4 = 4, 7-5 = 2 etc). Max difference between stock price is 12 - 1 = 11 but max loss is 9 -4 = 5

Code:

Pythogorous triplets

Q: How to find pythagorean triplets in an array?

OR

Q: Given an array, find all such triplets i,j and k, such that a[i]² = a[j]²+a[k]²

Pythagorean triplet is a set {a,b,c} such that a² = b² + c². Example: for array [9, 2, 3, 4, 8, 5, 6, 10] the output of the algorithm should be {3, 4, 5} and {6, 8, 10}

Algorithm:

Square each element. (This takes O(n) time). This will reduce the original task to "find three numbers in array, one of which is the sum of other two".

1. Sort the array in ascending order. This takes O(n log n).
2. Now consider each element a[i]. If a[i]=a[j]+a[k], then, since numbers are positive and array is now sorted, k<i and j<i. To find such indexes, run a loop that increases j from 1 to i, and decreases k from i to 0 at the same time, until they meet. Increase j if a[j]+a[k] < a[i], and decrease k if the sum is greater than a[i]. If the sum is equal, that's one of the answers, print it, and shift both indexes. This takes O(i) operations.
   
3. Repeat step 2 for each index i. This way you'll need totally O(n²) operations, which will be the final estimate.

Code:

Time Complexity : Efficiency is (i) O(nlogn) : for sorting (ii) O(n^2) : for finding pairs adding equal to A[i] So total efficeincy is O(n^2)