victoriousvishal
BAN USER@Andy2000 - topological sort works in the following way: the following code returns precedence of characters OR error in case the graph has a cycle (cycle in case of wrong input)!
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
nice clean code..
- victoriousvishal September 06, 2012anonymous - if you want to print all the triplets then instead of "return" just right "break" in the while loop.
- victoriousvishal September 04, 2012saumils - how come is it O(n + k) time complexity? for further elements if an element gets replaced by the max of array[1..k] then to recompute the new max again you need O(k) time...so it would be O(k + (n - k)*k) right?
- victoriousvishal September 04, 2012Mr Bean it would be O(2*n*logn) + O(2n) = O(2*n*logn) = O(n*logn)
Reason: If you only check if all the elements of BST-1 are present n BST-2 and not check if all the elements of BST-2 are also present in BST-1 then you might get wrong answers if BST-1 contains DUPLICATES but BST-2 doesn't contain any DUPLICATES!
Mr Bean it would be O(2*n*logn) + O(2n) = O(2*n*logn) = O(n*logn)
Reason: If you only check if all the elements of BST-1 are present n BST-2 and not check if all the elements of BST-2 are also present in BST-1 then you might get wrong answers if BST-1 contains DUPLICATES but BST-2 doesn't contain any DUPLICATES!
lyra_vega I saw that the questions asked from you were very tough so I wanted to know if you were a fresher (just completed/doing B.Tech) at your time of interview or not? Actually even I have my interview on coming 10th of this month and I am a fresher so I am getting a bit scared by seeing such difficulty level. :)
- victoriousvishal September 03, 2012what Psycho said is correct. We should sort on one dimension and then sort on the other.
Eg: After sorting on length lets say this is what you get: 1,4 1,2 2,5 4,6
Now you might get wrong answer as 3 with what Anonymous said.
But sort the above array on width so to get this:
1,2 1,4 2,5 4,6
Now you'll get the correct ans as 4.
Assuming denomination to be 25 cents(quarters), 10 cents(dimes), 5 cents(nickels) and 1 cent(pennies). Printing number of ways possible to make change for "n" cents:
Algorithm : We know that makeChange(100):
= makeChange(100 using 0 quarters) + makeChange(100 using 1 quarter) + makeChange(100 using 2 quarter) + makeChange(100 using 3 quarter) + makeChange(100 using 4 quarter)
Can we reduce this further? Yes!
= makeChange(100 using 0 quarters) + makeChange(75 using 0 quarter) + makeChange(50 using 0 quarters) + makeChange(25 using 0 quarters) + 1
Now what? We’ve used up all our quarters, so now we can start applying our next biggest denomination: dimes.
Code:
#include<stdio.h>
int makeChange(int n, int denom) {
int next_denom = 0;
switch (denom) {
case 25:
next_denom = 10;
break;
case 10:
next_denom = 5;
break;
case 5:
next_denom = 1;
break;
case 1:
return 1;
}
int i,ways = 0;
for (i = 0; i * denom <= n; i++) {
ways += makeChange(n - i * denom, next_denom);
}
return ways;
}
int main(){
int n = 100;
printf("%d",makeChange(n, 25));
return 1;
}
I am not comfortable in using tries. But would definitely like to know how we can use it. @lucifer please can you give me the solution using tries?
Thanks!
Graph creation:
struct Node{
char val;
Node*[] list;
};
Start from the first pair in the dictionary. Compare two strings in this pair. When I am comparing two consecutive strings then i should compare till first mismatch.
Eg: aad & aab, in this case create an edge d -> b
then go to that character's node "list" (here node list of char "d") and if the new character (char "b") to be linked is not already present then add it....Do the above steps for all the consecutive pairs in the dictionary.
Finally do topological sort in the following way to return precedence of characters OR error in case the graph has a cycle (cycle in case of wrong input)!
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
Graph creation:
struct Node{
char val;
Node*[] list;
};
Start from the first pair in the dictionary. Compare two strings in this pair. When I am comparing two consecutive strings then i should compare till first mismatch.
Eg: aad & aab, in this case create an edge d -> b
then go to that character's node "list" (here node list of char "d") and if the new character (char "b") to be linked is not already present then add it....Do the above steps for all the consecutive pairs in the dictionary.
Finally do topological sort in the following way to return precedence of characters OR error in case the graph has a cycle (cycle in case of wrong input)!
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
Graph creation:
struct Node{
char val;
Node*[] list;
};
Start from the first pair in the dictionary. Compare two strings in this pair. When I am comparing two consecutive strings then i should compare till first mismatch.
Eg: aad & aab, in this case create an edge d -> b
then go to that character's node "list" (here node list of char "d") and if the new character (char "b") to be linked is not already present then add it....Do the above steps for all the consecutive pairs in the dictionary.
Finally do topological sort in the following way to return precedence of characters OR error in case the graph has a cycle (cycle in case of wrong input)!
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
@Psycho - take tree 1 as:
9
6 13
5 7 10 14
tree 2 as:
4
3 5
now pass "t2,t1" as parameters. You'll have an exception when stack 1 gets empty but stack 2 still has elements...
- victoriousvishal August 28, 2012
Well you're right only when the input is not wrong! If the input is wrong then the graph which you built will have cycle and in that case you can't just traverse the graph! I hope you get it..
- victoriousvishal September 09, 2012