Cracking the Coding Interview (Fach) / Data Structures (Lektion)
In dieser Lektion befinden sich 15 Karteikarten
a
Diese Lektion wurde von Aglae erstellt.
Diese Lektion ist leider nicht zum lernen freigegeben.
- Hash Table: - runtime and worst case runtime - implementation ... - 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 ...
- ArrayList & Resizable Arrays - most common implementation ... - 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 ...
- 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 ...
- Linked Lists - singly vs doubly linked - pro and con ... 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 ...
- Linked Lists: "Runner" technique - how it works - ... 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 ...
- Stack - Sorting System - operations (4) - implementation ... 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 ...
- Queue - Sorting system - implementation - used often ... 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 ...
- Tree - what is it? - access - node without children ... - 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: ...
- Types of Trees - binary tree - binary search 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 ...
- 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 ...
- Binary Heaps - two types - what is a heap - two operations: ... 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 ...
- Tries - also called - what is it? - used for - runtime ... 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 ...
- Graphs - what is it: tree vs graph - types of graphs ... 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 ...
- Ways to represent a graph in code (2) - paint both ... 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 ...
- 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 ...