Collections part 2

Question 1

Set characteristics

Answer 1

1. Elements are not ordered.
2. Elements in the set must be unique.
3. Adding a duplicate does nothing.
4. Cannot access elements by index, only by iterator (for each).
5. add( x ) adds an element to the set.

Question 2

Set syntax

Answer 2

Set  variable = new HashSet();
Set - Set interface
 - Data Type the Set will Hold
HashSet - implementation class

Question 3

Set order

Answer 3

The Order of the elements in a Set can be controlled by the Implementation Class used.

Question 4

HashSet - implementation class of Set

Answer 4

1. Does not guarantee Order.

2. Allows null.

Question 5

LinkedHashSet - implementation class of Set

Answer 5

1. Order of Insertion

2. Allows null.

Question 6

TreeSet - implementation class of Set

Answer 6

1. Natural Order of Data Type
2. Does not allow null
   Natural Order of numeric types is numeric order:
   1, 2, 10, 20, 21, 30
   Natural Order of String is alphanumeric order:
   1, 10, 2, 20, 21, 30

Question 7

Key-Value pairs

Answer 7

A set of 2 pieces of data, where the value is associated by a unique key, allowing the value to be retrieved by providing the key.

Question 8

Map

Answer 8

A collection that utilizes Key-Value pairs, allowing values to be assigned and then located using user-defined keys.

Question 9

Map keys characteristics

Answer 9

1. Can be any reference type.
2. Must be unique.
3. Cannot be null.
4. Stored as a Set.

Question 10

Map values characteristics

Answer 10

1. Can be any reference type.
2. Can have duplicates.
3. Can be null.

Question 11

Map syntax

Answer 11

Map variable = new HashMap();
Map - is an interface
K - the first Type is the Data Type of the Key
V - the second Type is the Data Type of the Value
HashMap - the implementation class to instantiate

Question 12

Map Methods

Answer 12

put( key, value ), get( key ), remove( key ), containsKey( key ), containsValue( value ), keySet(), entrySet()

Question 13

Algorithm Problems

Answer 13

Algorithms are not measured by the speed they run, but by how their performance increases as the problem size increases.

Question 14

Big O Complexities

Answer 14

O(1) - Constant-time
- The complexity doesn’t increase as the problem increases (selecting an item from an Array by index).
O(log n) - Logarithmic
- The complexity increases at a constant factor that is not directly related to the problem size.
O(n) - Linear
- Doubling the problem size, doubles the complexity (iterating over every item in a list).
O(n log n) - Linearithmic
- Doubling the problem increases the complexity by a fixed size (most search algorithms).
O(n2) - Quadratic
- Doubling the problem size multiplies the complexity by a factor of 4 (loop within a loop)
O(nx) - Polynomial
- Double the size of the problem multiplies the complexity by a factor multiplied by the exponent
O(2n) - Exponential
- Increasing the problem size by 1 double the complexity. Doubling the problem size squares the work.
O(n!) - Factorial
Something has gone horribly wrong

Question 15

Collection Complexity

Answer 15

Each collection time has a complexity associated with
Insert (at the end, at the beginning, at the end), Searching, Retrieval, Removal (from the end, from the beginning, from the end)

Question 16

Map implementation classes

Answer 16

HashMap - does not maintain order.
LinkedHashMap - maintains the order of insertion.
TreeMap - maintains the natural order of the key data type.

Question 17

Algorithm Complexity

Answer 17

Big O notation is used to describe an algorithm’s change in performance as the problem size increases.
Big O and complexity are always measured in the Worst Case Scenario.