DS Flashcards
List 6 methods an ArrayList can perform?
add(e)
remove(pos)
get(post)
set(pos, e)
size()
clear()
Explain the time complexity of inserting into an array?
O(n) worst case because you have to go through all of the elements before the one you are inserting
Why do we use Big O notation?
Big O notation is used to describe the performance of an algorithm. It helps us understand scalability of an algorithm
What is O(1)?
Size of input doesn’t matter it will always run in constant time
What is O(n)?
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
What is O(N^2)?
The algorithm runs in quadratic time
What is O(log n)
logarithmic time complexity
O(log N) is more scalable and efficient than O(N) because it slows down at some point ie., Binary Search
What is O(2^n)
Not scalable at all (opposite of logarithmic growth rates)
What is an example of O(n) space complexity?
String[] a = new String[items.length]
What are issues with an Array?
Fixed size
What is the time complexity of inserting into an array?
O(1) first index
(worst case O(n) because we have to skip all the elements before that index)
What is the time complexity removing an item from an array?
O(n) worst case
How do you print an array?
System.out.println(Arrays.toString(nums));
How do you get the length of an array?
array.length
What are two types of dynamic arrays?
Vector
ArrayList
What are two types of dynamic arrays?
Vector
ArrayList
What is the difference between an ArrayList and Vector?
A Vector will grow by 100% of its size when it is full, ArrayList will grow by 50% of its size
When should you use ArrayList instead of Vector?
ArrayList for multi threaded environments because it is not syncronized
Vector is synchronized so only works in a single thread environment
What is the time complexity of inserting into a Binary Search Tree?
O(log2n) logarithmic if balanced
O(N) if unbalanced
What is the time complexity of deleting a node from a Binary Search Tree?
O(log2n) logarithmic if balanced
O(N) if unbalanced
What is the time complexity of a look up of a Binary Search Tree?
O(log2n) logarithmic if balanced
O(N) if unbalanced
What is a B+ tree?
Can have a maximum of M children
What is the difference between B-Tree and BST?
BST has 2 children, B-Tree has M children
What is the max number of times you will need to traverse a BST?
Height of the tree is the max number of steps you need to take
What does not thread safe mean?
The data structure shouldn’t be accessed simultaneously by different threads
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
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
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
How is an ArrayList implemented internally?
An ArrayList used an array internally to implement the list interface
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
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
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
What is the benefit of adding a possible max number of items in an ArrayList like this?
List<String> li = new ArrayList<>(possibleMaxNumElements)</String>
Prevents lots of unnecessary copying and array allocations
How are arrays indexed in Java?
Using int values
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
Which 2 have an index based structure:
Set
Map
List
Map and List
A set isn’t indexed based because it isn’t ordered
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’]
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
