Programming Interview Questions - 13

Q1.  Given an unsorted array of -ve's, +ve's, and zeros, design an algorithm to arrange the numbers such that all the -ve's are in the left, zeroes are in the middle, and all the +ve's are in the right of the array.

Hint1: Dutch national flag problem
Hint2: Quick sort with 0 as pivot such that all -ve's are left of first zero and all the duplicate zeroes and +ve's are right of the first zero.  Duplicate zeroes and +ve's may be in nay order. So, we again apply quicksort on right sub-array with 1 as pivot.


Q2.  Given two sorted arrays A and B of size (m+n) and m respectively, design an algorithm to merge A and B in-place.


Q3.  Count the number of 1's in a number's representation.

Hint:    while(num > 0) { count++ ;  num = num & (num-1);}


Q4.  Given an array of N numbers, find a set of k numbers whose sum is maximum.
Hint: Find top-k greatest numbers. Construct a max heap in O(n) time and  retrieve top-k in O(k log n).


Q5. Given two arrays A and B of  N and M elements each, write an algorithm to find min(|A[i]-B[j]|).

Hint: Sort each of the arrays in the ascending order. Use an algorithm similar to merge sort to find adjacent pairs of A and B in the combined sorted array. In place of creating a new sorted array, in the merge process itself, find the pairs and take the difference. Find the pair with the smallest difference.


Q6.  Given a string of characters, find the longest substring made up of only three distinct characters.

E.g. Given string s =  abcdaaabbcccefbccc
Here the longest substring having 3 distinct characters is "aaabbccc".

Hint:  Use the principle of Knuth-Morris-Prat algorithm. Remember the position of three characters.


Q7.  Given an array of  integers, design an algorithm to put all the zeros in the beginning of the array.

Hint: 1. Use the principle of quick-sort.
        2. Scan from both ends of the array using a left index  ( i from 0 to n-1, i++)  and a right index ( j from n-1 to 0, j-- ). Exchange a non-zero element on the left with a zero element on the right.  Repeat this until the i < j.


Q8. Given  N  two-dimensional co-ordinates (X_i, Y_i ), find the line passing through the most co-ordinates.

Hint: Hough Transform


Q9.  Given an array of +ve integers and the option to change any integer to it negative value as per required, design an algorithm to find the minimum sum  S >= 0 and all the changes required.


Q10.  Given a sorted list of non-overlapping intervals A= {(4-8),(10-12), (17-23), (25-31)}, design following functions
(a) Given a new interval (a-b), insert it into A such that the list is still sorted and the intervals are non-overlapping.  We can merge all the intervals that overlap with the new interval.
e.g.: Insert (9,24) into A.
       Result list A = {(4-8),(9-24),(25-31)}