DSA and Algos.pdf

DSA and Algos Tuesday, March 21, 2023 7:20 PM Linked List: Good for….insert and delete in O(1), because in an array the elements need to be shifted Bad for….Access is in Linear Time because you start from head and travers to the point you're looking for. Structure: Is the node an...

DSA and Algos Tuesday, March 21, 2023 7:20 PM Linked List: Good for….insert and delete in O(1), because in an array the elements need to be shifted Bad for….Access is in Linear Time because you start from head and travers to the point you're looking for. Structure: Is the node and the reference to the next node. ○ Class ListNode: ▪ Def __init__(self, data): □ Self.data = data □ Self.next = None Types of Linked List: ○ Singly: each node points to the next node and last points to none or null ○ Doubly: each node has two pointers. Next point points to next node and the Prev pointer points to the previous node. Note that the prev pointer of the first node will point to null and the next pointer of the last node will point to ○ Circular: this is a singly linked list where the last node points back to the first node. The Prev pointer of the first node point to the last node and the next pointer of the last node points to the first node. Time Complexity: ○ Access: Going to get a specific value is O(n) because you must traverse starting from the head and reach the value you're looking for. ○ Search: O(n) Same thing with accessing if you're searching for the node you must traverse each node starting from the head. ○ Insert: O(1) assumes you have traverses to the insertion position ○ Remove: O(1) assumes you have traversed to the node to be removed. Common Routines: ○ Reversing in-place ○ Finding the middle of the linked list using two pointers (fast and slow) ○ Merging two linked list together Edge Cases: ○ Empty linked list: ▪ If not head: □ Return "Linked list is empty" ○ Single nodes ○ Two nodes ○ Clarify the type of linked list and if it has cycles. "Can there be a cycle in the list?" Techniques: ○ Dummy Nodes: ▪ Dummy node help to ensure you're not doing any operations on the head or tail so you don’t lose access to the head. ○ Two pointers: ▪ Getting the kth from the last node: you have two pointers where one pointer is k nodes ahead of the other. When the node ahead reaches the end, the other pointer is k nodes behind. ▪ Detecting Cycles: you have two pointers where one pointer increments twice as much as the other. Is the two pointers meet that means there is a cycle. This is cool because in order to detect a cycle there needs to be a pointer that is going twice as fast as the other. ▪ Getting the middle node: you have two pointers where one pointer increments twice as much as the other. When the faster node reaches the end of the list the slower node will be at the middle. Space Complexity: ○ If you make a new linked list and add nodes to the new linked list it will take extra space O(n) and will be too easy. ○ If you modify the linked list in place it will be O(1) Essential Questions: ○ Reverse a Linked List ○ Detect Cycle in a Linked List Try: ○ Merge Two Sorted Lists ○ Merge K Sorted Lists ○ Remove Nth Node From End Of List ○ Reorder List DSA and Algos Page 1 Matrices: Related to dynamic programing or graph traversal problems. Matrices can be used as graphs where each node is a cell on the matrix which has 4 neighbors (except those cells on the edge and corners) Edge Cases: ○ Empty Matrix; so check that the length of the array is not 0. ○ Matrix that are 1x1 ○ A matrix with only one row or one column Techniques: ○ For questions involving traversal or dynamic programming you want to make a copy of the matrix with the same size/dimensions that is then initialized to empty values to store the visited state or dynamic programming table. ▪ For python this can be done like this: □ Zero_matrix = [[0 for _ in range(len(matrix))] for _ in range(len(matrix))] ▪ Copying a matrix in python: □ Copied_matrix = [row[:] for row in matrix] ▪ Transposing a matrix: □ Trans_matrix = zip(*matrix) Essential Questions: ○ Set Matrix Zeros ○ Spiral Matrix Try: ○ Rotate Image ○ Valid Sudoku Queue: Enqueue Operation: adding elements at one end of the sequence Dequeue Operation: removal of elements First in First out: BFS is implemented using queues Learning Resource: ○ Readings ▪ To Queue Or Not To Queue, basecs ○ Videos Queues, University of California San Diego Implementations: ○ from collections import deque Time Complexity: ○ Enqueue(adding): O(1) ○ Dequeue(removing): O(1) ○ Adding to Front: O(1) ○ Adding to Back: O(1) ○ isEmpty: O(1) Note that the doing dequeue on the front of the queue will be O(n) because you would have to shift elements to the left by on e. Make sure you flag this to the interviewer and say that you assume that there's a queue data structure that has an good deque ue operation. Edge Cases: ○ Empty Queue ○ Queue with one item ○ Queue with two items Essential Questions: ○ Implement Stack using Queues Try: ○ Implement Queue using Stacks ○ Design Circular Queue ○ Design Hit Counter Stack: Stacks do push and pop operations (there are others) DSA and Algos Page 2  Stacks do push and pop operations (there are others) ○ Push: insert a new element to the top of stack (aka. add to the right of list) ○ Pop: remove and return the most recently added element from the top of the stack (aka. Pop from the top of the stack) Last in First out; Used to implement DFS DFS can be implemented using a stack or recursion Learning resources Readings Stacks and Overflows, basecs Videos Stacks, University of California San Diego Implemented in python by list: [] Time Complexity: Top/Peek: O(1) Push: O(1) Pop: O(1) isEmpty: O(1) Search: O(n) Edge Cases: Empty Stack and popping from an empty stack Stack with one item Stack with two items Essential Questions: Valid Parenthesis Implement Queue using Stacks Try: Implement Stack using Queues Min Stack Asteroid Collision Evaluate Reverse Polish Notation Basic Calculator Basic Calculator II Daily Temperatures Trapping Rain Water Largest Rectangle in Histogram Intervals: Interval Questions are a subset of array questions. They are an array of two element arrays. Note: ask interviewer whether [1, 2] and [2, 3] are considered overlapping intervals as it affects how you will write your equality checks. Clarify whether an interval of [a, b] will strictly a < b (a is smaller then b); will the beginning of the interval Edge Cases: No intervals Single Intervals Two intervals Non-Overlapping intervals An interval completely in another interval Duplicate intervals (exactly the same start and end) Intervals which start right where another interval ends ([ [1, 2], [2, 3] ]) Techniques: Sort the array of intervals by its starting point You need to know how to solve this problem to solve merge intervals question. Checking if two intervals overlap Be comfortable with writing code to checking if two intervals overlap Def is_overlap(a, b): □ Return a < b and b < a Merging two intervals Def merge_overlap_intervals(a, b): □ Return [min(a, b), max(a, b)] Essential Questions: Merge Intervals DSA and Algos Page 3  Merge Intervals Insert Intervals Try: Non-Overlapping Intervals Meeting Rooms (LeetCode Premium) Meeting Rooms II (LeetCode Premium) Advanced Data Structures: Tree: Each node in the tree can be connected to many children, but must be connected to exactly one parent. Except for the root node, which has no parent. A tree is a undirected acyclic graph. There are no cycles or loops. Each node can be like the root node of its own subtree, m aking recursion a useful technique for tree traversal. For the purpose of interviews, you will be asked binary trees a opposed to ternary or n-ary trees. Note binary search trees are a special case of binary trees. Trees are commonly used to represent hiarchial data, a trie is an advanced trie used to efficiently store and search strings. Learning resources Videos Trees, University of California San Diego A Brief Guide to Binary Search Trees (slides), Samuel Albanie, University of Cambridge A Brief Guide to Red-Black Trees (slides), Samuel Albanie, University of Cambridge A Brief Guide to B-trees (slides), Samuel Albanie, University of Cambridge Readings How To Not Be Stumped By Trees, basecs Leaf It Up To Binary Trees, basecs Additional (only if you have time) The Little AVL Tree That Could, basecs Busying Oneself With B-Trees, basecs Painting Nodes Black With Red-Black Trees, basecs Common terms you need to know Neighbor - Parent or child of a node Ancestor - A node reachable by traversing its parent chain Descendant - A node in the node's subtree Degree - Number of children of a node Degree of a tree - Maximum degree of nodes in the tree Distance - Number of edges along the shortest path between two nodes Level/Depth - Number of edges along the unique path between a node and the root node Width - Number of nodes in a level Diameter - Diameter is the longest path between any two nodes in a tree. This path may or may not pass through the root Binary Tree Nodes in a binary tree have a maximum of two children Terms: Compete Binary Tree - A binary tree is binary tree in which every level, except possibly the last, is completely filled and all nodes in the last level are as far left as possible. Balanced Binary Tree - A binary tree structure in which the left and right subtree of ever node differ in height by no more than 1. Traversals DSA and Algos Page 4  Traversals In-order Traversal: Left -> Root -> Right 2, 7, 5, 6, 11, 1, 9, 5, 9 Pre-order Traversal: Root -> Left -> Right 1, 7, 2, 6, 5, 11, 9, 9, 5 Post-order Traversal: Left -> Right -> Root 2, 5, 11, 6, 7, 5, 9, 9, 1 Binary Search Tree: In-order traversal of a BST will give you all elements in order. Be very familiar with the properties of a BST and validating that a binary tree is a BST. This come up more often than expected. When a question involves BST, look for a solution that runs fast than O(n). Time Complexity: Accessing :: O(long(n)) Searching :: O(long(n)) Inserting :: O(long(n)) Removing :: O(long(n)) Space Complexity: Traversing a balanced tree is O(h) where h is the height of the tree while traversing skewed trees (which is essentially a linked list) will be O(n). Notes for interview: Be very familiar with pre-order, in-order, and post- order traversals recursively. As a challenge write it iteratively. Edge Cases for Trees: Empty Tree Single Node Two Nodes Very skewed trees like a linked list Common Routines: Trees Inserting a value Deleting a value Count number of nodes in a tree Checking for values in a tree Calculating height of a tree Binary Search Trees: Determine if it’s a binary search tree Get maximum value Get minimum value Techniques: Recursion is the most common approach for traversing trees. For recursion in trees always check for the base case, usually where the node is null or none. Sometimes it's possible that your recursive function needs to return two values. Traversing by level: To traverse by level use breadth- first search Summation of nodes: If you're summing nodes, check for whether nodes can be negative. DSA and Algos Page 5  If you're summing nodes, check for whether nodes can be negative. Essential Questions: Binary Tree Maximum Depth of Binary Tree Invert/Flip Binary Tree Binary Search Tree Lowest Common Ancestor of a Binary Search Tree Try: Binary tree Same Tree Binary Tree Maximum Path Sum Binary Tree Level Order Traversal Lowest Common Ancestor of a Binary Tree Binary Tree Right Side View Subtree of Another Tree Construct Binary Tree from Preorder and Inorder Traversal Serialize and Deserialize Binary Tree Binary search tree Validate Binary Search Tree Kth Smallest Element in a BST Graph: A graph is a structure containg a set of objects (nodes and verticies) where there can be edges between the nodes/verticies. Edges can be directed or undirected Trees are undirected graphs in which any two verticies are connected by exactly one edge and there can be no cycles in the gr aph. Learning Resources: Readings From Theory To Practice: Representing Graphs, basecs Deep Dive Through A Graph: DFS Traversal, basecs Going Broad In A Graph: BFS Traversal, basecs Additional (only if you have time) Finding The Shortest Path, With A Little Help From Dijkstra, basecs Spinning Around In Cycles With Directed Acyclic Graphs, basecs Graph Representations You can be given a list of edges and you have to build a graph from that. The common graph representations are: Adjacency Matrix Adjecency List Hash table of hash tables Using a hash table of hash tables would be the simplest approach during algo interviews. It is rare to use a adjacency matrix or list for graph questions. In interviews graphs are commonly given as 2D matrices where the cells are the node and each cell can traverse to its adjacent cell (up, down, right, left) Its so important to be familiar with traversing a 2D matrix. When traversing the matrix, always ensure that your current position is within the boundary of the matrix and it has not been visited. Time Complexity: Depth First Search O(V+E) Breadth First Search O(V+E) Topological Sort O(V+E) Note during an interview… a tree like diagram could verry well be a graph that allows for cycles and a naïve recursive solution would not work. In that case, you will have to handle cycles and keep a set of visited nodes when traversing. Ensure you are correctly keeping track of visited nodes and not visitng each node more than once. Otherwise, your code could end up in an infinte loop. Edge Cases: Empty Graph Graph with one or two nodes Disconnected graphs Graphs with Cycles Graph search algorithms: Common: BFS and DFS Uncommon: Topological Sort, Dijkstra's algorithm Essential Questions: DSA and Algos Page 6  Essential Questions: Number of Islands Flood Fill 01 Matrix Try Breadth-first search Rotting Oranges Minimum Knight Moves (LeetCode Premium) Either search Clone Graph Pacific Atlantic Water Flow Number of Connected Components in an Undirected Graph (LeetCode Premium) Graph Valid Tree (LeetCode Premium) Topological sorting Course Schedule Alien Dictionary (LeetCode Premium) DFS Implementation BFS Implementation DSA and Algos Page 7  Heap: Heap is a specialized tree-based data structure that is a complete tree. There are two type of heaps: Max Heap Min Heap Heaps are useful when its necessary to repeatedly remove the object with the highest (or lowest) priority, or when insertions need to be interspersed with removals of the root node. Learning Resources: Learning to Love Heaps, basecs Heapify All The Things With Heap Sort, basecs Heaps, James Aspnes, Yale University Implementations In Python: use a heapq Time Complexity: Finding max/min ::: O(1) Inserting ::: O(log(n)) Removing ::: O(log(n)) Heapify (creating a heap out of a given array of elements)::: O(n) Techniques: If you see top or lowest k mentioned in a question, it is usually a signal that a heap can be used to solve the problem. (i.e Top K Frequent Elements) If you need to find the top k elements use a min heap of size k. Iterate through each element pushing it into the heap (inver t the array before pushing to find max value) When the heap size exceeds k, remove the minimum element, that will guarantee that you have the k largest element. Essential Questions: Merge K Sorted Lists K Closest Points to Origin Try: DSA and Algos Page 8  Try: Top K Frequent Elements Find Median from Data Stream Trie: Tries are special trees (prefix trees) that make searching and storing strings more effiecent. Be familiar with implementing a trie class and its add, remove, and search methods. Learning resources Readings Trying to Understand Tries, basecs Implement Trie (Prefix Tree), LeetCode Additional (only if you have time) Compressing Radix Trees Without (Too Many) Tears, basecs Time complexity: Searching ::: O(m) Inserting ::: O(m) Removing ::: O(m) Edge Cases: Searching for a string in an empty trie Inserting empty strings into a trie Techniques: Preprocessing a dictinary of words (given in a list) into a trie, will improve the efficiency of searching for a word of leng th k, among n words. Searching becomes O(k) instead of O(n). Essential Questions: Implement Trie (Prefix Tree) Try: Add and Search Word Word Break Word Search II Dynamic Programming: Dynamic Programming is usually used to solve optimization problems. The only way to get better at Dynamic Programming is to practice. It take some amount of time to be able to recognize if a problem can be solves by Dynamic Programming. Learning Resources: Demystifying Dynamic Programming Dynamic Programming – 7 Steps to Solve any DP Interview Problem Less Repetition, More Dynamic Programming, basecs Dynamic Programming, James Aspnes, Yale University Techniques: Sometimes you do not need to store the whole DP table in memory, the last two values or the last two rows of the matrix will suffice. Essential Questions: Climbing Stairs Coin Change House Robber Longest Increasing Subsequence Try 0/1 Knapsack or Partition Equal Subset Sum Longest Common Subsequence Word Break Problem Combination Sum House Robber II Decode Ways Unique Paths Jump Game Binary: Bit Manipulation Questions DSA and Algos Page 9  Bit Manipulation Questions Learning Resources: Readings Bits, Bytes, Building With Binary, basecs Bitwise operation, Wikipedia Videos Algorithms: Bit Manipulation, HackerRank Practice Practice with bit operations Edge Cases: Check for overflow and underflow Negative Numbers Techniques: Essential Questions: Sum of Two Integers Number of 1 Bits Try Counting Bits Missing Number Reverse Bits Single Number Array: Arrays hold values of the same type at memory locations beside each other. In arrays we are usually concerned about two thing s -- the position of an element and the element itself. Mastery of Arrays is Essential!! Good: Storing values of the same type with one single variable name Accessing elements is fast as long as you have the index. Bad: Addition and removal of elements is slow because the remaining elements must be shifted. Only exception is the element at DSA and Algos Page 10  Addition and removal of elements is slow because the remaining elements must be shifted. Only exception is the element at the end of the array. Creating a new array and transferring elements over takes O(n) time. Learning Resources: Readings Array in Data Structure: What is, Arrays Operations, Guru99 Videos Arrays, University of California San Diego Add Remove Beginning O(n) O(n) End O(1) O(1) Middle O(n) O(n) Common Terms: Subarray: A range of contiguous values within an array. given an array [2, 3, 6, 1, 5, 4], [3, 6, 1] is a subarray while [3, 1, 5] is not a subarray. Subsequence: A sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. given an array [2, 3, 6, 1, 5, 4], [3, 6, 1] is a subarray while [3, 1, 5] is not a subarray. Time Complexity Accessing::: O(1) Search::: O(n) Search (sorted array)::: O(log(n)) 0, then the two strings have common characters. Anagram Two approaches to anagram problems. □ Sorting both input strings should produce the same resulting string; however, this takes O(nlog(n)) time and O(log(n)) space. □ Map each char to a prime number and we multiply each mapped number together. □ Frequency counting of the characters will help determine if the two strings are anagrams. Palindrome Ways to check if a string is a palindrome □ Reverse the string and it should be equal to itsself. □ Have two pointers at the start and end of the string. Move the pointers inward till they meet. At every point in time, the characters at both pointers should match. Essential Questions: Valid Anagram Valid Palindrome Longest Substring Without Repeating Characters DSA and Algos Page 12  Longest Substring Without Repeating Characters Try Longest Repeating Character Replacement Find All Anagrams in a String Minimum Window Substring Group Anagrams Longest Palindromic Substring Encode and Decode Strings (LeetCode Premium) Hash Table: Learning Resources Readings Taking Hash Tables Off The Shelf, basecs Hashing Out Hash Functions, basecs Videos Core: Hash Tables, University of California San Diego A Brief Guide to Hash Tables (slides), Samuel Albanie, University of Cambridge Implementations: defaultdict or {} Time Comp: Accessing: IDK Searching: O(1) Inserting: O(1) Removing: O(1) Sample Questions: Describe an implementation of a least-used cache, and big-O notation of it. A question involving an API's integration with hash map where the buckets of hash map are made up of linked lists. Essential Questions: Two Sum Ransom Note Try Group Anagrams Insert Delete GetRandom O(1) First Missing Positive LRU Cache All O one Data Structure Recursion: Method of solving computational problems. Where the solution depends on solutions to smaller instances of the same problem. 2 parts of a recursive function: Base Case: defines when the recursing should stop or is stopped Breaking down the problem into smaller subproblems and invoking the recursive call. Recursion use cases: Binary Search Merge Sort Tree Traversal DFS Learning Resources Readings Recursion, University of Utah Videos Tail Recursion, University of Washington Things to look out for… Always remember to define a base case Recursion is useful for permutations because it generates all combinations and tree-based questions. Recursion implicitly uses a stack. So all recursive approaches can be written iteratively using a stack. Recursion is never O (1) space complexity Number of base cases Edge Cases: N=0 N=1 Handle all possible Techniques DSA and Algos Page 13  Techniques Memoization Essential Questions: Generate Parentheses Combinations Subsets Try Letter Combinations of a Phone Number Subsets II Permutations Sudoku Solver Strobogrammatic Number II (LeetCode Premium) Sorting and Searching: Interviews: Know the time complexity of your languages sorting algorithm: O(nlog(n)) Edges Case: Empty Seq. Sequence with one element Sequence with two elements Sequence containing duplicate elements Technique Sorted Inputs When given a sequence in a sorted order (ascending or descending), using binary search should be one of the first things that come to your mind. Sorting an input that has limited range Counting sort is a non-comparison-based sort you can use on numbers where you know the range of values beforehand. Ex: H-Index Essential Question: Binary Search Search in Rotated Sorted Array Try Kth Smallest Element in a Sorted Matrix Search a 2D Matrix Kth Largest Element in an Array Find Minimum in Rotated Sorted Array Median of Two Sorted Arrays DSA and Algos Page 14