Data Structures And Algorithms

Front 1

Merge sort time complexity

Back 1

O(n log n) in every case. Always divides the array into two halves and then merges the arrays in linear time.

Hint 1

Divides the array in half until down to a single unit, then merges them all.

Front 2

Merge sort space complexity

Back 2

O(n) it requires an equal amount of extra space as the original list, so it's not recommended for large unsorted lists.

Front 3

Bubble sort space complexity

Back 3

O(1) because it only requires a single additional unit for the temp variable.

Front 4

Anonymous Array

Back 4

An array in Java created by a keyword new with an array initializer.

Front 5

Ragged Array

Back 5

A degenerate matrix where rows have different numbers of column elements. Visualized as jagged. An array of arrays where the first is two elements, another is three, another is one, etc.

Front 6

Big O Definition

Back 6

Denotes "fewer than or the same as" <expression> iterations. The set of functions that grow slower than or the same as the rate of expansion. Described the worst case run time of the function

Front 7

Big Omega Definition

Back 7

Denotes "more than or the same as" <expression> iterations. The set of functions that grow faster than or the same as the rate of expansion.

Front 8

Big Theta

Back 8

Denotes "the same as" <expression> iterations. Consists of all the functions that lie in both Big O and Big Omega.

Front 9

Little O

Back 9

Denotes "fewer than" <expression> iterations.

Front 10

Little Omega

Back 10

Denotes "more than" <expression> iterations.

Front 11

Predicate

Back 11

A predicate is a function that returns true or false. It is generally used to make a decision about an action to take.

someMethod(..., (Unity Engineer. Color c) => c== Color.white,...) ;

Front 12

Bubble Sort Definition

Back 12

Sorts N elements. It compares all elements one by one and sorts them based on their values. Each iteration through the smaller elements bubble up toward the front of the array.

It compares two numbers and if they are out of order, it swaps them before moving in to the next two numbers.

Front 13

Determine When To Stop Sorting

(Bubble Sort)

Back 13

Use a flag. If no swaps were made for the entire iteration, then the array is sorted and you can stop.

Front 14

Bubble Sort Time Complexity

Back 14

Best: O(n) when already sorted.

Worst and Average: O(n^2)

because every item must be compared against nearly every item. (n-1)+(n-2)+...+1 = n(n-1)/2 = n^2

Front 15

Insertion Sort Definition

Back 15

Sorts the array by shifting elements one by one. We have a sorted section and an unsorted section. We start at position 2 and compare it to the numbers before it, then put the number in the correct position. The sorted section is thus always in order.

Front 16

Insertion Sort Stats

Back 16

Stable

Adaptive

Efficient for small sets, inefficient for large sets.

Better Rohan selection or bubble sort.

Front 17

Stable Definition

Back 17

A stable sort does not change the relative order of the elements with equal keys. If R and S have the same key, but R came before S in the original list, a stable sort keeps R before S in the sorted list.

Front 18

Adaptive Definition

Back 18

If the sort takes advantage of the presortedness of the input. A presented array may make a sort linear time instead of quadratic.

Front 19

Insertion Sort Time Complexity

Back 19

Best Case: O(n) when array is sorted.

Average and Worst Case: O(n^2). Because each item must be compared with nearly every other item in order to find the correct location.

Front 20

Static Variable / Class Variables

Back 20

Only one instance of the variable, at the class level. Usually as you create new instances of the class, each instance gets its own copy of the variable. If however you wanted to keep track of total books you could have a static variable. Referenced by

ClassName.variableName instead of using the instance name.

Book.totalBooks += 1 instead of

MobyDick.totalBooks += 1

Front 21

Static Method / Class Method

Back 21

Often used to access static variables, but they cannot access instance variables since they are part of the class, not of the specific instance.

ClassName. methodName() ;

Front 22

Constants

Back 22

Static final VARIABLENAME

The values of a final variable cannot change.

Constant names are all caps.

They cannot be reassigned.

If it is a primitive or string then at compile time the compiler actually replaces every instance of the variable with the value.

Front 23

Java Default Initialization

Back 23

Boolean false

Byte 0

Int 0

Char \u0000

Double 0.0d

Object reference null

Front 24

this()

Back 24

Used in constructors, it must be the first thing. It's used to call other constructors. The code after this() will execute after the invoked constructor completes.

Front 25

Super()

Back 25

Used in the constructor. Must be the first thing in it. Used to call the constructor of the Super class. Almost always used with arguments since the default constructor is always called anyway unless you specifically use this() or a super with arguments.

Front 26

In place sorting algorithms

Back 26

Quicksort

Heapsort

Front 27

What is in place sorting?

Back 27

It does not mean you can't create additional variables. It means you can't create a copy of the input. No copy of array to move the sorted array into.

It works directly on its input which means the original is destroyed.

Front 28

Prototype Pattern

Back 28

You create a prototype interface that contains a clone method.

You extend it into concrete classes that employ the clone method to clone themselves.

If object creation is slow or compute heavy (reading lots of data from database for example) it is faster to copy an object already created.

You can clone an object just by knowing its base type.