Posted: Wed, 05 Dec 2007 01:32:47 -0600
- Write a C program to count bits set in an integer?
- What purpose do the bitwise and, or, xor and the shift operators serve?
- How to reverse the bits in an integer?
- Check if the 20th bit of a 32 bit integer is on or off?
- How to reverse the odd bits of an integer?
- How would you count the number of bits set in a floating point number?
The answers shall be posted in one or two days. In the meanwhile you guys try out these questions. I will post answers to my previous post "" today.
- Solutions to problems in recursion analysis
Posted: Wed, 05 Dec 2007 01:47:31 -0600
- Using the substitution method, we substitute the function recursively till we arrive at T(1).
i.e T(n)=T(n/2) + 1 = T(n/4) + 1 + 1 = ....
We get a total of lg(n) iterations
i.e T(n)=T(1) +lg(n)
Thus the complexity is O(lg n). - Similar to the 1st problem, it takes lg(n) iterations to reach T(1).After final iteration:
T(n)=(2^lg(n))*(T(1) + lg(n)*17)
Thus the complexity is (2^lg(n))*(lg n) = n*lg(n) - Let n=2^m,then T(2^m)=2*T(2^m/2) + 1
Now let S(m)=T(2^m).
=>S(m)=2*S(m/2) +1
This is the same as 2nd problem.
Thus the complexity is O(m*lg(m)),but m=lg(n)
Thus the final complexity is O(lg(n)*lg(lg(n)))
- Using the substitution method, we substitute the function recursively till we arrive at T(1).
Posted: Thu, 20 Dec 2007 09:48:14 -0600
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.
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(N)
Click here for the questions
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);
}8.Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn
Solution:we divide the array in four sections:[X,Y|A,B]
It is easy to see that with swaps we can modify it to the form [X,A|Y,B].
Now do recursion to solve [X|A] and [Y|B] separately,essentially using divide and conquer.[as given in comments section]
9.Given two sequences of items, find the items whose
absolute number increases or decreases the most when comparing
one sequence with the other by reading the sequence only once.
Solution:Well, this question requires some reading and understanding
of data streams.The stress is upon the algorithmic challenges in web search engines.It wouldn't be appropriate to quote a short piece of text
as the answer.So please go through the paperFinding Frequent Items in Data Streams to have a thorough understanding of the problem
as well as its applications.
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.
13.Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?
Solution:This solution has been framed on the assumption that all the occurances of a string in the large string of length N are to be reported.
So one can just sort the M strings in O(l*Mlog(M)).An additional l figures because comparison function of strings of length l is of complexity O(l).
Once these M strings are sorted,we can simply do a binary search on them for each of the N-l+1 continuous substrings of big string.The complexity of this search for each such substring is O(l*logM).
So the complexity of this procedure is O(l*MlogM)+O((N-l+1)*(l*logM)).
For N>>l this reduces to O(l*MlogM)+O(N*l*log(M).
This can be reduced to O((M+N)*l*log(M)).
If you find a better solution than this,please post it in the comments section.
14.Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree
Hint: Some kind of pointer handling with In Order Traversal - anybody in for
writing some code.
Solution:If the given binary tree is a Binary search tree,then the inorder traversal should output the elements in increasing order.We make use of this property of inorder traversal to check whether the given binary tree is a BST or not.We make note of the latest element that could have been printed and compare it with the current element.Given below is a C function to check it.
bool flag=true;
void inorder(tree T,int *lastprinted)
{
if(T==NULL)
{
printf("the tree is empty .Hence, it is a BST\n");
}
else
{
if(T->left!=NULL)
{
inorder(T->left,lastprinted);
}
if(T->data > *lastprinted)
{
*lastprinted=T->data;
}
else
{
printf("the given binary tree is not a BST\n");
flag=false;
exit(0);
}
inorder(T->right,lastprinted);
}
}
Now check the value of flag to say whether it is a BST or not.If it is not then it is already taken care by the code.
15.You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
Solution:For each chunk of sorted list which occupies a block,make a note of the first and last elements.Thus we have lookup table giving the first and last elements of each of the blocks.Now associate an empty list with each of the blocks.
Now try to find the block which might contain the first entry A[1]of the small sorted list(say)A given.Since we knew the first and last elements of all the blocks,we can identify the block Bi ,which only can contain the desired number.Now add A[1] to the empty list associated with Bi.Now we need to identify the candidate block for A[2].As A is also sorted,A[2] should lie either in Bi or its successors.So we simultaneously traverse
A as well as lookup table.When we are done with finding the probable blocks of all the numbers in A,we have also finished the look up table. We also have in the lists associated with each block,all those entries of A to search for, in that particular block.Now for each block Bi,search for all the entries in its list using binary search.This way we have minimized the number of disk block accesses,which is the bottleneck .
