So, the following is a list of interview problems I found on various sites which I could not solve or for which I could not find appropriate solutions on various forums. Please post the solutions, if you can solve or have solved any or an argument if it cannot be done.
1. Given a set of positive and negative integers group all the positive integers on one side and negative integers on one side. The numbers should be in the same order they appear.
2. Given an array of integers where some numbers appears once, some numbers appear twice and only one number appears three times, how do you find the number that repeat 3 times. Using extra memory is not allowed.
3. Delete duplicates from a sorted array in O(log n) time and O(1) space.
4. Given an array of ‘n’ random integers. Given an integer 1<=k<=n. Find the k numbers such that the minimum difference of all the possible pairs of k numbers is maximum (maximum among other minimum differences
for various possible selections of k numbers ).
5. Given an array of size n wherein elements keep on increasing monotonically upto a certain location After which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in place (ie. using only O(1) extra memory) [Is there a nice solution that uses the increasing decreasing property ?]
6. There are N nuts and N bolts, all unique pairs of Nuts and Bolts. You cant compare Nut with Nut and a Bolt with Bolt. However, you CAN compare Nut with Bolt. Now how would you figure out matching pairs of nut and bolt from the given N Nut and Bolt.
Is there a O(NlogN) time and O(1) space complexity solution.
[The various forums I have looked at propose a quicksort like solution and all of them seem to be O(N) space.]
7. Given a set of numbers, transform it to an array such that the value at i is the the product of all elements except the element at ai. To be solved with no extra memory.
8. Design a data structure that supports the following two operations on a set S of integers:
a. Insert(x; S), which inserts element x into set S, and
b. DeleteLargerHalf(S), which deletes the largest ceil(|S|/2) elements from S.
Show how to implement this data structure so both operations take O(1) amortized time.
9. Given a>0, compute a-1 without using division.
10. You are given an array of positive integers a[1..n] such that a[1] < a[2] < … a[n]
Given a positive integer C find j and i such that Choose(a[j], a[i]) = C
where Choose(b,a) = b choose a, the binomial coefficient = the number of ways of choosing a balls from a set of b balls. Assume you have a fast Choose(b,a) calculating function at your disposal.
11. You have an integer array of length N, containing values in the range 1,2,3…N^2. Sort the array in O(N) time.
[Solutions on various forums have proposed a radix sort like method as the number of bits to describe the number can now be bounded. However, describing a number upto O(N^2) takes upto 2logN bits and hence, the radix sort will be O(Nk) which is equivalent to O(NlogN).]
