Amazon Interview Flashcards
Breath First Search Time complexity
O(E+V). Edges + vertex.
Breath First Search Space Complexity
O(v)
Pros of BFS
- useful for finding the shortest path on unweighted graphs
What is BFS
exploring all the vertices in a graph at the current depth before moving onto the next vertices. It may contain cycles.
To avoid processing a node more than once, can note the node as visited.
Uses Queue. First in First out
What is DFS
traversing node to the lowest depth of each branch of the root each time to search for a node.
DFS time complexity
O(V+E)
DFS Time complexity
O(V+E)
DFS uses what data structure?
Stack
Pros and Cons of DFS
Can be slow if the graph depth is large.
Binary Search
searching for a target by dividing the array in half each time
Binary Search Time Complexity
O(logN)
Binary Search Space Complexity
O(1)
LinkedList Pros
Allows efficient insertion and deletion operations compared to arrays
Heap insertion time complexity
O(logn)
heap deletion time complexity
O(logn)