Amazon Interview

Question 1

Breath First Search Time complexity

Answer 1

O(E+V). Edges + vertex.

Question 2

Breath First Search Space Complexity

Answer 2

O(v)

Question 3

Pros of BFS

Answer 3

1. useful for finding the shortest path on unweighted graphs

Question 4

What is BFS

Answer 4

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

Question 5

What is DFS

Answer 5

traversing node to the lowest depth of each branch of the root each time to search for a node.

Question 6

DFS time complexity

Answer 6

O(V+E)

Question 7

DFS Time complexity

Answer 7

O(V+E)

Question 8

DFS uses what data structure?

Answer 8

Stack

Question 9

Pros and Cons of DFS

Answer 9

Can be slow if the graph depth is large.

Question 10

Binary Search

Answer 10

searching for a target by dividing the array in half each time

Question 11

Binary Search Time Complexity

Answer 11

O(logN)

Question 12

Binary Search Space Complexity

Answer 12

O(1)

Question 13

LinkedList Pros

Answer 13

Allows efficient insertion and deletion operations compared to arrays

Question 14

Heap insertion time complexity

Answer 14

O(logn)

Question 15

heap deletion time complexity

Answer 15

O(logn)

Question 16

heapify ( building a heap from an array)

Answer 16

O(N)

Question 17

Priority Queue

Answer 17

allows elements to be removed base on their prioority rather than the order they were added.

Question 18

heap peek

Answer 18

O(1)

Question 19

Max heap uses what type of queue

Answer 19

Priority Queue

Question 20

Bubble Sort

Answer 20

comparing the current and the next element and swapping to sort them in order.

Question 21

Bubble sort cons

Answer 21

Worse and average Case Time Complexity (O(n^2))

Question 22

Bubble Sort Space Complexity

Answer 22

O(1)

Question 23

Merge Sort

Answer 23

Divide and Conquer

Question 24

Merge Sort Time complexity

Answer 24

O(nlogn)

Question 25

Merge Sort Space Complexity

Answer 25

O(n) need for proportional to the size of the input list to store temporary sublist

Question 26

Hash Table

Answer 26

Searhc O(1)

Question 27

Binary Tree height

Answer 27

if it depth is 0 1 2 the height is 3

Question 28

Quick Sort

Answer 28

pick a pivot, usualt at the end and sort the list. having smaller value to the left and the bigger vlaue to the right.

Question 29

Quick Sort Time complexity

Answer 29

O(nlogn) average O(n^2) worse case

Question 30

bucket sort

Answer 30

distributes elements in to a number of buckets, sort each bucket individually, and then concatenates the sorted buckets to produce the final sorted array

Question 31

QuickSort space complexity

Answer 31

O(logn) because the stack space used for recursion

Question 32

Bucket Sort time complexity

Answer 32

O(n+K) best worse O(n^2)

Question 33

Bucket sort space complexity

Answer 33

O(N+k)