[2017/08/03] Facebook电面面经

brn 发表于 2017-8-4 09:57
第二题怎么dp 不就是个裸dfs吗

DFS当然是可以的，你用一个SET去过滤重复的值。但是因为你在计算过程中会产生重复，所以时间上并不是最佳的。

chris612ku 发表于 2017-8-4 10:21
楼主
想请问一下第一题也要自己build一个tree跑test case吗？

面试官会给你一个例子，你就照着他给的例子手动跑一边你的程序。

这个质数组题，结果的个数是 (2^n)  - 1吧,就是所有集合数去掉空集，因为是质数 a*b != c*d, 所以子集元素乘积各不相同。

Flatten Binary Tree To Linked List变形。LC原题是前序遍历，返回的是原来的数据结构，现在返回的是中序遍历，用Doubled Linked List有什么特殊意义吗？

shurui91 发表于 2017-8-4 10:05
同问 第二题如何DP

这个是我的做法，对于每一个新的数，我们将它和每一个之前所产生的结果相乘，然后也放到结果数组里，再是把这个数本身也放到数组里，为了之后的计算。

vector<int> product(vector<int> input) {
    vector<int> result;
    for(int element : input) {
        int curr_size = result.size();
        for(int pos = 0; pos < curr_size; pos++) { result.push(element * result[pos]); }
        result.push_back(element);
    }
    return result;
}

xuepanchen 发表于 2017-8-5 03:53
这个是我的做法，对于每一个新的数，我们将它和每一个之前所产生的结果相乘，然后也放到结果数组里，再是 ...

谢谢！祝楼主拿到onsite

daguanyuan 发表于 2017-8-5 03:42
没有重复的prime，直接再怎么互相组合乘机，也不会有完全相同的因子吧，且又是最小的因子，所以不可再分解 ...

我所谓的重复是指在DFS的计算过程中会产生重复的结果，需要用一个SET去过滤掉重复的中间结果。可以参考下水道那层的做法。

edyyy 发表于 2017-8-5 03:48
这个质数组题，结果的个数是 (2^n)  - 1吧,就是所有集合数去掉空集，因为是质数 a*b != c*d, 所以子集元素 ...

对的，一共是(2^N) - 1个答案，所以我说复杂度是O(2^N)。

edyyy 发表于 2017-8-5 03:50
Flatten Binary Tree To Linked List变形。LC原题是前序遍历，返回的是原来的数据结构，现在返回的是中序 ...

我也不知道有什么特殊意思，估计就是为了不出原题吧，做法都是一样的。

找到一個視頻 可是是circular double linkedlist
https://www.youtube.com/watch?v=Dte6EF1nHNo