Important Data Structure And Algorithms To Prepare For Interview

Below is the cheat sheet for imp. DS and Algos !

A. String/Array/Matrix

1) Evaluate Reverse Polish Notation
2) Longest Palindromic Substring
3) Word Break
4) Word Ladder
5) Median of Two Sorted Arrays
6) Regular Expression Matching
7) Merge Intervals
8) Insert Interval
9) Two Sum
9) 3Sum
9) 4Sum
10) 3Sum Closest
11) String to Integer
12) Merge Sorted Array
13) Valid Parentheses
14) Implement strStr()
15) Set Matrix Zeroes
16) Search Insert Position
17) Longest Consecutive Sequence
18) Valid Palindrome
19) Spiral Matrix
20) Search a 2D Matrix
21) Rotate Image
22) Triangle
23) Distinct Subsequences Total
24) Maximum Subarray
25) Remove Duplicates from Sorted Array
26) Remove Duplicates from Sorted Array II
27) Longest Substring Without Repeating Characters
28) Longest Substring that contains 2 unique characters
29) Palindrome Partitioning
30) Reverse Words in a String

B. Linked List

1) Add Two Numbers
2) Reorder List
3) Linked List Cycle
4) Copy List with Random Pointer
5) Merge Two Sorted Lists
6) Merge k Sorted Lists *
7) Remove Duplicates from Sorted List
8) Partition List
9) LRU Cache

C. Tree & Heap

1) Binary Tree Preorder Traversal
2) Binary Tree Inorder Traversal
3) Binary Tree Postorder Traversal
4) Word Ladder
5) Validate Binary Search Tree
6) Flatten Binary Tree to Linked List
7) Path Sum
8) Construct Binary Tree from Inorder and Postorder Traversal
9) Convert Sorted Array to Binary Search Tree
10) Convert Sorted List to Binary Search Tree
11) Minimum Depth of Binary Tree
12) Binary Tree Maximum Path Sum *
13) Balanced Binary Tree

D. Graph

1) Clone Graph

E. Sorting

1) Mergesort
2) Quicksort
3) InsertionSort.

Some Resources For Above Problems

Concepts

1. Heap Data Structure & Priority Queue
2. Heap Operations
3. Standar Trie, Compressed Trie, Suffix Tree Concepts and Runtimes
4. Trie Concepts and count matching prefixes and words
5. Growth of time complexity explained in Big O
6. Understanding B Tree and B+ Tree – 1
7. Understanding B Tree and B+ Tree – 2
8. When to use B and B+ Tree
9. Power of B+ Tree in DB
10. AVL Tree Animation
11. AVL Tree 
12. Difference AVL & RB Tree
13. Splay Tree

Video Tutorials

• IIT Video Tutorials  – My Favorite – Best of Best
• MIT Video Lectures
• XOAX – All sorting & searching algorithms & Big O Concepts
• Red Black Tree Demo
• Splay Tree Demo
• AVL Tree Demo

 

Java Implementations of various Algorithms

• Suffix Tree
• BST
• Binary Heap
• Trie -1
• Trie -2
• Trie -3
• Inorder Traversal
• Preorder Traversal
• Postorder Traversal
• B Tree
• AVL Trees
• N-Way Inmemory merge sort
• Selection Sort

Practice Java Programs

1. Reverse Singly Linked List
2. Reverse Doubly Linked List
3. BST to Sorted Doubly Linked List
4. Sorted List to Balanced BST
5. Sudoku Checker-1
6. Sudoku Checker-2

Best Books for practice programs

1. Cracking code Interview – Gayle
2. Programming Interview Exposed

Other Useful References

1. Number Systems
2. General Maths