Note for Cracking the Coding Interview

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: 生成所有合法的括号对。