Data Structure topics

Hans Peter Luhn, the man behind Hash Map

Hans Peter Luhn was a computer scientist who is famously remembered as the inventor of Hash Map and has laid the foundations of text information processing.

Data Structures

Applications of Bloom Filter

We have explored the applications of Bloom Filter which includes weak password detection, use in Internet cache protocol, safe browsing in Google Chrome and much more.

Data Structures

Bloom Filter: Better than Hash Map

Bloom Filter is a probabilistic Data Structure that is used to determine whether an element is present in a given list of elements. It is quite fast in element searching.

Data Structures

Dynamic Array

Dynamic Array solves the problem of array where the size needs to fixed beforehand. On average, dynamic array achieves same performance as an array by using resize operation.

Software Engineering

Approaches for implementing Autocomplete Feature

The various approaches for Text Auto-completion are Linear Search (Brute Force), Binary Search Approach, TRIE Data Structure, Ternary Search Tree Approach, Fuzzy Search, Burkhard Keller Tree Approach and Machine Learning Approach.

Data Structures

Burkhard Keller Tree (BK Tree)

Burkhard Keller Tree (BK-Tree) is a Tree Data Structure that is used to find the near-matches to a String Query. It is used in several applications like spell correction and autocompletion.

Data Structures

Must read research papers on Data Structures

We presented research papers on Data Structures that are a must read for everyone. These come from authors like Raimund Seidel, Knuth, Rubinchik and others

Data Structures

Autocomplete Feature using Ternary Search Tree

Autocomplete Feature can be implemented using Ternary Search Tree as well which is a memory optimized version of trie and performs equally well.

Algorithms

Autocomplete feature using TRIE Data Structure

Autocomplete is a feature of suggesting possible extensions to a partially written text and is widely used in search engine, code IDEs and much more. Trie data structure is a perfect fit to implement this feature efficient in terms of memory and time [O(length of string)].

Software Engineering

Implement Least Recently Used (LRU) Cache

In this article, we have implemented Least Recently Used cache using 2 data structures: Doubly Linked Lists and Hash Map and compared LRU with FIFO cache.

Data Structures

Gap Buffer

Gap buffer is a data structure used to edit array of text in an efficient manner which is currently being edited. It is used in text editors.

Data Structures

Interval Trees: One step beyond BST

Interval tree is a variant of BST and is able to handle intervals in logarithmic time for search, insert and delete operations and is used in geometry.

Data Structures

Sparse Table

Sparse table is a data structure which pre-process the information to answer static Range Queries in constant time O(1) with O(N log N) preprocessing.

Data Structures

Persistent Segment Tree

Our aim is to introduce persistency in segment trees but also ensure that the space and time complexity is not affected.

Data Structures

Rope: the Data Structure used by text editors to handle large strings

Rope data structure is widely used by software such as text editors like Sublime, email systems like Gmail and text buffers to handle large strings efficiently.

Algorithms

Algorithm to convert Binary Search Tree into Balanced Binary Search Tree

In this article, we will explore an algorithm to convert a Binary Search Tree (BST) into a Balanced Binary Search Tree in linear time O(N).

Algorithms

Converting Postfix to Infix using Stack

We have explored an algorithm to convert a Postfix expression to Infix expression using Stack. This takes linear time O(N)

Data Structures

Count inversions in an array using Fenwick Tree

Fenwick tree is usually used for range query problems but it can be used to solve the problem of finding the number of inversions in an array efficiently.

Data Structures

Understanding Fenwick tree (Binary Indexed Tree) with Range product

Fenwick tree is a tree based data structure that is widely used to solve range query problems in logarithmic time O(log N) which would otherwise have taken linear time O(N). In this article, we have explained it in depth using the range product query problem.

Algorithms

Learn how to traverse a Binary Tree (Inorder , Preorder , Postorder)

In this article we will learn three Depth first traversals namely inorder, preorder and postorder and their use. These three types of traversals generally used in different types of binary tree. In summary, Inorder: left, root, right; Preorder: root, left, right and Postorder: left, right, root

Data Structures

Optimizing a Segment Tree with Lazy Propagation

Lazy propagation is an optimization technique for segment tree to delay some of the update queries so that a set of update queries can be performed more efficiently together and thus, reducing the number of operations performed. The time complexity remain the same.

Data Structures

Understand everything about Binary Search Tree

Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers in a tree data structure. It can be used to search for the presence of a number in O(log(n)) time and a simple traversal gives the numbers in sorted order.

Data Structures

Fibonacci Heap

A Fibonacci heap is a heap data structure similar to the binomial heap. It uses Fibonacci numbers and also used to implement the priority queue element in Dijkstra’s shortest path algorithm which reduces the time complexity from O(m log n) to O(m + n log n)

Data Structures

Understanding Bit mask/ Bit map in depth

A bit mask is a data structure, usually an integer or array of bits, that represent a bit pattern which signifies a particular state in a particular computational problem. It takes advantage of bitwise operations.

Data Structures

Binary Tree

A binary tree is a tree data structure in which each node has upto two children (that is a maximum of two children nodes), which are referred to as the left child and the right child. Implementation and applications of binary tree