Introduction To
Advanced Data Structures
Data Structures are used to store and manage data in an efficient and organised way for faster and easy access and modification of Data. Some of the basic data structures are Arrays, LinkedList, Stacks, Queues etc.
To understand the material in this book you should be comfortable enough in a programming language to be capable of working with and writing your own variables, arithmetic expressions, if-else conditions, loops, subroutines (also known as functions), pointers (also known as references or object handles), structures (also known as records or classes), simple input and output, and simple recursion. Because many different languages approach the construction of data structures differently, we use pseudo-code so that you can translate the code into your own language.
Course Structure
Advanced Lists
Segment Tree
- Segment Tree | Set 1 (Sum of given range)
- Segment Tree | Set 2 (Range Minimum Query)
- Lazy Propagation in Segment Tree
- Persistent Segment Tree | Set 1 (Introduction)
- Efficiently design Insert, Delete and Median queries on a set
- Min-Max Range Queries in Array
- Count and Toggle Queries on a Binary Array
- Querying maximum number of divisors that a number in a given range has
- Smallest Subarray with given GCD
- Largest Rectangular Area in a Histogram | Set 1
- Heavy Light Decomposition | Set 1 (Introduction)
- Heavy Light Decomposition | Set 2 (Implementation)
- Reconstructing Segment Tree
- Longest Common Extension / LCE | Set 1 (Introduction and Naive Method)
- Longest Common Extension / LCE | Set 2 ( Reduction to RMQ)
- Longest Common Extension / LCE | Set 3 (Segment Tree Method)
Trie
- Trie | (Insert and Search)
- Trie | (Delete)
- Longest prefix matching – A Trie based solution in Java
- Pattern Searching using a Trie of all Suffixes
- Find shortest unique prefix for every word in a given list | Set 1 (Using Trie)
- Longest Common Prefix using Trie
- Print all words matching a pattern in CamelCase Notation Dictonary
- Implement a Phone Directory
- Construct a unique matrix n x n for an input n
- Count of distinct substrings of a string using Suffix Trie
- Minimum XOR Value Pair
- Find the maximum subarray XOR in a given array
- Weighted Prefix Search
- Boggle | Set 2 (Using Trie)
- Print all valid words that are possible using Characters of Array
- Find the k most frequent words from a file
- Palindrome pair in an array of words (or strings)
- Word formation using concatenation of two dictionary words
- Given a sequence of words, print all anagrams together | Set 2
- How to Implement Reverse DNS Look Up Cache?
- How to Implement Forward DNS Look Up Cache?
Binary Indexed Tree
- Binary Indexed Tree or Fenwick Tree
- Two Dimensional Binary Indexed Tree or Fenwick Tree
- Binary Indexed Tree : Range Update and Range Queries
- Count inversions in an array | Set 3 (Using BIT)
- Count Inversions of size three in a given array
- Count inversion pairs in a matrix
- Counting Triangles in a Rectangular space using BIT
- Finding the number of triangles amongst horizontal and vertical line segments
- Querying the number of distinct colors in a subtree of a colored tree using BIT
- Queries on substring palindrome formation
- proto van Emde Boas Trees | Set 1 (Background and Introduction)
Suffix Array and Suffix Tree
- Suffix Array | Set 1 (Introduction)
- Suffix Array | Set 2 (nLogn Algorithm)
- kasai’s Algorithm for Construction of LCP array from Suffix Array
- Pattern Searching using Suffix Tree
- Ukkonen’s Suffix Tree Construction – Part 1
- Ukkonen’s Suffix Tree Construction – Part 2
- Ukkonen’s Suffix Tree Construction – Part 3
- Ukkonen’s Suffix Tree Construction – Part 4
- Ukkonen’s Suffix Tree Construction – Part 5
- Ukkonen’s Suffix Tree Construction – Part 6
- Generalized Suffix Tree 1
- Suffix Tree Application 1 – Substring Check
- Suffix Tree Application 2 – Searching All Patterns
- Suffix Tree Application 3 – Longest Repeated Substring
- Suffix Tree Application 4 – Build Linear Time Suffix Array
- Suffix Tree Application 5 – Longest Common Substring
- Suffix Tree Application 6 – Longest Palindromic Substring
- Print Kth character in sorted concatenated substrings of a string
Self-Balancing BSTs
- AVL Tree | Set 1 (Insertion)
- AVL Tree | Set 2 (Deletion)
- Splay Tree | Set 1 (Search)
- Splay Tree | Set 2 (Insert)
- B-Tree | Set 1 (Introduction)
- B-Tree | Set 2 (Insert)
- B-Tree | Set 3 (Delete)
- B and B+ Trees
- Red-Black Tree | Set 1 (Introduction)
- Red-Black Tree | Set 2 (Insert)
- Red-Black Tree | Set 3 (Delete)
- ScapeGoat Tree | Set 1 (Introduction and Insertion)
- Treap (A Randomized Binary Search Tree)
- Treap | Set 2 (Implementation of Search, Insert and Delete)
- Maximum subarray sum modulo m
- Find N’th item in a set formed by sum of two arrays
- Count smaller elements on right side
- Maximum product of an increasing subsequence of size 3
- How to sort a big array with many repetitions?
- Find last unique URL from long list of URLs in single traversal
k Dimensional Tree
Disjoint Set
n-ary Trees and LCA
- Mirror of n-ary Tree
- Diameter of an N-ary tree
- Depth of an N-Ary tree
- Height of n-ary tree if parent array is given
- Second Largest element in n-ary tree
- Diameter of n-ary tree using BFS
- Number of ways to traverse an N-ary tree
- Number of nodes greater than a given value in n-ary tree
- Number of children of given node in n-ary Tree
- Next Larger element in n-ary tree
- Immediate Smaller element in an N-ary Tree
- Sum of all elements of N-ary Tree
- Serialize and Deserialize an N-ary Tree
- Subtrees formed after bursting nodes
- Locking and Unlocking of Resources arranged in the form of n-ary Tree
- LCA for general or n-ary trees (Sparse Matrix DP approach < O(nlogn), O(logn)>)
- Sqrt (or Square Root) Decomposition | Set 2 (LCA of Tree in O(sqrt(height)) time)
- LCA for n-ary Tree | Constant Query O(1)
- Tarjan’s off-line lowest common ancestors algorithm
- Left-Child Right-Sibling Representation of Tree
- Node having maximum sum of immediate children and itself in n-ary tree
- Given a n-ary tree, count number of nodes which have more number of children than parents
- General Tree (Each node can have arbitrary number of children) Level Order Traversal
Others
- Palindromic Tree | Introduction & Implementation
- Ternary Search Tree
- Interval Tree
- BK-Tree | Introduction & Implementation
- Ropes Data Structure (Fast String Concatenation)
- Summed Area Table – Submatrix Summation
- LRU Cache Implementation
- Substring with highest frequency length product
- Find whether a subarray is in form of a mountain or not
- Find all possible interpretations of an array of digits
- How to design a tiny URL or URL shortener?
- Second minimum element using minimum comparisons
- Decision Trees – Fake (Counterfeit) Coin Puzzle (12 Coin Puzzle)
- Data Structure for Dictionary and Spell Checker?
- Cartesian Tree
- Cartesian Tree Sorting
- Sparse Set
- Centroid Decomposition of Tree
- Gomory-Hu Tree | Set 1 (Introduction)