Data Structures and Algorithms

Question 1

A _________________ cannot directly access variables in the outer class. It needs to refer to an ____________ of the outer class.

Answer 1

nested static class, instance

Question 2

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 ____________.

Answer 2

local class, method

Question 3

In nested classes, the variable in the nested/inner class ______________ the value from the outer class.

Answer 3

shadows

Question 4

A nested __________ class cannot directly access variables in the outer class.

Answer 4

static

Question 5

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 _______

Answer 5

linked list, node, head, tail

Question 6

A _________________ is like a train, with nodes pointing forward.

Answer 6

singly linked list

Question 7

A _______________ resembles web browsing history, with nodes pointing forward and backward so that all are connected both ways.

Answer 7

doubly linked list

Question 8

A ___________________ is a variation of a singly linked list, and the tail node points back to the head

Answer 8

circular linked list

Question 9

Unlike arrays, a _______________ has non-continuous memory, and it requires you to step through each node to find a given node.

Answer 9

linked list

Question 10

When compared to an array, why is a linked list less efficient?

Answer 10

You need to traverse each node.

Question 11

In this type of linked list, the tail node points to the head node.

Answer 11

circular linked

Question 12

In a singly linked list, the tail node points to what?

Answer 12

Null

Question 13

How does your browsing history demonstrate a doubly linked list?

Answer 13

You can traverse the list forwards and backwards.

Question 14

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.

Answer 14

objects, address

Question 15

You can use == for _______________ like integers, but not objects, such as arrays.

Answer 15

primitive variables

Question 16

Are two arrays of the same set of elements equivalent using the comparison operator (==) ?

Answer 16

The two arrays are references to 2 different objects in memory hence not equivalent

Question 17

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?

Answer 17

The two objects are not equal because the overriding method introduced replaces the initial parent class method

Question 18

A ____________ of an array only creates a copy of an array (or parts of an array) for primitive data types.

Answer 18

shallow copy

Question 19

A ______________ creates a copy of an array of objects while still creating new references to objects underneath.

Answer 19

deep copy

Question 20

The _____________ method lets you copy part of an array or an entire array.

Answer 20

arraycopy

Question 21

A _________ creates a mirror image of the array.

Answer 21

clone

Question 22

In Java, a _____ copy would copy only the double data types of an array.

Answer 22

shallow

Question 23

Clone the oldRates array and name it rates, double data type.

Answer 23

double[] rates = oldRates.clone();

Question 24

If a program needed to create a copy of an array with new references to an object, what type of copy would be performed?

Answer 24

Deep copy

Question 25

If you only want to clone a portion of an array in Java, which method do you use?

Answer 25

arraycopy

Question 26

Why is cloning multi-dimensional arrays in Java not available using the clone method?

Answer 26

A Java multi-dimensional array is an array of objects

Question 27

Contra attack

Answer 27

The use of contrapositive and contradiction methods in order to justify a given statement.

Question 28

Induction

Answer 28

One of the most important tools for analyzing algorithms. It involves proving mathematical statements true with a finite set of elements.

Question 29

Loop variants

Answer 29

Analyzing the correctness of an algorithm consisting of loops with conditions that both hold true immediately before and immediately after every iteration of the

Question 30

This can be defined as the function which determines the amount of time an algorithm takes to give the desired output.

Answer 30

Time complexity

Question 31

This function describes the total memory space consumed upon running an algorithm.

Answer 31

Space complexity

Question 32

Consumption of space depends on these three things:

Answer 32

1: type of data structures 2: the memory allocations completed for the variables used 3: the results stored after execution

Question 33

data structure

Question 34

algorithm

Answer 34

a collection of steps to solve a problem

Question 35

Stack data structure

Answer 35

last in first out, stores object in a "vertical tower" structure

Question 36

How to initialize a stack in Java?

Answer 36

Stack stack = new Stack();

Question 37

How to add an element to a stack?

Answer 37

stack.push("ElementOne"); stack.push("ElementTwo");

Question 38

How to remove the top most object from a stack?

Answer 38

stack.pop();

Question 39

What does the peek method do with a stack?

Answer 39

Looks for the object at the top of the stack without removing it. stack.peek();

Question 40

Queue data structure

Answer 40

First in First Out (FIFO), similar to waiting in line to checkout at a store a collection designed for holding elements prior to processing

Question 41

Enqueue

Answer 41

adding an element to the tail of a queue offer();

Question 42

Dequeue

Answer 42

removing an element from the head of the queue poll();

Question 43

Priority queue data structure

Answer 43

A FIFO data structure that serves elements with highest priorities first before elements with lower priority. Queue queue = new PriorityQueue<>();

Question 44

Linked lists data structure

Answer 44

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 linkedlist = new LinkedList();

Question 45

ArrayList vs. LinkedList

Answer 45

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

Question 46

Linear time

Answer 46

O(n) looping through elements in an array searching through a linked list

Question 47

Constant time

Answer 47

O(1) random access of an element within an array inserting at the beginning of a linked list

Question 48

Logarithmic time

Answer 48

O(log n) binary search

Question 49

Quasi linear time

Answer 49

O(n log n) quicksort mergesort heapsort

Question 50

quadratic time

Answer 50

O(n^2) insertion sort selection sort bubblesort slow with large data set

Question 51

O(n!)

Answer 51

factorial time extremely slow

Question 52

Linear search

Answer 52

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

Question 53

Binary search

Answer 53

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

Question 54

BubbleSort

Answer 54

A sorting algorithm that compares adjacent elements and goes along the length of the array. not very efficient. O(n^2) time complexity

Question 55

SelectionSort

Answer 55

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.

Question 56

InsertionSort

Answer 56

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)

Question 57

Recursion

Answer 57

Apply the result of a procedure to a procedure. A recursive method calls itself.

Question 58

Insertion Sort explanation:

Answer 58

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.

Question 59

What is the advantage of selection sort?

Answer 59

it requires no additional memory for operation

Question 60

For a given array of [32, 44, 12, 15], the number of iterations performed using selection sort algorithm are:

Answer 60

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.

Question 61

What type of structure uses data stored inside a tree node?

Answer 61

key-value

Question 62

An important use of heap data structure is _____.

Answer 62

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.

Question 63

Which of the following Java statements best depicts the instantiation of the first element within a stack?

Answer 63

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.

Question 64

Steps in Dijkstra's algorithm:

Answer 64

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

Question 65

Graphs come under which category of data structures?

Answer 65

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.

Question 66

A while loop can evaluate ________ conditions.

Answer 66

one or more

Question 67

Which interface requires the compareTo method to be overridden

Answer 67

Comparable

Question 68

Regular queues use the _________ while priority queues remove elements based on _________

Answer 68

FIFO, priority

Question 69

What is a bad character rule?

Answer 69

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

Question 70

What are similarities between recursion and iteration?

Answer 70

they both return the same end result

Question 71

Which package does the List interface belong to?

Answer 71

java.util

Question 72

How many forms of the add method can be used with lists?

Answer 72

TWO, the add method can be used with and without passing an index value

Question 73

B-tree feature to optimize speed is ____?

Answer 73

the use of indexing

Question 74

An abstract class cannot ________

Answer 74

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.

Question 75

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?

Answer 75

Swapping

Question 76

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.

Answer 76

doubly linked list

Question 77

A sort map is _______?

Answer 77

a searchable collection of elements

Question 78

Which of the following sets are implemented classes of the List interface?

Answer 78

There are 10 implemented classes, including ArrayList, LinkedList, Stack, and Vector.

Question 79

Consider a situation where the minimum number of swap operation is required. Which sorting algorithm is best for this use-case?

Answer 79

selection sort Selection sort requires fewer swap operations as compared to other sorting algorithms.

Question 80

What is the main characteristic of binary trees?

Answer 80

each parent only has two children

Question 81

In loop variants, the relationship between the variables __________.

Answer 81

is the same before and after the loops.

Question 82

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 _____.

Answer 82

Linear