For a lot of algorithms that use linked lists and binary trees, I often repeat the same struct for each respectively, set up an example, and then create the same helpers (usually print and delete or something). These helpers and struct definitions get repeated a lot, so it might make sense to factor them out into utilities, or even use the homemade data structures in this repository (though for some problems that might not be possible, given problem-specific modifications).

The repository is now published to https://domfarolino.com/algorithms and adding a table of contents to the README would make the site much more navigable and improve the ...wait for it...SEO.

/cc thanks @isiah-lloyd

It would be nice if this repository, under datastructures, we had an implementation of a data structure that supports arbitrarily large integers. This should be relatively easy to implement, at least naively, and can be helpful for some future number-theory based algorithms under Number_Algorithms.

See: https://leetcode.com/problems/group-anagrams/description/

Docs for datastructures

• Stack
• Queue
• BST (implementation not published yet)

need added. Maybe even @kytrol could proofread them!!

See https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

See https://leetcode.com/problems/merge-intervals/description/

Very interesting one: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/description/

See https://www.hackerrank.com/challenges/largest-rectangle/problem

Reading https://github.com/domfarolino/algorithms/tree/master/src/datastructures/Vector#void-vectortclear should give you a good idea on the changes that may need made to clear(). This is primarily because as it stands, clear() can be called multiple times however the vector becomes unusable after a single call.

See https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/description/.

This repository has a lot of data structures (more coming!) and things like Leetcode algorithm solutions and documentation. There are some classic CS problems in here as well, like searching and sorting, however I think more needs done to make it easier to move more algos in. For example, I'd rather not put things like KMP string matching in the super /String_Algorithms. It'd be nice to maybe have some "fundamentals" that carry textbook and classic algos in.

See https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

All binary search tree iterators support the increment and decrement operators (delegating to the tree's inorder_successor and inorder_predecessor methods, except for the iterator returned by end(). The end() iterator is currently naively implemented, simply wrapping a null node.

In order to support decrementing the end iterator (i.e., end()--), this seems to require some sort of dummy-max node to be maintained as a special right-child of the maximum node in the tree. This will probably not be too hard to implement, but it does interact with at least the tree's insert logic. We should consider doing it so that we can make the binary_search_tree<T>::iterator support the std::bidirectional_iterator_tag.

https://leetcode.com/problems/perfect-squares/

See src/datastructures/BST/README.md

Some cursory research shows that std::multiset::find returns an iterator to the lowest node matching the given key. For example, this means if a tree consists only of one node value, but many duplicates of it, then the find(val) operation will always return an iterator that equals begin().

I don't believe this repository's binary search tree implementation has the same lower-bound find guarantee, but we should check, change our implementation if necessary, and add tests regardless.

Some logic is being duplicated in different forms (primarily in regards to shifting elements) inside Vector::push_front() mainly due to the conditional. Factor as much of the logic out of the condition al as possible so it only appears one time. The result of a size == capacity check should only modify this->_data so that after a resize, the problem can be put in terms of the average case where we know the vector has room to shift elements around.

The README should do a much better job describing exactly what is going on in this repository. Things include:

• Brief difference between algorithm_practice and datastructures folders
• Explanation on exactly what algorithms go in this repository, why, and how each folder is organized
• Explanation of where these files are coming from (difference between problem.cpp and ojAns.cpp and how to find the original problem description/submission page
• Explanation to why I pretty much only accept C/C++ in this repository

...the above is a running list and is definitely subject to change.

https://leetcode.com/problems/count-and-say/

See: https://leetcode.com/problems/last-stone-weight/description/. It's a good problem about using a binary search tree / set, but also needing to keep track of occurrences/duplicates. You can use a map or a multiset for this, which is nice.

https://leetcode.com/problems/maximal-square/description/

The data structure implementations in this repository should adhere to the Chromium & Google C++ Style Guide. See #133 (comment) and https://github.com/domfarolino/algorithms/blob/master/src/datastructures/README.md.

• BinarySearchTree
• MinHeap
• Queue
• QueueFromStacks
• SLL
• Stack
• Vector

See: https://leetcode.com/problems/diameter-of-binary-tree/description/. It's a good problem about selectively propagating information up a tree's suspended stack frames.

The recursive binary search "first occurrence" and "last occurrence" variations index out of bounds given an empty array, producing undefined (usually fine though) behavior. This should be fixed. Perhaps in these binary search variants, since we will always come out of the while loop before returning, we should perform size == 0 checks early on?

The algorithm maxTrianglePath currently in Array_Algorithms/ seems to not produce .out files that match the ground truth ones included in the repository. Probably something is overflowing or being indexed incorrectly but it should be looked into.

See https://leetcode.com/problems/binary-tree-inorder-traversal/description/

Adding algorithms/datastructures

I have a ton of algorithms and datastructures I'll be committing to this repository over the next few weeks (and years) but if you have anything you'd like to add please do! Algorithms in this repository range from technical interview questions/answers, to online judge problems/solutions, and classic fundamental CS problems.

If it is useful, add whatever you'd like. I only ask that:

• Everything is well documented
• A common language is used (C++, Java, Python, JavaScript, C#, C...)
• and that your commit message has one of the prefixes in the contributing.json file to keep things neat

Modifications

If you'd like to modify something that already exists in the repository go ahead. Useful changes shouldn't have an issue getting merged.

API-wise, both min() and max() should return iterators, and we should introduce the following methods:

• begin(): returns the result of min().
• end(): returns an iterator pointing to nullptr
• find(): returns an iterator pointing to the a found value. Similar to exists(), but with an iterator return value

A binary_search_tree<T>::iterator should support the following operations:

• Pre-increment
  • Should rely on a newly-introduced static binary_search_tree::inorder_successor
• Post-increment
  • ditto
• Pre-decrement
  • Should rely on a newly-introduced static binary_search_tree::inorder_predecessor
• Post-decrement
  • ditto

Given iterator increment and decrement support, does that imply we want to mark the iterator as a bidirectional iterator? See #146

This was a cool problem, don't have time to add it right now, but I certainly should soon.

... we want this :)

Ones left are:

• insertionSort
• mergeSort
• numberOfInversions
• quickSort
• sortArrayGivenCustomOrder

The documentation for this algorithm currently exists in the implementation file and we should move it out to a README.md file

Following #124, we should convert the current data structure tests/test runner to gtest. For starters, I've done this to the BinarySearchTree implementation in #126.

• binary_search_tree
• min_heap
• queue
• linked_list
• stack
• vector

The SLL class needs an iterator mechanism if we're going to ever use it as the underlying datastructure for the Stack and Queue (others) classes.

https://www.hackerrank.com/challenges/magic-square-forming/problem

LC example of this is: https://leetcode.com/problems/middle-of-the-linked-list/description/

This is a basic and fundamental problem to solve when learning linked lists, so this could be added to the linked list data structure algorithms folder.

See https://leetcode.com/problems/palindrome-linked-list/.

Look into running valgrind memory tests on travis for ease of PR.

There is an issue in the base case of the SLL/addTwoNumbers algorithm. The algorithm should always return a brand new list (consisting of entirely separate memory from the input lists) even if one of the input lists was NULL.

The reasoning for this is so a user of this algorithm does not have to worry about a double free when freeing both input lists as well as the output list. As it stands, we're just returning one of the input lists if the other is NULL, so if a consumer of this algorithm were to call deleteList(a) and deleteList(outputList) they might be trying to delete the same list twice. See screenshot of valgrind below:

We can get around this by simply making a copy of the one input list we're returning now. This yield a much safer implementation!

TODO:

Look out for other issues with base cases like this in SLL algos

Find dynamic programming-related problems and solutions and move them out into their own Dynamic_Programming folder. One known algorithm that can be moved is maxTrianglePath.

See https://leetcode.com/problems/course-schedule/description/ & https://leetcode.com/problems/course-schedule-ii/description/

The "rule of three" should really be implemented for the

• Vector
• SLL
• Stack
• Queue
• MinHeap

classes.