PHASE 1 : Array Linked List – Single and Doubly and Circular Stack Queues Hashing Sorting - SBI (selection, bubble, insertion) - Merge sort - Heap sort (learn this later when you understand graphs/trees) - Quick sort (mainly, hoare’s partition scheme) - Use quick sort everywhere, it worked well for all algorithms. Search Algo… Continue reading THE PLAN
Ordered Set
An ordered set is same as the sorted set data structure in Redis. An ordered set can be implemented using a number of data structure. Like the sorted set in Redis is implemented using Skip List. It can be implemented using AVL tree, Red-Black Tree, Splay Tree. An ordered set is a common data structure that… Continue reading Ordered Set
Gnutella Working
Video How a Gnutella client finds a song Given that there is no central server to store the names and locations of all the available files, how does the Gnutella software on your machine find a song on someone else's machine? The process goes something like this: You type in the name of the song… Continue reading Gnutella Working
B – Tree
B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red Black Trees), it is assumed that everything is in main memory. To understand use of B-Trees, we must think of huge amount of data that cannot fit in main memory. When the number of keys is high, the data is… Continue reading B – Tree
Heap – Theory
For a binary heap we have O(log(n)) for insert, O(log(n)) for delete min and heap construction can be done in O(n). SO Searching in a heap - You need to search through every element in the heap in order to determine if an element is inside. One optimization is possible, though (we assume a max… Continue reading Heap – Theory
BST – Set 1
BST Visualizer In a complete(almost) binary tree number of nodes (n) and height of tree (h) have a relationship like => n = 2^(h+1) -1, this is the all the nodes of the tree. If we have n nodes in a complete(almost) BT then height of the tree will be floor(log(n)), (base 2) this is… Continue reading BST – Set 1
Binary Tree – Set 3
BT Set – 2, BT Set – 1, Question Set (101- ..) Binary Tree Visualizer Remove nodes on root to leaf paths of length < K. GFG Algo: The idea here is to use post order traversal of the tree. Before removing a node we need to check that all the children of that node in the shorter… Continue reading Binary Tree – Set 3
Binary Tree – Set 2
BT Set - 1, BT Set - 3 , Question Set(41-101) Binary Tree Visualizer *** Populate Inorder Successor for all nodes Code This is also referred to as Threaded Binary Tree. GFG Algo: 1. We need to do a reverse inorder traverse. 2. The same can be easily implemented using queue.We first do an inorder… Continue reading Binary Tree – Set 2
Self Balancing Binary Tree
AVL Tree Implementation. Code. GFG - Insert, Delete Youtube Time Complexity: The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Updating the height and getting the balance factor also take constant time. So the time complexity of AVL insert remains same as BST insert which is O(h) where… Continue reading Self Balancing Binary Tree
Binary Tree – Set 1
BT Set - 2, BT Set - 3 , Question Set (1- 40) Binary Tree Visualizer *** Binary Tree Traversal. Depth First Traversals: Code GFG Time Complexity: O(n) where n is number of nodes in the binary tree Inorder: Left, Root, Right - [Pending] Morris Traversal for Inorder ( No stack, No Recursion) (Code, GFG) - Iterative using… Continue reading Binary Tree – Set 1
Sorting – Set 3
Sorting, Sorting Set 1, Sorting Set 2 [Merge Sort] Sort array after converting elements to their squares Given a array of both positive and negative integers ‘arr[]’ which are sorted. Task is to sort square of the numbers of the Array. GFG Algo: 1. Efficient solution is based on the fact that given array is… Continue reading Sorting – Set 3
