As we continue MP3 we'll work on a task that requires us to apply both what we know about graphs and what we know about hashing. The restaurant preferences data actually forms a graph, and to complete the next test you'll need to traverse it. And there is also a bit of hashing-related work to do as well.
Before we discuss how to treat the related restaurants like a graph, let's examine an important connection between Java sets and hashing.
Today's task continues work on our
Previously you completed
getRelated, which used the data parsed from the
preferences.csv file to establish relationships between restaurants.
Two restaurants were related if they appeared in the same users list of preferences, and the strength of their relationship was determined by the number of times that they appeared together.
Viewed another way, this data forms a graph, where nodes are restaurants, and edges determined by the existince of a relationship between two restaurants. Note that this graph is:
testGetConnectedTo you'll need to traverse this graph of related restaurants to count the number of restaurants within a two-hop neighborhood of a given starting point.
However, as a twist, you should only consider nodes to be connected if they have a weight greater than 1!
Let's discuss how to do this visually first:
As a more complete description of your task, you should complete a new method
getConnectedTo on your existing
RelatedRestaurants class as follows.
getConnectedTo should take a
String containing a restaurant ID and return a
The set should contain all restaurants that are within two hops of the starting restaurant when the restaurant relationships are considered as a graph.
You should also not consider edges with a weight of one—so only pairs of restaurants that appear in two or more lists together are considered connected for the purposes of this problem.
If the restaurant ID passed to
getConnectedTo is not valid, you should throw an
You'll probably want to review the lessons on graphs, and the practice problem that we completed that is fairly similar. A few other notes:
getRelatedmethod, since the map it returns represents the neighbors of a given restaurant and the weights of the connections
Set<Restaurant>, but the starting point and the keys in the map returned by
Strings. A reasonable approach computes a
Set<String>containing restaurant IDs first and then converts it into a
This is the final algorithmic challenge on the machine project. Good luck!
As a reminder, on lessons where we focus on the machine project we will not assign a homework problem! However, the lesson will usually focus on helping you complete a particular part of the MP test suite, and so we encourage you to spend time on that in lieu of a homework problem.
Today your goal should be to complete the second MP3 test case: