Amazon Whiteboard Flashcards
What is a heap?
A tree based data structure that satisfy heap properties.
For a max heap, the node will always be greater than its child nodes. For a min heap, the node will always be less than its child nodes. They’re typically implemented a complete binary tree.
What are the benefits of a heap?
Heaps provide efficient insertion, deletion and lookups for min/max values.
Heapify ( Creating a heap from array in Python): O(N)
Insertion/Deletion: O(logN)
Peak: O(1)
Name some heapq functions in Python.
heappop(heap): removes top element.
heappush(heap,item): Add number to heap.
heappushpop(heap,item): Pop the top and add number in 1 operation
nlargest/nsmallest(n,interatble): Returns the n smallest/largest from dataset.
How to create a max heap in Python and functions asccotiated with it.
Creating max heap(same loop to print):
numbers = [ 1,2,5,6,1,1,8]
maxheap = [-num for num in numbers]
heapq.heapify(maxheap)
Getting top value:
-heappop(heap)
Adding to heap:
heappush(heap,-n)
What is list comprehension in Python.
List comprehension allows one to generate list by performing actions on a iterable and filter items.
Ex:
Getting num from a hashmap
[value for key,value in iterable]
What is Kadanes Algorithm and when is it used?
Kadanes algorithm is a dynamic programming technique to find the maximum sum of a contiguous array.
Maximum subarray Leetcode
res=nums[0]
total=0
for i in nums:
if total<=0:
total=0
total=total+i
res=max(res,total)
return res
]
What is a prefix sum?
A prefix sum is where you keep running total sum of elements in a array as you iterate through it.
What is an array?
Arrays are data structures consisting of a collection of elements identified by an index. The array is stored in contiguous memory.
What is a linked list?
Linked list is a linear data structure where the elements, called nodes, contain a value and a reference to the next node in the sequence. Unlike arrays this is not stored in contiguous memory.
What is a Hashmap?
A Hash Map is a data structure that implements an associated array abstract data type by mapping keys to a value. It utilizes a hashing function on a element to compute a index allowing for fast search insert and removal processes O(1)
What is BFS
BFS is a alogrithm used for graph traversal or searching graph data structures. It can be applied to matrixes and tree like structures. The process is to explore the neighboring nodes at the present depth before moving to the next level of nodes.
BFS Graph Traversals
Queue management: Start at any node
Requirements: A Visited Set
Purpose: Shortest path, connected components etc
Steps:
- Initialize
Choose starting node. Use a queue to manage nodes visited. Use a set to manage nodes visited. - Traversal
Enqueue the starting node and mark it as visited - Process Nodes by level
When the queie not empty:
-dequeue the current node
-process the current node
-for each unvisited neighbor of the node, mark the neighbor as visited and enque the neighbor - When the queue is empty, all reachable nodes from the start have been visited
from collections import deque
def bfs_graph(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
BFS in Tree
This is often called level-order traversal. Each node has one path from root so we dont need a set.
Steps
1. Initialize
- start with the root
- use a queue to hold nodes to visit
- Traversal
- Enqueue the root node
3.Process Nodes level by level
-dequeue the current node
-process the current node
-if current node has a left child enqueue it then the right
- when queue is empty, all levels have been traverersed.
from collections import deque
Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root: TreeNode):
if not root:
return []
result = []
queue = deque([root]) # Initialize the queue with the root node
while queue:
level_size = len(queue) # Number of nodes at the current level
current_level = []
for _ in range(level_size):
node = queue.popleft() # Dequeue the front node
current_level.append(node.val) # Add the node's value to the current level
# Enqueue children if they exist
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level) # Append the current level to the result
return result
BFS on Matrixes
Utilize a set to keep track of visited nodes
Utilize a queue to keep track of cells to visit next.
BFS Template Matrix
def bfs(matrix):
# Check for an empty matrix/graph.
if not matrix:
return []
rows, cols = len(matrix), len(matrix[0])
visited = set()
directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
def traverse(i, j):
queue = deque([(i, j)])
while queue:
curr_i, curr_j = queue.popleft()
if (curr_i, curr_j) not in visited:
visited.add((curr_i, curr_j))
# Traverse neighbors.
for direction in directions:
next_i, next_j = curr_i + direction[0], curr_j + direction[1]
if 0 <= next_i < rows and 0 <= next_j < cols:
# Add in question-specific checks, where relevant.
queue.append((next_i, next_j))
for i in range(rows):
for j in range(cols):
traverse(i, j)
