Data Structures and Algorithms Flashcards
A _________________ cannot directly access variables in the outer class. It needs to refer to an ____________ of the outer class.
nested static class, instance
A _____________ is actually defined WITHIN a method (as opposed to the class). It’s not a class within a class, but a class within a ____________.
local class, method
In nested classes, the variable in the nested/inner class ______________ the value from the outer class.
shadows
A nested __________ class cannot directly access variables in the outer class.
static
The ________ is a chain of connected elements. Each element in the list is called a __________. While the type of connection may vary, the core structure consists of elements that point to each other. The first element in the list is the ______, and the last element is the _______
linked list, node, head, tail
A _________________ is like a train, with nodes pointing forward.
singly linked list
A _______________ resembles web browsing history, with nodes pointing forward and backward so that all are connected both ways.
doubly linked list
A ___________________ is a variation of a singly linked list, and the tail node points back to the head
circular linked list
Unlike arrays, a _______________ has non-continuous memory, and it requires you to step through each node to find a given node.
linked list
When compared to an array, why is a linked list less efficient?
You need to traverse each node.
In this type of linked list, the tail node points to the head node.
circular linked
In a singly linked list, the tail node points to what?
Null
How does your browsing history demonstrate a doubly linked list?
You can traverse the list forwards and backwards.
The reason that the == does not work is because arrays are _________ in Java, and so the compiler is comparing their __________ in memory, NOT the values that you gave them.
objects, address
You can use == for _______________ like integers, but not objects, such as arrays.
primitive variables
Are two arrays of the same set of elements equivalent using the comparison operator (==) ?
The two arrays are references to 2 different objects in memory hence not equivalent
What happens when you compare two objects of the same parent class for equivalency on which one of the objects overrides a parent class method? Are the objects equivalent?
The two objects are not equal because the overriding method introduced replaces the initial parent class method
A ____________ of an array only creates a copy of an array (or parts of an array) for primitive data types.
shallow copy
A ______________ creates a copy of an array of objects while still creating new references to objects underneath.
deep copy
The _____________ method lets you copy part of an array or an entire array.
arraycopy
A _________ creates a mirror image of the array.
clone
In Java, a _____ copy would copy only the double data types of an array.
shallow
Clone the oldRates array and name it rates, double data type.
double[] rates = oldRates.clone();
If a program needed to create a copy of an array with new references to an object, what type of copy would be performed?
Deep copy
If you only want to clone a portion of an array in Java, which method do you use?
arraycopy
Why is cloning multi-dimensional arrays in Java not available using the clone method?
A Java multi-dimensional array is an array of objects
Contra attack
The use of contrapositive and contradiction methods in order to justify a given statement.
Induction
One of the most important tools for analyzing algorithms. It involves proving mathematical statements true with a finite set of elements.
Loop variants
Analyzing the correctness of an algorithm consisting of loops with conditions that both hold true immediately before and immediately after every iteration of the
This can be defined as the function which determines the amount of time an algorithm takes to give the desired output.
Time complexity
This function describes the total memory space consumed upon running an algorithm.
Space complexity
Consumption of space depends on these three things:
1: type of data structures
2: the memory allocations completed for the variables used
3: the results stored after execution
data structure
algorithm
a collection of steps to solve a problem
Stack data structure
last in first out, stores object in a “vertical tower” structure
How to initialize a stack in Java?
Stack<String> stack = new Stack<String>();</String></String>
How to add an element to a stack?
stack.push(“ElementOne”);
stack.push(“ElementTwo”);
How to remove the top most object from a stack?
stack.pop();
What does the peek method do with a stack?
Looks for the object at the top of the stack without removing it.
stack.peek();
Queue data structure
First in First Out (FIFO), similar to waiting in line to checkout at a store
a collection designed for holding elements prior to processing
Enqueue
adding an element to the tail of a queue
offer();
Dequeue
removing an element from the head of the queue
poll();
Priority queue data structure
A FIFO data structure that serves elements with highest priorities first before elements with lower priority.
Queue<String> queue = new PriorityQueue<>();</String>
Linked lists data structure
stores Nodes in 2 parts (data+address), node are in non consecutive memory locations, elements are linked using pointers.
easy to insert and remove elements in this data structure with constant time complexity O(1), non-contiguous nodes, unlike array lists when inserting a new element there is no shifting of contiguous elements.
Bad at searching because there is no index. Must do a linear search which is timely in large data sets. O(n)
singly linked lists can on be traversed UNIDIRECTIONALLY
doubly linked lists can be traversed BIDIRECTIONALLY
LinkedList<String> linkedlist = new LinkedList<String>();</String></String>
ArrayList vs. LinkedList
ArrayList is much faster to retrieve an element compared to LinkedList.
Doubly LinkedLists are fastest at the beginning and end of the list, but slowest in the middle. But still slower than
Linear time
O(n)
looping through elements in an array
searching through a linked list
Constant time
O(1)
random access of an element within an array
inserting at the beginning of a linked list
Logarithmic time
O(log n)
binary search
Quasi linear time
O(n log n)
quicksort
mergesort
heapsort
quadratic time
O(n^2)
insertion sort
selection sort
bubblesort
slow with large data set
O(n!)
factorial time
extremely slow
Linear search
iterate through a collection one element of a time
linear time complexity
slow for large data sets,
fast for small data sets
DOES NOT NEED TO BE SORTED
Binary search
Search algorithm that finds the position of a target value within a sorted array. Half of the array is eliminated during each “step”.
DATA NEEDS TO BE SORTED
most efficient with large data sets
BubbleSort
A sorting algorithm that compares adjacent elements and goes along the length of the array.
not very efficient.
O(n^2) time complexity
SelectionSort
search through an array and keep track of the minimum value during each iteration. At the end of each iteration, we swap variables.
O(n^2) time complexity.
InsertionSort
after comparing elements to the left shift elements to the right to make room to insert a value.
O(n^2) quadratic time complexity
less steps than bubble sort,
best case is O(n) better than selectionSort O(n^2)
Recursion
Apply the result of a procedure to a procedure.
A recursive method calls itself.
Insertion Sort explanation:
Two loops should be made: one that starts looping through the array, the other loops again, but goes backward (decrements) down. Each nested loop ensures the next element is greater than the current.
What is the advantage of selection sort?
it requires no additional memory for operation
For a given array of [32, 44, 12, 15], the number of iterations performed using selection sort algorithm are:
The number of iterations performed in case of selection sort is (n - 1) where n is the length of the array. Since this is 4 element array, the number of iterations will be 3.
What type of structure uses data stored inside a tree node?
key-value
An important use of heap data structure is _____.
Priority queue
Since heaps are very useful in the data structures that require an element to be removed with highest or lowest priority, one of its major application areas is designing priority queues.
Which of the following Java statements best depicts the instantiation of the first element within a stack?
private Node top;
We use a class (usually called Node) to represent an element in our linked list. Since the head of the list is the one we can use in a stack, we can name it top.
Steps in Dijkstra’s algorithm:
start at the ending vertex and mark it with a 0 and label it as your current vertex by putting a circle around it.
identify all of the vertices that are connected by an edge to your current vertex, and calculate their distance to the ending vertex by adding their current mark to the weight of the connecting edge
once you’ve marked all of the vertices that are connected by an edge to your current vertex, label the current vertex as visited and put an X through it
Graphs come under which category of data structures?
Non-linear
Graphs come under the category of non-linear data structures, as the data elements are organized non-sequentially and multiple data elements can be reached from a single data element.
A while loop can evaluate ________ conditions.
one or more
Which interface requires the compareTo method to be overridden
Comparable
Regular queues use the _________ while priority queues remove elements based on _________
FIFO, priority
What is a bad character rule?
The character that does not match with the pattern string is a bad character. When the mismatch is encountered the pattern is shifted until the mismatch is a match or until the pattern crosses the mismatched character
What are similarities between recursion and iteration?
they both return the same end result
Which package does the List interface belong to?
java.util
How many forms of the add method can be used with lists?
TWO, the add method can be used with and without passing an index value
B-tree feature to optimize speed is ____?
the use of indexing
An abstract class cannot ________
be instantiated
You cannot create an instance of an abstract class/instantiate one. It is better used for hierarchies: Think of it as a model. You could have a Vehicle class that is abstract, with Truck, SUV, or Semi as classes under it.
What is the operation called that is performed by selection sort to move numbers from the unsorted section to the sorted section of an array?
Swapping
The back/forward functionality is best served by a ________________. You can’t go past the last step, nor can you proceed before the first. However, you can go back and forth within the quest itself.
doubly linked list
A sort map is _______?
a searchable collection of elements
Which of the following sets are implemented classes of the List interface?
There are 10 implemented classes, including ArrayList, LinkedList, Stack, and Vector.
Consider a situation where the minimum number of swap operation is required. Which sorting algorithm is best for this use-case?
selection sort
Selection sort requires fewer swap operations as compared to other sorting algorithms.
What is the main characteristic of binary trees?
each parent only has two children
In loop variants, the relationship between the variables __________.
is the same before and after the loops.
Out of a random bunch of last year’s holiday greeting cards, Clara wants to find the one her mother sent her. The optimal algorithm to use will be _____.
Linear
