Divide-and-Conquer
1. Input for this problem are two arrays A and B. As output we want all elements which are common to both. Do this in O(nlogn) time.
2. In an array A, a pair of elements A[i] and A[j] is called bad if i < j and A[i] > 2A[j]. Design an O(nlogn) algorithms to output the number of bad pairs in an array.
3. The input to this problem is an Array A such that A[i] < A[i+1] for i < k, and A[i] > A[i +1] for i ≥ k
4. Given a sorted array A of integers, consisting of n distinct elements, give the best algorithm you can determine if there is an index i such that A[i] = i. How many comparisons does your algorithm make?
5. You are given an n x n matrix. It is known that each row is sorted in increasing order from left to right and each column is sorted in increasing order from top to bottom. Design an algorithm to determine if an element x is present in this matrix.
| << Back to Tech Archives |