Data Structures and Algorithms [DSA]
Introduction
Data Structures & Algorithms (DSA) are the building blocks that allow programmers to code and think at a higher level. Data structures are unique ways of organising and collecting data so that we can perform operations in an effective way. Algorithms are a set of instructions that solve hard problems in an efficient manner. Understanding DSA is critical for entry level interviews. DSA is usually technology agnostic so it instills a strong computer science mindset.
Abstract Data Structures
DSA.1 Understand that native data types and how you associate them is the foundation of all abstract data Structures.
DSA.1.a Show examples of association between data, example: linking lists and graphs.
DSA.1.b Singly Linked List: Understand how to build a Node class and the relationship between nodes, implement SLL class with Head only, implement: push(), pop(), find(), and understand the run time for each method.
DSA.1.c Doubly Linked List: Implement DLL class with Head and Tail pointers, implement: push(), pop(), find(), removeAt(), understand the run time for each method.
DSA.1.d Hash Tables: Understand dictionaries, key and value mapping, real world use cases, and common methods and run times. Understand the reason for a Hash Method, how to get O(1) insert and find, collision, and best case vs worst case runtimes.
DSA.1.e Stacks: Understand LIFO and real world use cases, implement: push(), pop(), isEmpty(), and understand the run time for each method.
DSA.1.f Queues: Understand FIFO and real world use cases, implement: Enqueue(), Dequeue(), isEmpty(), and understand the run time for each method.
DSA.1.g Trees: Understand abstraction of a tree data structure and be able to implement it using nodes. Know the use cases for trees.
DSA.1.h Graphs: Understand abstraction of a graph data structure and be able to implement it using nodes. Know the use cases for graphs.
Big(O) Notation
DSA.2 Know that big(O) notation is used to describe the worst case space or time required to execute an algorithm.
DSA.2.a Know that O(1) describes and algorithm that will require the same time/space no matter the size of the data set it operates on. Explain why a O(1) algorithm's graph is flat line.
DSA.2.b Know that O(n) describes an algorithm that will increase space/time requirements linearly in proportion to the size of the data set it operates on. Explain why an O(n) algorithm's graph is a straight diagonal line, going up from left to right.
DSA.2.c Know that O(n2) describes an algorithm that will increase space/time requirements in proportion to the square of the size of the data set. Understand that usually refers to an iteration nested within an iteration and that additional nestings will lead to O(n3), O(n4), etc. Know that O(n2) will produce a parabolic graph.
DSA.2.d Know that O(2n) describes an algorithm that will double in space/time requirements for every increase in the size of the data set. Know that the graph for O(2n) is exponential, starting off shallow and increasing sharply until it appears vertical.
DSA.2.e Know that O(log n) describes an algorithm (most commonly binary search) where the data set is halved at each iteration so that the increase in space/time requirements increases very little with an increase in the size of data set. Know that the graph for O(log n) is a horizontal parabola, starting off sharply, then leveling off horizontally.
DSA.2.f Know the the order of most efficient(requires the least space/time) to least efficient (requires the most space/time) is O(1), O(log n), O(n), O(n2), O(2n).
Recursion
DSA.3 Understand that a recursive function is any function that calls itself until a task is complete. Able to write recursive functions to solve a problem.
DSA.3.a Understand the concept of a base case and how to determine the base case for a recursive solution.
DSA.3.b Understand how to write a recursive solution that avoids cycles and simplifies the problem with each call.
DSA.3.c Able to determine when a recursive solution is most appropriate (such as with hierarchies, graphs, or networks) and give the big O for the solution in comparison to an iterative solution.
DSA.3.d Understand the call stack's relationship to recursion and how the returns bubble up through the stack in a recursive function.
DSA.3.e Able to fluently solve common recursive problems such as factorials and fibonacci.
DSA.3.f Able to use dynamic programming, including memoization to improve space/time complexity of recursive solutions.
Sorting Algorithms
DSA.4 Understand why we sort and why it's useful. Know real world examples of sorting. Able to compare different sorting algorithms and run times.
DSA.4.a Implement Bubble Sort and know it's run time.
DSA.4.b Implement Quick Sort and know it's run time.
DSA.4.c Implement Merge Sort and know it's run time.
Search Algorithms
DSA.5 Understand the purpose of search algorithms, when to implement them, and able to compare different search algorithms and run times.
DSA.5.a Divide and Conquer: Know how to brute force search an array and understand the worst case for brute force search.
DSA.5.b Binary search: Understand binary search, know the worst case scenario for binary search, and implement binary search.
DSA.5.c Binary Search Tree: Understand rules of a BST, understand use case of a BST, and implement insert(), find(), Min() and Max().
DSA.5.d Depth First / Breadth First: Implement Depth First Search and Breadth First Search.
DSA.5.e Dijkstra’s Algorithm: Understand concept of shortest path algorithm and vertex. Understand use cases, example: Google Maps, MTA Route to Destination. Implement Dijkstra's Algorithm.