z*s
发帖数: 209 | 1 上个月中旬面的试，在Mountain View。由于之前在学校进行了校园面试（2*45分钟）
，所以这一次on site只有三个人，每个人还是45分钟；外加一个人带着吃午饭，没有
反馈。
一、二叉树中给定一个节点，查找按照中序遍历顺序它的后继节点，要求写代码，并给
出复杂度；二叉树中查找中序遍历顺序中的第k个节点，如果每个节点都添加了子树中
节点个数这个变量，如何在插入、删除和旋转时更新这个值（旋转是为了保证logn的复
杂度而要使二叉树保持平衡）。
二、C++概念题，包括虚函数、多继承、私有的构造、析构函数、重载的new运算符等；
以前的project问题；开放性问题，跟网络有关，包括了分组交换、拥塞控制、流控制
、多播等等知识点；最后问了一个编程题，跟quad tree有关，不太常见，但不是很难
，我觉得考查了函数的递归。
三、一道编程题，大意是给定一个类read1，它有一个函数read4096，每次调用它可以
从文件中读取4K个字节，同时移动文件指针4K个位置（若文件中剩余数据不足4K，则读
取剩下的所有数据），这个函数返回实际读取的字节数，int型；要求实现另一个类
read2中的一个函数read，它有一个参数int n_byte，这个函数可以从文件中读取由n_
byte指定的字节数，同样返回实际读取的字节数；然后又给出一个函数reset，它可以
将文件指针重置到起始位置，要求实现read2中的另一个函数seek，有一个参数int pos
，它可以将缓冲区的指针移动到第pos个字节的位置，返回实际指针移动到的位置。可
以在read2中添加任意变量来完成这两个函数。
这道题也不难，需要注意代码的一些细节，比如循环的终止条件、特殊的输入等。 |
g*********s
发帖数: 1782 | 2 从面试到拿offer要多久？
【在 z*s 的大作中提到】
: 上个月中旬面的试，在Mountain View。由于之前在学校进行了校园面试（2*45分钟）
: ，所以这一次on site只有三个人，每个人还是45分钟；外加一个人带着吃午饭，没有
: 反馈。
: 一、二叉树中给定一个节点，查找按照中序遍历顺序它的后继节点，要求写代码，并给
: 出复杂度；二叉树中查找中序遍历顺序中的第k个节点，如果每个节点都添加了子树中
: 节点个数这个变量，如何在插入、删除和旋转时更新这个值（旋转是为了保证logn的复
: 杂度而要使二叉树保持平衡）。
: 二、C++概念题，包括虚函数、多继承、私有的构造、析构函数、重载的new运算符等；
: 以前的project问题；开放性问题，跟网络有关，包括了分组交换、拥塞控制、流控制
: 、多播等等知识点；最后问了一个编程题，跟quad tree有关，不太常见，但不是很难
|
f*******4
发帖数: 1401 | 3 晕 google on-site问这么多知识题常见吗？C++的还好对付，
网络题基本没有准备呀...
【在 z*s 的大作中提到】
: 上个月中旬面的试，在Mountain View。由于之前在学校进行了校园面试（2*45分钟）
: ，所以这一次on site只有三个人，每个人还是45分钟；外加一个人带着吃午饭，没有
: 反馈。
: 一、二叉树中给定一个节点，查找按照中序遍历顺序它的后继节点，要求写代码，并给
: 出复杂度；二叉树中查找中序遍历顺序中的第k个节点，如果每个节点都添加了子树中
: 节点个数这个变量，如何在插入、删除和旋转时更新这个值（旋转是为了保证logn的复
: 杂度而要使二叉树保持平衡）。
: 二、C++概念题，包括虚函数、多继承、私有的构造、析构函数、重载的new运算符等；
: 以前的project问题；开放性问题，跟网络有关，包括了分组交换、拥塞控制、流控制
: 、多播等等知识点；最后问了一个编程题，跟quad tree有关，不太常见，但不是很难
|
g*********s
发帖数: 1782 | 4 it depends.
i know someone with industry experience was being asked about qa issues
for 45 mins, although he's applying for the sde position.
【在 f*******4 的大作中提到】
: 晕 google on-site问这么多知识题常见吗？C++的还好对付，
: 网络题基本没有准备呀...
|
d****2
发帖数: 6250 | 5
这个明显是跟哪个组有关，以及你的简历。
【在 f*******4 的大作中提到】
: 晕 google on-site问这么多知识题常见吗？C++的还好对付，
: 网络题基本没有准备呀...
|
n*******p
发帖数: 72 | 6 请问你面的是网络相关的吗？ 是SDE还是SDET？ 这么难啊？ |
f*******4
发帖数: 1401 | 7 第一个人的题，“二叉树中给定一个节点，查找按照中序遍历顺序它的后
继节点”，就是普通的中序遍历然后当找到了给定节点后开始打印么？
二叉树为何要旋转？如果不是BST的话每次插入删除都可以随便啊...
第三个人题，不理解啊，是要用read1类的那个方法来实现read2类的
所有方法么？
【在 z*s 的大作中提到】
: 上个月中旬面的试，在Mountain View。由于之前在学校进行了校园面试（2*45分钟）
: ，所以这一次on site只有三个人，每个人还是45分钟；外加一个人带着吃午饭，没有
: 反馈。
: 一、二叉树中给定一个节点，查找按照中序遍历顺序它的后继节点，要求写代码，并给
: 出复杂度；二叉树中查找中序遍历顺序中的第k个节点，如果每个节点都添加了子树中
: 节点个数这个变量，如何在插入、删除和旋转时更新这个值（旋转是为了保证logn的复
: 杂度而要使二叉树保持平衡）。
: 二、C++概念题，包括虚函数、多继承、私有的构造、析构函数、重载的new运算符等；
: 以前的project问题；开放性问题，跟网络有关，包括了分组交换、拥塞控制、流控制
: 、多播等等知识点；最后问了一个编程题，跟quad tree有关，不太常见，但不是很难
|
g*********s
发帖数: 1782 | 8
no, i think it's like: void print_all_succ(T_Node* node);
the node is not necessarily the root. it could be the second last node and
u will just output the last node.
balanced bst. i think lz has a tough question here. the rb tree
rebalancing algorithm is long and not easy to remember.
given read1 and reset, implement read2. this is a practical exercise.
【在 f*******4 的大作中提到】
: 第一个人的题，“二叉树中给定一个节点，查找按照中序遍历顺序它的后
: 继节点”，就是普通的中序遍历然后当找到了给定节点后开始打印么？
: 二叉树为何要旋转？如果不是BST的话每次插入删除都可以随便啊...
: 第三个人题，不理解啊，是要用read1类的那个方法来实现read2类的
: 所有方法么？
|
p*****a
发帖数: 147 | 9
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~这个怎么做？
【在 g*********s 的大作中提到】
:
: no, i think it's like: void print_all_succ(T_Node* node);
: the node is not necessarily the root. it could be the second last node and
: u will just output the last node.
: balanced bst. i think lz has a tough question here. the rb tree
: rebalancing algorithm is long and not easy to remember.
: given read1 and reset, implement read2. this is a practical exercise.
|
g*********s
发帖数: 1782 | 10 use a buffer with size 4k. use read4096 to fill out the buffer.
【在 p*****a 的大作中提到】
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~这个怎么做？
|
f*******4
发帖数: 1401 | 11 一：如果是这样的话，假设给你root的左孩子，如果没有parent指针，你怎么
可能回到root？因为root按照中序顺序是在他的左孩子后面
二：如果是self-balancing bst的话要写代码肯定很麻烦，但是LZ的意思应
该是描述一下就好，说rotate的一种情况就可以了吧
三：seek是先reset然后用read来前进么？
and
【在 g*********s 的大作中提到】
: use a buffer with size 4k. use read4096 to fill out the buffer.
|
l*****a
发帖数: 14598 | 12 maybe the hiring committee want to hire him as a SET...
【在 g*********s 的大作中提到】
: it depends.
: i know someone with industry experience was being asked about qa issues
: for 45 mins, although he's applying for the sde position.
|
z*s
发帖数: 209 | 13 我申请的职位是Software Engineer New Grad。
第一个人的寻找后继节点问题，可以使用parent指针；关于二叉树的旋转，只需要描述
一下过程就行了，不需要写代码。面试官当时只让我描述了一种旋转的情况（我只学过
AVL tree，一共有四种旋转的情况）。
关于网络方面的知识，我也很意外；我觉得开放性问题并没有标准答案，而且就我的能
力，当时只能想到一些网络方面的东西，所以就说了；面试官当时也没有提出反对的意
见。
第三个人的问题我是在read2类中定义了一个char buffer[]，表示缓冲区；同时定义两
个整型变量start和end，表示缓冲区中数据的起止位置；read函数每次先从缓冲区中读
取数据；若读完后还不够需要的字节数，再调用read4096，此时要先将读出的数据写入
这个自定义的缓冲区，在读取需要的字节数。 |
