In general, the worse case scenario when searching through a data set is when the datum being searched for doesn’t exist. In this case, the complete data storage needs to be searched before it’s possible to conclude that the datum cannot be found. If only there was a way to eliminate the need to perform unnecessary searches when we know the data won’t be found. Fortunately, there is a data structure that allows you to do just that. This data structure is knows as a “Bloom Filter”.
Continue reading “Bloom Filters”
Tag: data structures
Lowest Common Ancestor (non-BST)
In the earlier article, Lowest Common Ancestor (BST), I discussed how you can use the special ordering of a Binary Search Tree to quickly and easily identify the Lowest Common Ancestor of two nodes. Of course, not all trees are BSTs and so in this article we’ll look at a way of finding the LCA in a non-BST. Continue reading “Lowest Common Ancestor (non-BST)”
Lowest Common Ancestor (BST)
The Binary Search Tree (BST) is a tree like data structure that allows for the quick lookup of data. They work by storing inserted data in a tree like structure that uses the “divide and conquer” approach to locate data. Each node in the tree has, at most, two children. The left hand side (lhs) node will always contain a value that is less than it’s parent. The right hand side (rhs) node will always contain a value that is greater-than or equal to it’s parent.
Down-casting re-visited
In my previous article I discussed the difference between up-cast and down-cast and explained why down-casting is rarely a good idea (or even necessary). That said, there are a few times when down-casting is valid and so this article shows how to do so, safely, in C++.
LRU Cache Implementation
One of the problems any developer will eventually have to resolve is one of latency; specifically, being able to retrieve and process data in a timely fashion. This issue can come in many guises but they generally manifest as needing to read data from a backing store that cannot deliver the high performance needed by the application. This can be a tricky problem to solve but the general method is to implement some form of caching. The remainder of this article will discuss one caching mechanism, called the LRU Cache.
Reversing a linked list
Linked lists are an interviewers favourite subject matter. Whilst they are pretty easy to understand, at least in principle, they do require a little bit of brain warping to get your head around what’s going on under the hood. Of the common questions about linked lists I’ve come across, this quiz tackles the most common: how to reverse a linked list.
Which STL Container?
Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and when to use it.
The dangers of iterators
When working with STL containers we generally use iterators to access, manipulate and enumerate the contents. This almost becomes second nature and it’s very easy to go on auto-pilot and end up coding an innocuous looking bit of code that can contain a rather nasty surprise. This little quiz shows just one example of how such a surprise might come back to bite you.
evilrix 