https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/CtCILibrary/CtCILibrary
public class HashMapList<T, E> {
private HashMap<T, ArrayList<E>> map = new HashMap<T, ArrayList<E>>();
/* Insert item into list at key. */
public void put(T key, E item) {
if (!map.containsKey(key)) {
map.put(key, new ArrayList<E>());
}
map.get(key).add(item);
}
/* Insert list of items at key. */
public void put(T key, ArrayList<E> items) {
map.put(key, items);
}
/* Get list of items at key. */
public ArrayList<E> get(T key) {
return map.get(key);
}
/* Check if hashmaplist contains key. */
public boolean containsKey(T key) {
return map.containsKey(key);
}
/* Check if list at key contains value. */
public boolean containsKeyValue(T key, E value) {
ArrayList<E> list = get(key);
if (list == null) return false;
return list.contains(value);
}
/* Get the list of keys. */
public Set<T> keySet() {
return map.keySet();
}
@Override
public String toString() {
return map.toString();
}
}
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/CtCILibrary/CtCILibrary/BTreePrinter.java
public class HashMapList<T, E> {
private HashMap<T, ArrayList<E>> map = new HashMap<T, ArrayList<E>>();
/* Insert item into list at key. */
public void put(T key, E item) {
if (!map.containsKey(key)) {
map.put(key, new ArrayList<E>());
}
map.get(key).add(item);
}
/* Insert list of items at key. */
public void put(T key, ArrayList<E> items) {
map.put(key, items);
}
/* Get list of items at key. */
public ArrayList<E> get(T key) {
return map.get(key);
}
/* Check if hashmaplist contains key. */
public boolean containsKey(T key) {
return map.containsKey(key);
}
/* Check if list at key contains value. */
public boolean containsKeyValue(T key, E value) {
ArrayList<E> list = get(key);
if (list == null) return false;
return list.contains(value);
}
/* Get the list of keys. */
public Set<T> keySet() {
return map.keySet();
}
@Override
public String toString() {
return map.toString();
}
}
public class Trie
{
// The root of this trie.
private TrieNode root;
/* Takes a list of strings as an argument, and constructs a trie that stores these strings. */
public Trie(ArrayList<String> list) {
root = new TrieNode();
for (String word : list) {
root.addWord(word);
}
}
/* Takes a list of strings as an argument, and constructs a trie that stores these strings. */
public Trie(String[] list) {
root = new TrieNode();
for (String word : list) {
root.addWord(word);
}
}
/* Checks whether this trie contains a string with the prefix passed
* in as argument.
*/
public boolean contains(String prefix, boolean exact) {
TrieNode lastNode = root;
int i = 0;
for (i = 0; i < prefix.length(); i++) {
lastNode = lastNode.getChild(prefix.charAt(i));
if (lastNode == null) {
return false;
}
}
return !exact || lastNode.terminates();
}
public boolean contains(String prefix) {
return contains(prefix, false);
}
public TrieNode getRoot() {
return root;
}
}
public class TrieNode {
/* The children of this node in the trie.*/
private HashMap<Character, TrieNode> children;
private boolean terminates = false;
// The character stored in this node as data.
private char character;
/* Constructs a trie node and stores this character as the node's value.
* Initializes the list of child nodes of this node to an empty hash map. */
public TrieNode() {
children = new HashMap<Character, TrieNode>();
}
/* Constructs a trie node and stores in the node the char passed in
* as the argument. Initializes the list of child nodes of this
* node to an empty hash map.
*/
public TrieNode(char character) {
this();
this.character = character;
}
/* Returns the character data stored in this node. */
public char getChar() {
return character;
}
/* Add this word to the trie, and recursively create the child
* nodes. */
public void addWord(String word) {
if (word == null || word.isEmpty()) {
return;
}
char firstChar = word.charAt(0);
TrieNode child = getChild(firstChar);
if (child == null) {
child = new TrieNode(firstChar);
children.put(firstChar, child);
}
if (word.length() > 1) {
child.addWord(word.substring(1));
} else {
child.setTerminates(true);
}
}
/* Find a child node of this node that has the char argument as its
* data. Return null if no such child node is present in the trie.
*/
public TrieNode getChild(char c) {
return children.get(c);
}
/* Returns whether this node represents the end of a complete word. */
public boolean terminates() {
return terminates;
}
/* Set whether this node is the end of a complete word.*/
public void setTerminates(boolean t) {
terminates = t;
}
}
public class LinkedListNode {
public LinkedListNode next;
public LinkedListNode prev;
public LinkedListNode last;
public int data;
public LinkedListNode(int d, LinkedListNode n, LinkedListNode p) {
data = d;
setNext(n);
setPrevious(p);
}
public LinkedListNode(int d) {
data = d;
}
public LinkedListNode() { }
public void setNext(LinkedListNode n) {
next = n;
if (this == last) {
last = n;
}
if (n != null && n.prev != this) {
n.setPrevious(this);
}
}
public void setPrevious(LinkedListNode p) {
prev = p;
if (p != null && p.next != this) {
p.setNext(this);
}
}
public String printForward() {
if (next != null) {
return data + "->" + next.printForward();
} else {
return ((Integer) data).toString();
}
}
public LinkedListNode clone() {
LinkedListNode next2 = null;
if (next != null) {
next2 = next.clone();
}
LinkedListNode head2 = new LinkedListNode(data, next2, null);
return head2;
}
}
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/CtCILibrary/CtCILibrary/TreeNode.java
public class TreeNode {
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode parent;
private int size = 0;
public TreeNode(int d) {
data = d;
size = 1;
}
private void setLeftChild(TreeNode left) {
this.left = left;
if (left != null) {
left.parent = this;
}
}
private void setRightChild(TreeNode right) {
this.right = right;
if (right != null) {
right.parent = this;
}
}
public void insertInOrder(int d) {
if (d <= data) {
if (left == null) {
setLeftChild(new TreeNode(d));
} else {
left.insertInOrder(d);
}
} else {
if (right == null) {
setRightChild(new TreeNode(d));
} else {
right.insertInOrder(d);
}
}
size++;
}
public int size() {
return size;
}
public boolean isBST() {
if (left != null) {
if (data < left.data || !left.isBST()) {
return false;
}
}
if (right != null) {
if (data >= right.data || !right.isBST()) {
return false;
}
}
return true;
}
public int height() {
int leftHeight = left != null ? left.height() : 0;
int rightHeight = right != null ? right.height() : 0;
return 1 + Math.max(leftHeight, rightHeight);
}
public TreeNode find(int d) {
if (d == data) {
return this;
} else if (d <= data) {
return left != null ? left.find(d) : null;
} else if (d > data) {
return right != null ? right.find(d) : null;
}
return null;
}
private static TreeNode createMinimalBST(int arr[], int start, int end){
if (end < start) {
return null;
}
int mid = (start + end) / 2;
TreeNode n = new TreeNode(arr[mid]);
n.setLeftChild(createMinimalBST(arr, start, mid - 1));
n.setRightChild(createMinimalBST(arr, mid + 1, end));
return n;
}
public static TreeNode createMinimalBST(int array[]) {
return createMinimalBST(array, 0, array.length - 1);
}
public void print() {
BTreePrinter.printNode(this);
}
}
public class BitVector {
private static int DATA_SIZE = 32;
private int length;
private int[] vector;
public BitVector(int length) {
this.length = length;
if (length % DATA_SIZE == 0) {
vector = new int[length / DATA_SIZE];
} else {
vector = new int[length / DATA_SIZE + 1];
}
}
public int length() {
return length;
}
public boolean get(int i) {
int b = vector[i / DATA_SIZE];
int bit_index = i % DATA_SIZE;
if (((b >> bit_index) & 1) == 1) {
return true;
} else {
return false;
}
}
public void print() {
for (int k : vector) {
for (int i = 0; i < DATA_SIZE; i++) {
if ((k >> i & 1) == 1) {
System.out.print(1);
} else {
System.out.print(0);
}
}
System.out.println();
}
}
public void set(int i, boolean flag) {
if (i >= 0 && i < length) {
int mask = ~(1 << i);
int b = vector[i / DATA_SIZE] & mask;
if (flag) {
vector[i / DATA_SIZE] = b | (1 << i);
} else {
vector[i / DATA_SIZE] = b;
}
}
}
}
https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/CtCILibrary/CtCILibrary/BTreePrinter.java
