DS

Question 1

List 6 methods an ArrayList can perform?

Answer 1

add(e)
remove(pos)

get(post)
set(pos, e)

size()
clear()

Question 2

Explain the time complexity of inserting into an array?

Answer 2

O(n) worst case because you have to go through all of the elements before the one you are inserting

Question 3

Why do we use Big O notation?

Answer 3

Big O notation is used to describe the performance of an algorithm. It helps us understand scalability of an algorithm

Question 4

What is O(1)?

Answer 4

Size of input doesn’t matter it will always run in constant time

Question 5

What is O(n)?

Answer 5

The cost of the algorithm grows linearly with the size of the input.

We drop constants because they don’t matter because the constant is independent of N

Question 6

What is O(N^2)?

Answer 6

The algorithm runs in quadratic time

Question 7

What is O(log n)

Answer 7

logarithmic time complexity

O(log N) is more scalable and efficient than O(N) because it slows down at some point ie., Binary Search

Question 8

What is O(2^n)

Answer 8

Not scalable at all (opposite of logarithmic growth rates)

Question 9

What is an example of O(n) space complexity?

Answer 9

String[] a = new String[items.length]

Question 10

What are issues with an Array?

Answer 10

Fixed size

Question 11

What is the time complexity of inserting into an array?

Answer 11

O(1) first index
(worst case O(n) because we have to skip all the elements before that index)

Question 12

What is the time complexity removing an item from an array?

Answer 12

O(n) worst case

Question 13

How do you print an array?

Answer 13

System.out.println(Arrays.toString(nums));

Question 14

How do you get the length of an array?

Answer 14

array.length

Question 15

What are two types of dynamic arrays?

Answer 15

Vector
ArrayList

Question 15

What are two types of dynamic arrays?

Answer 15

Vector
ArrayList

Question 16

What is the difference between an ArrayList and Vector?

Answer 16

A Vector will grow by 100% of its size when it is full, ArrayList will grow by 50% of its size

Question 17

When should you use ArrayList instead of Vector?

Answer 17

ArrayList for multi threaded environments because it is not syncronized

Vector is synchronized so only works in a single thread environment

Question 18

What is the time complexity of inserting into a Binary Search Tree?

Answer 18

O(log2n) logarithmic if balanced
O(N) if unbalanced

Question 19

What is the time complexity of deleting a node from a Binary Search Tree?

Answer 19

O(log2n) logarithmic if balanced
O(N) if unbalanced

Question 20

What is the time complexity of a look up of a Binary Search Tree?

Answer 20

O(log2n) logarithmic if balanced
O(N) if unbalanced

Question 21

What is a B+ tree?

Answer 21

Can have a maximum of M children

Question 22

What is the difference between B-Tree and BST?

Answer 22

BST has 2 children, B-Tree has M children

Question 23

What is the max number of times you will need to traverse a BST?

Answer 23

Height of the tree is the max number of steps you need to take

Question 24

What does not thread safe mean?

Answer 24

The data structure shouldn’t be accessed simultaneously by different threads

Question 24

What are the 5 key differences between an ArrayList and Vector

Answer 24

syncronization
- vector syncronized, arraylist not synchronized

growth
- vector doubles in size, arraylist by half its length

iteration
- vector iterator or enumeration, arraylist iterator only

performance
- vector slow compared to arraylist because it is synchronzied

framework
- arraylist part of collections, vector legacy

Question 25

Why is inserting into an unbalanced binary search tree O(N)

Answer 25

Because it is basically a LinkedList the idea that each time you are halving the area you search within no longer applies

Question 26

What is dynamic programming?

Answer 26

A technique that breaks a problem into smaller sub problems and saves the result for the future so we don’t need to re-compute again

Question 27

How is an ArrayList implemented internally?

Answer 27

An ArrayList used an array internally to implement the list interface

Question 28

Why is adding an element to an ArrayLists worst case time complexity O(N) ?

Answer 28

Internally once the fixed array is full

A new arra is initialized with more capacity

existing items are copied into the array

then the new element is added

Question 29

Why is getting an item from an ArrayList at a given index i always O(1)

Answer 29

we just need to return the ith element from the array

Question 30

Why is removing an element from an ArrayLists worst case time complexity O(n)

Answer 30

Once we mark the element we want to delete

We need to move all elements after the index back

Question 31

What is the benefit of adding a possible max number of items in an ArrayList like this?

List<String> li = new ArrayList<>(possibleMaxNumElements)</String>

Answer 31

Prevents lots of unnecessary copying and array allocations

Question 32

How are arrays indexed in Java?

Answer 32

Using int values

Question 33

What comes first compile time or run time?

Answer 33

Compile time comes first, converting the program to machine code and then runtime is when the program is running after

Question 34

Which 2 have an index based structure:
Set
Map
List

Answer 34

Map and List

A set isn’t indexed based because it isn’t ordered

Question 35

You have an arraylist [‘a’, ‘b’, ‘c’]

What happens if you add (1, ‘d’)

Answer 35

d added at index 1

and everything from index 1 shifted right

[‘a’, ‘d’, ‘b’, ‘c’]

Question 36

How do you find the number of moves needed to make all elements in an array equal?

Answer 36

Sort the array using Arrays.sort
Traverse from the back of the array, adding the difference of all elements except the last