Common implementation for queue
- PriorityQueue - sorts elements in their natural order as they are inserted - don’t use for BFS
- Linked list - keep the same order as when they are inserted
Queue<Integer> q = new PriorityQueue<>(); Queue<Integer> linkedList = new LinkedList<>();
Methods to add and remove items from the queue
- add/remove: throw exception if queue is full
- offer/poll: returns null if queue is full
Implementation for a stack
Stack<Integer> stack = new Stack<>();</Integer>
- stack inherits from Vector abstract class
Methods:
- from Stack class
- push/pop
- peek - look w/o popping
Whats a TreeMap
- items are sorted using their natural order
- use comparators to define sort order
Implement a comparator
- return 1 when greater
- descending order is when o2 > o1
Map<Integer, List<Set<Integer>>> profitToDayIndexMap = new TreeMap<>(</Integer>
// descending order
new Comparator<Integer>() {</Integer>
@Override
public int compare(Integer o1, Integer o2) {
return o2 > o1 ? 1 : o2 == o1 ? 0 : -1;
}
} );Think this way. You are given two items. Return 1 for the item you want the comparator to return first when it’s greater than the other.
For descending order, return 1 when b > a.
Convert array to list and vise verse
- better not use primitive types for easy conversion
- list <- array:
- use Arrays.asList(array)
- and pass the array
- array <- list
- use list.toArray(new Integer[0])
- it’s always new Integer[0]
// init array
Integer[] array = new Integer[]{1, 2, 3};
// convert array to list
List<Integer> list = Arrays.asList(array);
// convert list to array
array = list.toArray(new Integer[0]);What Set implementation to use to
1. maintain the insertion order
2. maintain the natural ordering of the elements
- maintain insertion order: LinkedHashSet
- maintain natural ordering: TreeSet
Whats the limits to recursion in java
- it’s the overall thread stack size
- can be tuned via -Xss flag
- causes stack overflow error if reached
How to sort an array in place
int[] nums = new int[]{2, 3, 5, 1};
Arrays.sort(nums);
How to sort an array w/o modifying the array
int[] nums2 = new int[]{2, 3, 5, 1};
int[] sorted = Arrays.stream(nums2).sorted().toArray();
How to sort a list
List<Integer> nums = Arrays.asList(1, 4, 3, 2);
List<Integer> sorted = nums.stream().sorted().collect(Collectors.toList());</Integer></Integer>
Name some common methods on the Arrays class
These modifies the array in place
- Arrays.sort(array)
- Arrays.binarySearch(sortedArray, value)
- return position of the key or -1 if not found
- Arrays.fill(array, valueToFill)
These allow the array to be viewed and operated on as a list
- Arrays.stream(array)…. // more manipulation
- Arrays.asList(array);
- Arrays.asList(1,2,3);
int[] array = new int[]{1,2,3};
// static method for search
Arrays.sort(nums);
int pos = Arrays.binarySearch(nums, 1);
// static method to fill
Arrays.fill(nums, 1);
// static methods for sort
Arrays.sort(array); // sorts in place
// allow arrays to be viewed as lists
Arrays.stream(array)... // view array as a list
Arrays.asList(1,2,3); // inits a list with value
Arrays.asList(array); // inits a list with an array
What are some highlights of the Arrays class
- Arrays is a concrete class
- Contains methods to manipulate arrays such as sorting and searching
- Contains static factory to allow arrays to be viewed as lists.
- sorted() is a method on the Stream interface
How to convert list <-> array with primitive types
- the complication here is because we need to do “boxing”
- list <- array: use Arrays.stream(array).boxed()
- array <- list: use mapToInt()
// with primitive types
int[] primitiveArray = new int[]{1, 2, 3};
// convert array to list (where array is with primitive type)
List<Integer> list2 = Arrays.stream(primitiveArray).boxed().collect(Collectors.toList());
// convert list to array
primitiveArray = list2.stream().mapToInt(Integer::intValue).toArray();
primitiveArray = list2.stream().mapToInt(i -> i).toArray();
Collection, Collections, Collector, Collectors, etc
What are the high level differences
- two pairs of class (with s) and interface (w/o s)
- Collectors: reduction operation: toList, joining, groupingBy
- Collections: utility (static) methods on Collection (List, Set, Map, Queue)
For Collection, Collections, Collector, Collectors, etc
What’s “Collectors” (with s)
Name some common operations and how to call it.
Collectors (class)
- Implements the Collector interface (via a static inner class)
- Implements various reduction operation
- Collectors.toList()
- Collectors.toCollection(TreeSet::new) // convert to specific Set implementation
- Collectors.joining(“,”)
- Collectors.groupingBy
- Collectors.partitioningBy
- to call Collectors, use collect(Collectors.toList())
For Collection, Collections, Collector, Collectors, etc
What’s “Collector” (w/o s)
Collector (interface)
- implemented by the “Collectors” class
- mutable reduction operation
- accumulates input elements into a mutable result container
- optionally transform the accumulated result into a final representation and all input elements have been processed
- reduction operation can be sequential or parallel
For Collection, Collections, Collector, Collectors, etc
What’s “Collections” (w/ s)
Collections (class)
- does NOT implement the “Collection” interface itself
- a utility class to operate on Collection
- contains all static methods
- methods such as sort, binarySearch, min, max, replaceAll, reverse, swap
What are some useful utility methods on the Collections class
- sort (List<T> list) -> void</T>
- binarySearch (List<T> list, T key) -> int</T>
- frequency (Collection<?> c, Object o) -> int
- fill (List<T> list, T object) -> void</T>
- min (Collection<T> c) -> T</T>
- max (Collection<T> c) -> T</T>
- replaceAll (List<T> list, T oldVal, T newVal) -> boolean
</T>- returns true if at least one element is replaced
- reverse (List<?> list) -> void
- shuffle (List<?> list) -> void
- rotate (List<?> list, int distance) -> void
- swap (List<?> list, int i, int j) -> void
- swaps the elements at these indices
List<Integer> list = Arrays.asList(4, 1, 2, 3);
Collections.sort(list);
Collections.fill(list, 3);For Collection, Collections, Collector, Collectors, etc
What’s “Collection” (w/o s)
Collection (interface)
- interface for List, Set, Queue, Map etc
What’re some differences between Deque vs Stack
Deque vs Stack
- Deque is an interfaces implements Queue
- Deque supports insertion/removal from both ends, deque means double ended queue
- Implementing class includes LinkedList
- Stack is a class implementing Vector
- Stack is synchronized (thread-safe) while Dequeue is not
- Dequeue is faster because it’s not synchronized
Common methods for Deque
Common methods for Deque
- addFirst/addLast, removeFirst/removeLast
- offerFirst/offerLast, pollFirst/pollLast
- peakFirst/peakLast, getFirst/getLast
Stream interface and Streams class
- produces a sequence of elements
- supports aggregate operations
- aggregation can be sequential or parallel
- a Stream is created via Collection (list.stream())
- need to find out how Collection.stream() relates to the Stream interface
- the class itself is deprecated
- the stream() methods we normally use are either from Collection.stream() (w/o param) or Arrays.stream(array) (with param)
Differences/similarities in methods between Arrays vs Collections
- Collections has min() and max() while Arrays does not
- Neither has sum()
- both has binary search and sort
