- To start with,we are posting solutions to some of the questions.In due course of time ,all the questions shall be solved.
1.There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].
Solve it without division operator and in O(n).
Solution:At each position i,we need to assign A[i], the product of all the elements in the array except A[i].This amounts to same as putting A[i]=a*b,where a=cumulative product of all those elements to the left of A[i] and b=cumulative product of all those elements to the right of A[i].
We can put this simply by storing the result in a separate array and by traversing the input array twice.
In the first iteration, we traverse the input array left to right and assign Output[i]=a (where a is the product of all the numbers preceding A[i]).
Now we traverse the input array again ,but in reverse direction and this time we find
b(here b is the product of all the numbers following A[i]) and Assign
Output[i]=Output[i]*b; which amounts to putting Output[i]=a*b
Hence Each Output[i] contains the product of all the elements in A except A[i].
Below is a C function to do the same.
int* function(int input[],int size,int output[])
{
long int result=1;
for(int i=0;i<size;i++)
{
output[i]=result;
result*=input[i];
}
result=1;
for(int i=size-1;i>=0;i--)
{
output[i]*=result;
result*=input[i];
}
return output;
}
2.There is a linked list of numbers of length N. N is very large and you don't know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
Hint:
1. Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
2. It should be done in O(n).
Solution:Traverse the list, generating a new random number for each entry. Keep a 'top k' chart of the highest random numbers, and their associated entries. When we hit the end of the list, the numbers in the chart are the required random numbers.
This random number generated for each element can be defined as a function f=absolute(irand()-rand()),which is random enough.
3 Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm
Solution:This problem can be solved using bitmaps.bitmap will be an array (say b_array) where we have one bit per M possible number. If we use a character array to store bitmaps, b_array size will be M/8, since 1 char can store 8 bits. Bitmap array will be initialized to zero first. Now for each of the N numbers its corresponding bit should be turned on(1). Corresponding bit for 'n' can be found as follows:
base = n/8; (base is the char whose certain bit needs to be set)
offset = 1 << (n mod 8); (offset is the bit to be set)
b_array[base] |= offset; (I set the particular bit)
Once this is done of all N numbers, given a number m,
we can first find corresponding bit offset and check whether it is one.
base = m/8; (base is the char whose certain bit needs to be set)
offset = 1 << (m mod 8); (offset is the bit to be set)
if (b_array[base] & offset)
// found the number
else
//number could not be found
*Any other solutions will be appreciated.
5)You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.
Solution:Please refer to Question1.This question is identical to the first one,except that it is made to look much harder.
6 How do you put a Binary Search Tree in an array in a efficient manner.
Hint :: If the node is stored at the ith position and its children are at
2i and 2i+1(I mean level order wise)Its not the most efficient way.
Solution:The method of construction given in Hint though looks good at a mere glance,it has too many shortcomings.Exponential memory is required at the worst case.
The solution is maintain inorder and one of the other 2 traversals of the tree.These 2 are sufficient to construct back the tree.So the space requirement now is 2N i.e O
7. How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Note :: You should not use use any extra space. i.e sorting Binary Search Tree
and storing the results in an array and listing out the fifth element.
Solution:
int num=0;
void max(tree*t)
{
if(t==NULL)
return;
max(t->right);
num++;
if(num==5)
printf("%d\n",t->no);
max(t->left);
}
11.How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?
Solution:The three non-collinear points form a triangle. There will be 3 lines which are equidistant from all the three points.
Draw altitudes from each point to the line joining the other two points.We get 3 altitudes.Now draw a line passing through the mid point of the altitude line and parallel to line onto which the altitude is drawn.This line is equidistant from all the 3 points.Thus we get 3 lines.
19.Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
Solution:Use 2 stacks S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.
When one needs to insert an element E ,we first push E on to S1 and then access the top element T of S2 which is the minimum before E has been inserted.If only E is less than T , we push E on to S2 .
When one needs to pop an element ,pop the top element of S1 and if this element is also equal to the one on top of S2, then pop it off S2 as well.
Hence the current minimum will always be on top of S2 .Hence along with other normal stack operations, access of minimum element is also possible in O(1).
20.Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
Solution:This is a flavour of coin change problem ,for which sufficient material is available at Coin Change Problem.
If you have gone through the above link,please refer below to the minor changes we make to the pseudo code of one given in the above link.
Let p[n][m] denote the minimum no of coins of various denomination required to give change for n cents from coins of m different denominations.
P[n][m]=min((1+p[n-S[m]][m]),p[n][m-1])// these notations will be clear only if you go through the above link thoroughly.
Then it isn't much difficult to write the conditions for base cases as well.
This is only a suggested solution to this problem and we have clues here and there as to how to proceed.
23.Write a function to find the middle node of a single link list.
Solution:
typedef struct linklist
{
int no;
struct linklist*next;
}list;
void midvalue(list*start)
{
list*head;
head=start;
while(1)
{
if(start->next==NULL)
{
if(head->next==NULL)
{
printf("Only one node in the list which is %d\n",head->no);
}
else
{
printf("Middle node is %d\n",head->next->no);
}
break;
}
if(start->next->next==NULL)
{
printf("Middle nodes are %d and %d\n",head->no,head->next->no);
}
start=start->next->next;
head=head->next;
}
return;
}This algorithm loops for n/2 times where n is the length of the list.Thus its complexity is O(n).
24.Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
Solution:The following is a function to check if the two trees are similar or not.It returns true if they are similar else false.
int compareTree(struct node* a, struct node* b) {
if (a==NULL && b==NULL)
return(true);
else if (a!=NULL && b!=NULL) {
return(
a->data == b->data &&
compareTree(a->left, b->left) &&
compareTree(a->right, b->right)
);
}
else return(false);
}
26 You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then
distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"
Please give a solution in O(n) time complexity
Solution: Point to the first elements of the three arrays, namely a[0],b[0],c[0].
Find the smallest and second smallest of the three.Let us say that a[0] is the smallest and b[0] is the second smallest. Increment the pointer of a until you find a[i]>b[0]. Calculate the difference between a[i-1] and c[0] and store it as current min. Now,again find the smallest and second smallest between a[i], b[0], and c[0] and repeat the above process. If the new difference is smaller than current min,update the value of current min.
Repeat the above process until one of the arrays are finished.
