Skip to main content

advanced-ds

Advanced Data structures#

  • Advanced List -

    • xor based linked list can be used to store a single address for double linked list
    • Skip list can be used to divide list into sqrt(n), where n is length of linked list and keep sqrt(n) extra nodes and connect them , so that they can be skipped, for a sorted list in order to search. this gives O(sqrt(n))

  • Segment Tree -

    • An array for sum in a given range gives O(n) and update an index gives O(1).
    • we can create a new Data struture Segment Tree that does n order time complexity problems for a given array in O(logn). like (finding sum for a range in an array). we construct and store values in node of segment tree based on the problem.
    • size of the segment tree is 2n-1 .
    • Just like heap, An array representation of tree is used to represent Segment Trees. For each node at index i, the left child is at index 2i+1, right child at 2i+2 and the parent is at (i-1)/2
    • for each change in our segment tree we create a new version of it. We will consider our initial version to be Version-0. Now, as we do any update in the segment tree we will create a new version for it and in similar fashion track the record for all versions. ~

  • Trie -

    • trie is used to search a name in phone contacts; searching for "shu" should give shubham, shubhendu, shubhash etc. This search query is highly optimized. We can give up space as its cheaper.
    • A kind of tree that is used to store a set of words in a particular fashio that is efficient in terms of search, providing time complexity as O(m) where m is the length of word searched.
    • It needs a lot of memory to implement. The maximum number of children of a node is equal to the size of the alphabet(for english it is 26).
    • Each node has a key(equal to letter) and has a hash map that stores the letter as children and isEnd filed which indicates if it marks the end of a word.
    • it supports insert, search and deplete opeartion.
    • while creating a trie from words, we can store the count also in a node, how many times that letter has come. (this helps solving some of the problems)
    • creating a trie of all suffixes of a word
    • for a binary matrix, we can store 0 and 1 in atrie and construct the rows
    • if a question is related to prefix or suffix, pay attention to what information you can store while conctructing trie, that can give result easily e.g https://www.geeksforgeeks.org/weighted-prefix-search/