Many algorithms will specify that duplicates are excluded. For example, the example algorithms in the MIT Algorithms book usually present examples without duplicates. It is fairly trivial to implement duplicates (either as a list at the node, or in one particular direction.) Most (that I’ve seen) specify left children as <= and right children as … Read more
A common idiom for clearing standard containers is swapping with an empty version of the container: void clear( std::queue<int> &q ) { std::queue<int> empty; std::swap( q, empty ); } It is also the only way of actually clearing the memory held inside some containers (std::vector)
The main trick behind this algorithm is that if you, observing a stream of random integers, see an integer which binary representation starts with some known prefix, there is a higher chance that the cardinality of the stream is 2^(size of the prefix). That is, in a random stream of integers, ~50% of the numbers … Read more
Print a [large] tree by lines. output example: z ├── c │ ├── a │ └── b ├── d ├── e │ └── asdf └── f code: public class TreeNode { final String name; final List<TreeNode> children; public TreeNode(String name, List<TreeNode> children) { this.name = name; this.children = children; } public String toString() { StringBuilder buffer = new StringBuilder(50); print(buffer, “”, “”); return buffer.toString(); } … Read more
Python doesn’t have a builtin frozendict type. It turns out this wouldn’t be useful too often (though it would still probably be useful more often than frozenset is). The most common reason to want such a type is when memoizing function calls for functions with unknown arguments. The most common solution to store a hashable … Read more
A static two-dimensional array looks like an array of arrays – it’s just laid out contiguously in memory. Arrays are not the same thing as pointers, but because you can often use them pretty much interchangeably it can get confusing sometimes. The compiler keeps track properly, though, which makes everything line up nicely. You do … Read more
Time to go back in time for a lesson. While we don’t think about these things much in our fancy managed languages today, they are built on the same foundation, so let’s look at how memory is managed in C. Before I dive in, a quick explanation of what the term “pointer” means. A pointer … Read more
A HashMap contains more than one key. You can use keySet() to get the set of all keys. team1.put(“foo”, 1); team1.put(“bar”, 2); will store 1 with key “foo” and 2 with key “bar”. To iterate over all the keys: for ( String key : team1.keySet() ) { System.out.println( key ); } will print “foo” and … Read more
Another good reason is that linked lists lend themselves nicely to efficient multi-threaded implementations. The reason for this is that changes tend to be local – affecting only a pointer or two for insert and remove at a localized part of the data structure. So, you can have many threads working on the same linked … Read more
According to this thread: Indeed, CPython’s sets are implemented as something like dictionaries with dummy values (the keys being the members of the set), with some optimization(s) that exploit this lack of values So basically a set uses a hashtable as its underlying data structure. This explains the O(1) membership checking, since looking up an … Read more