Tulley
BAN USERMore over:
below is the code for coin denomination which prints the optimal solution by remembering that at sum i which coin was used.
#include <stdio.h>
#include <stdlib.h>
#define MAX (1<<(sizeof(int)-1))
void coinDenomination (int* pDenomination, int size, int sum)
{
int AllDenom[100] = {0};
int prev[100] = {0};
int i,j,index,curSum=sum, prevSum=0;
for(i=0;i<sum+1;i++)
{
AllDenom[i] = MAX;
}
AllDenom[0]=0;
for(i=1;i<sum+1;i++)
{
for(j=1;j<size+1;j++)
{
if(i>=pDenomination[j-1])
{
if((AllDenom[i-pDenomination[j-1]] + 1) < (AllDenom[i]))
{
AllDenom[i] = AllDenom[i-pDenomination[j-1]] + 1;
prev[i]=j-1;
}
}
}
}
printf("Num Of Coins:[%d]\n",AllDenom[sum]);
printf("Coins:");
for(index = prev[sum];curSum>0;)
{
prevSum = curSum;
printf("[%d]", pDenomination[index]);
curSum = curSum-pDenomination[index];
index = prev[prevSum-pDenomination[index]];
}
printf("\n");
}
int main ()
{
int denom[]={1,3,5,6,25};
int amount;
scanf("%d",&amount);
coinDenomination(denom,sizeof(denom)/sizeof(int),amount);
return 0;
}
@above:
its good that lol is not giving the solution. I suggest everyone to try, try n try, and not only here, in the interview also.
remembering the sequence of decisions and printing them is always tricky in DP, but u have to do it if u want to learn DP and there is no limit of DP.
I suggest that to learn DP first create a recursive solution, then use memoization (by Hash or what ever u want) and try to achieve same solution, then use as many space as u want and try to achieve again same solution and at last try to think if u can reduce the space in your previous solution, if u arrived.
you can follow these which i feel is very very good:
www(.)youtube.com/watch?v=6h6Fi6AQiRM&list=PL7DC83C6B3312DF1E
and other useful stuffs:
www(.)nptel.iitm.ac.in/
Follow completely with patience.
:)
Proof for second idea given by lol.
Let counting starts from 0 from LSB in binary
representation of given number.So in this manner
Let number of 1s at odd positions is Xd.
Let number of 1s at even postions is Xn.
Then the number can be represented as
i j
N=Sumation(2) + Sumation(2)
i=d1,d2..Xd j=e1,e2..Xn
d1,d2.. are odd positions with 1
e1,e2.. are even positions with 1.
now all even power of 2 can be written as 3p+1 and all odd
powers of 2 can be written as 3q+2. (deduce it by urself).
Therfore we have:
N=Sumation(3q+2) + Sumation(3p+1)
i=d1,d2..Xd j=e1,e2..Xn
So N can be represented as:
N = (3M+2Xd) + (3P+Xn)
N = 3(P+M)+2Xd+Xn
N = 3(P+M+Xd)+Xn-Xd
Therfore N is divisible by 3 if (Xn-Xd) is divisible by 3.
This can be implimented very easily.
Please refer below blog:
igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/
"Branches (i.e. conditional jumps) present a difficulty for the processor pipeline. After fetching a branch instruction, the processor needs to fetch the next instruction. But, there are two possible “next” instructions! The processor won’t be sure which instruction is the next one until the branching instruction makes it to the end of the pipeline."
I'm convinced with this blog and hope the interviewer wanted to listen the same.
I don't know if the complexity can be represented in terms of given input number. if the number is N and its prime factorization is:
k1 k2 kr
N=[P1] * [P2].........[Pr]
where P1, P2 ...Pr are primes,
then the total number of divisors is (1+k1)*(1+k2)*...*(1+kr).
So to determine total number of divisors we must know k1,k2....kr. and to determine this we must repeatedly divide the numbers by the primes <= sqrt(number). So the time complexity is O((k1+k2+...+kr)*sqrt(N)).
Notice here that I am giving it in Big O because in few cases we need not to loop till sqrt(N), we can break in between if the number has already become 1 by successive devision.
Comments are welcome :)
@Sanjay:
How can you say that probability of opening the door is 1/16. You calculated when every body inside the room open the door at the same time.
Probability of getting in is that at least one person opens the door which is same as (1-p(no body opens the door)). So in my opinion AK is correct.
I am also saying the same. All possible combinations not the "Number of combinations" :).
Below is the code for your reference:
void coinDenomination (int sum,int index, int count, int size, int* pAllDenom, int* pDenomArray)
{
if(count<size)
{
if(sum<0)
{
return;
}
if(sum==0)
{
int m;
for(m=0;m<index;m++)
printf("[%d]", pAllDenom[m]);
printf("\n");
return;
}
pAllDenom[index]=pDenomArray[count];
coinDenomination(sum-pDenomArray[count],index+1,count,size,pAllDenom,pDenomArray);
coinDenomination(sum,index,count+1,size,pAllDenom,pDenomArray);
}
}
int main()
{
int array[]={2,3,6,7,8};
int n=10;
int printArr[100]={0};
coinDenomination(n,0,0,sizeof(array)/sizeof(int),printArr,array);
return 0;
}
Hi Algoseekar:
if u have data type (built in or user defined) to take input for big integers then same u can use in my code for processing and output.
if u r taking the input as string of digits then one of the solution given below is extremely good and clean:
ideone.com/ElXqx given by some anonymous.
0 1 1 0 1
1 1 1 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
Lets say Square is N*N matrix. Colored cell=0, uncolored cell=1
So problem reduces to finding out a square(rectangle) sub matrix containing all 1s.
It can be done using DP with in O(N*N) with O(N*N) space.
Scan the entire matrix and keep on increamenting(accumulate) the number of 1s.
for any cell [i,j] if anyof [i-1,j-1] or [i][j-1] or [i-1][j] contains 0 then reinitailize the count (i mean again start count with 1).
if(givenMatrix[i][j]==1)
auxMatrix[i][j]=1+MIN(auxMatrix[i-1,j-1],auxMatrix[i][j-1],auxMatrix[i-1][j])
else
auxMatrix[i][j]=0
below is the full code, please address bug in it. this code is for square but with few modification it can be done for rectangle also.
void findMaxSubMatrix(int matrix[10][10], int row, int col)
{
int sumMatrix[10][10]={0}, sum = -1;
int i,j, bottomRight_i, bottomRight_j, topLeft_i, topLeft_j;
/*initialize col 0 and row 0 of sum matrix same as given matrix*/
for(i=0; i<row; i++)
sumMatrix[i][0] = matrix[i][0];
for(i=0; i<col; i++)
sumMatrix[0][i] = matrix[0][i];
/*calculate the sum matrix*/
for(i=1; i<row; i++)
for(j=1; j<col; j++)
if(matrix[i][j]==1)
sumMatrix[i][j] = 1 + MIN(sumMatrix[i-1][j-1],sumMatrix[i][j-1],sumMatrix[i-1][j]);
else
sumMatrix[i][j] = 0;
/*find the top left and bottom right indixes of square matrix*/
for(i=1; i<row; i++)
for(j=1; j<col; j++)
if(sum<sumMatrix[i][j])
{
sum = sumMatrix[i][j];
bottomRight_i = i;
bottomRight_j = j;
}
i=bottomRight_i;
j=bottomRight_j;
while(i>0 && j>0)
{
if(((sumMatrix[i][j]-sumMatrix[i-1][j-1])>0) && (sumMatrix[i-1][j-1] != 0))
{
i--;
j--;
}
else
{
break;
}
}
topLeft_i=i;
topLeft_j=j;
printf("Top left indexes: [%d,%d]\n", topLeft_i, topLeft_j);
printf("Bottom right indexes: [%d,%d]\n", bottomRight_i, bottomRight_j);
}
I tried for the below pseudo to be self explanatory, sorry if its not so. Comments are welcome :)
Q.Enqueue(root),currQsize=1,newQsize=0,currNode=prevNode=NULL;
while(Q is not empty)
{
while(currQsize)
{
currNode=Q.Dqueue();
if(prevNode)
{
prevNode->next=currNode;
}
/*enque the childrens of next level and make
count of number of node at next level*/
if(currNode->left)
{
Q.Enqueue(currNode->left);
newQsize++;
}
if(currNode->right)
{
Q.Enqueue(currNode->right);
newQsize++;
}
currQsize--;
prevNode=currNode;
}
currQsize=newQsize; /*number of node at next level*/
newQsize=0;
currNode->next=NULL; /*last node sibling is null*/
prevNode=NULL;
}
Nice approach
Using extra space it can be done without altering the input strings.
One Optimization to yr solution is that once we sorted the window of size "m" first time, after that no need to sort,we can call min heapify for the next entry.
so the time is (n-1)logm + mlogm = (n+m-1)logm instead of nmlogm.
Let pArray is pointer pointing to given array A of length LEN.
Naive approach
1. Find the max number which is at the index <=n+1 in pArray. lets say such number exists at index m where m<=n+1.
2. Swap pArray[m] with pArray[m-1] till m is not equal to 1.
3. n=n-m, pArray++
4. if (n==0) or (pArray == &A[LEN])then exit else go to 1.
Do let me know about some more efficient approach.
- Tulley April 16, 2011When I saw the solutions here I got one doubt. Does the question says that
1. for a given B find a substring in A which is anagram of B?
Or it says
2. for a given B find a substring in A which contains anagram of B?
e.x.
1.
A=ghefdckjcaaadebclpq
B=aabedcca
here in A one of the substring is "caaadebc" which is anagram of B
2.
A=efcadckjaghadeblpcq
B=aabedcca
Here here in A one of the substring is "cadckjaghadeblpc" which contains anagram of B.
Solution posted above works for 2 only.
@Sathya, Mat, Anony please correct me if I m wrong.
You r right. Instead of doing XOR, when we are at colom J then the entries AncestorMatrix[I->N][J] must be checked. If more than 1 exist in the entries AncestorMatrix[I->N][J] then the AncestorMatrix[I][J] wont be considers as child.
Same is corrected now. Please check again if u find any more bug.
@Anonymous: Thanks for yr valuable suggestion. It always happens that u r not able to identify all bugs in yr code. I love to put code here for discussions, suggestions and taking input from many minds :)
By the way I've edited the above code n hope it works for all the cases now.
Unique Tree is not possible. Below algo is applicable for n-ary tree also with small modification.
Algo+Pseudocode:
Bool isLeftChildDone=FALSE
Bool isImmidiateChild=TRUE;
1. Sort the rows of matrix in descending order of number of 1s.
(this will form root as root is ancestor of all nodes)
2. R=newNode(); Root=R. Enque(Root).
3. FOR (I=1 to NumOfRow-1) && (Queue is not empty)
{
isLeftChildDone=FALSE;
/*Make Tree*/
R=Dequeue();
FOR (J=1 to NumOfCol)
{
FOR (K=I+1 to numOfRow-1)
{
IF(AncestorMatrix[K][J]==1)
isImmidiateChild=FALSE;
break;
}
IF (isImmidiateChild==FALSE)
{
isImmidiateChild=TRUE;
continue;
}
IF (AncestorMatrix[I][J]==1)
{
IF (isLeftChildDone==FALSE)
{
R->leftChild=newNode();
isLeftChildDone=TRUE;
Enqueue(R->leftChild);
}
ELSE
{
R->rightChild=newNode();
Enqueue(R->rightChild);
}
}
}
}
I assumed that there wont be overflow and the number is palindrome.
Dealing with a number which cant be expressed in 32 or 64 bit of architecture is another area of research and many papers had been already published but in the same question if numbers are represented as string then above algorithm holds with few modifications.
If we want a solution better than nlogn then there is only one option left out is to find Kth largest element where K=(n+1)/2. This could be O(N^2) also in worst case but average case is still O(N).
@xedgenes: I am not agree with u that "median is also the average of the highest and the lowest element in the array."
void PrintPath(node* root)
{
int array[100];
int depth=0;
PathRootToLeave(root,array,&depth);
}
void PathRootToLeave(node* root, int* pArray, int* depth)
{
if(root)
{
pArray[(*depth)++]=*((int*)root->pData);
if(root->lChild)
{
PathRootToLeave (root->lChild,pArray,depth);
(*depth)--;
}
if(root->rChild)
{
PathRootToLeave (root->rChild,pArray,depth);
(*depth)--;
}
if((!(root->lChild))&&(!(root->rChild)))
{
int i = 0;
for(i=0;i<(*depth);i++)
{
printf("[%d]", pArray[i]);
}
printf("\n");
}
}
}
1. Get the num till half of the number of digit of given num.
2. Add 1 in to it.
3. Reverse the num obtained in step 2.
4. Append the numbers obtained in 2 and 3.
***Take care of odd and even num of digits.
int nextPalindromInt(int inPalindromeInt)
{
int numOfDigit=0, placeValue=1;
int num=inPalindromeInt, halfNum=0, i;
int isAll9Digit=1;
if((num>=-9)&&(num<=9))
return num;
/*Get Total num of digit and place value of most significant digit*/
while(num)
{
numOfDigit++;
if(((num%9)!=0)||((num%10)==0))
{
isAll9Digit=0;
}
num=num/10;
placeValue = placeValue*10;
}
if(((isAll9Digit==1)&&(inPalindromeInt>0))||
((((inPalindromeInt+1)%100)==0)&&(inPalindromeInt<0)))
{
return inPalindromeInt+2;
}
i=(numOfDigit>>1)+((numOfDigit%2)?1:0);
num=inPalindromeInt;
placeValue=placeValue/10;
/*Get the num till half of the number of digit*/
while(i)
{
halfNum = halfNum*10 + num/placeValue;
num=num%placeValue;
placeValue = placeValue/10;
i--;
}
/*Add one in halfnum, get next palindrome by appending
halfNum in to halfNum in reverse manner*/
halfNum=halfNum+1;
num=halfNum;
if(numOfDigit%2)
{
num=halfNum/10;
}
while(num)
{
halfNum=halfNum*10 + num%10;
num=num/10;
}
return halfNum;
}
1.For CatsOutDogs, above algo will give following output:
Output: Cat, Cats, Out, Dogs
2.For CatsAndDogs it will give following output:
Output: Cat, Cats, Sand, And, Dogs.
if this is not the desired question then I think I misunderstood the question. Please let me know.
I assume that raw dictionary is given (no dictionary method is given for look up).
1. Pre-process the dictionary in TRIE. Let S is the string and M is its length.
2. FOR I=1 to M
FOR J=I to M
search S[j] in TRIE.
IF terminating node found then outpout S[I to J].
Complexity O(M^2).
When these type of question comes my mind set is to use TRIE (sufix tree is too tough for an interview). Can anybody suggest other approach? Same or better complexity.
1. the if check is to avoid array over-bound. This if check is not required if u take array of size N+2 (i have taken it as N).
2. When these lines will get executed we have already printed the path("i" at line number 14), so in next call we dont want to print it thats y again making it to 0.
@Algoseekar:
As I wrote above that total number of path will be Nth Fibonacci number. If u trace the recursion (trace the variable "count") u can easily find how its printing the path.
e.g.
if N=5
count=0, pArray[0]=1, call with count=count+1 (=1)
.......
count=4,pArray[4]=1,all with count=count+1 (=5)
print path and return.
Now call'll take place with count=6 and it'll return at line 5. So, for count=4 both call finished. Now the execution will take place for count=3 from line 25. So on..
I think this will help.
@Kishore: You have mixed in and pre above. Logic simple:
1. Read first element of pre-order array. Make it root. Find it in in-order array. left partition corresponding to this root in in-order array will go in left and right will go in right. So recursively build left and right sub tree.
In-order: 4 2 5 1 6 3
Pre-order: 1 2 4 5 3 6
1 will be the root of tree.
1
/ \
/ \
4 2 5 6 3
2 will be the root of left subtree and
3 will be the root of right subtree
1
/ \
/ \
2 3
/ \ /
/ \ /
4 5 6
I think u r alo saying the same.
- Tulley April 02, 2011node* buildTree(char* pInOrder, char* pPreOrder, int inOrderStart, int last, int*pPreIndex)
{
int rootIndex;
node* pRoot;
if(inOrderStart > last)
return NULL;
/*take element from preorder array and make a new node*/
pRoot = newNode(pPreOrder[(*pPreIndex)++]);
/*return if node has no children*/
if(inOrderStart == last)
return pRoot;
/*find the index of root in inorder array*/
rootIndex = search(pInOrder, inOrderStart, last, pRoot->data);
/*recursively build left and right subtree*/
pRoot->left = buildTree(pInOrder, pPreOrder, inOrderStart, rootIndex-1);
pRoot->right = buildTree(pInOrder, pPreOrder, rootIndex+1, last);
return pRoot;
}
The function F is nothing but an equation of line on 2-d plane, y=mx+c.
Functions U and D are discrete functions acquiring one of y=mx+c on different interval of X which makes it max and min respectively.
S is min of(U-D). Also there is no global maxima or minima for the functions U and D (trivial is + and - infinity), but there exist a X for which U tends to local minima and D tends to local maxima and that X must be one of the intersection point of the lines y=mx+c.
So here y=A[K]X+B[K] and y=A[L]X+B[L] are two different lines by solving them we are getting the intersection of these two lines and checking for U and D.
Now I think u r clear why the condition L != K is there (same lines, infinite solution).
FOR EACH K<=0<N
FOR EACH L<=0<N
IF L != K
Compute X by solving A[K]X+B[K]=A[L]X+B[L]
Compute U(X) and D(X) for this X.
Compute S(X). IF S(X) is less than previous S(X) then update.
Complextity O(N^3)
Logic is that we have to find the max of D(X) and min of U(X) for same X.
Its O(n) solution. Don't b confused by seeing nested while loops. index1 and index2 were initialized only once.
About Modification:
As per the code after finding both the numbers only one of the while loop is running at a time. This check ensures that both the while loop don't point to same index in the array when same numbers are given as input. Please let me know if I am still not clear.
IMO its a good variation of longest increasing sub sequence.
I didn't run the code other than the input given in this post. Please let me know if there is a bug or mistake in logic. Code expects valid input text file with newline in the end.
- Tulley June 30, 2011I'll explain the detailed logic latter.