Note for Cracking the Coding Interview

Posted on 2018-05-31 Edited on 2018-08-05 In Tech Disqus:

Note for Cracking the Coding Interview 6th Edition.

Big O

Multipart Algorithms

Add: do A, then when A is all done, do B.
Multiply: do B each time you do A. (recall Zillow mistake…)

Recursive Runtimes

See branched recursive calls from parent calls to form a “tree”. Pattern: O(barnches ^ depth), branches = #times each recursive call branches.

Arrays and Strings

Hash Tables

Array of linked lists: O(1) general lookup time.
Balanced BST: O(logN) lookup time, less space.

Resizable Arrays

ArrayList: O(1) amortized insertion time.

String v.s.StringBuilder

String: immutable, always create a new copy of the string when concatenating(might bring the runtime to O(N^2))
StringBuilder: resizable char array.

Problems

Q：给一个String，判断它是否包含完全不同的unique characters。
- 用一个bucket数组，ASCII一共有128个字符。O(N)时间和空间。
- O(NlogN) sort之后遍历一波，判断相邻的char即可。无额外空间。
- 如果只是26个字母，可以直接用bit当作bucket来用，一旦有一个bit之前已经设为1了就说明不unique。
Q：给两个String，判断它们是否是同一个permutation.
- O(NlogN) sort之后比较一波。
- 用一个bucket数组统计每个字符出现的个数。
Q：给一个char array和它的real length（array.length足够hold住替换之后的所有字符），将其中所有的空格都替换成%20，.
- 从给定的len - 1开始从后往前遍历，依次复制／替换到char数组的末尾。String manipulation问题通常可以尝试从后往前做，因为这样相当于在末尾有一个inplace的buffer。
Q：给一个String，判断它是否是palindrome的permutation。
- 用一个bucket记录所有字符出现的个数，最后再一波O(N)统计是否有超过一个的count是odd。
- 用一个countOdd变量在统计个数的时候顺便记录有多少个是odd的，全部统计完了之后直接就可以判断了。
- 我们并不关心『每个字符具体有多少个』，而只是想知道『每个字符个数是even还是odd』。因此直接用bit作为on/off即可，最后要么为0（全是even），要么只有一位是1（判断x & (x-1) == 0即可）。
Q：给两个String，判断他们是否之多差一步操作即可相互转换：插入一个字符／删除一个字符／替换一个字符。
- 关键在于发现插入和删除其实是逆操作，直接根据长度判断一下即可知道是哪个操作。
Q：给一个String，将相邻连续出现的字符压缩成a2b3c1的形式，若压缩后长度并没有缩短则维持原字符串。
- 在实际操作之前先判断一下压缩之后的长度再决定要不要执行压缩。
Q：给一个nn的方matrix，向右旋转90度。*
- 老老实实进行四位替换，top-left, left-bottom, bottom-right, right-top.
Q：给一个mn的matrix，若其中一个位置为0则将它所处的行和列全都设为0.*
- 维护两个boolean array分别存放row和column的0的位置，最后再设为0。
- 直接用矩阵的第一行和第一列存放0的位置（需要额外用两个变量mark一下第一行和第一列本身有没有0），就不需要额外空间了。
Q：给两个String，判断其中一个是否是另一个通过rotate形成的，例如abbc->bcab。
- 假设rotation point前面的部分为x，后面的为y，则形成xy的形式。要判断另一个字符是不是yx，其实只需要将xy自己拼接一下形成xyxy，直接看另一个字符串是否是它的substring即可。

Linked List

Runner technique: iterate through linked list with two pointers simultaneously, with one ahead or faster movement.

Problems

Q：给一个unsorted的链表，删除其中重复的元素。
- fix一个节点然后一路往后删，O(N^2)时间。
- 用Set。
Q：给一个链表，返回倒数第k个元素。
- 利用双指针，让后一个指针先挪k，然后两个一起挪即可。
Q：给一个链表中间的某个节点，删除它。
- 其实这题是假的删除，因为无法拿到该节点前面一个节点，因此只能把后面节点的值往前覆盖。
Q：给一个链表和一个int，要求将链表中小于x的元素都排在前面、大于等于x的元素都排在后面，而两个partition内部的顺序不需要维护。
- 链表问题有个经典做法是建“新”的链表、而节点都是原来的。这里就是用两个“新链表”，一个存小于的节点、一个存大于等于的节点，最后合起来。
Q：给两个链表，表示从低位到高位的整数，求它们的和（也用链表表示）。
- 就直接加，需要处理进位和两个链表长度不一样的情况。
- 如果链表表示的是从高位到低位的数字，首先需要将较短的链表前面pad zero，然后再用自定义类（因为需要进位）recursive地求。
Q：给一个链表，判断是否palindrome。
- 先拷贝一份reverse的链表，然后直接比较两个链表是否相等。
- 用快慢指针将前半部分投入stack，然后一边pop一边往后比较。
- 用自定义类（需要boolean以及后续指针）recursive地判断，若之前都为true且当前元素和返回的元素相等，则继续返回true。
Q：给两个链表，判断它们是否相交并返回第一个汇合点。
- 先走两波获取两个链表的长度求出delta，然后让长的先走delta，再一起遍历即得汇合点。
- 交叉走法：A和B同时往后走，当A走到尽头就再从B出发、B同理，最后如果汇合了即为汇合点。假设A的独立部分长度为a，B的独立部分长度为b，公用部分为c，(a+c+b) = (b+c+a).
Q：给一个链表，判断它是否有环并返回环的入口。
- 快慢指针出发，相遇之后再从起点走一个慢指针，相遇处即为入口。设环长度为l，环之前长度为a，相遇时慢指针在环内走了b。有(a+l+b) = 2(a+b)，即l - b = a，因此继续走必定相遇。

Stacks and Queues

Stack: LIFO
Queue: FIFO

Problems

Q：用一个array实现三个Stack。
- 将array划分成3等份，然后每个stack就只有固定一部分的capacity进行pop, push.
- 如果想要flexible size，可以学习arraylist那样在一开始先有一个initial capacity，满了之后再进行扩容。
Q：实现一个stack，支持push, pop, min方法，其中min可以返回当前所有stack中元素的最小值。
- push的时候如果最小值更新了，则先把当前最小值push进去，然后再把新值push进去并更新最小值；pop的时候如果最小值和栈顶一致，则需要再pop一下把最小值更新。
Q：实现stacks的ArrayList，当一个stack满了之后就新建另一个stack继续存。
- push好办，对应index进行存放，满了就在下一个index新建stack继续放。pop则需要考虑是否需要维护『前面所有stack都维持在满的状态』这个条件，如果需要就得把指定index之后的stack都进行roll over，将栈底釜底抽薪放到前面。
Q：用两个stack实现queue。
- 一个stackA只负责存、另一个stackB只负责取。如果peek的时候没有东西了，就需要将B中所有内容都pop到A中，再从A中取，这样就可以保证FIFO。
Q：给一个stack，将它排序，最小值在栈顶。只允许使用一个辅助stack。
- s2作为辅助stack，维持从大到小的顺序。s1中pop栈顶元素先存入一个变量temp，若发现temp比s2栈顶大则完美存入，否则需要先将s2的元素不断pop并存入直到temp元素可以放入，然后再重复从s1 pop存入temp的过程插入s2。
- 如果有无限制的辅助stack可以使用，就可以实现类似于mergesort和quicksort的排序。mergesort在每一个recursion level都需要两个辅助stack来排序，将他们各自排好序然后将他们汇集到输入的原始stack中，依次递归就能将整个stack排序完成；quicksort也需要在每一个recursion level两个辅助stack，将他们divide based on pivot value最后再汇集到原始stack。
Q：动物收容所领养动物必须遵循FIFO规则，只能选择动物种类cat/dog，或者随机选择入队最久的anything。要求使用linkedlist。
- 维护两个LinkedList分别存放cat和dog，直接append到List末尾即可，dequeue就直接从头部取；dequeueAny则利用timestamp保证取最久的。

Trees and Graphs

Types of Trees

Complete Binary Tree: Every level is fully filled, except last level; In each level, nodes are filled from left to right.
Full Binary Tree: Every node has either 0 or 2 children.
Perfect Binary Tree: Both Full and Complete Binary Tree.
BST: left <= n < right

Traverse

DFS: simpler implementation(recursion) for visiting all nodes in graph. Need to check if the node has been visited.
BFS: find path(shortest path) between two nodes.
Bidirectional Search: find the shortest path between a src and dest node by running two BFS from src and dest simultaneously.

Problems

Q：给一个有向图和两个node，判断它们之间是否有path
- 就是简单的考察BFS和DFS。
Q：给一个含有不同int的升序数组，创建一个对应的最小height的BST
- 要想生成高度最小的BST，也就是root需要是数组中间元素。因此一个递归方法就出来了，先找到中间元素作为root，然后递归生成左半边的BST和右半边的BST分别作为左右孩子。
Q：给一个二叉树，求每一个depth处的nodes，存在LinkedList中
- 其实就是level traverse，用BFS层级遍历即可。时间O(N)，空间不包括输出的话是O(1)。
- 也可以用DFS的preorder traversal，附加传入一个level信息即可。时间O(N)，空间O(logN)。
Q：给一个二叉树，判断它是否balanced（左右子树的高度相差不超过1）
- 暴力递归，对于每一个节点递归地求深度，对于每一个节点都会被在它上面的节点访问一次，因此时间是O(NlogN)。
- 考虑优化求height的过程，在递归的时候事实上可以通过传回「特殊值」来表示unbalanced的情况，这样可以保证每一个节点只会被访问一次，因此时间是O(N)。
Q：判断一个BST是否合法
- 用in-order traverse和一个全局变量来比较prev和curr，保证完全小于。
- 传入min和max值限定孩子节点的值域，一旦不符合就直接false了。
Q：给一个二叉树中的node，求它在in-order traverse中的successor(假设每一个节点都可以访问到parent节点)
- 需要分情况讨论：如果当前node有右子树，则需要访问到右子树的最左节点；如果没有右子树，则说明当前节点及其孩子已经全部访问完了，需要回到parent，而这parent又要分node是它的左孩子还是右孩子，是右孩子的话说明是已经访问过parent才来到node的，因此还要往parent的parent找，只有当node是parent的左孩子时，parent才是successor.

TreeNode inorderSuccessor(TreeNode node) {
    if (node == null) {
        return null;
    }
    if (node.right != null) {
        return getLeftMostChild(node.right);
    } else {
        TreeNode curr = node;
        TreeNode prev = curr.parent;
        while (prev != null && prev.left != curr) {
            curr = prev;
            prev = prev.parent;
        }
        return prev;
    }
}
TreeNode getLeftMostChild(TreeNode node) {
    if (node == null) {
        return null;
    }
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

Q：给一个List包含一系列project，然后给出部分dependencies表示要想做b必须先完成a。求一个可以完成所有project的顺序。
- 经典拓扑排序，和利口210一样。BFS方法是先遍历一遍dependencies维护一个inDegree数组，然后找出所有入度为0的点入队作为起点，将所有相邻的点的入度减1（删掉从起点到该点的这条边），同时将新的入度为0的点入队。时间是O(v + e).
- DFS也可以做，首先构建邻接链表，然后用一个for-loop尝试从某一点出发能够完全走完所有node的，在DFS时维护一个visited和onpath分别表示当前节点已经访问过or当前节点正在被访问，一旦出现cycle（onpath为true）就说明有cyclic dependencies，不可能走完；如果都ok则吧当前节点插入到当前遍历path的最前面，表示从当前节点出发可以走到后续这些节点，这样回溯到上一层递归调用时又会把对应的incoming node加进来。时间也是O(v + e).

Q：First Common Ancestor

如果是正常的二叉树，只有从parent到child的Link，就是利口236。但注意限制条件，p和q不同且p和q都必须在二叉树中存在。如果拿掉这些限制条件，就无法区分p是q的ancestor和p在树中而q不存在的情况，此时就需要对return的结果小小修改一下，增加返回一个boolean值表示这个是不是真的找到了ancestor.

class Result {
    public TreeNode node;
    public boolean isAncestor;
    public Result(TreeNode node, boolean isAncestor) {
        this.node = node;
        this.isAncestor = isAncestor;
    }
}
TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {
    Result r = helper(root, p, q);
    if (r.isAncestor) {
        return r.node;
    }
    return null;
}
Result helper(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
        return new Result(null, false);
    }
    if (root == p && root == q) {      // p和q相等且存在于树中
        return new Result(root, true);
    }
    Result rLeft = helper(root.left, p, q);
    if (rLeft.isAncestor) {
        return rLeft;
    }
    Result rRight = helper(root.right, p, q);
    if (rRight.isAncestor) {
        return rRight;
    }
    if (rLeft.node != null && rRight.node != null) {  // 左右两边分别找到了p和q
        return new Result(root, true);    // 当前root即为LCA
    } else if (root == p || root == q) {  // 当前root恰好为p/q时，需要确定另一方是否在子树中
        boolean inSubTree = rLeft.node != null || rRight.node != null;
        return new Result(root, inSubTree);
    } else {
        return new Result(rLeft.node != null ? rLeft : rRight, false);
    }
}

如果有Link可以访问parent，则类似于intersection of two linkedlist，利用depth的差值先把较深的节点往上提几个level，然后一起向上挪，汇合处即为ancestor。时间复杂度为O(depth)。

此外还可以选择从其中一个节点出发，在向上的时候总会解锁另一侧的child（即使为null），这时去那一侧check是否包含另一个节点即可，如果不包含就再往上走，继续解锁继续搜。时间复杂度为O(t)，t为ancestor所在subtree的节点数，这个t也可能包含所有节点。

 TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (!contains(root, p) || !contains(root, q)) {
        return null;
    } else if (contains(p, q)) {
        return p;
    } else if (contains(q, p)) {
        return q;
    }

    TreeNode sibling = getSibling(p);
    TreeNode parent = p.parent;
    while (!contains(sibling, q)) {
        sibling = getSibling(parent);
        parent = parent.parent;
    }
    return parent;
}
boolean contains(TreeNode root, TreeNode p) {
    if (root == null) {
        return false;
    }
    if (root == p) {
        return true;
    }
    return contains(root.left, p) || contains(root.right, p);
}
TreeNode getSibling(TreeNode node) {    // 得到和node相同地位的兄弟节点
    if (node == null || node.parent == null) {
        return null;
    }
    TreeNode parent = node.parent;
    return parent.left == node ? parent.right : parent.left;
}

Q:假设BST是通过一个List从左到右填充出来的。给一个BST，求所有可能形成该BST的List of List。例如root为2、左孩子为1、右孩子为3的BST可能是[2,1,3]或者[2,3,1]生成的，需要返回所有可能的List.

BST虽然要求当前节点所有左子树都小于它、所有右子树都大于它，但给定一个List和树的形状之后，只要知道了根节点，左右节点出现的先后顺序没有关系，因为一定是大的在右、小的在左。因此需要递归来实现“把所有左右子树可能情形枚举完后，将当前root插入到所有情况的开头”。

       List<List<Integer>> allSeq(TreeNode root) {
           List<List<Integer>> result = new ArrayList<>();

           if (root == null) {
               result.add(new LinkedList<Integer>());
               return result;
           }
           List<Integer> prefix = new LinkedList<>();
           prefix.add(root.val);

           // 将左右子树的所有情况都列出来
           List<List<Integer>> leftSeq = allSeq(root.left);  
           List<List<Integer>> rightSeq = allSeq(root.right);

           for (List<Integer> left : leftSeq) {     // 两两组合一波
               for (List<Integer> right : rightSeq) {
                   List<List<Integer>> weaved = new ArrayList<>();
                   weaveLists(left, right, weaved, prefix);
                   result.addAll(weaved);
               }
           }
           return result;
       }
       void weaveLists(List<Integer> first, List<Integer> second, List<List<Integer>> results, List<Integer> prefix) {
           if (first.size() == 0 || second.size() == 0) {
               List<Integer> result = (List<Integer>) prefix.clone();
               result.addAll(first);
               result.addAll(second);
               results.add(result);
               return;
           }
           int headFirst = first.removeFirst();
           prefix.addLast(headFirst);
           weaveLists(first, second, results, prefix);   // 递归，将前半部分的第一个元素append到prefix中
           prefix.removeLast();
           first.addFirst(headFirst);

           int headSecond = second.removeFirst();
           prefix.addLast(headSecond);
           weaveLists(first, second, results, prefix);   // 将后半部分的第一个元素append到prefix中
           prefix.removeLast();
           second.addFirst(headSecond);
       }
     ```  
* *Q: 给两个binary tree T1和T2（含有N和M个节点，可能很大），判断T2是否是T1的subtree。*
  - 用类似于二叉树serialized的办法，前序遍历将所有节点都append成StringBuilder，注意null节点也需要表示出来。这样需要O(N + M)空间和O(N + M)时间。
  - 递归的办法，遍历T1的节点，只有当T2的root出现时才开始逐一匹配每一个节点。需要O(log(N) + log(M))空间和O(N + k*M)的时间，其中k是T2的root出现在T1中的次数。（WHY空间是那个？？？？？？？？？）
* *Q: 要求实现一个BST类，含有insert, find, delete以及一个`getRandomNode()`以相等概率返回任意一个节点。*
  - 方法一：如果有`N`个节点，那么相等概率就是`1/N`.因此考虑在每个节点处保存它下属总共有多少个节点，然后就以`1/N`的概率取。
     ```Java
       class TreeNode {
           public int val;   // 简化了
           public TreeNode left;
           public TreeNode right;
           public int size = 0;
           ...

           public TreeNode getRandomNode() {
               int leftSize = left == null ? 0 : left.size;
               Random random = new Random();
               int index = random.nextInt(size);  // 根据当前tree总共有多少节点来决定
               if (index < leftSize) {
                   return left.getRandomNode();
               } else if (index == leftSize) {
                   return this;
               } else {
                   return right.getRandomNode();
               }
           }
           public void insertInOrder(int d) {
               if (d <= val) {
                   if (left == null) {
                       left = new TreeNode(d);
                   } else {
                       left.insertInOrder(d);
                   }
               } else {
                   if (right == null) {
                       right = new TreeNode(d);
                   } else {
                       right.insertInOrder(d);
                   }
               }
               size++;     // 当前这个node的size需要增长
           }
           public TreeNode find(int d) {
               if (d == val) {
                   return this;
               } else if (d <= val) {
                   return left != null ? left.find(d) : null;
               } else {
                   return right != null ? right.find(d) : null;
               }
           }
       }

方法二：方法一调用Random次数较多，因为每次递归下去都要pick一个随机数。考虑在最开始就根据总size选定一个随机数i，然后一路递归下去，按照中序遍历找到第i个节点。

class Tree {
    TreeNode root = null;
    private treeSize = root == null ? 0 : root.size;

    public TreeNode getRandomNode() {
        if (root == null) {
            return null;
        }
        Random random = new Random();
        int i = random.nextInt(treeSize);
        return root.getIthNode(i);
    }
    public void insertInOrder(int value) {
        if (root == null) {
            root = new TreeNode(value);
        } else {
            root.insertInOrder(value);
        }
    }
}
class TreeNode {
    public TreeNode getIthNode(int i) {
        int leftSize = left == null ? 0 : left.size;
        if (i < leftSize) {
            return left.getIthNode(i);
        } else if (i == leftSize) {
            return this;
        } else {
            return right.getIthNode(i - (leftSize + 1));
        }
    }
}

Q: path sum: 给一个二叉树，每个节点含有任意整数，给一个sum，求有多少条从上往下的路径之和等于该sum。

暴力枚举，尝试从root出发看有多少，然后尝试从left和right出发。时间复杂度推导可以这样考虑，对于深度为d的节点，会被在它上面的d个节点touch到，因此对于一个balanced tree来说，时间为O(NlogN)。对于unbalanced的来说，例如一条单边的tree下来，就是O(N^2)

显然暴力方法有很多可以reuse的东西，可以将问题抽象一下。从root往下走的时候，可以看作是一个数组，每一个bucket就是走到该处的runningSum，而给的targetSum其实就是某两个runningSum之间的差，这就转换成了2 Sum的问题，如何在更新runningSum的时候快速判断是否能和之前的某个runningSum刚好相差targetSum.

int countPathSum(TreeNode root, int targetSum) {
    return countPathSum(root, targetSum, 0, new HashMap<Integer, Integer>());
}
int countPathSum(TreeNode node, int targetSum, int runningSum, Map<Integer, Integer> pathSumCount) {
    if (node == null) return 0;

    runningSum += node.val;
    int previousSum = runningSum - targetSum;
    int totalPaths = pathSumCount.getOrDefault(previousSum, 0); // 和之前的某个sum恰好形成差值为target

    if (runningSum == targetSum) {  // running其实就表示从root开始的pathSum
        totalPaths++;
    }

    updatePathSumCount(pathSumCount, runningSum, 1);    
    totalPaths += countPathSum(node.left, targetSum, runningSum, pathSumCount);  // 只能选一边往下走（链式）
    totalPaths += countPathSum(node.right, targetSum, runningSum, pathSumCount);
    updatePathSumCount(pathSumCount, runningSum, -1);

    return totalPaths;
}
void updatePathSumCount(Map<Integer, Integer> pathSumCount, int key, int delta) {
    int newCount = pathSumCount.getOrDefault(key, 0) + delta;
    if (newCount == 0) {
        pathSumCount.remove(key);
    } else {
        pathSumCount.put(key, newCount);
    }
}

Bit Manipulation

2’s Complement

Negative K’s binary represenetation is concat(1, 2^(N-1) - K), where N is the total length of bits.
Another interpretation: -K = ~K + 1, then prepend 1 at the beginning.
Arithmetic right shift = divides by two; Logical right shift = visually shiftying of bits.

Common bit tasks

boolean getBit(int num, int i) {
    return ((num & (1 << i)) != 0);
}

int setBit(int num, int i) {
    return num | (1 << i);
}

int clearBit(int num, int i) {
    int mask = ~(1 << i);
    return num & mask;
}

int clearBitsMSBthroughI(int num, int i) {   // 把最高位到i清0
    int mask = (1 << i) - 1;
    return num & mask;
}

int clearBitsIthrough0(int num, int i) {     // 把i到最低位清0
    int mask = (-1 << (i + 1));
    return num & mask; 
}

int updateBit(int num, int i, boolean bitIs1) {
    int value = bitIs1 ? 1 : 0;
    int mask = ~(1 << i);       // 先将该bit重置为0
    return (num & mask) | (value << i);
}

Problems

Q: 给两个32bit的整数N和M，给定两个索引i和j(j > i且一定可以包含所有M的有效bit)。将N中j~i的部分替换成M的对应部分。

可以考虑分成三步：将N中j~~i置为0、shift M挪到正确的j~~i范围中、合并。

int updateBits(int N, int M, int i, int j) {
    int allOnes = ~0;// 或者直接用-1
    int left = allOnes << (j + 1);
    int right = ((1 << i) - 1);
    int mask = left | right;

    return (N & mask) | (M << i);
}

Q: 给一个(0, 1)之间的double，求它的binary字符串表示，如果超过32bit则返回“ERROR”。
- 小数的二进制表示其实就是小数点后的bit乘以2^(-i)。因此直接先乘一个2上去看看是否超过1，决定bit。如果不能乘，那么直接和1/2, 1/4, 1/8这样一路比下去也可以。

String getBinary(double num) {
    if (num >= 1 || num <= 0) {
        return "ERROR";
    }
    StringBuilder binary = new StringBuilder();
    binary.append(".");
    while (num > 0) {
        if (binary.length() > 32) {
            return "ERROR";
        }
        double r = num * 2;
        if (r > 1) {
            binary.append('1');
            num = r - 1;
        } else {
            binary.append('0');
            num = r;
        }
    }
    return binary.toString();
}

Q: 给一个int，只能flip其中一个0变成1，求最长的连续1的长度。

也就是找到夹在两个连续1中间的0使得两边的1长度最长。维护一个prev和curr判断即可。

int flipBit(int a) {
    if (~a == 0) return Integer.BYTES * 8;   // 已经全是1了
    int curr = 0, prev = 0, maxLen = 1; // flip之后至少有一个1
    while (a != 0) {
        if ((a & 1) == 1) {
            curr++;
        } else {
            prev = (a & 2) == 0 ? 0 : curr;  // 看看下一位是否为0，连续的0就没法flip了
            curr = 0;
        }
        maxLen = Math.max(maxLen, curr + prev + 1);
        a >>>= 1;   // visual的右移
    }
    return maxLen;
}

Q: 给一个正数，返回最小的下一个数和最大的前一个数，这些数含有的1数量必须相同。
- 对于getNext，就是找到最靠右的非末尾的0，将它变为1后再把右侧的1先统计个数，然后清空后全部放到最右侧。对于getPrev也是类似，找到最靠右的非末尾的1，统计右侧的1后全置为0，然后紧接着拼到原最右侧1的后面。
- 还可以考虑arithmetic的做法，因为对于getNext其实就类似于10000 - 1 -> 01111的效果，因此就变成了先找011100，根据右侧0的个数加一个1 << 2变成100000，然后加上一个(1 << (3 - 1)) - 1 -> 000011，即n + (1 << count0) + (1 << (count1 - 1)) - 1. getPrev也是根据右侧0的个数和1的个数，返回n - (1 << c1) - (1 << (count0 - 1)) + 1。
Q: 请解释((n & (n - 1)) == 0)的目的。
- n和n - 1没有一个bit有相同的1分布，类似于1000 - 1 -> 0111，因此可以用来判断n是否是2的幂。

Q: 给两个int，判断他们之间需要flip多少个bit才能转换成对方。

也就是看异或之后有多少个1，除了老老实实地shift求有多少个1，还可以利用减1的trick加速求有多少个1。

int bitSwapCount(int a, int b) {
    int count = 0;
    for (int c = a ^ b; c != 0; c = c & (c - 1)) {  // 每次都可以直接将最右的1置0，比一个个shift快得多
        count++;
    }
    return count;
}

Q: 用尽可能少的instrction实现奇数位和偶数位的bit互换。
- 可以先用mask分别把奇数和偶数的部分提取出来，然后分别shift即可（right shift必须是logic的）:(((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1))
Q: 假设一个黑白屏幕的像素存储在byte数组中，即每8个bit的上色情况存在一个byte中。给定坐标(x1, y)和(x2, y)，实现画线的函数。
- 可以傻傻地一个bit一个bit地上色，但是更高效的做法是先找到可以完整上色的区间直接赋值0xFF，然后如果头尾还有一点残余，再创建前后两小段的mask。注意edge case，如果x1和x2都在一个byte里面，就不能这样头尾搞来搞去了，直接在区间内自己搞小mask或一蛤。

Math and Logic Puzzles

Object-Oriented Design

Recursion and Dynamic Programming

3 recursion approach

Bottom-up: Start with knowing how to solve the problem for a simple case, then build previous case upon it.
Top-down: Divide the problem for case N into subproblems(careful: overlap cases)
Half-and-half: divide the dataset into halves. like Binary search and merge sort.

Problems

Q: 爬楼梯，一次只能爬1、2、3级，求到第n级共有多少走法。
- 利用memo数组记录下从0～n的所有走法数量，每次从前面三个累加即可。注意这种连续加法要考虑overflow的情况，向面试官指出来。
Q: 走grid，每次只能向下走或这向右走，grid值为false的地方是障碍物，求一条从左上角到右下角的路径。
- 可以从终点往回递归，这样如果找到路径了就只需要在List末尾插入当前坐标即可。为了提升time，需要额外空间记录每个点是否访问过。

Q: 给一个排好序的dinstinct int数组，求其中一个magic index若存在的话. magic index指的是i s.t. A[i] == i

看到排好序就想到是否可以用二分查找？若i > A[i]，而且数组中元素各不相同，说明i之前不可能有magic index，因此可以直接往后找，非常类似二分查找的思想。

int getMagicIndex(int[] arr) {
    return getMagicIndex(arr, 0, arr.length - 1);
}
int getMaticIndex(int[] arr, int start, int end) {
    if (end < start) {
        return -1;
    }
    int mid = start + (end - start) / 2;
    if (arr[mid] == mid) {
        return mid;
    } else if (arr[mid] > mid) {
        return getMagicIndex(arr, start, mid - 1);
    } else {
        return getMagicIndex(arr, start + 1, end);
    }
}

Follow-up: 如果数组中含有重复元素，如何改进？还是沿用这个思路，区别在于当i > A[i]，不能把整个index < i都放弃，只能说明[A[i], i]这部分是不可能的，还需要保留[start, A[i]]的部分。

int getMagicIndex(int[] arr) {
    return getMagicIndex(arr, 0, arr.length - 1);
}
int getMaticIndex(int[] arr, int start, int end) {
    if (end < start) {
        return -1;
    }
    int midIndex = start + (end - start) / 2;
    int midValue = arr[midIndex];
    if (midValue == midIndex) {
        return midIndex;
    } 
    // 搜索左边剩余部分
    int leftEnd = Math.min(midIndex - 1, midValue);
    int left = getMagicIndex(arr, start, leftEnd);
    if (left >= 0) {
        return left;
    }
    int rightStart = Math.max(midIndex + 1, midValue);
    int right = getMagicIndex(arr, rightStart, end);
    return right;
}

Q: Power set, 求一个set（元素各不相同）的所有subset

经典递归，每一步直接考虑在前一个subset的基础上添加一个元素。

List<List<Integer>> getSubsets(List<Integer> set, int index) {
    List<List<Integer>> ans;
    if (set.size() == index) {
        ans = new ArrayList<>();
        ans.add(new ArrayList<>());
    } else {
        ans = getSubsets(set, index + 1);
        int curr = set.get(index);
        List<List<Integer>> moreSet = new ArrayList<>();
        for (List<Integer> subset : ans) {
            List<Integer> temp = new ArrayList<>();
            temp.addAll(subset);
            temp.add(curr);
            moreSet.add(temp);
        }
        ans.addAll(moreSet);
    }
    return ans;
}

还可以考虑用bit，每一个元素取/不取就用1/0来指代。

List<List<Integer>> getSubsets(List<Integer> set) {
    List<List<Integer>> ans = new ArrayList<>();
    int max = 1 << set.size();
    for (int i = 0; i < max; i++) {
        List<Integer> subset = int2Set(k, set);
        ans.add(subset);
    }
    return ans;
}
List<Integer> int2Set(int num, List<Integer> set) {
    List<Integer> subset = new ArrayList<>();
    int index = 0;
    for (int i = num; i > 0; i >>= 1) {
        if ((k & 1) == 1) {
            subset.add(set.get(index));
        }
        index++;
    }
    return subset;
}

Q: 只使用加、减、shifting实现两个正整数的乘法，要求operations尽量少。

对于一大一小x, y两个数，相当于把大数x加y次，这个y次又可以通过shift进行折半。如果y是偶数折半刚好，如果是奇数就需要递归完成后再加一个x。时间复杂度只需要O(log(smaller)).

int minProd(int a, int b) {
    int smaller = a < b ? a : b;
    int bigger = a < b ? b : a;
    return minProdHelper(smaller, bigger);
}
int minProdHelper(int times, int num) {
    if (times == 0) {
        return 0;
    } else if (times == 1) {
        return num;
    }
    int newTimes = times >> 1;
    int halfProd = minProdHelper(newTimes, num);
    if (times % 2 == 0) {
        return halfProd + halfProd;
    } else {
        return halfProd + halfProd + num;
    }
}

Q: 汉诺塔，一堆从小到大的碟子，有三个柱子分别为起始、中介、终点，要求将这些碟子全部移到终点。

这三个柱子的角色并不是固定的，因此考虑用递归来利用传参确定角色。

class Tower {
    private Stack<Integer> disks;
    private int index;  // getter...
    public Tower(int index) {
        disks = new StacK<>();
        this.index = index;
    }
    public void add(int disk) throws Exception {
        if (!disks.isEmpty() && disk >= disks.peek()) {
            throw new Exception();
        } else {
            disks.push(disk);
        }
    }
    public void moveTop(Tower target) {
        target.add(disks.pop());
    }
    public void moveDisks(int n, Tower target, Tower buffer) {
        if (n > 0) {
            moveDisks(n - 1, buffer, target);       // 将buffer作为终点，target作为buffer
            moveTop(target);
            buffer.moveDisks(n - 1, target, this);  // 将起点作为buffer，终点为target
        }
    }
}

Q: Permutation，重复和无重复元素
Q: 生成所有合法的括号对。