Aashish
BAN USER
- 0of 0 votes
AnswersGive a good data structure for having n queues ( n not fixed) in a finite memory segment. You can have some data-structure separate for each queue. Try to use at least 90% of the memory space
- Aashish in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersYou are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs.
- Aashish in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
Answersyou are given a system of passing binary trees among 2 ppl
- Aashish in India
Step1: convert the tree to preorder and inorder strings
Step2:send those strings to the intended person
Step3:get back tree from the strings
whats your strategy of testing?write various test scenarios.---10 marks| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer - 0of 0 votes
AnswersWe have a text editor application where we can choose 1)between 100s of
- Aashish in India
different fonts like arial, calibri, etc.. 2)different text sizes 3) different formatting such as bold, Italics, regular, etc..
Imagine that the application is similar to word(there we will have these options). Now give different test cases to test this application.| Report Duplicate | Flag | PURGE
Microsoft Software Development Manager - 0of 0 votes
AnswersTest cases for finger print reader say in a laptop to login. Here you can swipe your finger to have a secured login. e.g. I will swipe my finger and the system will allow me to login.
- Aashish in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test Testing - 0of 0 votes
AnswersGiven an array of 32bit unsigned integers in which every number appears exactly twice except three of them, find those three numbers in O(n) time using O(1) extra space. The input array is read-only. What if there are k exceptions instead of 3?
- Aashish in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.
- Aashish in United States| Report Duplicate | Flag | PURGE
Facebook Software Engineer / Developer Algorithm - 3of 3 votes
AnswersGiven a circular single linked list.Write a program that deletes every kth node until only one node is left.
- Aashish in India
After kth node is deleted, start the procedure from (k+1)th node.
e.g.list is 1->2->3->4->5->1
k=3
1. You are at 1, delete 3.
List is: 1->2->4->5->1
2. You are at 4, delete 1
List is: 2->4->5->2
3. You are at 2,delete 5
List is: 2->4->2
4. You are at 2, delete 2
List is: 4
Return 4.
How efficient you can do it?| Report Duplicate | Flag | PURGE
Amazon Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDesign the Class diagram for vending machine for Tea & Coffee. This machine can generate the diff type of tea like Cardemom, Elichi, Ginger. Same way 3 type of coffee. The thing is when you make the tea or coffee user can add n number of flavors like sugar, honey or etc.
- Aashish in India| Report Duplicate | Flag | PURGE
InMobi Software Engineer / Developer Application / UI Design - 0of 0 votes
AnswersRemove duplicates from min-heap.
- Aashish in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat is wrong with the below code?
- Aashish in India#include <iostream> #include <string.h> using namespace std; class A { char *p; public: A(const char* str) { p=new char[strlen(str)+1]; strcpy(p,str); } ~A() { delete p; } }; int main() { A s("Object s"); A t=s; s.~A(); A u("Object u"); u=s; return 0; }
| Report Duplicate | Flag | PURGE
Sap Labs Software Engineer / Developer Algorithm - 0of 0 votes
Answers
- Aashish in Indiavoid freeList( struct node *n ) { while( n ) {????} } Which one of the following can replace the ???? for the function above torelease the memory allocated to a linked list? Choice 1 n = n->next; free( n ); Choice 2 struct node m = n; n = n->next; free( m ); Choice 3 struct node m = n; free( n ); n = m->next; Choice 4 free( n ); n = n->next; Choice 5 struct node m = n; free( m ); n = n->next;
| Report Duplicate | Flag | PURGE
Aricent Software Engineer / Developer Algorithm - 0of 0 votes
Answersvoid *ptr;
- Aashish in United States
myStruct myArray[10];
ptr = myArray;
Which of the following is the correct way to increment the variable "ptr"?
Choice 1 ptr = ptr + sizeof(myStruct);
Choice 2 ++(int*)ptr;
Choice 3 ptr = ptr + sizeof(myArray);
Choice 4 increment(ptr);
Choice 5 ptr = ptr + sizeof(ptr);| Report Duplicate | Flag | PURGE
Aricent Software Engineer / Developer Algorithm - 4of 8 votes
AnswersDesign an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )
- Aashish in India
You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 0of 0 votes
AnswersIf i type some numbers in my cell, all phone numbers which have these typed nos in any order should appear, tell data structure for this.
- Aashish in United States
eg:if i type 926 then
932678....
92678...
9777726....
should appear.
[EDIT]: It seems you have lot of confusion.
Let me clear it through another example
eg: i enter 321, then
o/p(if they r in book)
9344241..
972153....| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Data Structures - 0of 0 votes
AnswersGiven a set of data ranges (i.e. 2-7, 5-9, 10-20), write a function to determine if there is any overlap within the set. Write test cases. Which data structure would be best to represent the intervals.
- Aashish in India| Report Duplicate | Flag | PURGE
Microsoft Software Engineer in Test - 2of 2 votes
AnswersDoes it always happen that stack always grows downwards & heap grows upwards?
- Aashish in India
If its so, then how does OS keeps the heap area protected from the interference of the stack & vice-versa?
If its not, then what factors affect it? OS version ? Compiler? Anything else??| Report Duplicate | Flag | PURGE
Microsoft Software Engineer / Developer Operating System
Use modified Inorder traversal.
correctBST(root)
{
static Node* temp1,*temp2,*prev;
static int found;
if(root)
{
correctBST(root->left);
if(!temp1 && prev && root->data<prev->data)
{
temp1=prev;
temp2=root;
}
else if(prev && root->data<prev->data)
temp2=root;
else if(temp1 && temp2 && !found)
{
swap(&(temp1->data),&(temp2->data));
found=1;
return;
}
prev=root;
correctBST(root->right);
}
}
LCA(root,a,b)
{
if(a==root || b==root) return root;
if(a->data < root->data && b->data < root->data)
return LCA(root->left,a,b);
if(a->data > root->data && b->data > root->data)
return LCA(root->right,a,b);
return root;
}
CountHops(root,a,b)
{
if(!root || !a || !b) return INT_MIN;
temp=LCA(root,a,b);
hopa=-1;hopb=-1;
p=temp;
while(p!=a)
{
if(a->data < p->data)
p=p->left;
else
p=p->right;
hopa++;
}
p=temp;
while(p!=b)
{
if(b->data < p->data)
p=p->left;
else
p=p->right;
hopb++;
}
return hopa + hopb + 1;
}
1. Yes, you have a good thought. Three positions are redundant to check. These are (-1,-1),(-1,0) and (0,-1).
2. static is chosen to avoid the memory allocation in each recursion. Yes, we can make them global. But, r[] & c[] are needed in this function only. So, static.
3. Yes, i am modifying the original input here. If we are not allowed to modify it, sure, take an auxiliary visited array. .
Choose a slot with value 1, Perform DFS from here & set all slots to 0 while visiting to avoid them in the further visits.
int isSafe(int (*M)[COL],int r,int c)
{
return r>=0 && r<ROW && c>=0 && c<COL && M[r][c];
}
void DFS(int (*M)[COL],int i,int j)
{
static int r[]={-1,-1,-1,0,0,1,1,1};
static int c[]={-1,0,1,-1,1,-1,0,1},k;
M[i][j]=0;
for(k=0;k<8;++k)
if(isSafe(M,i+r[k],j+c[k]))
DFS(M,i+r[k],j+c[k]);
}
int countImage(int (*M)[COL])
{
int count=0,i,j;
for(i=0;i<ROW;i++)
for(j=0;j<COL;j++)
if(M[i][j])
{
DFS(M,i,j);
count++;
}
return count;
}
Complete working code: ideone.com/RhZcU
- Aashish July 25, 2012I would just say how is the tree implemented?
1. Using child-sibling concept?
2. Using only child concept & no sibling?
my_delete(root) //case 1
{
if(root)
{
my_delete(root->child);
my_delete(root->sibling);
free(root);
}
}
Assume N -ary tree.
my_delete(root) //case 2
{
if(root)
{
for(i=0;i<N;i++)
my_delete(root->child[i]);
free(root);
}
}
A brief description of Pointers vs References.
1. Memory is allocated when a pointer is defined. A reference however, is a name alias & hence no memory is allocated for it[in most of the cases, memory is not allocated. However it is implementation defined.The compiler might be able to avoid storing the address, if it's a reference to local object for instance.].
2. Reference is bound to be initialized at the time of definition because, a reference is implemented with a constant pointer & hence cannot be made to point to the other object.
A pointer however, is not necessary to be initialized at the time of definition & hence can also be changed to point to some other object.
3. A reference automatically gets de-referenced. When you write cout<<p;
It is automatically de-referenced by the compiler & treated as cout<<*p; by the compiler.
Here, p is the reference.
4. A reference to a reference is not possible.Whenever, you declare a reference to a reference, its actually the reference to the same variable.
e.g.
int i;
int &r1=i;
int &r2=r1; <-------------------2
Compiler interprets the statement 2 as:
int &r2=(*r1)
and (*r1) is nothing but the variable i itself.
A pointer to a pointer is however possible.
5. Array of pointer is possible while array of references is not possible(Why?).
6. Address of pointer is possible. Address of reference is not possible. It gives of the address of the variable.
7. There are situations where you are bound to use references.You cannot use pointers there.
Consider the below example:
A a=b+c;
Where a,b,c are objects of class A.
The operator '+' is overloaded as follows:
const A& operator+(const A& o)
{
return A(i+o.i);
}
See sample code here: ideone.com/Q0pE1
Here the reference in the argument list is used to save the memory footprints.
You cannot use pointer in the argument list as you are bound to pass the address of object in the operator function.
A a=&b + &c;
However, if pointer is used in the parameter list, then we will end up adding the addresses rather than object itself.
Any other reason??
Use DP.
void foo(int n)
{
static int ind2,ind3,ind5;
static int arr[30],depth;
int num2,num3,num5,num,flag=0;
if(n<=0) return;
if(depth==0)
{
ind2=ind3=ind5=0;// i know this is redundant
arr[depth++]=1;
}
num2=arr[ind2]*2;
num3=arr[ind3]*3;
num5=arr[ind5]*5;
num=min(num2,min(num3,num5));
if(num==num2)
{
ind2++;
if(arr[depth-1]!=num2)
{
flag=1;
printf("%d\n",arr[depth-1]);
arr[depth++]=num2;
}
}
else if(num==num3)
{
ind3++;
if(arr[depth-1]!=num3)
{
flag=1;
printf("%d\n",arr[depth-1]);
arr[depth++]=num3;
}
}
else
{
ind5++;
if(arr[depth-1]!=num5)
{
flag=1;
printf("%d\n",arr[depth-1]);
arr[depth++]=num5;
}
}
if(flag)
foo(n-1);
else
foo(n);
}
Complete working code: ideone.com/qz4Py
It prints first n ugly numbers.
Note: I have also considered 1 as part of the ugly number series.
void foo(int* arr,int size)
{
int i=0,j=size-1;
while(i<j)
{
if(i&1)
{
if(!(arr[i]&1))
{
while(!(arr[j]&1)) j--;
arr[i]^=1;
arr[j]^=1;
}
}
else
{
if(arr[i]&1)
{
while(arr[j]&1) j--;
arr[i]^=1;
arr[j]^=1;
}
}
i++;
}
for(i=0;i<size;i++)
printf("%d ",arr[i]);
}
Complete code here: ideone.com/HHAja
- Aashish July 24, 2012int findMSBPos(int n)
{
int count=0;
while(n)
{
count++;
n>>=1;
}
return count;
}
int countSetBits(int n)
{
int pos,num;
if(!n) return 0;
pos=findMSBPos(n);
num=1<<(pos-1);
return ((num*(pos-1))>>1) + (n-num+1) + countSetBits(n&~(1<<(pos-1)));
}
Complete code here: ideone.com/yHSNA
- Aashish July 24, 2012One can also go for TRIE. Store all the 100 words in TRIE in sorted form.
As a new word comes, search for its sorted sequence in the TRIE.
The time complexity would be O(length of the word to be searched).
However, it is space consuming.Ternary search trees can be used to reduce the space..
Use DP.
void foo(int n)
{
static int ind2,ind3,ind5;
static int arr[30],depth;
int num2,num3,num5,num,flag=0;
if(n<=0) return;
if(depth==0)
{
ind2=ind3=ind5=0;// i know this is redundant
arr[depth++]=1;
}
num2=arr[ind2]*2;
num3=arr[ind3]*3;
num5=arr[ind5]*5;
num=min(num2,min(num3,num5));
if(num==num2)
{
ind2++;
if(arr[depth-1]!=num2)
{
flag=1;
printf("%d\n",arr[depth-1]);
arr[depth++]=num2;
}
}
else if(num==num3)
{
ind3++;
if(arr[depth-1]!=num3)
{
flag=1;
printf("%d\n",arr[depth-1]);
arr[depth++]=num3;
}
}
else
{
ind5++;
if(arr[depth-1]!=num5)
{
flag=1;
printf("%d\n",arr[depth-1]);
arr[depth++]=num5;
}
}
if(flag)
foo(n-1);
else
foo(n);
}
Complete working code: ideone.com/qz4Py
It prints first n ugly numbers.
Are we allowed to move balls between the jars?
Edit: Fresh Solution
Let P(1) is probability of choosing jar 1,
P(2) is probability of choosing jar 2,
X is the probability of choosing a red ball in jar1.
Y is the probability of choosing a red ball in jar2.
Total probability= P(1)*X + P(2)*Y
Where P(1)=P(2)=1/2
What is the maximum number of balls a jar can have??
If its 100, move 49 red balls from jar1 to jar2.
Now, jar 1 contains 1 red ball & jar 2 contains 50 blue balls & 49 red balls.
Total probability of drawing a red ball is 1/2 + 0.5*49/99= 74/99=74.74%
Suppose node p is to be deleted.
if(!(p->next)) {free(p); return; }
while(p->next)
{
p->data=p->next->data;
if(p->next->next)
p=p->next;
else
break;
}
free(p->next);
p->next=NULL;
This won't work if the node to be deleted is the last node.This problem can be easily solved with the help of dummy node.
void HuffmanTraverse(struct node* root,int* arr,int depth)
{
int i;
if(root)
{
if(root->left)
{
arr[depth]=0;
HuffmanTraverse(root->left,arr,depth+1);
}
if(!(root->left || root->right))
{
printf("%d: ",root->data);
for(i=0;i<depth;i++)
printf("%d",arr[i]);
printf("\n");
}
if(root->right)
{
arr[depth]=1;
HuffmanTraverse(root->right,arr,depth+1);
}
}
}
Complete code here: ideone.com/FHzHI
- Aashish July 24, 2012a) int temp=a;
a=b;
b=temp;
b) a=(a+b)-(b=a)
c) a^=b^=a^=b
The first method can be used even with user defined type however, it takes a temp variable.
The second method doesn't work with user defined types as arithmetic is not possible in case of user defined types.. However, after overloading arithmetic operator[like in C++], it is possible.
The third method is the best as it works on the bits at H/W level & thus doesn't require any temporary register. It thus, guarantees faster operation. However, it fails when the situation needs swapping user defined types.
@ eugene.yarovoi, there seems to be issues with the binary search also.
Suppose, we want to perform binary search in a 2D array which is sorted row-wise as well as column wise.
------------
| 1 | 2 |
| | |
|----X-----|
| 3 | 4 |
| | |
------------
Suppose the middle element is X. If the item to be found is less than X, only part 1 needs to be searched. However, if the item is larger than X, all the parts 2,3,& 4 need to be searched.
So, the array is not equally distributed in two halves as mentioned in the approach.
What do you think?
Steps:
1. Take two auxiliary arrays r[] & c[].
r[i] would be containing the column number of the largest number in the row i.
c[i] would be containing the row number of the smallest number in the column i.
Now find a i such that arr[i][r[i]] is equal to arr[col[j]][j].
This would give the intersection of the row having largest number with column having minimum number.
Here is the sample code:
void foo(int (*arr)[COL])
{
int r[ROW],c[COL],i,j,max;
for(i=0;i<ROW;i++)
{
max=0;
for(j=0;j<COL;j++)
if(arr[i][j]>arr[i][max])
max=j;
r[i]=max;
}
for(i=0;i<COL;++i)
{
max=0;
for(j=0;j<ROW;++j)
if(arr[j][i]<arr[max][i])
max=j;
c[i]=max;
}
for(i=0;i<ROW;++i)
for(j=0;j<COL;++j)
if(arr[i][r[i]]==arr[c[j]][j])
printf("%d ",arr[i][r[i]]);
}
Complete code here: ideone.com/1OYSZ
- Aashish July 23, 2012First of all, What is the difference between mutex & semaphore.
Binary semaphore is also called MUTEX as per their values but their purposes are different..
Semaphore is used for signalling purpose. A thread waiting for a semaphore might be signalled by the other thread.
Mutex is used for Blocking purpose.
Mutex is used to provide synchronization on same block of code.
An ownership kind of thing is attached with a MUTEX. The lock is released by the object which has acquired it.
While semaphore is used to control the access to finite number of resources.
Since, here is only queue,
Hence, i feel that MUTEX would be a better choice.
A recursive approach:
void print(int* res,int depth)
{
int i;
for(printf("\n"),i=0;i<depth;printf("%d ",res[i]),++i);
}
void foo(int sum,int N,int* res,int depth)
{
int i;
if(sum<0) return;
if(!sum)
print(res,depth);
else
for(i=1;i<N;i++)
if(!depth || i>=res[depth-1])
{
res[depth]=i;
foo(sum-i,N,res,depth+1);
}
}
Complete code here: ideone.com/z2rcm
- Aashish July 22, 2012Good answers.
However, some points are missing. I am re-writing including the missing ones.
1. Memory is allocated when a pointer is defined. A reference however, is a name alias & hence no memory is allocated for it.
2. Reference is bound to be initialized at the time of definition because, a reference is implemented with a constant pointer & hence cannot be made to point to the other object.
A pointer however, is not necessary to be initialized at the time of definition & hence can also be changed to point to some other object.
3. A reference automatically gets de-referenced. When you write cout<<p;
It is automatically de-referenced by the compiler & treated as cout<<*p; by the compiler.
Here, p is the reference.
4. A reference to a reference is not possible.Whenever, you declare a reference to a reference, its actually the reference to the same variable.
e.g.
int i;
int &r1=i;
int &r2=r1; <-------------------2
Compiler interprets the statement 2 as:
int &r2=(*r1)
and (*r1) is nothing but the variable i itself.
A pointer to a pointer is however possible.
5. Array of pointer is possible while array of references is not possible(Why?).
6. Address of pointer is possible. Address of reference is not possible. It gives of the address of the variable.
7. There are situations where you are bound to use references.You cannot use pointers there.
Consider the below example:
A a=b+c;
Where a,b,c are objects of class A.
The operator '+' is overloaded as follows:
const A& operator+(const A& o)
{
return A(i+o.i);
}
See sample code here: ideone.com/Q0pE1
Here the reference in the argument list is used to save the memory footprints.
You cannot use pointer in the argument list as you are bound to pass the address of object in the operator function.
A a=&b + &c;
However, if pointer is used in the parameter list, then we will end up adding the addresses rather than object itself.
Any other difference??
There are multiple ways.
1. Use vector STL.
class A
{
int p;
public:
A(int i)
{
p=i;
cout<<"Called"<<endl;
}
A(const A & rhs) :p(rhs.p) {
cout << "Copied\n";
}
};
int main()
{
vector<A> v(5,A(1));<-------5 objects are constructed.
return 0;
}
output here: ideone.com/lHX5W
2. Call constructor for each object.
A arr[3]={A(1),A(2),A(3)};
This would be better if we want to initialize different objects with different values.
The first object is initialized with1, second with 2 & so on.
However,in the first method using vector, only one object is constructed & initialized with 1 [in our case], & copy constructor is called 5 times to copy that object.
O(N^2) approach
For each 2D array, search an item in O(N).
How?
Let the matrix be ABCD sorted from A to B & from A to C & C to D & B to D.
A B
------------
| |
| |
------------
C D
Start searching the item at point C. If the item is greater,we can ignore the column AC. If its less, we can ignore row CD.
In this way, based on the comparison one of the row or column gets rejected. So, time complexity will be O(N+N)=O(N).
1. Take an auxiliary array & copy all the strings of the original array.
2. Sort each of the string in auxiliary array.
3. Take another auxiliary array keeping track of the indices of the original array.
4. Sort auxiliary array & simultaneously change the index array.
5. Print the original array according to the index array[while checking contents of the auxiliary array, we want only anagrams right.].
Time complexity: O(N*d*log N)
where d is the max number of chars in a string.
EDIT:
Taking an example:
Lets say, the array contains "abc","abd","bac","bca"
Aux array after sorting each slot: "abc","abd","abc","abc"
The index array would be: 0,1,2,3
After sorting aux array: "abc","abc","abc","abd"
Corresponding Index array: 0,2,3,1
Print Original array a/c to Index array:
abc[at index 0]
bac[at index 2]
bca[at Index 3]
Don't print "abd" [Index 1], it hasn't any anagram.
Exhaustive backtracking approach:
void foo(int* arr,int k,int* res,int depth,int N,int sum,int dec)
{
int i;
if(sum>N) return;
if(depth==k)
{
if(sum==N)
print(res,N);
}
else
{
if(dec<N)
{
if(!res[dec])
{
res[dec]=1;
foo(arr,k,res,depth+1,N,sum+arr[dec],dec+1);
res[dec]=0;
foo(arr,k,res,depth,N,sum,dec+1);
}
}
}
}
Complete code here: ideone.com/BeAnJ
- Aashish July 21, 2012Take a double linked list. The head will always contain the most recently used page & tail will contain the least recently page..
A hash where page number will be used for indexing will be taken. Whenever, a page fault occurs i.e. page is not in the memory[the hash slot will be empty], We will create a new node in DLL, put it in the head & store its pointer in the hash.
At any time, if a page needs to be referenced, it will be searched in the hash. If its there, we need to change at most 6 pointers to attach it at the head of DLL.
reqPage->next->prev=reqPage->prev;
reqPage->prev->next=reqPage->next;
reqPage->next=head;
reqPage->prev=NULL;
head->prev=reqPage;
head=reqPage;
void print(char* op,int depth)
{
int i;
for(i=0;i<depth;++i)
printf("%c ",op[i]);
}
int calculate(int* arr,int size,char* op,int depth,int result,int val)
{
if(depth==size)
{
if(val==result)
{
print(op,depth);
printf("\n");
return 1;
}
}
else
{
op[depth]='+';
calculate(arr+1,size,op,depth+1,result,val+*arr);
op[depth]='-';
calculate(arr+1,size,op,depth+1,result,val-*arr);
op[depth]='*';
if(val)
calculate(arr+1,size,op,depth+1,result,val*(*arr));
op[depth]='/';
if(*arr && val)
calculate(arr+1,size,op,depth+1,result,val/(*arr));
}
}
Complete code here: ideone.com/XDML8
- Aashish July 20, 2012int findTriplet(int *arr,int size)
{
int a,b,c;
c=size-1;
while(c>1)
{
a=0;b=c-1;
while(a<b)
{
if(arr[a]*arr[a]+arr[b]*arr[b]==arr[c]*arr[c])
{
printf("%d %d %d\n",arr[a],arr[b],arr[c]);
a++;b--;
}
else if(arr[a]*arr[a]+arr[b]*arr[b]<arr[c]*arr[c])
a++;
else
b--;
}
c--;
}
}
Complete code here: ideone.com/Z3B5O
- Aashish July 20, 2012struct node* trim(struct node* root,int A,int B)
{
struct node* temp;
if(root)
{
if(root->data>=A && root->data<=B)
{
root->left=trim(root->left,A,B);
root->right=trim(root->right,A,B);
return root;
}
else if(root->data<A)
{
temp=root->right;
free(root);
return trim(temp,A,B);
}
else if(root->data>B)
{
temp=root->left;
free(root);
return trim(temp,A,B);
}
}
else
return NULL;
}
Complete code here: ideone.com/xHclt
- Aashish July 19, 2012Say, we know the number of coins required for n-1, we can extend it for n also.
1. Take a minCount array. If minCount[i]==j, then minimum of j number of coins are required for i.
void countCoins(int* coin,int size,int tofind)
{
int minCount[tofind+1],i,j,mintillnow;
for(i=0;i<tofind+1;++i)
minCount[i]=0;
for(i=0;i<size;i++)
if(coin[i]<=tofind)
minCount[coin[i]]=1;
for(i=1;i<=tofind;i++)
{
if(!minCount[i])
{
mintillnow=INT_MAX;
for(j=1;j<i;++j)
{
if(minCount[j]+minCount[i-j]<mintillnow)
mintillnow=minCount[j]+minCount[i-j];
}
minCount[i]=mintillnow;
}
}
printf("Minimum number of coins needed is: %d",minCount[tofind]);
}
The only disadvantage of this method is that it may require large amount of space.
e.g. we may need change of Rs 1 lakh[space required is 1lakh bytes]. However, it can be reduced if we go for bit-vector.
Complete code here: ideone.com/pKEwC
- Aashish July 29, 2012