Arrays

Question 1

time complexity of accessing an index from an array

Answer 1

O(1)

Question 2

how is array stored in memory?

Answer 2

statically allocated contiguous blocks

Question 3

what’s soft removal

Answer 3

leave the removed data in the data structure unless it’s absolutely necessary to get rid of it.

e.g. in arraylists, the end of the array is controlled by size variable, so to remove the last item we can just decrement size by 1 without explicitly removing the data at that slot.

Question 4

what’s hard removal

Answer 4

ensure the data you removed is completely removed from the backing structure.

Question 5

what is arraylist

Answer 5

an abstraction built upon arrays that allows dynamic allocation of space without user knowledge.

Question 6

what’s the size of an arraylist

Answer 6

number of data (non-null) being stored in it.

Question 7

what’s the capacity of an arraylist

Answer 7

number of data that can be stored without a resize

Question 8

what’s the amortized time complexity of adding to the back of an arraylist and why

Answer 8

O(1)*,
because normal case is O(1)
worst case is when a resizing is needed but it happens rarely

Question 9

time complexity of adding elsewhere in the arraylist

Answer 9

O(n),
because we must shift data around to keep contiguity of data

Question 10

time complexity of removing from the back of an arraylist

Answer 10

O(1)

Question 11

time complexity of removing anywhere but the back of an arraylist

Answer 11

O(n) due to shifting