Dineshkumar Ponnusamy

If you want to get a job in any software company, and you are ready to learn anything, then try the following items.

Algorithms forever

Note: At least 50% of the software engineers may not even heard of these algorithms.

First start with Linear data structures and algorithms.

• Arrays
• Linked List
• Stack
• Queues

Then move to basic algorithms :

• Sorting - Merge Sort, Insertion Sort, Quick Sort, Number of inversions
• Matrix Multiplication (just know the algorithm, if not implement it)
• Prime Sieving
• Modular Math including multiplication and division
• Euclidean Algorithm for GCD, Modular Inverse, Fast Exponentiation
• Fibonacci number with matrix multiplication
• Probability distribution and expected value
• Stats - Mean, Median, Variance, Bayes theorem

Then one can learn some popular algorithmic techniques:

• Divide and Conquer - Binary Search, Maximum Subarray
• Greedy Algorithms - Activity Selection, Huffman encoding
• Dynamic Programming - Matrix Chain Multiplication, Knapsack,
• Linear Programming - Variable Maximisation, Linear time sorting
• String Algorithms - Manacher, LCS, Edit Distance

Then comes some typical non-linear data structures:

• Trees - Binary Tree, General Tree, Lowest Common Ancestor
• Binary Search Tree - In order Traversal, Level order traversal, finding kth largest element, diameter, depth, number of nodes, etc.
• Heaps - Array Implementation, Heapify, Heap Sort
• Union Find
• Hash Table - Linear Probing, Open addressing, Collision avoidance

Then you can learn about Graphs:

• Adjacency List, Adjacency Matrix, Weighted Edge Graphs
• Basic Traversal algos - Breadth First Search, Depth First Search, etc
• Shortest Path Finding Algorithm - Dijkstra, Floyd Warshal, Bellman Ford
• Minimum Spanning Tree - Kruskal's Algorithm, Prim's Algorithm

By this time you are already pretty good with programming. You will do better than most of undergrad CS students. If you want to learn more and delve deep read more.

Advance Tree and Graph :

• Balanced Trees - AVL, Red-Black
• Heavy Light Decomposition, B+ Trees, Quad Tree
• Advance Graph - Min Cut, Max Flow
• Maximum Matching - Hall's Marriage
• Hamiltonian Cycle
• Edge Graphs / Line Graphs
• Strongly Connected Components
• Dominant Sub-Graph, Vertex Cover, Travelling Salesman - Approx algorithms

Advance String Algorithms :

• Knuth Morris Pratt Algorithm
• Rabin Karp Algorithm
• Tries and Compressed Tries
• Prefix Trees, Suffix Trees, Suffix Automation - Ukkonen Algorithm

Advance Math:

• Fast Fourier Transformation
• Primality Testing
• Computational Geometry - Closest point pair, Voronoi diagram, Convex Hull.

General Advance topics :

• Iterating through all combination / permutation
• Bit manipulation