Time: Sat 10/27/17 2 pm (moved from Tue 10/24/17 10 am)
Property of a min/max heap? Is it easier to find a min or a max item in a min heap? What'll be the best/worst height of a heap (if drawn like a tree) for n nodes? What are the procedures of adding an item to a tree or of removing an item from a tree? (The entry removal is a little more difficult.)
What's the result tree after removing the minimum from the following min heap [0, 1, 4, 8, 2, 6, 8, 9]?
A heap can be stored in an array--begin with index 0 or index 1?
Additionally, if possible, how can we use a min heap to implement a max heap?
Assume integers are represented by 32 bits. If they are unsigned, how many distinct integers can be stored?
Think of a way to represent negative numbers. Does storing a sign bit by itself efficient when going into computation--4 different cases of adding numbers, whoa?! What's the number of distinct integers (signed) this can represent?
Check out two's complement--is this option a little bit easier, or not? Is the heavy math computation easier less troublesome without the various 4 cases? What's the range now? What's the min/max integer in two's complement, written in hexadecimal?
How do we negate an integer in two's complement?
There's a weird number within the range that the integer itself is its own negation.
Common bitwise operations: &, |, ~, ^, <<, >> and >>>.
There's quite a close relationship between Object.equals() and Object.hashCode(). What's a perfect hashing?
In a best/worst scenario, what's the runtime of inserting/finding an element in a hash set (with external linked list)?
Can this improved by tying to another data structure other than linked list?
Why do we care using generics? What's a generic type parameter?
Generics have to be around classes; after all (pretty much) everything is just an object, like literally, with type erasure.
Practice
Will the following class compile?
public final class Algorithm {
public static <T> T max(T x, T y) {
return x > y ? x : y;
}
}Write a generic method to exchange the positions of two different elements in an array.
public final class Algorithm {
public static <T> void swap(T[] a, int i, int j) {
/* Code here */
}
}Will the following code compile?
public static void print(List<? extends Number> list) {
for (Number n : list)
System.out.print(n + " ");
System.out.println();
}Given the following classes:
class Shape { /* ... */ }
class Circle extends Shape { /* ... */ }
class Rectangle extends Shape { /* ... */ }
class Node<T> { /* ... */ }Will the following code compile? If not, why?
Node<Circle> nc = new Node<>();
Node<Shape> ns = nc;Questions selected from The Java™ Tutorials: Questions and Exercises: Generics.