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)}
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)}
