Java Collections Flashcards
What are the types of collections?
1- Lists 2- Sets 3- Queue 4- Dequeue 5- Map 6- TreeMap
What is the most commonly used collection?
Use List quite a bit, but don’t use sets as much
What is one powerful method in Maps?
Search, can search an array for a certain element in the array
Equals and hashcode methods
this is an object comparison , when comparing strings use equals method and not == to see if they are equals
What is binary search algorithm?
The data must be sorted , breaking problem solving in half on every search.
What is java recursion?
A method that invokes itself. Recursion in java is a process in which a method calls itself continuously. A method in java that calls itself is called recursive method. It makes the code compact but complex to understand.
What is the difference between a binary search and a recursive version of binary search?
The major difference between the iterative and recursive version of Binary Search is that the recursive version has a space complexity of O(log N) while the iterative version has a space complexity of O(1).
What is the big o notation?
Bachmann–Landau notation (Big O notation) is an Asymptotic Notation for the worst case, or ceiling of growth for a given function. Computer programming uses Big O notation to classify algorithms according to how their computing time or space requirements grow as the input size grows. It is used to measure performance and give you an idea of how much memory it will take to run a program.
What are advantages of logarithmic algorithms vs exponential algorithms?
The logarithmic will shorten the curve because it halfs each time it is run
What is the selection sort?
it will organize numbers from min to max. Select min and make sure it is the minumum and sort it until it is a min and a max
What is insertion sort?
Divide array into a sorted and unsorted portion and move parts of array into the other part
What is merged sort?
Divide and conquer algorithm and copies the array and sorts it.
what is the quick sort?
Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
Always pick first element as pivot.
Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.
what is a binary search tree?
Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
Most popular data structure, non-binary tree
