Q1. Given 3 arrays of numbers A, B and C, design a method to find all the triplets (i, j, k) such that A[i] - B[j] = C[k].
Q2. Given a stream of characters, design an algorithm to verify efficiently if the string received at any point of time is a palindrome.
Q3. Given two sorted arrays of numbers, design an algorithm to find
a) median of the arrays
b) a given number k in the arrays
c) first k smallest number
Hint: a) Perform a binary search on the two arrays
b) Perform simultaneous binary search on both arrays
c) Merge the two sorted arrays on line with merge sort.
Q4. Given a matrix/2D-array where each row and each column is sorted in ascending order, design an algorithm to find
a) median of the matrix
b) a given number k
c) first k smallest number
Q5. You are standing with N-1 other people in a circle. Starting from a random person, every kth person is removed till a single person is left. Design an algorithm to make sure that you are the last person left.
Hint: Josephus Problem
Q6. Given a matrix M of numbers, discuss an efficient algorithm to generate another matrix M' such that M'[i,j] is the sum of all the elements M[k,l] for 0<=k<=i and 0<=l<=j.
Hint: M'[i, j] = M[i,j]+M'[i-1,j]+M'[i,j-1]-M'[i-1,j-1]
Q7. Efficiently find the median of an unsorted array.
Hint. Selection Algorithm
Q8. Given an array A of n numbers, design a method to generate another array B such that B[i]= A[0] x ... x A[i-1] x A[i+1] x ... x A[n], i.e., B[i] is the product of all the elements of A except A[i].
Hint. Generate C such that C[i] = A[0] x ... x A[i]
Generate D such that D[i] = A[i] x ... x A[n]
Then, B[i] = C[i-1] x D[i+1]
Q9. Given an infinite string a,b,c,d,e,f,g,h, ...,u,v,w,x,y,z,aa,ab,ac,ad,ae,af,ag,ah, ..., ba,bb, bc, ...,bx,by,bz,...., give an algorithm to find the kth string.
Hint: If we treat each string as a number, then we see that its a number system of base 26.
Q10. Given an array if n numbers, generate all the subsets of size k such that any two subset has only one element in common. For simplicity lets assume that n = k*l
Q2. Given a stream of characters, design an algorithm to verify efficiently if the string received at any point of time is a palindrome.
Q3. Given two sorted arrays of numbers, design an algorithm to find
a) median of the arrays
b) a given number k in the arrays
c) first k smallest number
Hint: a) Perform a binary search on the two arrays
b) Perform simultaneous binary search on both arrays
c) Merge the two sorted arrays on line with merge sort.
Q4. Given a matrix/2D-array where each row and each column is sorted in ascending order, design an algorithm to find
a) median of the matrix
b) a given number k
c) first k smallest number
Q5. You are standing with N-1 other people in a circle. Starting from a random person, every kth person is removed till a single person is left. Design an algorithm to make sure that you are the last person left.
Hint: Josephus Problem
Q6. Given a matrix M of numbers, discuss an efficient algorithm to generate another matrix M' such that M'[i,j] is the sum of all the elements M[k,l] for 0<=k<=i and 0<=l<=j.
Hint: M'[i, j] = M[i,j]+M'[i-1,j]+M'[i,j-1]-M'[i-1,j-1]
Q7. Efficiently find the median of an unsorted array.
Hint. Selection Algorithm
Q8. Given an array A of n numbers, design a method to generate another array B such that B[i]= A[0] x ... x A[i-1] x A[i+1] x ... x A[n], i.e., B[i] is the product of all the elements of A except A[i].
Hint. Generate C such that C[i] = A[0] x ... x A[i]
Generate D such that D[i] = A[i] x ... x A[n]
Then, B[i] = C[i-1] x D[i+1]
Q9. Given an infinite string a,b,c,d,e,f,g,h, ...,u,v,w,x,y,z,aa,ab,ac,ad,ae,af,ag,ah, ..., ba,bb, bc, ...,bx,by,bz,...., give an algorithm to find the kth string.
Hint: If we treat each string as a number, then we see that its a number system of base 26.
Q10. Given an array if n numbers, generate all the subsets of size k such that any two subset has only one element in common. For simplicity lets assume that n = k*l
No comments:
Post a Comment