Data Structures & Algorithms

Question 1

What is Big O Notation

Answer 1

shows how efficient an algorithm is in the worst-case scenario relative to its input size

Omicron

Question 2

Time Complexity

Answer 2

How much time does it take to run completely?

Question 3

Space Complexity

Answer 3

How much extra space does it require in the process?

Question 4

Ω

Omega

Answer 4

Best case scenario

Loop through [1, 2, 3, 4, 5, 6, 7] looking for 1

Question 5

θ

Theta

Answer 5

Average case

Loop through [1, 2, 3, 4, 5, 6, 7] looking for 4

Question 6

O

Omicron

Answer 6

Worst case

Loop through [1, 2, 3, 4, 5, 6, 7] looking for 7

Question 7

Contiguous vs Noncontigous

Types of memory allocation

Answer 7

• Contiguous -single contiguous section/part of memory is allocated
• Noncontiguous - memory is allocated to different locations

Question 8

Stack

Data Structure

Answer 8

• You can only get to the last item (most recently added) that you pushed onto the stack
• Example - back button in Web Browser will pop off the most recently visited site

Question 9

Queue

Data Structure

Answer 9

• Typically FIFO
• Add on one end, remove on other end

Question 10

Binary Tree

Data Structure

Answer 10

• nodes can have this.left and this.right values
• Full - every node either points to two nodes or zero nodes
• Perfect - Any level in the tree that has any nodes is completely filled across
• Complete -as long as left side is filled with no gaps
• Although Binary Tree will only have each node point to two nodes, other trees could have nodes that point to multiple nodes

Question 11

Binary Search Tree

Answer 11

for any node:
* any nodes below and right will be greater than
* any nodes below and left will be less than

Question 12

Big O of for loop

Answer 12

O(n)

Linear Time

Question 13

Big O of arr.push() or arr.pop()

Answer 13

O(1)
Constant time

Question 14

Big O of sorting algorithm

Answer 14

usually O(nlog n)

For JS array sort, depends on (browser) implementation