1 .In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?
A. 1
B. n - 1
C. n log n
D. n^2
Solution: B. n-1
2 .Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?
* A. O(n log n) sorts
* B. Divide-and-conquer sorts
* C. Interchange sorts
* D. Average time is quadratic.
Solution: C.Interchange sorts reason:Selection sort is not O(n log n) and not a Divide-conquer sort too and Average time of quicksort is not quadratic.
3 . Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?
* A. 21
* B. 41
* C. 42
* D. 43
Solution: C. 42
4 .Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:
1 2 3 4 5 0 6 7 8 9
Which statement is correct? (Note: Our selection sort picks largest items first.)
* A. The algorithm might be either selection sort or insertion sort.
* B. The algorithm might be selectionsort, but could not be insertionsort.
* C. The algorithm might be insertionsort, but could not be selectionsort.
* D. The algorithm is neither selectionsort nor insertionsort.
Solution: C. The algorithm might be insertion sort, but could not be selection sort.
5 .Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:
2 4 5 7 8 1 3 6
Which statement is correct? (Note: Our selectionsort picks largest items first.)
* A. The algorithm might be either selectionsort or insertionsort.
* B. The algorithm might be selectionsort, but it is not insertionsort.
* C. The algorithm is not selectionsort, but it might be insertionsort.
* D. The algorithm is neither selectionsort nor insertionsort.
Solution: C. The algorithm is not selectionsort, but it might be insertionsort.
6 .When is insertionsort a good choice for sorting an array?
* A. Each component of the array requires a large amount of memory.
* B. Each component of the array requires a small amount of memory.
* C. The array has only a few items out of place.
* D. The processor speed is fast.
Solution: C. The array has only a few items out of place.
7 What is the worst-case time for mergesort to sort an array of n elements?
* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)
Solution : C. O(n log n)
8 What is the worst-case time for quicksort to sort an array of n elements?
* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)
Solution: D. O(n^2)
9 .Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
* A. The array elements form a heap.
* B. Elements in each half of the array are sorted amongst themselves.
* C. Elements in the first half of the array are less than or equal to elements in the second half of the array.
* D. None of the above.
Solution: B. Elements in each half of the array are sorted amongst themselves.
10 .Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:
2 5 1 7 9 12 11 10
Which statement is correct?
* A. The pivot could be either the 7 or the 9.
* B. The pivot could be the 7, but it is not the 9.
* C. The pivot is not the 7, but it could be the 9.
* D. Neither the 7 nor the 9 is the pivot.
Solution: A. The pivot could be either the 7 or the 9.
11 .What is the worst-case time for heapsort to sort an array of n elements?
* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)
Solution: C. O(n log n)
12.Suppose you are given a sorted list of N elements followed by f(N) randomly ordered elements.How would you sort the entire list if
* A. f(N)=O(1)
* B. f(N)=O(logN)
* C. f(N)=O(N^1/2)
* D. How large can f(N) be for the entire list still to be sortable in O(N) time?
Solution:
A. f(N)=O(1) In this case insertion sort would be the best ,giving the time complexity of O(N)
B. f(N)=O(log N) Merge sort is the best option with a time complexity of O(N)
C.f(N)=O(N^1/2) Merge sort is the best option with a time complexity of O(N)
D.complexity = f(N)log f(N) + N +f(N)
Clearly f(N) is O(N) for the complexity to be of O(N)
Now O(N) is an over estimate on the upper bound of f(N) ,which is quite clear from the first term in the above expression.
Now let f(N) is of the form k.N^(1/p ).Then with some simplification we get
f(N)log(f(N)) is O(N ^(2/p)) and now to restrict the whole expression to O(N)
we need to restrict p to p >= 2
But f(N)is O(N^(1/p)) which means f(N) can at most be of size N^1/2 .
13.Prove that any algorithm that find an element X in a sorted list of N elements requires Omega(log N) comparisons.
Solution:The search essentially becomes a search for X in a binary decision tree and this requires Omega(log N) comparisons.
14.Prove that sorting N elements with integer keys in the range 1 < Key < M
takes O(M + N) time using bucket sort.
Solution: Putting the elements in to their corresponding buckets is of O(N).Then iteration of the buckets and printing the corresponding keys as many times as their frequency is of O(M+N).Hence the total complexity.
15.Suppose you have an array of N elements,containing only 2 distinct keys, true and false.Give an O(N) algorithm to sort the array.
Solution:Use bucket sort with 2 buckets.
16.Prove that any comparison based algorithm to sort 4 elements requires at least 3 comparisons and at the max comparisons
Solution:The binary decision tree has maximum distance of 3 and a maximum distance of 5 ,from the root to the leaf.As each edge corresponds to a comparison,we need minimum of 3 and maximum of 5 comparisons to sort 4 elements.
17. In how many ways can 2 sorted arrays of combined size N be merged?
Solution:Still up for debate.Any answers? :)
18.Show that binary insertion may reasonably be expected to be an O(n log n) sort.
Solution:Binary insertion sort employs binary search to find the right place to insert new elements, and therefore performs ceil (log(n!)) comparisons in the worst case, which is Θ(n log n). The algorithm as a whole still takes Θ(n2) time on average due to the series of swaps required for each insertion, and since it always uses binary search, the best case is no longer Ω(n) but Ω(n log n).
19.You are given two sets of numbers Xi and Yj , where i and j run from 1 to N.
Devise an algorithm to find the M largest values of Xi −Yj . This algorithm should
not be quadratic in N, though it is permitted to be quadratic in M.
You should regard N as being of the order of 20,000 and M as being of the order
of 1,000.
Solution:Use an order-statistic algorithm to find the Mth largest number in X,partition around that number and sort the M largest numbers.Repeat this for Y but sorting the M smallest numbers.This can be done in O(N+M log(M))Now with each of these sub-arrays having M elements,find the difference between each element of X and Y.We have M difference elements for each Xi in sorted order and in total M^2 differences.Use merge sort repeatedly to merge these portions .This is of complexity M^2.Hence the procedure.
20.If 1024 numbers are drawn randomly in the range 0–127 and sorted by binary
insertion, about how many compares would you expect?
Solution:We have 3 comparisons coming in to the picture a<b, a>b, a=b.The overall number of comparisons won't change and it is still of the O(N log N). strictly speaking log(N!) comparisons.
The answers for the rest of the questions shall be posted in a day.
Click Here For the set of Questions
Showing posts with label Solutions. Show all posts
Showing posts with label Solutions. Show all posts
C-program to count the leaves in a tree
12. Write a C program to count the number of leaves in a tree
Solution:
Click Here For More Questions
Solution:
#include<stdio.h>
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
int count_leaves(tree T)
{
if(T==NULL)
return 0;
else if(T->left==NULL && T->right==NULL)
{
return 1;
}
else
return count_leaves(T->left)+count_leaves(T->right);
}
Click Here For More Questions
Search On a Binary Search Tree
11. Write a C program to search for a value in a binary search tree (BST).
Solution:
Click Here For More Questions
Solution:
#include<stdio.h>
#include<stdbool.h>
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
tree search_node(tree T,int num)
{
if(T==NULL)
{
return NULL;
}
else
{
if(T->data>num)
search_node(T->left,num);
else if(T->data<num)
search_node(T->right,num);
return T;
}
}
Click Here For More Questions
C-program to delete a node from a tree
10. Write a C program to delete a node from a Binary Search Tree?
Solution:
Click Here For More Questions
Solution:
#include<stdio.h>
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
tree delete_node(tree T,int num)
{
tree temp;
if (T==NULL)
exit(0);
//return NULL;
else if(num<T->data)
T->left=delete_node(T->left,num);
else if(num>T->data)
T->right=delete_node(T->right,num);
else
{
if(T->left!=NULL&&T->right!=NULL)
{
temp=min(T->right);
T->data=temp->data;
T->right=delete_node(T->right,T->data);
}
else if(T->left==NULL)
{
temp=T;
T=T->right;
}
else if(T->right==NULL)
{
temp=T;
T=T->left;
}
free(temp);
}
return T;
}
Click Here For More Questions
C-program to check whether a binary tree is a Binary search tree
8. Write a C program to check if a given binary tree is a binary search tree or not?
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.
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.
Click Here For More Questions
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.
Click Here For More Questions
C-program to make a copy of a tree
7.Write a C program to create
a copy of a tree
Solution:
Click Here For More Questions
a copy of a tree
Solution:
#include<stdio.h>
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
tree copy(tree T)
{
if(T== NULL)
return NULL;
else
{
tree *newtree=(tree*)malloc(sizeof(tree));
newtree->data=tree->data;
newtree->left=copy(T->left);
newtree->right=copy(T->right);
return newtree;
}
}
Click Here For More Questions
Solution1
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.
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;
}
Solutions to problems in recursion analysis
Click here for the questions
- 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)))
Solutions to Google Top Interview Puzzles
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.
Click here for the questions
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.
Click here for the questions
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:
*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.
Click here for the questions
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(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:
Click here for the questions
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]
Click here for the questions
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.
Click here for the questions
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.
Click here for the questions
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.
Click here for the questions
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.
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.
Click here for the questions
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 .
Click here for the questions
16.Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
Solution:Different solutions exist for this problem,depending on how once perceives the question.
If all the companies are assumed to be unique things,then the solution goes like this.Initially we need to merge 2 companies.These 2 can be chosen in Nc2 ways.Now in the second iteration we can merge 2 companies among the remaining N-1 in N-1c2.
We go on merging like this until we have a single union of all the companies.
Hence the number of ways of doing this is (Nc2)*(N-1c2)*(N-2c2)*........*(2c2)=(N!*(N-1)!)/2^(N-1) .
One more way of looking at this problem is the structural aspect of merging.In the above solution suppose there are 4 companies say,to be merged.
We could have merged companies 1&2 in the first iteration and 3&4 in the 2nd iteration.Likewise we could have also merged 3&4 in the first iteration and then 1&2 in the 2nd iteration.After these 2 merges,both of them are identical,though we put them as different ways in solution1,depending on which 2 were merged before the other 2.If we were interested only in the structural aspects,then the above solution doesn't even consider that.
If we are interested in the number of structurally different ways to merge these, then we can confront this problem on the assumption that all the given companies are identical .Then this problem reduces to parenthesis problem,i.e number of ways of putting N pairs of parenthesis.The answer then would be N-1 th Catalan Number,
i.e (2N-2)!/N!(N-1)!.
If the companies aren't identical ,with some permutations also getting into the picture, then the solution isn't straightforward and we couldn't figure it out.
So if anyone has a solution to this,please post it in the comments section.
Click here for the questions
17.Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
Solution:The maximum size of int is 2,147,483,647 in case of 32-bit integers. Thus we need declare an array of long long int.
Then we can do a merge sort and in doing so we can find the integers which appear atleast twice in the merge step.Thus we can solve the problem in
nlogn time.
If you have any better solution then please comment.
Click here for the questions
18 Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
Solution:This question is similar to question 9 in the context which it appears and
answer lies in the same paper Finding Frequent Items in Data Streams.
Click here for the questions
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).
Click here for the questions
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.
Click here for the questions
21.Given an array,
i) find the longest continuous increasing subsequence.
ii) find the longest increasing subsequence.
Solution:a)Given a sequence,we can find the longest continuous increasing subsequence in O(n) time.We traverse the sequence one and keep track of the points where the number decreases.
b)This problem can be solved in O(n^2).This can be solved in 3 methods.One method is to find the longest path in a directed acyclic graph.The other method is to sort the given sequence and make it copy and find the longest common subsequence on the 2 sequences.The third one is using the dynamic programming.
The following is a function which returns the length of the longest increasing subsequence in a.
Click here for the questions
22.Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
Solution:This is a repeated question, same as the 16th. So please refer to the 16th answer.
Click here for the questions
23.Write a function to find the middle node of a single link list.
Solution:
This algorithm loops for n/2 times where n is the length of the list.Thus its complexity is O(n).
Click here for the questions
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.
Click here for the questions
25.Implement put/get methods of a fixed size cache with LRU replacement algorithm.
Solution:Each cache unit consists of an id,data and its age.In the Least recently used algorithm if the cache is full and we need to put some data, we replace it an the unit whose age is the least.
Getting some data is just a search for the data thereby incrementing it age and resorting the cache units.
Click here for the questions
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.
Click here for the questions
27.Classic - Egg Problem
You are given 2 eggs.You have access to a 100-storey building.
Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.
Solution:Let d be the number of drops required.
Now we need to find an optimal solution no matter at which floor the egg breaks.
So we find d such that it doesn't depend on the floor number.
Let us break the egg at floor d. If the egg breaks then we have atmax d-1 floors to test for the highest floor,thus making it d breaks in total.
If the egg doesn't break at floor d,then proceed to floor 2d-1,where we make the 2nd attempt.If it breaks here we have d-2 breaks in the worst case to find the highest floor.
We proceed in this fashion,till we reach the 100th floor.
Thus we break at d,2*d-1,3*d-2,....
thus d+(d-1)+(d-2)+.... 1 <=100
=>d=14
Thus we need atmax of 14 attempts for any case.
Click here for the questions
Solutions to the remaining puzzles will be posted soon. If we have a solution then please comment it.
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;
}
Click here for the questions
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.
Click here for the questions
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.
Click here for the questions
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(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);
}
Click here for the questions
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]
Click here for the questions
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.
Click here for the questions
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.
Click here for the questions
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.
Click here for the questions
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.
Click here for the questions
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 .
Click here for the questions
16.Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
Solution:Different solutions exist for this problem,depending on how once perceives the question.
If all the companies are assumed to be unique things,then the solution goes like this.Initially we need to merge 2 companies.These 2 can be chosen in Nc2 ways.Now in the second iteration we can merge 2 companies among the remaining N-1 in N-1c2.
We go on merging like this until we have a single union of all the companies.
Hence the number of ways of doing this is (Nc2)*(N-1c2)*(N-2c2)*........*(2c2)=(N!*(N-1)!)/2^(N-1) .
One more way of looking at this problem is the structural aspect of merging.In the above solution suppose there are 4 companies say,to be merged.
We could have merged companies 1&2 in the first iteration and 3&4 in the 2nd iteration.Likewise we could have also merged 3&4 in the first iteration and then 1&2 in the 2nd iteration.After these 2 merges,both of them are identical,though we put them as different ways in solution1,depending on which 2 were merged before the other 2.If we were interested only in the structural aspects,then the above solution doesn't even consider that.
If we are interested in the number of structurally different ways to merge these, then we can confront this problem on the assumption that all the given companies are identical .Then this problem reduces to parenthesis problem,i.e number of ways of putting N pairs of parenthesis.The answer then would be N-1 th Catalan Number,
i.e (2N-2)!/N!(N-1)!.
If the companies aren't identical ,with some permutations also getting into the picture, then the solution isn't straightforward and we couldn't figure it out.
So if anyone has a solution to this,please post it in the comments section.
Click here for the questions
17.Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
Solution:The maximum size of int is 2,147,483,647 in case of 32-bit integers. Thus we need declare an array of long long int.
Then we can do a merge sort and in doing so we can find the integers which appear atleast twice in the merge step.Thus we can solve the problem in
nlogn time.
If you have any better solution then please comment.
Click here for the questions
18 Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
Solution:This question is similar to question 9 in the context which it appears and
answer lies in the same paper Finding Frequent Items in Data Streams.
Click here for the questions
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).
Click here for the questions
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.
Click here for the questions
21.Given an array,
i) find the longest continuous increasing subsequence.
ii) find the longest increasing subsequence.
Solution:a)Given a sequence,we can find the longest continuous increasing subsequence in O(n) time.We traverse the sequence one and keep track of the points where the number decreases.
b)This problem can be solved in O(n^2).This can be solved in 3 methods.One method is to find the longest path in a directed acyclic graph.The other method is to sort the given sequence and make it copy and find the longest common subsequence on the 2 sequences.The third one is using the dynamic programming.
The following is a function which returns the length of the longest increasing subsequence in a.
int lis(int*a,int n)
{
int length[n],path[n],i,j,max=0;
for(i=0;i < N;i++)
length[i]=1,path[i]=i; //path contains the longest subsequence.
for(i=1;i < N;i++)
for(j=0;j < i;j++)
if(a[i] > a[j] && length[i] < length[j]+1)
length[i]=length[j]+1,path[i]=j;
for(i=0;i < N;i++)
if(max < length[i])
max=length[i];
return max;
}
Click here for the questions
22.Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
Solution:This is a repeated question, same as the 16th. So please refer to the 16th answer.
Click here for the questions
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).
Click here for the questions
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);
}
Click here for the questions
25.Implement put/get methods of a fixed size cache with LRU replacement algorithm.
Solution:Each cache unit consists of an id,data and its age.In the Least recently used algorithm if the cache is full and we need to put some data, we replace it an the unit whose age is the least.
Getting some data is just a search for the data thereby incrementing it age and resorting the cache units.
get(id)
{
z=search(id);
data=cache[z].data;
cache[z].age++;
sort(cache);
return(x);
}
put(id,x)
{
if(top==cachesize) //if cache is full
top--
cache[top].id=id;
cache[top].data=x;
cache[top].age=0;
top++;
}
Click here for the questions
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.
Click here for the questions
27.Classic - Egg Problem
You are given 2 eggs.You have access to a 100-storey building.
Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.
Solution:Let d be the number of drops required.
Now we need to find an optimal solution no matter at which floor the egg breaks.
So we find d such that it doesn't depend on the floor number.
Let us break the egg at floor d. If the egg breaks then we have atmax d-1 floors to test for the highest floor,thus making it d breaks in total.
If the egg doesn't break at floor d,then proceed to floor 2d-1,where we make the 2nd attempt.If it breaks here we have d-2 breaks in the worst case to find the highest floor.
We proceed in this fashion,till we reach the 100th floor.
Thus we break at d,2*d-1,3*d-2,....
thus d+(d-1)+(d-2)+.... 1 <=100
=>d=14
Thus we need atmax of 14 attempts for any case.
Click here for the questions
Solutions to the remaining puzzles will be posted soon. If we have a solution then please comment it.
Traversals of a Binary Tree
Write C code to implement the preorder(), inorder() and postorder() traversals. Whats their time complexities?
Each of them traverse all the nodes.
So the complexity is O(N).
Click Here For More Questions
#include<stdio.h>
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
void inorder_print(tree T)
{
if (T!=NULL)
{
printf("%d\n",T->data);
inorder_print(T->left);
inorder_print(T->right);
}
}
void postorder_print(tree T)
{
if (T==NULL)
{
return;
}
postorder_print(T->left);
postorder_print(T->right);
printf("%d\n",T->data);
}
void preorder_print(tree T)
{
if (T==NULL)
{
return;
}
printf("%d\n",T->data);
preorder_print(T->left);
preorder_print(T->right);
}
Each of them traverse all the nodes.
So the complexity is O(N).
Click Here For More Questions
Solutions to Amazon Intern Interview Questions
Click here for the questions
1)Place a red ball in a urn and all the further balls in the other urn.The probability for picking out the red ball is now greater than 0.5.
2)If v<=2V then the position is (v*L)/(2*V) from the starting point else it is 2*L -(v*L)/(2*V) from the starting point.
4)If we know the process then we can kill it by killall -9 "process name" else we can kill it using its process id obtained by the command ps -x by kill -9 "processid" .
5)Top command displays all the Linux tasks running at that particular time.It provides their running time and the resources used.
6)The number appearing 2 times is (sum of all the numbers in the array) - (sum of the numbers from 1 to n).
For floating numbers multiply it with 100 and proceed.
1)Place a red ball in a urn and all the further balls in the other urn.The probability for picking out the red ball is now greater than 0.5.
2)If v<=2V then the position is (v*L)/(2*V) from the starting point else it is 2*L -(v*L)/(2*V) from the starting point.
4)If we know the process then we can kill it by killall -9 "process name" else we can kill it using its process id obtained by the command ps -x by kill -9 "processid" .
5)Top command displays all the Linux tasks running at that particular time.It provides their running time and the resources used.
6)The number appearing 2 times is (sum of all the numbers in the array) - (sum of the numbers from 1 to n).
For floating numbers multiply it with 100 and proceed.
C program to create mirror copy of a tree
Question:Write a C program to create a mirror copy of a tree left nodes become right and right nodes become left)
Solution:
Click Here For More Questions
Solution:
#include<stdio.h>
struct binarysearchtree{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
tree mirror_copy(tree T)
{
if(T==NULL)
return T;
else
{
tree temp1=mirror_copy(T->left);
tree temp2=mirror_copy(T->right);
T->left=temp2;
T->right=temp1;
return T;
}
}
Click Here For More Questions
Solutions to Questions on recursion
Click here for the questions
6)
arr is an array containing N integers.You can also change the program by keeping characters.k is initially 0.
8)
Mergesort:a is an array of n intergers,temp is just a temporary array.low is initially 0 and high is n-1.
Quicksort:a is an array of n integers.left is initially 0 and right is n-1.
1)
int Fibinocci(int n)
{
if(n==1)
return 1;
else
n+Fibinocci(n-1);
}
2)
void reverse(char*str)
{
if(*str != '\0')
reverse(str+1);
}
3)
int Factorial(int n)
{
if(n==1)
return 1;
else
return(n*Factorial(n-1);
}
4)
void MoveTower(int disk, int source, int dest, int spare):
{
if(disk == 1)
printf("Move top disc from %d to %d\n",source,desc);
else
{
MoveTower(disk - 1, source, spare, dest);
printf("Move top disc from %d to %d\n",source,desc);
// Step 2
MoveTower(disk - 1, spare, dest, source);
}
}
5)
int gcd(int a,int b)
{
if(b==0)
return(a);
else
return(gcd(b,a(mod)b);
}
6)
arr is an array containing N integers.You can also change the program by keeping characters.k is initially 0.
void permutation(int *arr, int N, int k)
{
static level = -1;
level = level+1;
arr[k] = level;
if (level == N)
{
if(arr!=0)
for(int i=0; i < N;i++)
printf("%d",arr[i]);
}
else
for (int i = 0; i < N; i++)
if (arr[i] == 0)
permutation(arr, N, i);
level = level-1;
arr[k] = 0;
}
7)void combinations(char*str,int no)
{
int temp1=0;
int i,count,n=1,num,len;
for(i=0;*(str+i)!='\0';i++);
len=i;
for(i=0;i < len;i++)
n=2*n;
temp=(int*)malloc(len*sizeof(int));
for(i=0;i < len;i++)
*(temp+i)=0;
for(num=0;num <= n;num=num+1)
{
temp1=num;
for(i=0;i < len;i++)
{
*(temp+i) = temp1%2;
temp1=temp1/2;
}
count=0;
for(i=0;i < len;i++)
{
if(*(temp+i)==1)
count++;
}
if(count==no)
{
for(i=0;i < len;i++)
{
if(*(temp+i)==1)
printf("%c",*(str+i));
}
printf("\n");
}
}
8)
Mergesort:a is an array of n intergers,temp is just a temporary array.low is initially 0 and high is n-1.
void mergesort(int *a,int *temp,int low,int hi)
{
int mid;
if(hi==low)
{
return;
}
else
{
mid=(low+hi)/2;
mergesort(a,temp,low,mid);
printf("1\n");
mergesort(a,temp,mid+1,hi);
printf("2\n");
merge(a,temp,low,mid+1,hi);
}
}
void merge(int a[],int temp[],int left,int rig,int r)
{
printf("%d %d %d\n",left,rig,r);
int i,l,n,k;
l=rig-1;
k=left;
n=r-left+1;
while(left<=l&&rig<=r)
{
if(a[left]<=a[rig])
temp[k++]=a[left++];
else
temp[k++]=a[rig++];
}
while(left<=l)
temp[k++]=a[left++];
while(rig<=r)
temp[k++]=a[rig++];
for(i=0;i < n;i++,r--)
a[r]=temp[r];
}
Quicksort:a is an array of n integers.left is initially 0 and right is n-1.
void quick(int *a, int left, int right)
{
int temp,i,k;
temp=left;
if (left>=right)
{
return;
}
k=(left+right)/2;
swap(a,left,k);
for (i=left+1;i<=right;i++)
{
if (a[i] < a[left])
{
swap(a,++temp,i);
}
}
swap(a,left,temp); //swap a[left] and a[temp]
quick(a,left,temp-1);
quick(a,temp+1,right);
}
Minimum Value of a Binary Search Tree
Question:Write a C program to find the minimum value in a binary search tree.
Solution:
Click Here For More Questions
Solution:
#include<stdio.h>
struct binarysearchtree
{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
tree min(tree T)
{
if (T==NULL)
return NULL;
else
{
if(T->left==NULL)
return T;
else
return min(T->left);
}
}
Click Here For More Questions
C program to delete a tree
Write a C program to delete a tree(i.e, free up its nodes)
Click Here For Questions
#include<stdio.h>
struct binarysearchtree
{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
void tree_free(tree T)
{
if (T==NULL)
return;
else
{
tree_free(T->left);
tree_free(T->right);
free(T);
}
}
Click Here For Questions
C program to determine the number of nodes in a binary tree
Question:Write a C program to determine the number of elements(or size) in a binary tree?
Solution:
Click Here For More Questions
Solution:
#include<stdio.h>
struct binarysearchtree
{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
int tree_size(tree T)
{
if(T==NULL)
return 0;
else
{
return 1+tree_size(T->left)+tree_size(T->right);
}
}
Click Here For More Questions
C program to find the height of a binary search tree
Question:Write a C program to find the depth or height of a binary tree
Solution:
#include<stdio.h>
Click Here For More Questions
Solution:
#include<stdio.h>
struct binarysearchtree
{
int data;
struct binarysearchtree* left;
struct binarysearchtree* right;
};
typedef struct binarysearchtree* tree;
int max(int a,int b)
{
if(a >=b)
return a;
else
return b;
}
int height(tree T)
{
if(T==NULL)
return 0;
else
{
int h1=height(T->left);
int h2=height(T->right);
return 1+max(h1,h2);
}
}
Click Here For More Questions
Solutions to Logical Puzzles-3
Click here for the questions
1)
2)3,
The number obtained by dividing 48 with 4 is 12 which is even while all the others get odd number for the same.
3)4,
The sequence has to be AON,EWR,IEV,MMZ
4)2
The remaining 3 are input devices.
5)2
The remaining 3 represent an image.
6)3
Trousers can only take a plural form while others can also take a singular form.
7)
8)
9)4
All the other three lie inside a cell.
10)
11)4
12)3
13)1
14)2
15)3
16)3
17)1
18)3
19)3
20)4
1)
2)3,
The number obtained by dividing 48 with 4 is 12 which is even while all the others get odd number for the same.
3)4,
The sequence has to be AON,EWR,IEV,MMZ
4)2
The remaining 3 are input devices.
5)2
The remaining 3 represent an image.
6)3
Trousers can only take a plural form while others can also take a singular form.
7)
8)
9)4
All the other three lie inside a cell.
10)
11)4
12)3
13)1
14)2
15)3
16)3
17)1
18)3
19)3
20)4
Solutions to Logical Puzzles-1
Click here for the questions
We need 3 cuts to cut a cube into 6 equal pieces,with one cut in each dimension.Maximum identical pieces obtained with n cuts[if n is a factor of 3] = (n/3 + 1)^3, with n/3 cuts, we form n/3 + 1 equal pieces.If we need to get maximum number of identical cubes with some number of cuts then the number of cuts in all the dimensions should be equal if possible or almost equal.
The number of identical pieces formed with l,n,m cuts in the 3 demensions are (l+1)*(n+1)*(m+1).
1)3,Here there are 6,7,8 cuts in each dimension
2)2
3)4,Here the number of cuts are 7,7,6 in the 3 dimensions.
4)1
5)3
All the problems from 6-18 are based mostly on imagination.Note that 27 identical pieces have no color at all i.e they are inner pieces.
6)3
7)4
8)1
9)3
10)2
11)2
12)4
13)1
14)4
15)3
16)1
17)4
18)1
19)2
20)4
We need 3 cuts to cut a cube into 6 equal pieces,with one cut in each dimension.Maximum identical pieces obtained with n cuts[if n is a factor of 3] = (n/3 + 1)^3, with n/3 cuts, we form n/3 + 1 equal pieces.If we need to get maximum number of identical cubes with some number of cuts then the number of cuts in all the dimensions should be equal if possible or almost equal.
The number of identical pieces formed with l,n,m cuts in the 3 demensions are (l+1)*(n+1)*(m+1).
1)3,Here there are 6,7,8 cuts in each dimension
2)2
3)4,Here the number of cuts are 7,7,6 in the 3 dimensions.
4)1
5)3
All the problems from 6-18 are based mostly on imagination.Note that 27 identical pieces have no color at all i.e they are inner pieces.
6)3
7)4
8)1
9)3
10)2
11)2
12)4
13)1
14)4
15)3
16)1
17)4
18)1
19)2
20)4
Solutions to Basic C Interview Questions
Click here for the questions>
1)To check for it, create two pointers,and set each to the start of the list. Update each as follows:
while (pointer1) {
pointer1 = pointer1->next;
pointer2 = pointer2->next;
if (pointer2) pointer2=pointer2->next;
if (pointer1 == pointer2) {
print ("circular linked list\n");
}
}
2)Union x : 1101791232 21.500000
Union y : 100 d 0.000000
3)It is an object of some class whose purpose is to indicate that a real object of that class does not exist. One common use for a null object is a return value from a member function that is supposed to return an object with some specified properties but cannot find such an object.
4) Java,Smalltalk,Eiffel,Sather.
5)A container class is a class that is used to hold objects in memory or
external storage. A container class acts as a generic holder. A
container class has a predefined behavior and a well-known interface. A
container class is a supporting class whose purpose is to hide the
topology used for maintaining the list of objects in memory. When a
container class contains a group of mixed objects, the container is
called a heterogeneous container; when the container is holding a group
of objects that are all the same, the container is called a homogeneous
container.
6)fffffff0
7)C was the C++ predecessor. As it's name implies, a lot of C remains in C++. Although not actually being more powerful than C, C++ allows the programmer to more easily manage and operate with Objects, using an OOP (Object Oriented Programming) concept.
C++ allows the programmer to create classes, which are somewhat similar to C structures. However, to a class can be assigned methods, functions associated to it, of various prototypes, which can access and operate within the class, somewhat like C functions often operate on a supplied handler pointer.
Although it is possible to implement anything which C++ could implement in C, C++ aids to standarize a way in which objects are created and managed, whereas the C programmer who implements the same system has a lot of liberty on how to actually implement the internals, and style among programmers will vary a lot on the design choices made.
In C, some will prefer the handler-type, where a main function initializes a handler, and that handler can be supplied to other functions of the library as an object to operate on/through. Others will even want to have that handler link all the related function pointers within it which then must be called using a convention closer to C++.
To finish this discussion, C++ applications are generally slower at runtime, and are much slower to compile than C programs. The low-level infrastructure for C++ binary execution is also larger. For these reasons C is always commonly used even if C++ has alot of popularity, and will probably continue to be used in projects where size and speed are primary concerns, and portable code still required (assembly would be unsuitable then).
8)Incomplete types
refers to pointers in which there is non availability of the
implementation of the referenced location or it points to some location
whose value is not available for modification.
int *i=0x400 // i points to address 400
*i=0; //set the value of memory location pointed by i.
9)Printf : Call by value
Scanf : Call by reference
10)a const pointer means the pointer which represents the address of one value. so if you declare a pointer inside the function, it doesn't have scope outside the function. if it is also available to the outside function whenever we declare a pointer as const.
11)Type casting must be done wheneever the data type of the variable to which u r gonna assign some values is diff from the data type of the variable on the right side.
for instance;
float f;
int i = 10 , j = 5 ;
f = (float) ( i / j ) ;
f -------> left side variable.
i -------> right side variable.
but always make sure that the size of the var on the left is greater than that of the right. else there will be data loss.
A type cast should not be used to override a const or volatile declaration. Overriding these type modifiers can cause the program to fail to run correctly.
A type cast should not be used to turn a pointer to one type of structure or data type into another. In the
rare events in which this action is beneficial, using a union to hold the values makes the programmer.s
intentions clearer.
12)he answer is the standard library function qsort(). It.s the easiest sort by far for several reasons:
It is already written.
It is already debugged.
It has been optimized as much as possible (usually).
Void qsort(void *buf, size_t num, size_t size, int (*comp)(const void *ele1, const void *ele2));
13)The answer depends on what you mean by quickest. For most sorting problems, it just doesn't matter how quick the sort is because it is done infrequently or other operations take significantly more time anyway. Even in cases in which sorting speed is of the essence, there is no one answer. It depends on not only the size and nature of the data, but also the likely order. No algorithm is best in all cases.
There are three sorting methods in this author.s .toolbox. that are all very fast and that are useful in different situations. Those methods are quick sort, merge sort, and radix sort.
The Quick Sort
The quick sort algorithm is of the .divide and conquer. type. That means it works by reducing a sorting
problem into several easier sorting problems and solving each of them. A .dividing. value is chosen from the input data, and the data is partitioned into three sets: elements that belong before the dividing value, the value itself, and elements that come after the dividing value. The partitioning is performed by exchanging elements that are in the first set but belong in the third with elements that are in the third set but belong in the first Elements that are equal to the dividing element can be put in any of the three sets.the algorithm will still work properly.
The Merge Sort
The merge sort is a .divide and conquer. sort as well. It works by considering the data to be sorted as a
sequence of already-sorted lists (in the worst case, each list is one element long). Adjacent sorted lists are merged into larger sorted lists until there is a single sorted list containing all the elements. The merge sort is good at sorting lists and other data structures that are not in arrays, and it can be used to sort things that don.t fit into memory. It also can be implemented as a stable sort.
The Radix Sort
The radix sort takes a list of integers and puts each element on a smaller list, depending on the value of its least significant byte. Then the small lists are concatenated, and the process is repeated for each more significant byte until the list is sorted. The radix sort is simpler to implement on fixed-length data such as ints.
14)Both the merge sort and the radix sort are good sorting algorithms to use for linked lists.
15)The preprocessor is used to modify your program according to the preprocessor directives in your source code. Preprocessor directives (such as #define) give the preprocessor specific instructions on how to modify your source code. The preprocessor reads in all of your include files and the source code you are compiling and creates a preprocessed version of your source code. This preprocessed version has all of its macros and constant symbols replaced by their corresponding code and value assignments. If your source code contains any conditional preprocessor directives (such as #if), the preprocessor evaluates the condition and modifies your source code accordingly.
The C preprocessor is used to modify your program according to the preprocessor directives in your source code. A preprocessor directive is a statement (such as #define) that gives the preprocessor specific instructions on how to modify your source code. The preprocessor is invoked as the first part of your compiler program.s compilation step. It is usually hidden from the programmer because it is run automatically by the compiler.
16)The standard C library provides several functions for converting strings to numbers of all formats (integers, longs, floats, and so on) and vice versa.
The following functions can be used to convert strings to numbers:
Function Name Purpose
atof() Converts a string to a double-precision floating-point value.
atoi() Converts a string to an integer.
atol() Converts a string to a long integer.
strtod() Converts a string to a double-precision floating-point value and reports any .leftover. numbers that could not be converted.
strtol() Converts a string to a long integer and reports any .leftover. numbers that could not be converted.
strtoul() Converts a string to an unsigned long integer and reports any .leftover. numbers that could not be converted.
17)
The standard C library provides several functions for converting numbers of all formats (integers, longs, floats, and so on) to strings and vice versa
The following functions can be used to convert integers to strings:
Function Name Purpose
itoa() Converts an integer value to a string.
ltoa() Converts a long integer value to a string.
ultoa() Converts an unsigned long integer value to a string.
The following functions can be used to convert floating-point values to strings:
Function Name Purpose
ecvt() Converts a double-precision floating-point value to a string without an embedded decimal point.
fcvt() Same as ecvt(), but forces the precision to a specified number of digits.
gcvt() Converts a double-precision floating-point value to a string with an embedded decimal point.
18)The heap is where malloc(), calloc(), and realloc() get memory.
Getting memory from the heap is much slower than getting it from the stack. On the other hand, the heap
is much more flexible than the stack. Memory can be allocated at any time and deallocated in any order. Such
memory isn't deallocated automatically; you have to call free().
Recursive data structures are almost always implemented with memory from the heap. Strings often come
from there too, especially strings that could be very long at runtime. If you can keep data in a local variable (and allocate it from the stack), your code will run faster than if you put the data on the heap. Sometimes you can use a better algorithm if you use the heap.faster, or more robust, or more flexible. It's a tradeoff.
If memory is allocated from the heap, it.s available until the program ends. That's great if you remember to deallocate it when you.re done.
19)n++ takes more than one instruction, ++n is faster. n++ has to store n, increment the variable and return n, while ++n increment n and return without storing the previous value of n.
20) If a program is large, it is subdivided into a number of smaller programs that are called modules or subprograms. If a complex problem is solved using more modules, this approach is known as modular programming.
21)expression if (a=0) always return false
expression if (a=1) always return true
22)Malloc is dynamic memory allocation,it allocates the memory and initialize garbage value.Calloc is similar to malloc but only difference is initialize zero
23)A middle level language
24)Overloading is polymorphism which is one of the characteristics of Object oriented programming. C is not and object oriented language like C++ or Java. Therefore, no overloading, inheritance, etc.
25)Static int variable are accessed only inside the file where it is defined. Thus we can have same variable name in 2 files if the variable is defined as static. The scope of the variable is limited to the file in which it is defined.
On the other hand if the variable is not defined as static and defined globally then it can be accessed across the files. To access the variable which is global variable and declared and defined in file A, keyword "extern" is used in front of the variable in file B. This indicated to compiler while compiling that the variable is defined in some other file other than B and continues compiling and while linking the variable it search for the actual definition and links.
1)To check for it, create two pointers,and set each to the start of the list. Update each as follows:
while (pointer1) {
pointer1 = pointer1->next;
pointer2 = pointer2->next;
if (pointer2) pointer2=pointer2->next;
if (pointer1 == pointer2) {
print ("circular linked list\n");
}
}
2)Union x : 1101791232 21.500000
Union y : 100 d 0.000000
3)It is an object of some class whose purpose is to indicate that a real object of that class does not exist. One common use for a null object is a return value from a member function that is supposed to return an object with some specified properties but cannot find such an object.
4) Java,Smalltalk,Eiffel,Sather.
5)A container class is a class that is used to hold objects in memory or
external storage. A container class acts as a generic holder. A
container class has a predefined behavior and a well-known interface. A
container class is a supporting class whose purpose is to hide the
topology used for maintaining the list of objects in memory. When a
container class contains a group of mixed objects, the container is
called a heterogeneous container; when the container is holding a group
of objects that are all the same, the container is called a homogeneous
container.
6)fffffff0
7)C was the C++ predecessor. As it's name implies, a lot of C remains in C++. Although not actually being more powerful than C, C++ allows the programmer to more easily manage and operate with Objects, using an OOP (Object Oriented Programming) concept.
C++ allows the programmer to create classes, which are somewhat similar to C structures. However, to a class can be assigned methods, functions associated to it, of various prototypes, which can access and operate within the class, somewhat like C functions often operate on a supplied handler pointer.
Although it is possible to implement anything which C++ could implement in C, C++ aids to standarize a way in which objects are created and managed, whereas the C programmer who implements the same system has a lot of liberty on how to actually implement the internals, and style among programmers will vary a lot on the design choices made.
In C, some will prefer the handler-type, where a main function initializes a handler, and that handler can be supplied to other functions of the library as an object to operate on/through. Others will even want to have that handler link all the related function pointers within it which then must be called using a convention closer to C++.
To finish this discussion, C++ applications are generally slower at runtime, and are much slower to compile than C programs. The low-level infrastructure for C++ binary execution is also larger. For these reasons C is always commonly used even if C++ has alot of popularity, and will probably continue to be used in projects where size and speed are primary concerns, and portable code still required (assembly would be unsuitable then).
8)Incomplete types
refers to pointers in which there is non availability of the
implementation of the referenced location or it points to some location
whose value is not available for modification.
int *i=0x400 // i points to address 400
*i=0; //set the value of memory location pointed by i.
9)Printf : Call by value
Scanf : Call by reference
10)a const pointer means the pointer which represents the address of one value. so if you declare a pointer inside the function, it doesn't have scope outside the function. if it is also available to the outside function whenever we declare a pointer as const.
11)Type casting must be done wheneever the data type of the variable to which u r gonna assign some values is diff from the data type of the variable on the right side.
for instance;
float f;
int i = 10 , j = 5 ;
f = (float) ( i / j ) ;
f -------> left side variable.
i -------> right side variable.
but always make sure that the size of the var on the left is greater than that of the right. else there will be data loss.
A type cast should not be used to override a const or volatile declaration. Overriding these type modifiers can cause the program to fail to run correctly.
A type cast should not be used to turn a pointer to one type of structure or data type into another. In the
rare events in which this action is beneficial, using a union to hold the values makes the programmer.s
intentions clearer.
12)he answer is the standard library function qsort(). It.s the easiest sort by far for several reasons:
It is already written.
It is already debugged.
It has been optimized as much as possible (usually).
Void qsort(void *buf, size_t num, size_t size, int (*comp)(const void *ele1, const void *ele2));
13)The answer depends on what you mean by quickest. For most sorting problems, it just doesn't matter how quick the sort is because it is done infrequently or other operations take significantly more time anyway. Even in cases in which sorting speed is of the essence, there is no one answer. It depends on not only the size and nature of the data, but also the likely order. No algorithm is best in all cases.
There are three sorting methods in this author.s .toolbox. that are all very fast and that are useful in different situations. Those methods are quick sort, merge sort, and radix sort.
The Quick Sort
The quick sort algorithm is of the .divide and conquer. type. That means it works by reducing a sorting
problem into several easier sorting problems and solving each of them. A .dividing. value is chosen from the input data, and the data is partitioned into three sets: elements that belong before the dividing value, the value itself, and elements that come after the dividing value. The partitioning is performed by exchanging elements that are in the first set but belong in the third with elements that are in the third set but belong in the first Elements that are equal to the dividing element can be put in any of the three sets.the algorithm will still work properly.
The Merge Sort
The merge sort is a .divide and conquer. sort as well. It works by considering the data to be sorted as a
sequence of already-sorted lists (in the worst case, each list is one element long). Adjacent sorted lists are merged into larger sorted lists until there is a single sorted list containing all the elements. The merge sort is good at sorting lists and other data structures that are not in arrays, and it can be used to sort things that don.t fit into memory. It also can be implemented as a stable sort.
The Radix Sort
The radix sort takes a list of integers and puts each element on a smaller list, depending on the value of its least significant byte. Then the small lists are concatenated, and the process is repeated for each more significant byte until the list is sorted. The radix sort is simpler to implement on fixed-length data such as ints.
14)Both the merge sort and the radix sort are good sorting algorithms to use for linked lists.
15)The preprocessor is used to modify your program according to the preprocessor directives in your source code. Preprocessor directives (such as #define) give the preprocessor specific instructions on how to modify your source code. The preprocessor reads in all of your include files and the source code you are compiling and creates a preprocessed version of your source code. This preprocessed version has all of its macros and constant symbols replaced by their corresponding code and value assignments. If your source code contains any conditional preprocessor directives (such as #if), the preprocessor evaluates the condition and modifies your source code accordingly.
The C preprocessor is used to modify your program according to the preprocessor directives in your source code. A preprocessor directive is a statement (such as #define) that gives the preprocessor specific instructions on how to modify your source code. The preprocessor is invoked as the first part of your compiler program.s compilation step. It is usually hidden from the programmer because it is run automatically by the compiler.
16)The standard C library provides several functions for converting strings to numbers of all formats (integers, longs, floats, and so on) and vice versa.
The following functions can be used to convert strings to numbers:
Function Name Purpose
atof() Converts a string to a double-precision floating-point value.
atoi() Converts a string to an integer.
atol() Converts a string to a long integer.
strtod() Converts a string to a double-precision floating-point value and reports any .leftover. numbers that could not be converted.
strtol() Converts a string to a long integer and reports any .leftover. numbers that could not be converted.
strtoul() Converts a string to an unsigned long integer and reports any .leftover. numbers that could not be converted.
17)
The standard C library provides several functions for converting numbers of all formats (integers, longs, floats, and so on) to strings and vice versa
The following functions can be used to convert integers to strings:
Function Name Purpose
itoa() Converts an integer value to a string.
ltoa() Converts a long integer value to a string.
ultoa() Converts an unsigned long integer value to a string.
The following functions can be used to convert floating-point values to strings:
Function Name Purpose
ecvt() Converts a double-precision floating-point value to a string without an embedded decimal point.
fcvt() Same as ecvt(), but forces the precision to a specified number of digits.
gcvt() Converts a double-precision floating-point value to a string with an embedded decimal point.
18)The heap is where malloc(), calloc(), and realloc() get memory.
Getting memory from the heap is much slower than getting it from the stack. On the other hand, the heap
is much more flexible than the stack. Memory can be allocated at any time and deallocated in any order. Such
memory isn't deallocated automatically; you have to call free().
Recursive data structures are almost always implemented with memory from the heap. Strings often come
from there too, especially strings that could be very long at runtime. If you can keep data in a local variable (and allocate it from the stack), your code will run faster than if you put the data on the heap. Sometimes you can use a better algorithm if you use the heap.faster, or more robust, or more flexible. It's a tradeoff.
If memory is allocated from the heap, it.s available until the program ends. That's great if you remember to deallocate it when you.re done.
19)n++ takes more than one instruction, ++n is faster. n++ has to store n, increment the variable and return n, while ++n increment n and return without storing the previous value of n.
20) If a program is large, it is subdivided into a number of smaller programs that are called modules or subprograms. If a complex problem is solved using more modules, this approach is known as modular programming.
21)expression if (a=0) always return false
expression if (a=1) always return true
22)Malloc is dynamic memory allocation,it allocates the memory and initialize garbage value.Calloc is similar to malloc but only difference is initialize zero
23)A middle level language
24)Overloading is polymorphism which is one of the characteristics of Object oriented programming. C is not and object oriented language like C++ or Java. Therefore, no overloading, inheritance, etc.
25)Static int variable are accessed only inside the file where it is defined. Thus we can have same variable name in 2 files if the variable is defined as static. The scope of the variable is limited to the file in which it is defined.
On the other hand if the variable is not defined as static and defined globally then it can be accessed across the files. To access the variable which is global variable and declared and defined in file A, keyword "extern" is used in front of the variable in file B. This indicated to compiler while compiling that the variable is defined in some other file other than B and continues compiling and while linking the variable it search for the actual definition and links.
Subscribe to:
Posts (Atom)