i****7
发帖数: 26 | 1 电面1：
顺序统计树，找第K个节点。
电面2：
1）打印000到123所有的数，follow up，打印a到b所有的数（假设每一位都a<=b）
2）Next permutation
3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
Onsite:
1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
（国人大哥面的，可能会看到这个帖子，非常感谢，做题的时候给了很多引导。）
2）一个有向图，找出互相指向的点对数，（e.g. A指向B，B指向A，算一对）
Follow up， 写一个类，这个图会变化（加点，删点，加边，删边），维护这样的
点对数。
Follow up， 扯了扯大数据时候怎么分配到各个计算机上。
3）论文演讲
4）家族树，每个点左右指针指向自己的父亲和母亲，每个点存对应二叉堆的索引。
A）给一个这种树，给每个点标出对应二叉堆的索引值。
B）任意给一个节点（不需要输入根节点），输出这个点所在的层数。
C）任意给一个节点（不需要输入根节点），输出这个点和根节点的关系（e.g. 是
根节点父亲的母亲就输出“MF”）。
5）两道LC原题 1. Anagram 2. Reverse bit
直接给出最优解还不断让优化，优化涉及到系统设计。 |
l********r
发帖数: 7 | 2 第四题不太明白意思。
是说这个家族树自身是个二叉堆？ |
i****7
发帖数: 26 | 3 嗯，差不多，把二叉树看成二叉堆后，每个节点有个index，这个index存成节点的一个域
【在 l********r 的大作中提到】
: 第四题不太明白意思。
: 是说这个家族树自身是个二叉堆？
|
l********r
发帖数: 7 | 4 每一片可以刷两种颜色，相临三片不能同色这题，组合数学还是别的递推？
1.离散化+线段树（多个值域记次数，query走到底求和），构造O(n)，每次query O(
log n)
2.一个hashmap存所有边，一个邻接表存对数的边和数量。
删点O（n），其他O（1）
4.A）递归dfs，O（n） B和C）堆性质向上走，O(log n)
有啥猫腻么？ |
n******n
发帖数: 12088 | 5 电面一是用顺序统计树查询k因素？
【在 l********r 的大作中提到】
: 每一片可以刷两种颜色，相临三片不能同色这题，组合数学还是别的递推？
: 1.离散化+线段树（多个值域记次数，query走到底求和），构造O(n)，每次query O(
: log n)
: 2.一个hashmap存所有边，一个邻接表存对数的边和数量。
: 删点O（n），其他O（1）
: 4.A）递归dfs，O（n） B和C）堆性质向上走，O(log n)
: 有啥猫腻么？
|
c******n
发帖数: 4965 | 6 000 到 123 s是什么意思？
【在 i****7 的大作中提到】
: 电面1：
: 顺序统计树，找第K个节点。
: 电面2：
: 1）打印000到123所有的数，follow up，打印a到b所有的数（假设每一位都a<=b）
: 2）Next permutation
: 3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
: Onsite:
: 1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
: Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
: （国人大哥面的，可能会看到这个帖子，非常感谢，做题的时候给了很多引导。）
|
i****7
发帖数: 26 | 7 DP
【在 l********r 的大作中提到】
: 每一片可以刷两种颜色，相临三片不能同色这题，组合数学还是别的递推？
: 1.离散化+线段树（多个值域记次数，query走到底求和），构造O(n)，每次query O(
: log n)
: 2.一个hashmap存所有边，一个邻接表存对数的边和数量。
: 删点O（n），其他O（1）
: 4.A）递归dfs，O（n） B和C）堆性质向上走，O(log n)
: 有啥猫腻么？
|
i****7
发帖数: 26 | 8 输入：root和K
输出：inorder第K个node
【在 n******n 的大作中提到】
: 电面一是用顺序统计树查询k因素？
|
i****7
发帖数: 26 | 9 000
001
002
003
010
011
...
...
122
123
一般化是a到b所有数，
a,b的每一位是上界和下界，
不好意思，没说清楚，假设是a的每一位<=b的对应位
【在 c******n 的大作中提到】
: 000 到 123 s是什么意思？
|
x********u
发帖数: 1150 | |
|
|
b******i
发帖数: 914 | 11 Hi,
问一下，000到123这题，输入是string还是int呢？
哈有onsite 1）你是怎么做的？多谢啦！
【在 i****7 的大作中提到】
: 电面1：
: 顺序统计树，找第K个节点。
: 电面2：
: 1）打印000到123所有的数，follow up，打印a到b所有的数（假设每一位都a<=b）
: 2）Next permutation
: 3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
: Onsite:
: 1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
: Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
: （国人大哥面的，可能会看到这个帖子，非常感谢，做题的时候给了很多引导。）
|
i****7
发帖数: 26 | 12 000到123用的int
follow up用的string
onsite 1)
第一问，LC原题，sort, merge, query时候binary search
第二问，每个开始点标正，结束点标负，然后sort所有点，
query的时候binary search，算这个位置左边几个正，几个负（这个可以
preprocess）
（类似会议室问题）
【在 b******i 的大作中提到】
: Hi,
: 问一下，000到123这题，输入是string还是int呢？
: 哈有onsite 1）你是怎么做的？多谢啦！
|
c******n
发帖数: 4965 | 13 哦，那还是很好的题， 不算难 也有点意义。
recursive(int low[], int []high, int pos) {
if (pos == low.length) {
// print out answer or add answer to list
}
for(int candidate=low[pos];candidate<=high[pos];candidate++) {
answer[pos] = candidate;
recursive(low,high, pos+1);
}
}
【在 i****7 的大作中提到】
: 000
: 001
: 002
: 003
: 010
: 011
: ...
: ...
: 122
: 123
|
b******i
发帖数: 914 | 14 谢谢
onsite 1）我的大体思路和你差不多，除了的第二问，query的话我就想到从头开始++
--。不知道你binary search以后算这个位置左边几个正几个负怎么preprocess？
【在 i****7 的大作中提到】
: 000到123用的int
: follow up用的string
: onsite 1)
: 第一问，LC原题，sort, merge, query时候binary search
: 第二问，每个开始点标正，结束点标负，然后sort所有点，
: query的时候binary search，算这个位置左边几个正，几个负（这个可以
: preprocess）
: （类似会议室问题）
|
h****3
发帖数: 89 | |
n******n
发帖数: 12088 | 16 CLRS
【在 h****3 的大作中提到】
: 有人能具体指点一下电面一怎么写吗？
|
h****3
发帖数: 89 | 17 谢谢
原来是放在了augmenting data structure 里面。。
【在 n******n 的大作中提到】
: CLRS
|
s********l
发帖数: 998 | 18 >_<
电面第一题 是什么一丝啊？
顺序统计树，找第K个节点
【在 i****7 的大作中提到】
: 电面1：
: 顺序统计树，找第K个节点。
: 电面2：
: 1）打印000到123所有的数，follow up，打印a到b所有的数（假设每一位都a<=b）
: 2）Next permutation
: 3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
: Onsite:
: 1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
: Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
: （国人大哥面的，可能会看到这个帖子，非常感谢，做题的时候给了很多引导。）
|
h****3
发帖数: 89 | 19 算法导论的340 - 341 页，我也刚找到
【在 s********l 的大作中提到】
: >_<
: 电面第一题 是什么一丝啊？
: 顺序统计树，找第K个节点
|
i****7
发帖数: 26 | 20 preprocess就是sort以后走一遍，每个点左边几个正的，几个负的都记录一下。
如果没有preprocess，每次query都数一下，复杂度是O(n)
有了preprocess，每次query只有binary search，复杂度是O(logn)
+
【在 b******i 的大作中提到】
: 谢谢
: onsite 1）我的大体思路和你差不多，除了的第二问，query的话我就想到从头开始++
: --。不知道你binary search以后算这个位置左边几个正几个负怎么preprocess？
|
|
|
i****7
发帖数: 26 | 21 不用知道这个名字，面试的时候他给定义，
就是BST每个节点新加一个域，存的是从这个点开始的子树的节点个数。
我用的recursion, O(logn)，很简单，别想复杂了。
【在 s********l 的大作中提到】
: >_<
: 电面第一题 是什么一丝啊？
: 顺序统计树，找第K个节点
|
b*****d
发帖数: 39 | 22 楼主可以详细解释一下onsite的第二个问嘛？图的输入是什么？是1->2, 2->3这样的吗
？这个是怎么做++，--排序的呢？谢谢啦 |
i****7
发帖数: 26 | 23 图那题很随意，自己设计数据结构，我就怎么方便怎么来，
我用的C++，用的unordered_map>
【在 b*****d 的大作中提到】
: 楼主可以详细解释一下onsite的第二个问嘛？图的输入是什么？是1->2, 2->3这样的吗
: ？这个是怎么做++，--排序的呢？谢谢啦
|
l*k
发帖数: 10 | 24 栅栏这个，是 2F(n) 吗？ F(n)是第n个斐波那契数。
【在 i****7 的大作中提到】
: 电面1：
: 顺序统计树，找第K个节点。
: 电面2：
: 1）打印000到123所有的数，follow up，打印a到b所有的数（假设每一位都a<=b）
: 2）Next permutation
: 3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
: Onsite:
: 1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
: Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
: （国人大哥面的，可能会看到这个帖子，非常感谢，做题的时候给了很多引导。）
|
y******e
发帖数: 203 | |
s********l
发帖数: 998 | 26 hmm...
我怎么觉得 不用在每个节点加个value啊~
设一个counter
用stack in order traverse 然后update 这个count不就行了~
【在 i****7 的大作中提到】
: 不用知道这个名字，面试的时候他给定义，
: 就是BST每个节点新加一个域，存的是从这个点开始的子树的节点个数。
: 我用的recursion, O(logn)，很简单，别想复杂了。
|
s********l
发帖数: 998 | 27 onsite 1)
是lc的那道题啊？ 不记得呢。。。 |
s********l
发帖数: 998 | 28 电面2：
3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
这个题 有没有一共多少种颜色的限制？
【在 i****7 的大作中提到】
: 电面1：
: 顺序统计树，找第K个节点。
: 电面2：
: 1）打印000到123所有的数，follow up，打印a到b所有的数（假设每一位都a<=b）
: 2）Next permutation
: 3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
: Onsite:
: 1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
: Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
: （国人大哥面的，可能会看到这个帖子，非常感谢，做题的时候给了很多引导。）
|
i****7
发帖数: 26 | 29 好像有点像，不太记得了，反正就是分成最后两片一样和最后两片不一样，
然后递推就很明朗了。
【在 l*k 的大作中提到】
: 栅栏这个，是 2F(n) 吗？ F(n)是第n个斐波那契数。
|
i****7
发帖数: 26 | 30 每个点加的域是他给的条件，
用上条件复杂度是O(logn)
不用条件复杂度是O(n)
当然用了
【在 s********l 的大作中提到】
: hmm...
: 我怎么觉得 不用在每个节点加个value啊~
: 设一个counter
: 用stack in order traverse 然后update 这个count不就行了~
|
|
|
i****7
发帖数: 26 | 31 LC merge interval那道题再加上binary search的扩展
【在 s********l 的大作中提到】
: onsite 1)
: 是lc的那道题啊？ 不记得呢。。。
|
i****7
发帖数: 26 | 32 总共就两颜色，e.g. red and blue
【在 s********l 的大作中提到】
: 电面2：
: 3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
: 这个题 有没有一共多少种颜色的限制？
|
n******n
发帖数: 12088 | 33 复杂度不一样吧
【在 s********l 的大作中提到】
: hmm...
: 我怎么觉得 不用在每个节点加个value啊~
: 设一个counter
: 用stack in order traverse 然后update 这个count不就行了~
|
j******6
发帖数: 2 | 34 题目不难，可是要在10分钟里完成思路和实现呀。 |
q******6
发帖数: 4 | |
A*******e
发帖数: 2419 | 36 1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
follow-up包含了第一问吧？
先给区间每个端点排序，再从左向右扫描？如果是左端点计数加1，右端点计数-1，每
个端点记录当前的计数值，重复端点叠加。
然后二分查询找最后一个小于等于查询值的端点，计数值就是有几个interval包含它。
【在 i****7 的大作中提到】
: 电面1：
: 顺序统计树，找第K个节点。
: 电面2：
: 1）打印000到123所有的数，follow up，打印a到b所有的数（假设每一位都a<=b）
: 2）Next permutation
: 3）栅栏N个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。
: Onsite:
: 1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
: Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
: （国人大哥面的，可能会看到这个帖子，非常感谢，做题的时候给了很多引导。）
|
A*******e
发帖数: 2419 | 37 2）一个有向图，找出互相指向的点对数，（e.g. A指向B，B指向A，算一对）
Follow up， 写一个类，这个图会变化（加点，删点，加边，删边），维护这样的
点对数。
Follow up， 扯了扯大数据时候怎么分配到各个计算机上。
有向社交图，类似微博找互相关注。
每个节点维护一个关注对象，数组、链表、BST，或散列。
对节点A遍历对象，看对象节点是否指向自己。
加点时不会加边把？这样计数不变。
删点时先查有多少互相关注，减去。
加减边时看情况加减1或不变。
有向社交图分布存储问题。能想到的几点：
1. 互相关注的对象尽量放在一台机器上？互相关注会形成完全图，但完全图太大时还
是得分开。
2. 受关注多的名人分开放，或有镜像，免得一台宕机，多数用户受影响。
还有啥？
【在 A*******e 的大作中提到】
: 1）一堆interval，有叠加，给一个值，查询在不在这堆interval里（会调用很多次）
: Follow up， 给一个值，查询多少个interval包含这个值（会调用很多次）
: follow-up包含了第一问吧？
: 先给区间每个端点排序，再从左向右扫描？如果是左端点计数加1，右端点计数-1，每
: 个端点记录当前的计数值，重复端点叠加。
: 然后二分查询找最后一个小于等于查询值的端点，计数值就是有几个interval包含它。
|
A*******e
发帖数: 2419 | 38 4）家族树，每个点左右指针指向自己的父亲和母亲，每个点存对应二叉堆的索引。
A）给一个这种树，给每个点标出对应二叉堆的索引值。
B）任意给一个节点（不需要输入根节点），输出这个点所在的层数。
C）任意给一个节点（不需要输入根节点），输出这个点和根节点的关系（e.g. 是
根节点父亲的母亲就输出“MF”）。
// 编码从0开始。
void SetParent(Node* root) {
if (root == nullptr) return;
root->id = 0;
SetParentHelper(root);
}
void SetParentHelper(Node* root) {
if (root->father != nullptr) {
root->father = root->id * 2 + 1;
SetParentHelper(root->father);
}
if (root->mother != nullptr) {
root->mother = root->id * 2 + 2;
SetParentHelper(root->mother);
}
}
int GetLevel(Node* node) {
assert(node != nullptr);
int level = 0;
int id = node->id + 1;
while ((id /= 2) > 0) {
++level;
}
return level;
}
string GetParentChain(Node* node) {
assert(node != nullptr);
string chain;
int id = node->id + 1;
int d = id / 2;
int m = id % 2;
while (d > 0) {
chain.push_back(m == 0 ? 'F' : 'M');
d /= 2;
m = d % 2;
}
}
【在 A*******e 的大作中提到】
: 2）一个有向图，找出互相指向的点对数，（e.g. A指向B，B指向A，算一对）
: Follow up， 写一个类，这个图会变化（加点，删点，加边，删边），维护这样的
: 点对数。
: Follow up， 扯了扯大数据时候怎么分配到各个计算机上。
: 有向社交图，类似微博找互相关注。
: 每个节点维护一个关注对象，数组、链表、BST，或散列。
: 对节点A遍历对象，看对象节点是否指向自己。
: 加点时不会加边把？这样计数不变。
: 删点时先查有多少互相关注，减去。
: 加减边时看情况加减1或不变。
|
