Algorithm questions

1. Nth largest number in an array (Selection sort descending O(n^2)): Better method. Find the pivot and look at it's position. Details: Learn QuickSort (Complexity: O(n))
2. Nth smallest number in an array (Selection sort ascending) Same as above
3. How would you validate an XML document without using any APIs
4. given two string arrays find if they contain same strings i.e {"a","b","ab"} and {"ab","ab","a","b"} are same but {"a","b"} and {"ab"} are different
5. Design a  data structure that has order(1) time complexity for insert, update,delete, ispresent(key) operations
6. Implement Find and Delete for binary tree.
7. Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's say they are decreasingly sorted), we define a set S = {(a,b) | a \in A and b \in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values.