The topic of this month's newsletter is data structures and their applications. Some of your complex solutions just require the right data structure. Using appropriate data structures makes them more efficient and improves their readability and writability.
Meet our curator of the month
Elizabeth is a software engineer from Munich who has always been interested in system analysis and design, software architectures, cloud computing, algorithms, and complexity analysis. Her hobbies outside of technology include reading, playing the piano, and gaming.
In this article, Bruno Osiek looks closely at the PATRICIA (Practical Algorithm to Retrieve Alphanumeric Information) trie data structure to show how it is different from the hash map. A PATRICIA Trie is a structured tree that stores data. A node's position in the tree defines the key connected with that node; this makes Tries different from binary search Trees, in which a node keeps a unique key. PATRICIA tries can be used to construct associative arrays with strings as keys which saves storage space for the keys. You may have heard of the Patricia Merkle Trie data structure used in Ethereum. I would say this data structure is worth checking out.
Jainan M explains Skip List from the perspective of parallel computing and Skip List in use as a parallel data structure. A Skip List is a probabilistic data structure with an ordered sequence of n elements and an average time complexity of O(log n) for searching and insertion. In order to get to an element, regular linked list traversal has to go through all the elements before it. This results in a time complexity of O(n). What if we find a way to reach a certain element without visiting every preceding element? That'll reduce complexity by "the number of elements" we're skipping. It combines the best features of a sorted array (for searching) and the structure of a linked list that lets things be added, which a static array can't do.
Matthias Valentin discusses Bloom filters and their variants in this article. The Bloom filter is a type of data structure that lets you find out quickly and easily if an element is in a set. When fast-set membership tests on large data sets are needed, Bloom filters are useful. Spell checking, differential file updating, distributed network caches, and textual analysis are popular examples of scenarios where Bloom filters should be considered.
As a backend developer at Futurice, you will help the world's leading businesses develop compelling and well-thought-out digital solutions, together with the most skilled people in tech, design, and business.