Week 1 / Week 2 Flashcards
What is an array?
An array is a sequenced collection of variables all of the same type.
Syntax for array declaration.
elementType[] arrayName = {initialValue0, initialValue1, … , initialValue(n - 1)};
or
elementType[] arrayName = new elementType[n];
Syntax for folding over an array using stream.
Arrays.stream(arr).reduce(starting value, binary function);
Random numbers syntax.
Random random = new Random()
Name the four main design patterns.
Encapsulation
Inheritance
Iteration
Exceptions
What are the disadvantages of encapsulation?
- Interface may not effectively provide all desired operations.
- Indirection may reduce performance.
What are the disadvantages of inheritance?
- Code for a class can be spread over multiple files.
- Runtime performance overhead of dispatching.
What are the disadvantages of iteration?
- Iteration order is implementation dependent and not controlled by client.
What are the disadvantages of exceptions?
Unreadable
Have to find right place to catch
Using exceptions for normal control flow confusing..
How is a multidimensional array implemented in java?
An array of arrays.
How many bytes does a single dimensional array take up?
(length of array * type size + header) rounded up to nearest multiple of 8.
How many bytes does a multi-dimensional array take up?
(length of array * (size of inner array + reference size) + header) rounded up to nearest multiple of 8.
Define linked list generally.
Collection of nodes which contain an element and a pointer to the next node. Have a linear order.
The number of items in a list, the length, can vary over time.
What is the disadvantage of implementing linked list using array?
Fixed size n, lots of empty spaces, cannot grow beyond limits.
Define singly linked list.
Linked list where a pointer head points to the first node and the last node points to null. If the list is empty head points to null.
What are the two big advantages of linked lists?
The number of nodes in a linked list is not fixed.
Constant time for deletions and insertions.
What is the big disadvantage of linked list?
Does not provide direct access to the individual elements.
Define doubly linked list.
Two nodes called header and trailer always contain null element. Next ptr of header points to first element of list (or trailer if empty). Prev ptr of trailer points to last element of list (or header if empty). All nodes have next and prev ptrs.
Define circularly linked list.
SSL except instead of last node pointing to null it points back to first node. Instead of head ptr we have a cursor which points to the current “first” position in the circle and can be updated.
How is a linked list cloned?
Traversing the list and addLast for each element to a new version of that list which we return.
How is a linked list reversed?
Iterate along the list switching the current.next to be the current.prev and the current.prev to be the original current.next. Switch head to last current found.
How is a cycle detected in a linked list?
Run two pointers through the linked list at different speeds. If the slow ever points to the same node as the fast we know there is a loop.
What is an abstract data type? What does it include?
Is a model for data structures that defines the data and the operations that can be performed on it, while hiding the implementation details.
- type of data stored
- operations supported
- types of parameters of the operations
- No implementation details
What is the definition of the List Abstract Data Type in Java?
List ADT: An abstract data type which stores a collection of things all of the same type. You can only insert things of the declared type.
ADT Functions:
size()
isEmpty()
get(i)
set(i, e)
add(i, e)
remove(i)
