Amazon Interview Flashcards

1
Q

Breath First Search Time complexity

A

O(E+V). Edges + vertex.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Breath First Search Space Complexity

A

O(v)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Pros of BFS

A
  1. useful for finding the shortest path on unweighted graphs
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is BFS

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is DFS

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

DFS time complexity

A

O(V+E)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

DFS Time complexity

A

O(V+E)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

DFS uses what data structure?

A

Stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Pros and Cons of DFS

A

Can be slow if the graph depth is large.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Binary Search

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Binary Search Time Complexity

A

O(logN)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Binary Search Space Complexity

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

LinkedList Pros

A

Allows efficient insertion and deletion operations compared to arrays

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Heap insertion time complexity

A

O(logn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

heap deletion time complexity

A

O(logn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

heapify ( building a heap from an array)

A

O(N)

17
Q

Priority Queue

A

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

18
Q

heap peek

A

O(1)

19
Q

Max heap uses what type of queue

A

Priority Queue

20
Q

Bubble Sort

A

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

21
Q

Bubble sort cons

A

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

22
Q

Bubble Sort Space Complexity

A

O(1)

23
Q

Merge Sort

A

Divide and Conquer

24
Q

Merge Sort Time complexity

A

O(nlogn)

25
Q

Merge Sort Space Complexity

A

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

26
Q

Hash Table

A

Searhc O(1)

27
Q

Binary Tree height

A

if it depth is 0 1 2 the height is 3

28
Q

Quick Sort

A

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

29
Q

Quick Sort Time complexity

A

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

30
Q

bucket sort

A

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

31
Q

QuickSort space complexity

A

O(logn) because the stack space used for recursion

32
Q

Bucket Sort time complexity

A

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

33
Q

Bucket sort space complexity

A

O(N+k)