DS Flashcards

1
Q

List 6 methods an ArrayList can perform?

A

add(e)
remove(pos)

get(post)
set(pos, e)

size()
clear()

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

Explain the time complexity of inserting into an array?

A

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

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

Why do we use Big O notation?

A

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

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

What is O(1)?

A

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

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

What is O(n)?

A

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

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

What is O(N^2)?

A

The algorithm runs in quadratic time

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

What is O(log n)

A

logarithmic time complexity

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

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

What is O(2^n)

A

Not scalable at all (opposite of logarithmic growth rates)

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

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

A

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

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

What are issues with an Array?

A

Fixed size

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

What is the time complexity of inserting into an array?

A

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

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

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

A

O(n) worst case

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

How do you print an array?

A

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

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

How do you get the length of an array?

A

array.length

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

What are two types of dynamic arrays?

A

Vector
ArrayList

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

What are two types of dynamic arrays?

A

Vector
ArrayList

16
Q

What is the difference between an ArrayList and Vector?

A

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

17
Q

When should you use ArrayList instead of Vector?

A

ArrayList for multi threaded environments because it is not syncronized

Vector is synchronized so only works in a single thread environment

18
Q

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

A

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

19
Q

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

A

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

20
Q

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

A

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

21
Q

What is a B+ tree?

A

Can have a maximum of M children

22
Q

What is the difference between B-Tree and BST?

A

BST has 2 children, B-Tree has M children

23
Q

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

A

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

24
What does not thread safe mean?
The data structure shouldn't be accessed simultaneously by different threads
24
What are the 5 key differences between an ArrayList and Vector
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
25
Why is inserting into an unbalanced binary search tree O(N)
Because it is basically a LinkedList the idea that each time you are halving the area you search within no longer applies
26
What is dynamic programming?
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
27
How is an ArrayList implemented internally?
An ArrayList used an array internally to implement the list interface
28
Why is adding an element to an ArrayLists worst case time complexity O(N) ?
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
29
Why is getting an item from an ArrayList at a given index i always O(1)
we just need to return the ith element from the array
30
Why is removing an element from an ArrayLists worst case time complexity O(n)
Once we mark the element we want to delete We need to move all elements after the index back
31
What is the benefit of adding a possible max number of items in an ArrayList like this? List li = new ArrayList<>(possibleMaxNumElements)
Prevents lots of unnecessary copying and array allocations
32
How are arrays indexed in Java?
Using int values
33
What comes first compile time or run time?
Compile time comes first, converting the program to machine code and then runtime is when the program is running after
34
Which 2 have an index based structure: Set Map List
Map and List A set isn't indexed based because it isn't ordered
35
You have an arraylist ['a', 'b', 'c'] What happens if you add (1, 'd')
d added at index 1 and everything from index 1 shifted right ['a', 'd', 'b', 'c']
36
How do you find the number of moves needed to make all elements in an array equal?
Sort the array using Arrays.sort Traverse from the back of the array, adding the difference of all elements except the last