15
Cracking the Coding Interview (Fach) / Data Structures (Lektion)
a
Diese Lektion wurde von Aglae erstellt.
Diese Lektion ist leider nicht zum lernen freigegeben.
Anzeige
- Hash Table: - runtime and worst case runtime - implementation (2) - maps keys and values for highly efficient lookup - lookup time is O(1) - worst case runtime (many collisions) O(N), N = Number of keys e.g. implementation array of linked lists & hash code function - compute keys hash code - map hash code to index - store element in linked list at hash code linked list required because of collisions alternative implementation: hash table + balanced search tree - O(log N) - advantages: use less space (not a very long array) we can run through items in order
- ArrayList & Resizable Arrays - most common implementation - runtime - in some languages (Java) arrays (lists) are of fixed length - ArrayList resizes itself while still providing O(1) access - most common implementation: when array is full it doubles O(N) (copy every entry) - amortized insertion time is still O(1)
- StringBuilder - why? - what to do? - concatenate word by word to a string with word_length = x and number_of_words = n takes O(xn2) - sting = array_not_resizeable for word in words: string += string - first iteration x + second iteration 2x + n-th iteration nx O(x + 2x + 3x + … + nx) = O(n(n+1)/2) = O(nx2) - instead use resizable array and store words there
- Linked Lists - singly vs doubly linked - pro and con - Creating a Linked List (problem and solution) - Deleting a Node from a Linked List singly vs doubly linked- linked list: single pointers- doubly linked list: bidirectional pointers- know which one it is in the interview! pro and con- no constant time access, need to iterate- pro: add and delete items at beginning (end) in constant time- many linked list problems can be solved recursively Creating a Linked List- e.g. class node- pointer to head- method that appends and changes head- problem: if multiple objects need a reference to the head and the head changes, they stil point to old head- better implement Linked List class that wraps the Node class Deleting a Node from a Linked List- update node.previous.next variable- if double linked also update node.next.previous- update head and tail
- Linked Lists: "Runner" technique - how it works - example or second pointer technique how it works - iterate through linked list with two pointers simultaneously (one ahead)- fast node can be ahead or hop multiple nodes at a time example - linked list: a1 -> a2 -> an ->b1 -> b2 ->n - don’t know length but know it’s an even number- want to store: a1 -> b1 -> a2 -> b2 -> an ->bn- p1 hops two nodes at a time- when p1 at the end p2 is in the middle- p1 hops to the front- p1 stores nodes that p2 sends over
- Stack - Sorting System - operations (4) - implementation (2) - useful in (2) Basics - stack = Stapel zB Tellerstapel- LIFO: Last in first out operations - pop() – remove top item - push(item) – add item to top - peek() – return top - isEmpty() – True/False implementation - list - linked list useful in - e.g. in certain recursive algorithms push as you recurse, remove as you backtrack (e.g. recursive check failed)- also useful to implement recursive algorithm iteratively
- Queue - Sorting system - implementation - used often in (2) - operations (4) Basics- queue = Reihe/Schlange wie zB Warteschlange- FIFO = first in first out- implementation: linked list used often in- breadth-first-seach- implementing a cache operations - add(item) – neues Item - remove() – erstes Item - peek() – was ist das nächste - isEmpty() – true/false
- Tree - what is it? - access - node without children - implementation - type of graph - root note to access tree - node without children = leaf - implementation class Node: value/name children can be wrapped in a tree class class Tree: head = None
- Types of Trees - binary tree - binary search tree - balanced tree - complete binary tree - full binary tree binary tree - each node has up to two children- three children could be called a ternary tree- used e.g. bunch of phonenumbers stored in a tree with 10 (0-9) children binary search tree - specific ordering property all left descendents <= n <= all right descendents- definition can vary: could not have douplicates, or douplicates go on the right or the left (clear with interviewer)- must be true for all descendants! balanced tree - balanced means balanced enough to ensure that insert and find are O(n log n) a) The left and right subtrees' heights differ by at most one, AND b) The left subtree is balanced, AND c) The right subtree is balanced- common types: a) red-black trees b) AVL trees complete binary tree - every level of the tree is fully filled- levels are usually filled left to right full binary tree - every node has 0 or 2 children- no node has one child perfect binary tree - full and complete- all leaf nodes are at the same level- 2k -1 Nodes- rare in interviews and in real life
- Binary Tree Traversal - 3 types - code In-Order Traversal - most common- visit (often print) left branch, current node, right branch def in_order_traversal(node): if node: in_order_traversal(node.left) visit(node) in_order_traversal(node.right Pre-Order-Traversal visit current node before (pre) child-nodes def in_order_traversal(node): if node: visit(node) in_order_traversal(node.left) in_order_traversal(node.right Post-Order-Traversal visit current node after child-nodes (root is always the last visited) def in_order_traversal(node): if node: in_order_traversal(node.left) in_order_traversal(node.right visit(node)
- Anzeige
- Binary Heaps - two types - what is a heap - two operations: How do they work, runtime 2 types - min heaps = minimum at top- max heaps = maximum at top what is a heap? - heap = complete binary tree- completely filled except the rightmost elements on last level- each node is smaller than its children- root is minimum/maximum element element operations a) insert- insert node at the bottom rightmost spot (maintain complete property)- fix the tree by swapping with parent until appropriate spot (bubble node up)- takes O(log n) n = number of elements in tree b) extract_min/extract_max- top!- remove top element and swap with bottom rightmost element (maintain complete property)- swap down till appropriate place- swap with smaller child to maintain min heap ordering- takes O(log n), n = number of elements in tree
- Tries - also called - what is it? - used for - runtime - appropiate problem Basics- also called prefix tries- comes up in a lot of interview questions, textbooks don’t spend much time on it what is it- variant of an n-ary tree- characters are stored at each node- each path down may represent a word- * nodes are often used to indicate complete words (special type of child node, e.g. inherits from TrieNode) or Boolean flag within parent node used for- e.g. to store complete English language for quick prefix lookups- hash table can quickly lookup if a word is valid it cannot lookup if it’s a prefix of another word- trie can very quickly lookup if something is a prefix of a valid word runtime- O(k), k = length of string- same as hashtable- we refer to hashtable as lookup was O(1) but hashtable has to read through the string so it is also O(k), k = length of string appropriate problem- when we search through prefixes repeatedly- e.g. M, Ma, Man, Many
- Graphs - what is it: tree vs graph - types of graphs (3) what is it: tree vs graph- a tree is a graph but not all graphs are trees tree is a connected graph without cycles- a graph is a collection of nodes with edges between (some of) them Types of graphs a) directed vs undirected- directed: one-way street- undirected: two-way street b) connected vs unconnected- connected: all graphs are connected- unconnected: multiple isolated subgraphs c) cyclic vs acyclic graph- cyclic: Graph has cycles- acyclic: Graph has no cycles
- Ways to represent a graph in code (2) - paint both - problem with second? adjacency list - most common- every vertex (node) stores a list of adjacent (neighbor) vertices- in undirected graph edges are stored twice- graph class is necessary because not all vertices can necessarily be accessed from one node if graph is not connected- array or hash table o lists can store the graph example code class Graph: nodes = [] class Node name = None children = [] adjacency matrices - N * N Boolean matrix (N = number of nodes) or you can use 0 and 1- true at matrix[i][j] means an edge from i to j- sometimes less efficient- have to iterate through all the nodes to iterate through one nodes neighbors!
- Traverse a graph (3) 1. depth-first-search (DFS) - start at root (or another random node)- explore each branch completely before moving on to next branch we go deep first!- often used if we want to visit every node in graph (DFS is a bit simpler)- pre order and other forms of tree traversal are a form of DFS difference for a graph: must check if node already visited (otherwise infinitive loop) 2. breadth-first-search (BFS) - start at root (or another random node)- explore each neighbor before moving on to their children go wide before deep!- used to find the shortest path (or just any path) BFS is better e.g. all people connected by friendships see if B is As friend, don’t follow one endlessly long path, better go through all of As friends- BFS is not recursive, it uses a queue node a visits each of a’s neighbors before visiting any of their neighbors 3. bidirectional-search - used to find shortest path from A to B- runs two simultaneous BFS, one from each node- when they collide, a path is found- this makes a huge difference in speed graph: every node has k neighbors shortest path from s to t is of length d why is it faster? a) BFS search- k nodes in first level- k2 (k nodes for each of the k nodes) at the second level- kd nodes to go till t b) bidirectional search- two searches collide after d/2 levels (midpoint of the path)- search from s and t visits approx. kd/2 nodes each- approximates to 2kd/2 or O(kd/2)