In PHP, there is concept of single class inheritance i.e. a new class can extend an existing class. You are given a php source file which contains a few classes defined in it. You have to print the class hierarchy in the given desired format.
For example, classes in php source file are A, B extending A, C extending B, D extending A, E.
The output should look like:
A
B
C
D
E
For example, classes in php source file are A, B extending A, C extending B, D extending A, E.
The output should look like:
A
B
C
D
E
This can be done using the following approach
ReplyDeleteUse dfs to find the connected components
Use a topological sort in each of the connected components to find the required answer .
Another approach is to use weights .Assign a weight of 1 to each node initially .
if B extends A wt[b] =wt[b]+wt[a]
Sort all the points and print the inheritence heirarchy .
e.g.
input:
A
B extends A
C extends B
D extends A
E
The weights would be
A=1
B=1+1
C=1+wt[B](Insert B in the list of nodes for C as well)
D=a+wt[A]
E=1
We , can now print the inheritance heirarchy .
How are you doing it in O(1) extra space dude ? When you're reading from a file , you will at least have to store the entire heirarchy into some area .Even dfs would require you to have O(n) array of visited elements .