betsybaileyy / core_data_structures Goto Github PK

Your is_subset method is backwards. You are supposed to check if the current object (self) is a subset of the passed in object(i.e. other_set)

Good work on this assignment! Your tests covered a lot of typical cases and your test cases all passed.

I do feel that your tests could have covered more edge cases. One small change that would've improved the robustness of your tests would be to check self.size in more places.

Right now, your palindromes code is not taking into account edge cases such as whitespace and punctuation. It works with a sample like racecar, but not with a sample like race car or race.cAr. All of there should return True as palindromes.

Please resubmit once you have a chance to fix the above cases and work on strings.

• Nice work on you number bases. I would've liked to seen some comments that explain what some of the lines of code were doing as if I had wasn't familiar with number base conversion (what happens inside the loops starting on lines 21 and 42).
• Your recursive binary search looks good, but your iterative binary search algorithm is off even though it passes all of the tests. It also successfully found the item (if the item was in the list) in O(log n) time for all of the test cases in the test file, and a couple of my own test cases; however, it will take O(n) if the item is not in your list (your likley_hood variable), and it fails on bigger cases. Try adding this code at the bottom of search.py and running python3 search.py. You can also print what the halved variable inside the while loop at the end of it (around line 56).

# List with all numbers from 0 to 999
list_1 = [i for i in range(1000)]
# Returns None on this case
print(binary_search_iterative(list_1, 665))

• Your linked list looks good for the most part and is probably better than you than you think. All tests would be passing if the size property was implemented properly. Make sure you change the size when adding or removing an item from the linked list (should be three or four more size changes).
• The same goes for your LinkedQueue. Both your stacks and queues look good, but LinkedQueue would pass if you fixed the error. I'm seeing 'LinkedQueue' object has no attribute 'size', which is exactly what it sounds like and needs an additional line of code somewhere (or using a linked list property once that property is implemented).

• Your binary tree is closer than you think, despite all the failing tests. There are only a few bugs:

1. In BinaryTreeNode's height, there is an error about variables not being declared. This is because left_len and right_len only get set if the if statements are true, and they are not always true. To fix this, you can set both len variables to 0 before the if statements, so they are at least declared if the if statements are ever false.
2. If you want your post order traversal to work, import LinkedQueue at the top.
3. Now, here is the tricky part. I only found these errors because I tested your _find_node_iterative() and _find_parent_node_iterative() methods by replacing their recursive counterparts in search and insert. When you replace the recursive methods with the iterative ones, you'll see that all tests pass (if you fixed the bugs above). You can then narrow the bug down to one of the two recursive helpers. The one with the bugs is _find_parent_node_recursive.

• The first bug is handling the first base case. You return None, but you should return parent. The goal of this first if statement is not to only handle the case that the root does not exist. It also handles the case when you are trying to insert a node that doesn't exist yet. You can imagine that this function traverses to the spot where a node should be inserted (it does this by traversing until it hits a None), and then returning the parent of this empty spot (the empty spot is None). Returning parent handles the no-root case because parent is first set to None as a default argument (and it will return when node, or self.root, is None), and it handles this new case when a new node needs to be inserted. This will pass a few more tests.
• The second bug is fixing a logical error that is hard to see when the tests fail. If you look at the test_init_with_list_of_strings, you'll see that the root's right child is None, rather than 'C'. Another hint is if you look at the tests where you search for three items, you'll see that it breaks on the third item, the item that should be the right child of the node. To fix it, check to see what node you are returning when you descend to the right child in _find_parent_node_recursive.

Good work on this, Betsy! Your code is passing all tests.

This is not required, but you might consider going back through this class and adding time/space complexity annotations for the remaining methods. Not only will this be a good review, but it will also help deepen your knowledge of how hash tables work.

I also saw that there were a few comments that were out of place (e.g. lines 123 and 124). Consider going over your file and making sure that everything is orderly.