Implementation Of Generic Data Structures & Algorithms in Python & C++.
DSA : Array (Two pointers method, sliding window, variable swap) Linked List (Singly, Doubly, Circular, Circular Doubly) Stack Queue Binary Tree Binary Search Tree Heap Hashing Graph Matrix Advanced Data Structure
Linked List:
1. Len of LL
2. LL del (a key, a key at a given pos)
3. len of LL (iterative & recursive ways)
4. swap nodes in a ll w.o. swapping data
5. reverse a ll
6. merge two sorted ll
7. merge sort for ll
8. reverse a ll in groups of given size
9. rotate a ll
10.add two nums rep by a ll
Circular LL
1. CLL traversal
2. Split a CLL into two halves
DLL
1. Quicksort on dll
2. Mergesort for dll
Stack
1. Infix to postfix conversion
2. Eval of Postfix expression
3. Reverse a string using stack
4. stack using 2 arr
5. balanced parantheses
6. next greater elem
7. reverse a stack using recursion
8. sort a stack using recursion
9. stock span problem
10.design and implement spl stack ds
11.implement stack using queues
12.design a stack with operations on middle elem
13.how to efficiently implement k stacks in a single array
14.sort a stack using recursion
Queue
1. arr impl of queue
2. ll impl of queue
3. priority queue
4. deque using circular arr
5. queue using stack
6. circular tour that visits all gasoline stations
7. max of all subarr of size k
8. implement k Queues in a single arr
Binary Tree
1. handshaking lemma
2. enumeration of bin tree
3. tree traversals
4. bfs and dfs for tree
5. diameter of a bin tree
6. level order tree traversal
7. inorder tree traversal w.o. recursion
8. inorder tree traversal w/ recursion
9. threded binary tree
10.max depth ot ht of a tree
11,if u are given 2 traversal sequences, can you construct the bin tree?
12. clone a bin tree with random pointers
13. construct tree from given inorder and preorder traversals
14. max width of a bin tree
15. print nodes at k distance from root
16. print ancestors of a given node in binary tree
17. check if a binary tree is subtree of another binary tree
18. connect nodes at the same level
BST
1. search & insert in bst
2. del from bst
3. min val in a bst
4. inorder predecessor and successor in bst
5. check if tree is a bst or not
6. lowest common ancestor in a bst
7. inorder successor in bst
8. find k-th smallest elem in bst (order statistics in bst)
9. merge two bst with limited extra space
10. two nodes of a bst are swapped, correct the bst
11. floor and ceil from a bst
12. in-place conversion of sorted dll to balanced bst
14. find a pair with given sum in a bst
15. total num of possible bst with n keys
16. merge two balanced bst
17. bin tree to bst conversion
Heap
1. Bin heap
2. Why is bin heap preferred over bst for priority queue?
3. binomial heap
4. fibonacci heap
5. heap sort
6. kth largest element in an array
7. sort an almost sorted array
8. tournament tree and binary heap
Hashing
1. separate chainning for collision handling
2. open addressing for collision handling
3. print a bin tree in vertical order
4. find whether an array is a subset of another array
5. union and intersection of two ll
6. find a pair with given sum
7. check if a given array contains duplicate elements within k distance from each other
8. check if a given array contains duplicate elements within k distance from each other
9. find itineraru from a given list of tickets
10. find number of employees under every employee
Graph
1. Graph and its rep
2. BFS for a graph
3. DFS for a graph
4. detect cycle in a dg
5. detect cycle in an udg
6. longest path in a dag
7. topological sorting
8. check whether a given graoh in bipartite or not
9. snake and ladder problem
10. minimize cash flow among a given set of friends who have borrowed money from each other
11. boggle
Adv DS
1. Memory efficient dll
2. xor ll
3. skip list
4, self orgaizing list
5. unrolled ll
Segment Tree
1. trie
2. longest prefix matching
3. reverse dns look up cache
Trie
1. Trie (Insert and Search)
2. Trie (Del)
3. Longest prefix matching - A Trie based solution
4. Print unique rows in a given boolean matrix
5. How to implement reverse DNS look up cache
6. How to implement forward DNS look up cache
Binary Indexed Tree
1. Binary Indexed Tree
2. Two Dimensional Binary Indexed Tree or Fenwick Tree
3. Binary Indexed Tree: Range Updates and Point Queries
4. Binary Indexed TreeL Range Update and Range Queries
Suffix Array and Suffix Tree:
1. Suffix Array Intro
2. Kasai's algorithm for construction of LCP array from Suffix Arr
3. Suffix Tree Introduction
4. Ukkonen''s Suffix Tree Construction
5. Generalized Suffix Tree
6. Build Linear Time Suffix Arr Using Suffix Tree
7. Generalized Suffix Tree
8. Build Linear Time Suffix Arr
9. Substring Check
10.Longest Repeated Substring
11.Longest Common Substring, Longest Palindromic Substring
AVL Tree
1. AVL Tree
2. AVL Tree with duplicate keys
Splay Tree
1. Splay Tree
B Tree
1. B-Tree
Red Black Tree
1. Red Black Tree
K Dimensional Tree
1. Search,Ins,Del,Fin Max
Others:
1. Treap
2. Ternary Search Tree
3. Interval Tree
4. Implement LRU Cache
5. Sort numbers stored on diff machines
6. Find the K most frequent words from file
Array
1.Leaders in an arr
2.majority elem
3.find the num occuring odd num of times
4.largest sum contiguous subarr
5.Find the missing num
6. search an elem in a sorted and pivoted arr
7.merge an arr of size n into another array of size(m + n)
8.median of two sorted arrs
9.program for arr rotation
10.reversal algorithm for arr rotation
11.block swap algo for arr rotation
12.max sum s.t. no elems are adjácent
13.sort elems by frequency
13.count inversions in an arr
Matrix
1.Search in a row wise and col wise sorted matrix
2.Print a given matrix in spiral form
3.A boolean matrix question
4.Maximum size square sub-matrix with all 1s
5.Inplace MxN size matrix transpose
6. Strassen Mat multiplixation
7. Create a matrix with alternationg rectangles of 0 and x
8.print all elems in sorted order from row and col wise sorted matrix
9.count the number of islands where every island is row
10.find a common element in all rows of a given row-wise sorted matrix