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)
heapify ( building a heap from an array)
O(N)
Priority Queue
allows elements to be removed base on their prioority rather than the order they were added.
heap peek
O(1)
Max heap uses what type of queue
Priority Queue
Bubble Sort
comparing the current and the next element and swapping to sort them in order.
Bubble sort cons
Worse and average Case Time Complexity (O(n^2))
Bubble Sort Space Complexity
O(1)
Merge Sort
Divide and Conquer
Merge Sort Time complexity
O(nlogn)
Merge Sort Space Complexity
O(n) need for proportional to the size of the input list to store temporary sublist
Hash Table
Searhc O(1)
Binary Tree height
if it depth is 0 1 2 the height is 3
Quick Sort
pick a pivot, usualt at the end and sort the list. having smaller value to the left and the bigger vlaue to the right.
Quick Sort Time complexity
O(nlogn) average
O(n^2) worse case
bucket sort
distributes elements in to a number of buckets, sort each bucket individually, and then concatenates the sorted buckets to produce the final sorted array
QuickSort space complexity
O(logn) because the stack space used for recursion
Bucket Sort time complexity
O(n+K) best
worse O(n^2)
Bucket sort space complexity
O(N+k)
