XII. Code Library • 破解程式面試

概述#

Part XII — Code Library 收錄了本書在實作各題目解答時，反覆使用的幾個核心資料結構類別。在撰寫完整解答程式碼時，這些類別有時被省略以避免冗餘，但它們是許多解答的基礎。

本書完整可編譯的解答程式碼可至 CrackingTheCodingInterview.com ^↗ 下載。

HashMapList<T, E>#

HashMapList 本質上是 HashMap<T, ArrayList<E>> 的簡化封裝，讓我們能將型別 T 的 key 對應到型別 E 的 ArrayList。

使用前後對比#

沒有 HashMapList 時，需要這樣寫：

HashMap<Integer, ArrayList<String>> maplist =
    new HashMap<Integer, ArrayList<String>>();
for (String s : strings) {
    int key = computeValue(s);
    if (!maplist.containsKey(key)) {
        maplist.put(key, new ArrayList<String>());
    }
    maplist.get(key).add(s);
}

使用 HashMapList 後，可以簡化為：

HashMapList<Integer, String> maplist = new HashMapList<Integer, String>();
for (String s : strings) {
    int key = computeValue(s);
    maplist.put(key, s);
}

完整實作#

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

TreeNode（Binary Search Tree）#

雖然 Java 有內建的樹相關類別，但許多題目需要存取或修改節點的內部狀態（如 parent 指標、size），導致無法使用內建程式庫。

TreeNode 提供豐富的功能，包含父節點追蹤與子樹大小計算，部分功能在特定題目中可能刻意不使用（甚至明確禁止）。

完整實作#

public class TreeNode {
    public int data;
    public TreeNode left, right, parent;
    private int size = 0;

    public TreeNode(int d) {
        data = d;
        size = 1;
    }

    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 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;
    }

    public void setLeftChild(TreeNode left) {
        this.left = left;
        if (left != null) {
            left.parent = this;
        }
    }

    public void setRightChild(TreeNode right) {
        this.right = right;
        if (right != null) {
            right.parent = this;
        }
    }
}

此樹以 BST 方式實作，但也可作為一般二元樹使用——直接操作 setLeftChild/setRightChild 方法或 left/right 欄位即可。所有方法與欄位均為 public 以便靈活存取。

LinkedListNode（Linked List）#

與 TreeNode 類似，許多題目需要深入操控鏈結串列的內部結構，Java 內建的 LinkedList 類別無法提供這種靈活性。

完整實作#

public class LinkedListNode {
    public LinkedListNode next, prev, 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 LinkedListNode clone() {
        LinkedListNode next2 = null;
        if (next != null) {
            next2 = next.clone();
        }
        LinkedListNode head2 = new LinkedListNode(data, next2, null);
        return head2;
    }
}

setNext 與 setPrevious 方法會自動維護雙向鏈結的一致性。所有欄位均為 public，允許外部直接「破壞」鏈結串列結構——這在某些題目的解題過程中是必要的。

Trie & TrieNode#

Trie（字典樹）資料結構在多道題目中被使用，主要用途是快速判斷某個字串是否為字典中其他單字的前綴。這在遞迴建字詞的演算法中尤其重要——當前綴不合法時可提前終止搜尋。

Trie 類別實作#

public class Trie {
    // The root of this trie.
    private TrieNode root;

    /* Takes a list of strings and constructs a trie. */
    public Trie(ArrayList<String> list) {
        root = new TrieNode();
        for (String word : list) {
            root.addWord(word);
        }
    }

    public Trie(String[] list) {
        root = new TrieNode();
        for (String word : list) {
            root.addWord(word);
        }
    }

    /* Checks whether this trie contains a string with the given prefix.
     * If exact is true, checks for exact match; otherwise checks for prefix. */
    public boolean contains(String prefix, boolean exact) {
        TrieNode lastNode = root;
        for (int 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;
    }
}

TrieNode 類別實作#

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 an empty trie node (root node). */
    public TrieNode() {
        children = new HashMap<Character, TrieNode>();
    }

    /* Constructs a trie node for a specific character. */
    public TrieNode(char character) {
        this();
        this.character = character;
    }

    public char getChar() {
        return character;
    }

    /* Add a word to the trie, recursively creating 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 with the given character. Returns null if not found. */
    public TrieNode getChild(char c) {
        return children.get(c);
    }

    /* Returns whether this node marks 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;
    }
}

Trie.contains(prefix, false) 用於前綴查找（只要存在以 prefix 開頭的單字即回傳 true），Trie.contains(word, true) 用於精確匹配（要求 word 本身完整存在於 Trie 中）。