• 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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: 79179
377
  • 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: 27763
196
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.
 
Bartender
Posts: 5465
212
  • 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: 79179
377
  • 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
Bartender
Posts: 5465
212
  • 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: 79179
377
  • 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
Bartender
Posts: 5465
212
  • 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: 79179
377
  • 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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic