Java Interview Guide: How to Build Confidence With a Solid Understanding of Core Java Principles pdfdrive com

Binary Search Tree
A binary search tree (BST) is a data structure that sorts nodes in a hierarchical
tree. A red-black tree is a BST implementation that colors each node according
to its location. The color of adjacent nodes can determine whether or not a tree
is balanced. An unbalanced tree degrades to O(n) time on lookups, so a
balancing operation is used after inserting or removing nodes to guarantee
lookups in O(log n) time.
TreeMap
is a red-black tree implementation that uses entry nodes to store its
values. An Entry object contains a key, a value, a color, and a reference to its
parent entry, left entry, and right entry. A TreeMap stores its entries according
to the natural ordering of their keys or by a sorting strategy provided
by a Comparator. A naturally sorted tree requires that keys correctly
implement the compareTo() and equals() methods in the Comparable
interface. A TreeMap iterates through its entries in sorted order. TreeMap
is not thread-safe, but it can be decorated by the
Collections#synchronizedSortedMap()
method.

---

Heap
A heap is an unsorted data structure that organizes nodes in a hierarchical tree.
In a max-heap, the values of a parent node are always greater than the values
of its child nodes. In a min-heap, the values of a parent node are always less than
the values of its child nodes.
A heap is a maximally efficient implementation of a priority queue. A priority
queue serves elements according to their priority and falls back to a FIFO policy
for identical priorities. The PriorityQueue class uses an object array to store
its values. Although heaps are visually represented as a tree, they can
be compactly stored inside of an array and nodes can be located by index
arithmetic. PriorityQueue is not thread-safe,
but PriorityBlockingQueue is a thread-safe alternative.

---

Set
A Set is a data structure that holds a collection of unique values. Sets often
delegate functionality to maps because the keys in a map are already unique.
HashSet
utilizes a HashMap, which does not maintain the insertion order
of its elements. LinkedHashSet utilizes a LinkedHashMap,
which maintains insertion order by way of an auxiliary LinkedList.
TreeSet
utilizes a TreeMap, which maintains the natural ordering of its
elements. None of these classes are thread-safe, but the
Collections#newSetFromMap()
method can create a set out
of a ConcurrentHashMap.

---

Iterator
An Iterator is an object that can visit and remove elements in a collection.
A fail-fast iterator throws a ConcurrentModificationException if it
detects structural changes to a collection outside of its remove() method.
A fail-safe iterator will not throw an exception because it operates on a clone
of the original collection.

---

Questions
What is the difference between an ArrayList and a LinkedList?
How does a HashMap work internally?
What would happen if a key’s hashCode() or equals() method was incorrect?
What is the difference between a stack and a queue?
What is the difference between a binary search tree, red-black tree, and a heap?
What is the difference between a HashSet, LinkedHashSet, and TreeSet?
What is the difference between a fail-fast iterator and a fail-safe iterator?

---