So, I came across this question that is apparently being asked in pre-screen tests this year and thought to share it with the community. I have written a solution in python3 and have posted it below. Better solutions - with regards to time complexity in
java are welcome and will be greatly appreciated (especially by me since I am not big with Java and would very much like to see a implementation for it). It is a data structures question that has 3 objectives.
1. First, need to come up with a data structure to hold the following type of data.
2. Write an algorithm to check if the relations below are cyclic in nature.
3. Find the issuer with max rating
Data:
Issuer | Parent | Rating
A54365 | B34454 | AA
B34454 | C44563 | A
D45747 |B34454 | B
E36547 | D45747 | AAA
G34657 | D45747 | CCC
H84464 | C34563 |BB
I76474 | H84464 |AA
C34563 | |BBB
F34654 | | BB
J74576 | K46565 |C
K46565 | |CC
L54334 | I76474 | AA
H84464 | L54334 | BB
Assumptions can be made:
If asked to find a min or max rating, given an issuer, consider all the issuers in the path from the given issuer to the ultimate parent
Rating order AAA > AA > A > BBB > BB > B > CCC > CC > C
Further elaboration on input and output
Input:
The issuer entity which contains the following fields: Issuer, Parent, Rating separated by |
Output:
If the relations from the input table are cyclic or non cyclic in nature
Issuer with max rating, return None if invalid/NA
Max rating, again return None if invalid or NA
Test case:
A54365 | B34454 | AA
B34454 | C44563 | A
D45747 |B34454 | B
E36547 | D45747 | AAA
G34657 | D45747 | CCC
H84464 | C34563 |BB
I76474 | H84464 |AA
C34563 ||BBB
F34654 || BB
J74576 | K46565 |C
K46565 ||CC
L54334 | I76474 | AA
H84464 | L54334 | BB
Expected Output
Cyclic
A54365
AA
A possible solution in Python3