balmung421 / date_night Goto Github PK

• Practice breaking a program into logical components
• Distinguishing between classes and instances of those classes
• Understanding how binary search trees work to store and find data
• Testing components in isolation and in combination
• Use and implement iteration or recursion techniques

You are a junior developer at Netflix. You're on a team that is developing a list of movies for Netflix users called "Suggested for You." Each time movies are added to Netflix, an algorithm determines a score of how likely a given user is to enjoy that movie.

• Scores are integers between 0 and 100
• No two movies will get the same score

It is your job to take new movies that have been scored, and store them in a Binary Search Tree.

A binary search tree is a fundamental data structure useful for organizing large sets of data. It's ideal whenever you need to retrieve and sort data quickly.

More on Wikipedia: http://en.wikipedia.org/wiki/Binary_search_tree

A binary tree is built from nodes. Each node has:

• A) An element of data
• B) A link to the left. All nodes to the left have elements with a value less or lower than this node's data element.
• C) A link to the right. All nodes to the right have elements with a value more or greater than this node's data element.

Build a binary search tree which can fulfill each of the interactions below.

Assume we've started with:

tree = BinarySearchTree.new

The insert method adds a new node with the passed-in data. Each node is comprised of a score and a movie title. It returns the depth of the new node in the tree.

tree.insert(61, "Bill & Ted's Excellent Adventure")
# => 0
tree.insert(16, "Johnny English")
# => 1
tree.insert(92, "Sharknado 3")
# => 1
tree.insert(50, "Hannibal Buress: Animal Furnace")
# => 2

For all the later methods defined here, assume that we've run these four inserts.

Verify/reject the presence of a score in the tree:

tree.include?(16)
# => true
tree.include?(72)
# => false

Reports the depth of the tree where a score appears. Return nil if the score does not exist:

tree.depth_of(92)
# => 1
tree.depth_of(50)
# => 2

Which movie has the highest score in the list? What is it's score?

tree.max
# => {"Sharknado 3"=>92}

Which movie has the lowest score in the list? What is it's score?

tree.min
# => {"Johnny English"=>16}

Return an array of all the movies and scores in sorted ascending order. Return them as an array of hashes. Note: you're not using Ruby's Array#sort. You're traversing the tree.

tree.sort
# => [{"Johnny English"=>16},
#   {"Hannibal Buress: Animal Furnace"=>50},
#   {"Bill & Ted's Excellent Adventure"=>61},
#  {"Sharknado 3"=>92}]

Assuming we have a file named movies.txt with one score/movie pair per line:

# movies.txt sample format:
34, Hannibal Buress: Comedy Camisado
63, Meet My Valentine
22, Experimenter
84, French Dirty
41, Love
10, I Love You Phillip Morris

tree.load('movies.txt')
# => 26

Where the return value is the number of movies inserted into the tree. If a score is already present in the tree when load is called, ignore it.

See an example file here

Report on the health of the tree by summarizing the number of child nodes (nodes beneath each node) at a given depth. For health, we're worried about 3 values:

• Score of the node
• Total number of child nodes including the current node
• Percentage of all the nodes that are this node or it's children

tree.insert(98, "Animals United")
tree.insert(58, "Armageddon")
tree.insert(36, "Bill & Ted's Bogus Journey")
tree.insert(93, "Bill & Ted's Excellent Adventure")
tree.insert(86, "Charlie's Angels")
tree.insert(38, "Charlie's Country")
tree.insert(69, "Collateral Damage")
tree.health(0)
=> [[98, 7, 100]]
tree.health(1)
=> [[58, 6, 85]]
tree.health(2)
=> [[36, 2, 28], [93, 3, 42]]

Where the return value is an Array with one nested array per node at that level. The nested array is:

[score in the node, 1 + number of child nodes, floored percentage of (1+children) over the total number of nodes]

When the percentages of two nodes at the same level are dramatically different, like 28 and 42 above, then we know that this tree is starting to become unbalanced.

This extensions is made up of two methods:

A leaf is a node that has no left or right value. How many leaf nodes are on the tree?

tree.leaves
# => 2

What is the height (aka the maximum depth) of the tree?

tree.height
# => 3

Remove a specified piece score from the tree:

tree.delete(30)
# => 30
tree.delete(101)
# => nil

Note that any children of the deleted node should still be present in the tree.

The project will be assessed with the following rubric:

• 4: Application demonstrates excellent knowledge of Ruby syntax, style, and refactoring
• 3: Application shows strong effort towards organization, content, and refactoring
• 2: Application runs but the code has long methods, unnecessary or poorly named variables, and needs significant refactoring
• 1: Application generates syntax error or crashes during execution

• 4: Application is expertly divided into logical components each with a clear, single responsibility
• 3: Application effectively breaks logical components apart but breaks the principle of SRP
• 2: Application shows some effort to break logic into components, but the divisions are inconsistent or unclear
• 1: Application logic shows poor decomposition with too much logic mashed together

• 4: Application is broken into components which are well tested in both isolation and integration using appropriate data
• 3: Application is well tested but does not balance isolation and integration tests, using only the data necessary to test the functionality
• 2: Application makes some use of tests, but the coverage is insufficient
• 1: Application does not demonstrate strong use of TDD

• 4: Application meets all requirements, and implements one extension properly.
• 3: Application meets all requirements as laid out per the specification.
• 2: Application runs, but does not work properly, or does not meet specifications.
• 1: Application does not run, crashes on start.