SDEPost

What is Trie Data Structure? Trie is a kind of tree data structure used to store that data in an ordered and efficient way. We use Trie to store string. A single node in the Trie data structure has a character and 26 references to keep 26 different alphabets. Using the Trie data structure we can optimize the search complexity to O(l), the length of the string. Node Class Represents a single node of the Trie data structure  It has 3 instance variables- 1) char - to store the character of this node. 2) is_terminal - A boolean that represents whether it is the end of any word. 3) children - A dictionary that can store this node's 26 references Trie Class It has a single instance variable  1) root - root node of Trie, it does not store any character  It has 2 main methods  1) insert() - to insert a word in Trie. 2) search() - to search a word i Trie. Algorithm 1) Insert  We are using recursion to insert words.  a) If the word has a length of 0 - Check if the wo...

     How to implement LRU cache in python? What is LRU cache? Least-recently-used (LRU) cache replacement is algorithms that removes least recent used data to make room for newdata. Terminology Used in post DLL -> Doubly Linked List Front of DLL -> node just after head node of DLL Last node of DLL-> Node just before tail node of DLL LRU CLASS We have implemented LRU using a Doubly Linked list and Dictionary data structure. There are two nodes at the beginning and end of DLL, (HEAD and TAIL) that both have Key = -1 and Val = -1.  We have used dictionary to store key as key of item and value as node object DLL of the LRU class. We are saving item in dictionary having key as key of LRU cache(Node) item and value as Node object of LRU cache item, so at any instance if we have Key of item we can get the item by getting value of key which is Node object. Instance variable "size" is defined in order to define max size of LRU cache. ALGORITHM put(key, valu...