Data Structures Flashcards
Hash Table - what is it?
use hash code to insert a key and value by mapping the hash code to an index in an array or linked list
Retrieve from hash table
compute hash code from key, then index from hash code. Then search thru linked list for value with that key
Hash table run time
if collisions are high - O(N) N = number of keys.
generally, O(1)
Reverse Linked List - recursive
class Solution:
def reverseList(self, head):
if (not head) or (not head.next):
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
Reverse Linked List - iterative
class Solution:
def reverseList(self, head):
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
Pre-order Traversal - definition
Visit root first, then left, then right.
In-order Traversal - definition
Visit left first, then root, then right. SORTED ORDER
Post-order Traversal - definition
Left first, then right, then root. Deleting nodes in a tree will be in post-order - delete left child and right child before deleting node itself.
Level-order Traversal (BFS) - definition
traverse level by level. Start with root, then traverse neighbors, then the neighbor’s neighbors. Use queue
BFS runtime
O(vertices + edges)
DFS runtime
O(vertices + edges) use stack
Find depth of binary search tree
def depth(tree):
if not tree:
return 0
left_depth = depth(tree[‘left’])
right_depth = depth(tree[‘right’])
