Chapter 52 Linkedin 2016 11

52.1 384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result.
// Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

https://leetcode.com/problems/shuffle-an-array/

因为这题要求保留原始数组,所以S必须是O(N),因此naive和渔夫都可以用.

渔夫洗牌算法Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are given a function rand() that generates random number in \(O(1)\) time.

渔夫洗牌的两种形式,wikipedia说得很详细:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

C++实现1:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

C++实现2:

http://www.geeksforgeeks.org/shuffle-a-given-array/

一般采用第一种方法.

OJ: http://code.geeksforgeeks.org/09ulgx

概率证明(*)

  1. Naive Method

1->1: \(\frac{1}{n}\)

2->1: \(\frac{n-1}{n} \frac{1}{n-1} = \frac{1}{n}\)

…

Probability of ith element goes to jth cell is \(\frac{1}{n}\).

  1. 渔夫洗牌

The probability that ith element (including the last one) goes to last position is 1/n, because we randomly pick an element in first iteration.

The probability that ith element goes to second last position can be proved to be 1/n by dividing it in two cases.

Case 1: \(i = n-1\) (index of last element):

The probability of last element going to second last position is = (probability that last element doesn’t stay at its original position) x (probability that the index picked in previous step is picked again so that the last element is swapped) So the probability = \(\frac{n-1}{n} \frac{1}{n-1} = \frac{1}{n}\)

Case 2: \(0 < i < n-1\) (index of non-last):

The probability of ith element going to second last position = (probability that ith element is not picked in previous iteration) x (probability that ith element is picked in this iteration) So the probability = \(\frac{n-1}{n} \frac{1}{n-1} = \frac{1}{n}\)

We can easily generalize above proof for any other position. 所以ith element最后被放去任意格的概率都是\(1/n\).

52.2 235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree

http://www.cnblogs.com/yrbbest/p/5003610.html

52.4 254. Factor Combinations

http://leetcode.com/problems/factor-combinations/

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

http://segmentfault.com/a/1190000005801106

http://www.jianshu.com/p/9a883428cebb

不错的分析: http://www.cnblogs.com/grandyang/p/5332722.html

写出所有的因子相乘的形式,而且规定了因子从小到大的顺序排列.

  • Algo 1 - cherry pick at leaf node

可以用DFS traverse in the following divisor tree. 因为factor(divisor) are listed in non-descending order, child node must be greater than parent node. 如下图所示,叶节点为绿色代表一条通路.我们会遇到一些无效的路径,比如图中2->8之后就走不下去了,因为下一个可能的节点是2,但是2比8小.

DFS traverse until the leaf node is 1, then we do cherry pick.

  • Algo 2 - cherry pick at every child node
    最优的解法是利用这个特殊的factor tree. Tree node has two parts: divisor and quotient. We use quotient to find child node, divisor is the starting point of next level’s divisor:

Loop i in [initial value of divisor,sqrt(dividend)] to find dividend%i==0, which is the next child.

和subset那道题一样,cherry pick at every child node,而不是仅仅在leaf node.所以速度比上面的解法快几十倍.

还要注意这里p不在是以前的partial solution,其实是累积的所有divisor. t其实才是partial solution,t最后加上了quotient然后cherry pick到r里面. 在stackframe之间传递的是cumuliative divisors,不是partial solution,或者说是一种特殊的partial solution. 这是不同于以往的case的地方.After all, there are two parts in one node in our factor tree.

  • Algo 3
    上面两种方法得到的结果跟题目中给的答案的顺序不同,虽然顺序不同,但是并不影响其通过OJ.我们下面就给出生成题目中的顺序的解法,这种方法也不难理解,还是从2遍历到n的平方根,如果i是因子,那么我们递归调用n/i,结果用v来保存,然后我们新建一个包含i和n/i两个因子的序列out,然后将其存入结果r, 然后我们再遍历之前递归n/i的所得到的序列,如果i小于等于某个序列的第一个数字,那么我们将其插入该序列的首位置,然后将序列存入结果r中,我们举个例子,比n = 12,那么刚开始i = 2,是因子,然后对6调用递归,得到{2, 3},然后此时将{2, 6}先存入结果中,然后发现i(此时为2)小于等于{2, 3}中的第一个数字2,那么将2插入首位置得到{2, 2, 3}加入结果,然后此时i变成3,还是因子,对4调用递归,得到{2, 2},此时先把{3, 4}存入结果,然后发现i(此时为3)大于{2, 2}中的第一个数字2,不做任何处理直接返回,这样我们就得到正确的结果了:

复杂度: Loop次数, 递归次数, push to vector次数

52.5 170. Two Sum III - Data structure design

https://leetcode.com/problems/two-sum-iii-data-structure-design/

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure. find - Find if there exists any pair of numbers which sum is equal to the value.

add(1); add(3); add(5);
find(4) -> true
find(7) -> false

1. Add多find少

Two Sum的時候是用hashtable實時的查找.這道題也是用hashtable查找,但是不一樣的地方是hashtable預先建好的.

所以單純的hashtable是不夠的,比如這個Edge case: [1] 查找2應該是false

應該用一個counter,如果有這種edge case的情況,查看count是否大於1.

ONE COUNTER ( unordered_map )

2. Add少find多

TWO SETs - edge case是重复数字.

52.6 187. Repeated DNA Sequences

Here

52.8 Shortest Word Distance Series

https://segmentfault.com/a/1190000003906667

    1. Shortest Word Distance

https://leetcode.com/problems/shortest-word-distance/

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example, Assume that words = [“practice”, “makes”, “perfect”, “coding”, “makes”].

Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = “makes”, word2 = “coding”, return 1.

  • Algo 1 - 数据结构: index map
    笨办法 T:\(O(N^2)\), S:\(O(N)\)
  • Algo 2
    其实不需要index map
    T:\(O(N)\), S:\(O(1)\):
    1. Shortest Word Distance II

https://leetcode.com/problems/shortest-word-distance-ii/

数据结构: index map 算法: Two pointer

我感觉其实可以把结果cache起来.这样shortest可以做到\(O(1)\). 不过这样很耗空间.n个单词有\(n*(n-1)/2\)个pair.

    1. Shortest Word Distance III

https://leetcode.com/problems/shortest-word-distance-iii/

沿用II的思路:

沿用I的思路:

https://discuss.leetcode.com/topic/20887/12-16-lines-java-c

Follow up:

  • minimum window substring

三个单词的距离就是最小的window含有三个给定的单词.

比如下面是一个句子,三个单词是a,b,c, 最短的距离应该是4.

a k b d [a c g b] e f a  d  s  f  [b c  g  a]
0 1 2 3  4 5 6 7  8 9 10 11 12 13 14 15 16 17

这个是minimum substring window的简化版本 array

map<string,int> + two pointers即可搞定.

m[a]=0,4,10,17
m[b]=2,7,14
m[c]=5,15

就用minimum substring window sliding window的做法.

https://repl.it/FHG1

52.9 Maximum product of a triplet

Input:  [10, 3, 5, 6, 20]
Output: 1200
Input:  [-10, -3, -5, -6, -20]
Output: -90
Input:  [1, -4, 3, -6, 7, 0]
Output: 168

如图红正绿负.通过观察找规律,可以看出MaxProductOfThree一定是等于: max(max1*max2*max, min1*min2*max1).

时间复杂度: \(O(N)\), 空间复杂度: \(O(1)\)

http://www.geeksforgeeks.org/find-maximum-product-of-a-triplet-in-array/

这道题牵扯到在一个无序数列中找最大的前三和最小的前二,如果要求最小的比较数目,可以用tournament tree. Please refer to: linkedin-2017-01.html#tournament-tree

52.10 Median/Max/Min Stack

对midstack来说, popMedian()可以做到\(O(1)\). 如果是maxstack, minstack, popMin/Max和普通的pop()不可能同时做到\(O(1)\).

例如push 1,3,6,5,4. 返回6.返回index的中值. 双链表做,maintain一个pointer指向中间

follow up是写popMid()函数

Solution: http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/.

如果不要求popMedian常数时间,可以用vector实现. 如果popMedian要O(1),必须要linked list.

自己实现了一个返回Lower Median的midstack. 注意:

  1. Change mid pointer in two cases: 1) Linked List is empty 2) Number of nodes in linked list is odd

  2. stack为空的时候peekmedian返回一个特殊值,popmedian不做任何操作.

这个是纯手工的非STL版本: Design a stack with operations on middle element: http://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/

https://www.glassdoor.com/Interview/How-do-you-find-the-middle-of-a-stack-at-O-1-QTN_1096333.htm

https://www.glassdoor.com/Interview/Coding-Create-a-stack-with-the-usual-push-and-amp-pop-but-with-an-additional-function-getMiddle-that-returns-the-midd-QTN_1179717.htm

52.10.1 MaxStack

http://wxx5433.github.io/max-stack.html

import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class MaxStack<T> {

    LinkedList<T> stack;
    PriorityQueue<T> maxHeap;

    public MaxStack() {
        stack = new LinkedList<T>();
        maxHeap = new PriorityQueue<T>(10, Collections.reverseOrder());  // reverse order
    }

    public void push(T n) {
        stack.addLast(n);
        maxHeap.offer(n);
    }

    public T pop() {
        T num = stack.removeLast();
        maxHeap.remove(num);
        return num;
    }

    public T top() {
        return stack.peekLast();
    }

    public T peekMax() {
        return maxHeap.peek();
    }

    public T popMax() {
        T num = maxHeap.poll();
        stack.remove(num);
        return num;
    }

    public static void main(String[] args) {
        MaxStack<Integer> stack = new MaxStack<Integer>();
        int[] arr = {3, 1, 2, 4, 6, 5};
        for (Integer n: arr) {
            stack.push(n);
        }
        System.out.println(stack.popMax());  // 6
        System.out.println(stack.popMax());  // 5
        System.out.println(stack.popMax());  // 4
        System.out.println(stack.pop());     // 2
        System.out.println(stack.popMax());  // 3
    }
}

Complexity:

push, pop, top: \(O(logn)\)

peekMax: \(O(1)\)

popMax: \(O(logN)\) - 原来网页的复杂度是错误的!

普通的pop其实他没有问,但是我也写了一个给他.后来他说他见过的最clean的办法是用一个 包含index和max的数据结构 来做,但是没细说…反正我这轮过了,估计只要说出两个堆一起用差不多就行了
http://www.1point3acres.com/bbs/forum.php?mod=redirect&goto=findpost&ptid=106359&pid=1472407&fromuid=91137

假设数据value没有重复,可以用下面的数据结构:

list<int> stk;
list<list<int>::iterator> max_itr;
map<int,list<list<int>::iterator>::iterator> val2itr;

map to list<list<int>::iterator>::iterator is better to map to list<int>::iterator here!!! Why? list erase and remove difference!!

push()复杂度是\(O(N)\),pop()和popmax()的复杂度都是\(O(1)\).

https://github.com/shadowwalker2718/data_structure_algorithm/blob/6449fcfa8fbb8d0763bb18a0bb5704f1ab652331/leetcode_c/maxstack.h#L22

52.11 366. Find Leaves of Binary Tree

followup讨论graph的情况就是topological sort!

https://leetcode.com/problems/find-leaves-of-binary-tree/

52.12 Design Google Calendar

52.13 160. Intersection of Two Linked Lists

无环:

https://leetcode.com/problems/intersection-of-two-linked-lists/

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   \
                     c1 → c2 → c3
                   /
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

This takes \(O(M+N)\) time and \(O(1)\) space, where M and N are the total length of the linked lists. Maybe inefficient if the common part is very long (i.e. M,N >> m,n)

  1. Traverse the two linked list to find M and N.

  2. Get back to the heads, then traverse |M − N| nodes on the longer list.

  3. Now walk in lock step and compare the nodes until you found the common ones.

看到另外一种解法One pass更快,但是太tricky,不推荐,而且如果没有交叉,那么会陷入死循环.作为参考请看:http://www.jianshu.com/p/6b38199dac15

http://bookshadow.com/weblog/2014/12/04/leetcode-intersection-two-linked-lists/

  1. 无环不相交 2. 无环相交. 3. 有环不相交. 4. 有环相交

Leetcode的题目没有考虑Cyclic Linked List 3,4两种情况.

自己画的,双圆圈表示交点.一种交在环上,一种交在尾巴上.

个人总结,要明白以下几点:

  1. 无环链表和有环链表是不可能相交的;

  2. 两个有环链表若相交,其“整个环上”的所有node一定都重合;

  3. 有环链表的相交,情况只有2种:相交于“环上”或相交于“不是环的部分”,即下图所示;两种情况都需要使用“两个指针的追逐”方法来判断两个链表的环部分是否相交; 带环单向链表相交只有2种情况

  4. 有关链表追逐的考虑: 相对速度、距离、时间要算好,否则很容易漏掉几种边界情况;

  • 用快慢指针判断是否有采用Floyd's Tortoise and hare(Floyd龟兔赛跑)算法

参考: linked-list, 不过那道题我们返回bool,这里返回的是Node*.

https://leetcode.com/problems/linked-list-cycle-i
https://leetcode.com/problems/linked-list-cycle-ii

比leetcode还要generic的版本.应该用手写出来:

http://pfmiles.github.io/blog/algorithms-in-job-interview-test-if-two-linked-lists-intersected/

https://charleshm.gitbooks.io/leetcode/content/lian_biao_cheng_huan.html

https://my.oschina.net/acidsweet1990/blog/260852

上面只是判断了有环是否相交,那么如果相交,有环的情况下如何找交点呢?

对于有环在环上相交的情况,其实两个交点都是交点.
对于有环在尾巴上相交的情况,随便在环上找一个点,然后和无环相交的情况相同的算法可解.

52.14 50. Pow(x, n)

https://leetcode.com/problems/powx-n/

http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/

52.14.1 递归(Recusive)

Method: Divide and Conquer + Memorization + Recursive

用recursive把负数的问题变为正数,用DC把问题解决,用memorization实现复杂度优化\(O(LogN)\)

T: \(O(LogN)\) S: \(O(LogN)\)

52.14.2 Iterative

T: \(O(LogN)\) S: \(O(1)\)

The recursive solutions are generally not preferred as they require space on call stack and they involve function call overhead.

这种做法如何理解呢?加入 n = 13,13在二进制中表示为:00001101,那么\(13 = 2^3 + 2^2 + 2^0\)

比如输入是myPow(2.0, 13):

p     y      m
p*=(2.0)   , m = 13
   (2.0)^2 , m = 6
p*=(2.0)^4 , m = 3
p*=(2.0)^8 , m = 1
-          , m = 0

方法是:
m每次减半,m是偶数的时候y翻倍(square),m是奇数的时候,把y的值计入最终结果p*=y.

Another Explanation: http://stackoverflow.com/questions/25571377/iterative-implementation-of-powx-n

52.15 Hangman Game

Check: system-design

52.16 K Closest Points(KNN)

找N个点里面离origin最近的K个点.计算几何里面的经典问题.K-d Tree的典型应用. 下面是点point的定义:

很多种算法可解这个题,下面列举4种:

52.16.1 1. Priority Queue

构造函数API: http://en.cppreference.com/w/cpp/container/priority_queue/priority_queue

  • minheap

minheap是对所有N个点创建一个heap,然后pop出K-1个点,剩下的PQ的top即为答案.复杂度是T:\(O(N+KLogN)\), S: \(O(N)\)

注意 how to write priority_queue with a custom comparator.

注意推荐在constructor构建PQ,可以做到\(O(N)\). 不要通过插入的方式构建PQ,那样是\(O(NlogN)\).(见CLRS P166)

  • maxheap

maxheap是建立一个大小为K的maxheap,root是heap中的最大值,然后继续拿剩余的点(比如叫做点p)和root比较,如果比root大就continue继续下一个,如果比root小就弹出root,插入p.复杂度是T:\(O(K+(N-K)LogK)\), S:\(O(K)\)

  • which one is better

这里把N,K都看成变量,所以在复杂度公式中不能省去.

minheap和maxheap到底哪一个在实际中更快呢? 其实就是比较\(O(N+KLogN)\)和\(O(K+(N-K)LogK)\). \(log(x)\)是在这两个复杂度公式里面起主导作用的函数,如果N很大,那个用\(LogN\)那个肯定更快; 如果K很大,那么LogK那个肯定更快(推到极限如果N==K,肯定maxheap快).

我们可以做一个简单的运算来印证一下(因为复杂度里面的log是不看base的,所以2为底还是e为底没关系):

All in all,如果K相对N较小,第一种方法minheap其实更好; 如果K比较大,那么第二种方法maxheap更好.

52.16.2 2. QuickSelect

Another approach (instead of Minimum Heaps) is to use the median of medians select to find the k-th closest point to the origin and then iterate through the entire array and print k points which are closer/as close as the k-th closest point (to avoid missing some points in case there are several points as close as the k-th point, we might need two passes on the points array).

If we are allowed to change the original points array then this solution is O(n) run-time complexity and O(1) space complexity. If not then the space complexity is O(n).

n_element直接解题,注意函数的signature.

Selection Algorithm: 平均 \(O(N)\), 最差 \(O(N^2)\). 根据:http://en.cppreference.com/w/cpp/algorithm/nth_element, n_element的平均复杂度明确是\(O(N)\),但是最差是\(O(N^2)\).

STL n_element source code:

想让最差是\(O(N)\)的话需要用median of median算法: https://interviewalgorithm.wordpress.com/sortingordering/median-of-medians-algorithm/

One can assure linear performance even in the worst case by using a more sophisticated pivot strategy; this is done in the median of medians algorithm. However, the overhead of computing the pivot is high, and thus this is generally not used in practice. One can combine basic quickselect with median of medians as fallback to get both fast average case performance and linear worst-case performance; this is done in introselect.

http://en.wikipedia.org/wiki/Quickselect

52.16.3 3. Kd Tree

Kd树的典型应用之一就是Nearest neighbour search(参见:https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search).

If we have a set of points and a lot of queries , where start point , K change, maybe it is better to use Kd tree for 2d. With Kd tree time complexity is \(KLog(N)\) for query and \(NLog(N)\) for building the tree.Space complexity \(O(N)\).With Kd tree we don’t need even to calculate euclidean distance

Finding the nearest point is an O(log n) operation in the case of randomly distributed points, although analysis in general is tricky. However an algorithm has been given that claims guaranteed O(log n) complexity.[9]

52.16.4 4. RTree

//TODO

http://www.sai.msu.su/~megera/postgres/talks/pgcon-2010-1.pdf

现实应用:

  1. Scikit:

http://scikit-learn.org/stable/modules/neighbors.html#k-d-tree

  1. Alglib

http://www.alglib.net/other/nearestneighbors.php

  1. PostGIS

http://workshops.boundlessgeo.com/postgis-intro/knn.html

“KNN” stands for “K nearest neighbours”, where “K” is the number of neighbours you are looking for.

KNN is a pure index based nearest neighbour search. By walking up and down the index, the search can find the nearest candidate geometries without using any magical search radius numbers, so the technique is suitable and high performance even for very large tables with highly variable data densities.

The KNN system works by evaluating distances between bounding boxes inside the PostGIS R-Tree index.

参考:

https://shepherdyuan.wordpress.com/2014/07/23/linkedin-k-closest-points/

https://saravananthirumuruganathan.wordpress.com/2010/05/17/a-detailed-introduction-to-k-nearest-neighbor-knn-algorithm/

http://www.zrzahid.com/k-closest-points/

https://www.careercup.com/question?id=4751976126480384

相关的leetcode题目是这一道:

52.17 450. Delete Node in a BST

https://leetcode.com/problems/delete-node-in-a-bst/

There could be multiple ways to solve. Why OJ only check one possibility? e.g., 2,1,3 tree, delete 2, I can have 1,null,3 or 3,1. Both solutions are valid.

因为要delete,在find这个node的过程中要保留一个parent的变量

被删除的node有三种情况:没孩子(leaf),一个孩子,两个孩子(最麻烦)

分析:假设当前node 为root

  1. if value < root.val, 要被删除的节点在左子树,往左子树递归,并把操作结束后的返回值作为新的root.left

  2. if value > root.val, 要被删除的节点在右子树,往右子树递归, 并把操作结束后的返回值作为新的root.right

  3. if root == null, 递归到了一个null点,说明要删的value不存在,return null,而这个null点的parent的相应子树本来也是null,对树的结构没有任何影响

  4. if value == root.val,说明root是该被删除的了

　　A. if root.left == null, return root.right

　　B. if root.right == null, return root.left(这两个case其实包含了只有一个child和一个child都没有的三种情况)

　　C. 如果两个children都存在,从右子树中找最小的node,与root交换,再递归调用函数在右子树中删除root.val

http://algorithms.tutorialhorizon.com/binary-search-tree-complete-implementation/

http://www.1point3acres.com/bbs/thread-212481-1-1.html

52.18 Lazy caterer’s sequence and Cake number

https://en.wikipedia.org/wiki/Lazy_caterer's_sequence

Check this animation

在切第n刀的时候 最多能和之前的n-1刀相交 这个多出来的1刀多制造出了n块pizza.So就是dp[1] = 1, dp[n] = dp[n - 1] + n, 公式应该是 \(\frac{n(n + 1)}{2} + 1\).

52.19 78. Subsets I II

https://leetcode.com/problems/subsets/

https://leetcode.com/problems/subsets-ii/

主要是聊算法复杂度上的东西,要不要排序,排序的好处坏处是什么.

52.20 464. Can I Win (if I go first)

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

https://leetcode.com/problems/can-i-win/

http://blog.csdn.net/mebiuw/article/details/53266731

重要条件:

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

每个人开始前都不能选前面已经用过的数字!

分析:

The solution is quite strightforward. First off we have to eliminate primitive cases. So,

  1. if the first player can choose a number, which is already greater than or equal to the desired total obviously it wins.

  2. If max choosable integer is less than the desired total, but if it exceeds the desired total in sum with any other number then the first player loses anyway.

  3. If the sum of all number in the pool cannot exceed or reach the desired total, then no one can win.

Now, for the other cases we can use MiniMax logic to reveal the winner. Because both player play optimally, In order to win, the first player has to make a choice, that leaves the second player no chance to win. Thus, at each step we consider all the possible choices by the current player and give turn to the second player recursively. If we find a move, after which the second player loses anyway or we have already exceed the desired total by adding the chosen number, we return true, i.e the current player wins. This way the game looks like the following tree:

     player1 ->  0
              /| ...\
  player2 -> 1 2 ....max 
            /|\ ..../ | \
player1 -> 2 3...  1  2 ..max-1
           ...                \
player1 ->   /      |     \    lose
player2 -> lose    win    lose

The figure above helps to imagine how the algorithm considers all possible scenarios of the game. The leafs of the game tree are lose or win states for one of the players. Finally the logic concludes to the idea, that if some branch does not contain any leaf that ends with win state for player2, the move associated with that branch is the optimal one for the first player.

P.S: Time complexity of naive implementation will work for \(O(N!)\). Therefore we have to memorize branch states after traversing once.

例子:

(5,12) is true! 注意这里是采用最优策略走会赢,如果乱走还是会输. 如下图:

如果红先绿后,红如果第一次选5,是必然输的. The guaranteed win actually comes when Player 1 chooses 3 first:

3-1-2 {4,5} left for p2 to choose. Either way player 1 wins
3-2-1- {4,5} left for p2 to choose. Either way player 1 wins
3-4-5. P1 wins
3-5-4. P1 wins

代码:

二刷:

优化:

因为maxChoosableInteger will not be larger than 20,状态数量不会超过1M(\(2^{20}\)),所以unordered_map<int,bool>可以被优化为vector,int可以直接用vector index来表示.状态映射的值有三种情况: 0-unvisited, 1-win, 2-lose.

reference: https://discuss.leetcode.com/topic/68896/java-solution-using-hashmap-with-detailed-explanation/11

复杂度:

因为DP每个状态都要检查一下,得到一个状态最多循环N次,所以是\(O(N*2^N)\), N = maxChoosableInteger.

Time complexity of naive implementation is \(O(N!)\).

How to prove \(N! > N*2^N\):

\[ N!=1*2*3*4*5*6...*N \\ N*2^N=2*2*2*2*2*2...2*N \]

52.21 297. Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

follow up是如何序列化和反序列化Graph,如果有环怎么办.

52.22 449. Serialize and Deserialize BST

https://leetcode.com/problems/serialize-and-deserialize-bst/

上周面的LinkedIn,今天HR 打电话过来说我面得还行,但是是border line, 他们 hiring committee讨论了很长时间最终决定把我拒了,心情很难受,听到" unfortunately"的那一刻眼泪流出来.

把面试过程写出来,请过来人帮我看看.HR 说我主要是System Design 和coding 面的 不完美.其实题目都不难,面经和leetcode 上的题

System Design:LinkedIn有个share功能,在里面会出现一些URL,问题是找出在过去 一天,一小时,五分钟被share的top 5/10/…多的URL.

这个面的感觉有点窝囊,感觉再让我面一次一定说的更好,我是按照july那个帖子来说 的,先把这些url 的id hash一下 (总共1 million url 所以可以存到一张表里),然后 用kafka (Producer and Consumer),隔一段时间(这样可以减少IO)根据hash 结果 存到不同机器上做aggregation, 为了节省计算量,可以每一分钟一张表存frequency ,然后把这些表加起来用priority queue排序就行了(这是5分钟的情况), 还可以提到 中间可以缓存加cache, 还提到了consistency hashing,感觉关键点都说出来了(也许 不对?).可是面试官明明都点头的啊.

总体有点乱,我刚开始还只是一个high level solution呢,但我每提一个step面试官 就打断我问细节,有种被人不停push 加捣乱的感觉,加上白板有点小,画的有点乱, 自己阵脚也乱了.

Coding 1 : isomorphic string; serialize and deserialize Binary Tree

Coding 2:Sqrt(double x, double e), e为一个小数允许误差范围; Find leaves

除了sqrt我都是一次写出完美代码的, sqrt我之前只准备了integer的那个版本,现场 临时想double 还要小数范围废了点时间,主要用在clarification 上,刚开始 misunderstanding以为他要精确到0.01了,另外我还忘了\(0<x<1\)的情况,后来经提示才 补充上去.另外isomophic string 的follow up, 要讨论一组数的情况,开始没领会面 试官的意思,废了点时间communication.

其实都是小中面试官,估计年龄都没有我大,只有一个小印shadow, 面试前一天刚看到 hr给我发的邮件上除了hosting Mgr都是中国人的时候还挺高兴,心想至少不会被烙印 阴了,好好面就行.

Lz在别的州工作好几年,现在这个公司干的不开心,另外也为了到加州来可以让一家人 生活在一起,结束目前一家三口在三个地方生活的悲惨日子…其实linkedin是个很 好的公司, 至少口碑很好,我也是用心准备的.Lz时间有限,平时下班回家就刷题, 差不多刷了两遍,断了所有的社交,最近几个月工作也没有努力因为把所有空闲时间加 上一部分上班时间都 用来刷题了.因为在外州,面试需要请假,没有申请很多公司,目前面的都是hr在 linkedin上直接联系我的那种. 现在的状况是几个月前fail掉亚麻(那时候才刚刚开 始,coding和behavior都没有面好,fail掉不奇怪);9月 Ms家两轮电面后没有下文; GF这样的公司还没有敢去申请,.马上就要感恩节圣诞节了,好心塞 http://www.mitbbs.com/article_t/JobHunting/33246829.html

http://massivealgorithms.blogspot.com/2015/12/linkedin-interview-misc-2.html

52.24 Isomorphic String

https://leetcode.com/problems/isomorphic-strings/

有点像找对象,男女双方都不能找两个,必须严格一对一. 两个map搞定.

仔细想想发现第二个map可以改为用一个bitset代替,如果是新男,而对应的是旧女,就return false.

数学上这叫bijection. 由于问题的对称性,可以男女分别检查一遍.这样写:

follow up是给一堆string, 按组输出isomorphic strings, 输出格式是List<List>.小哥可能比较忙,中途离开了两次…

https://www.jiuzhang.com/qa/2521/

2016-11-01 张助教 想法是对的. 但是你这个程序是可以优化的,匹配的这个部分,你是用map做的,在数据量非常大的情况下可以考虑用字典树来处理.

52.25 Paint House + Biased Random Generator + KMeans

52.25.1 Paint House

Check: dynamic-programming

如果找最小开销就用DP就可以了.如果要找最优路径.需要把路径记录下来.

52.25.2 Biased Random Generator

参见: /math-probability.html#biased-random-generator

52.27 Union and Intersection of two Linked Lists

http://www.1point3acres.com/bbs/thread-214086-1-1.html

如果list是unsorted的,需要一个hashtable.O(M+N).不然O(M*N).

参考:http://www.geeksforgeeks.org/union-and-intersection-of-two-linked-lists/

If both lists are unsorted. T: \(O(M*N)\)

If both lists are sorted. T: \(O(min(M,N))\)

Alog1:

Algo2: