Java code snippet and implementations

Question 1

Common implementation for queue

Answer 1

• 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<>();

Question 2

Methods to add and remove items from the queue

Answer 2

• add/remove: throw exception if queue is full
• offer/poll: returns null if queue is full

Question 3

Implementation for a stack

Answer 3

Stack<Integer> stack = new Stack<>();</Integer>

• stack inherits from Vector abstract class

Methods:
- from Stack class
- push/pop
- peek - look w/o popping

Question 4

Whats a TreeMap

Answer 4

• items are sorted using their natural order
• use comparators to define sort order

Question 5

Implement a comparator

Answer 5

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

Question 6

Convert array to list and vise verse

Answer 6

• 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]);

Question 7

What Set implementation to use to
1. maintain the insertion order
2. maintain the natural ordering of the elements

Answer 7

• maintain insertion order: LinkedHashSet
• maintain natural ordering: TreeSet

Question 8

Whats the limits to recursion in java

Answer 8

• it’s the overall thread stack size
• can be tuned via -Xss flag
• causes stack overflow error if reached

Question 9

How to sort an array in place

Answer 9

int[] nums = new int[]{2, 3, 5, 1};
Arrays.sort(nums);

Question 10

How to sort an array w/o modifying the array

Answer 10

int[] nums2 = new int[]{2, 3, 5, 1};
int[] sorted = Arrays.stream(nums2).sorted().toArray();

Question 11

How to sort a list

Answer 11

List<Integer> nums = Arrays.asList(1, 4, 3, 2);
List<Integer> sorted = nums.stream().sorted().collect(Collectors.toList());</Integer></Integer>

Question 12

Name some common methods on the Arrays class

Answer 12

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

Question 13

What are some highlights of the Arrays class

Answer 13

• 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

Question 14

How to convert list <-> array with primitive types

Answer 14

• 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();

Question 15

Collection, Collections, Collector, Collectors, etc

What are the high level differences

Answer 15

• 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)

Question 16

For Collection, Collections, Collector, Collectors, etc

What’s “Collectors” (with s)

Name some common operations and how to call it.

Answer 16

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())

Question 17

For Collection, Collections, Collector, Collectors, etc

What’s “Collector” (w/o s)

Answer 17

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

Question 18

For Collection, Collections, Collector, Collectors, etc

What’s “Collections” (w/ s)

Answer 18

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

Question 19

What are some useful utility methods on the Collections class

Answer 19

• 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);

Question 20

For Collection, Collections, Collector, Collectors, etc

What’s “Collection” (w/o s)

Answer 20

Collection (interface)
- interface for List, Set, Queue, Map etc

Question 21

What’re some differences between Deque vs Stack

Answer 21

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

Question 22

Common methods for Deque

Answer 22

Common methods for Deque
- addFirst/addLast, removeFirst/removeLast
- offerFirst/offerLast, pollFirst/pollLast
- peakFirst/peakLast, getFirst/getLast

Question 23

Stream interface and Streams class

Answer 23

• 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)

Question 24

Differences/similarities in methods between Arrays vs Collections

Answer 24

• Collections has min() and max() while Arrays does not
• Neither has sum()
• both has binary search and sort

Question 25

Whats the name of the compare function for Comparator and Comparable.

What are some similarities and differences.

Answer 25

Comparator
Function: compare. Takes two args

Comparable
Function: compareTo. Take one arg

Both return 1 for the greater element.

Comparable is the interface to implement to be able to sort