• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Rob Spoor
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Junilu Lacar
  • Tim Cooke
Saloon Keepers:
  • Tim Holloway
  • Piet Souris
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Frits Walraven
  • Himai Minh

Data Structures in Java

 
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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



 
Marshal
Posts: 73760
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch

Is Python really an object‑oriented language? If I were writing that in Java┬«, I would start by creating an object to encapsulate all those data. Java┬« also provides a better way to order the ratings from AAA to C. Why have you declared the same mappings twice (lines 25 and 36)?
 
Saloon Keeper
Posts: 24207
166
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Is Python really an object‑oriented language?



If you're feeling generous. It's a procedure-oriented language with OOP bolted on. Kind of like C++.

And yes, I'd define the data structure as a class and probably externalise the visiting algorithm.
 
Jck Smith
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you so much for replying guys!! I am just starting Java so cannot really code this up in java right away! But I would categorize this as a difficult question, took me over an hour to write the python code.

I will greatly appreciate if someone can code this up in Java so I can get a feel of how to go about. It is a bit of an undertaking but I will really really appreciate.
 
Jck Smith
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Ritchie.. good obervation... declaring the dictionary twice was needless.
 
Saloon Keeper
Posts: 4612
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
To give you an idea:

I created the class 'Jck' as follows:

Next, I created a List<Jck> as:

And to check for any cycles. I created a Map<issuer, List<parent>>:

For each key, I created the path issuer -> parent -> parent -> ... , until the path ended or a parent was already present.

Finally, to determine the max and min as:

Hope this gets you going.
 
Campbell Ritchie
Marshal
Posts: 73760
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Who needs a Map when you can create a Ratings enum and the ratings then become mutually Comparable?
 
Piet Souris
Saloon Keeper
Posts: 4612
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I find a map easier, its what OP used as well, but an enum is also a good idea. Maybe you can give an example?
 
Campbell Ritchie
Marshal
Posts: 73760
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That will of course have AAA as the “smallest” element, but if that is a problem, it is easy enough to cure
 
Jck Smith
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Woah! thanks
 
Piet Souris
Saloon Keeper
Posts: 4612
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I see that enums implement Comparable... didn't know that. But you still need a Comparator for Jck, for instance:

and you need to give the field 'rating'the Ratings type,.
 
Campbell Ritchie
Marshal
Posts: 73760
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That's easy enough. All enums implicitly extend Enum<T> and that implements Comparable. You can probably replace that λ with Jck::getRating or similar.
 
You firghten me terribly. I would like to go home now. Here, take this tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic