Essential Data Structures and Algorithms

Over the past few years, I have taken numerous technical interviews and one thing that remains common throughout is the Data Structures and Algorithm round. Although most of the questions are always standard but still many people struggle to answer.

Keeping that in mind I thought of listing down a set of important Algorithms and Data Structure that I have come across and are tested again and again in the interviews.

Note that you don’t need to know all of these right from the beginning. I suggest you take one step at a time. Start with one data structure/algorithm understand its properties and then figure out the use cases where you can use it.

Algorithm

An algorithm is a technique or recipe for solving a problem, based on conducting a sequence of indicated activities. Knowing the various algorithm design techniques may help you in approaching a problem in a more informed way. I have listed below a set of algorithm design techniques:

• Divide and Conquer: the problem is divided into several small independent sub-problems. Then the sub-problems are solved recursively and combined to get the solution of the original problem. {Examples: Merge-Sort algorithm}
• Dynamic Programming: divides the problem into smaller overlapping sub-problems and after solving each sub-problem, dynamic programming reuses these solutions to solve the bigger problem in order to get the ultimate solution.
• Greedy approach: the best solution is chosen at any moment. This algorithm design technique is called greedy because it ignores the bigger picture as a whole and looks for optimal solution of a smaller instance. {Examples: Dijkstra’s algorithm, Prim’s algorithm, Krushkal’s algorithm}
• Backtracking: optimization technique to solve combinational problems under the given parameters. It could be applied to both programmatic and real-life problems. It looks for solution using — DFS approach.{Examples: Eight queen problem, Sudoku puzzle, Finding path in a Maze}
• Branch & Bound: is an optimization technique to get an optimal solution to the problem. It looks for the best solution for a given problem in the entire space of the solution. It realizes that it already has a better optimal solution than the pre-solution leads to so it abandons that pre-solution. It may traverse for solution in any fashion — BFS or DFS. {Example: 0/1 Knapsack Problem}

Standard good to know algorithms

• Searching Algorithms: Linear Search {O(n)} and Binary Search {O(logn)}
• Sorting Algorithms: Comparison Sorts make no assumptions on the data and compare all elements against each other. They have best case run time of O(N lg N). Where for “Linear Sorts” like Counting and Radix O(N) time is possible if we make assumptions about the data and don’t compare elements against each other (i.e., we know the data falls into a certain range or has some distribution).
• String Matching Algorithms: Knuth-Morris-Pratt, Boyer-Moore, Robin-Karp
• Graph Algorithms: Breadth First Search, Depth First Search, Dijkstra’s {single source shortest path with only positive edges, uses greedy approach}, Bellman-Ford {single source shortest path with both positive and negative edges}, Prim’s {minimam spanning tree, starts with a node, uses greedy approach}, Krushkal’s {minimam spanning tree, starts with an edge, uses greedy approach}, A* {used for path finding, an improvement on dijkstra’s}, Ford-Fulkerson {maximum flow in a flow network}, Edmonds-Karp {a specific impl of Ford-Fulkerson}

Data Structures

A data structure is a specialized format for organizing and storing data. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.

• Stack & Queues {LIFO & FIFO}
• Arrays and Vectors {store and retrieve data based on indexes}
• Linked Lists {singly LL, doubly LL, circular LL}
• Trees {binary trees, binary search trees, AVL trees, Red-Black trees}
• Maps {HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap, HashTable}
• Heaps {Min-Heaps, Max-Heaps}
• Skiplists {faster search within an ordered sequence}
• Tries & Suffix Trees {used for string processing — auto-complete and pattern matching}