b*****n
发帖数: 618 | 1 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcode原题，我说了binary search的解法，不过面试官只要求我写了O(m+n)的，被
批评code写的不够clean，还有一个bug，翻来覆去改了很久，终于在时间到之前改到他
满意的结果，又问了几个概念和编程习惯问题
2. very large array，can not fit into memory，怎么求median，不需要写code，说
想法就行
貌似是CLRS的median selection解法？divide and conquer，我现场没给出答案
2. 给出n对括号的所有有效排列，150CC原题，就不赘述了，现场run了几个test case
3. reverse binary number， leetcode原题，写了两种方法，被问了bit opeartion的
一些概念
4. 一个size n的array，求所有k sliding window最小值的最大值，
我给了用deque的解法，O(n). 被很仔细的分析了code，run了几个test case，然后被
问有其他做法吗
我说可以用heap来做，然后又问我用treeset怎么做，时间复杂度的区别
5. 一个deque，但是只支持pushBack，pushFront，popBack， 没有popFront
给一个1-N的排列，问能否把1-N按照从小到大的顺序push到deque，pop的时机可以任选
，使得pop出的顺序刚好是给定的排列
比如： 给定 23145， 那么对12345对应的操作序列是pushBack，pushBack，popBack，
pushBack，popBack，popBack，pushBack，popBack，pushBack，popBack
要求如果可能，输出任意一个可能的操作序列，如果没有可能的操作序列，输出
impossible
这道题现场没做出来，只给了一个observation
6. size n的array，求前k个最小的数，假设array可以fit to memory，解法越多越好
我给了quickselect和heap的做法，要分析时间复杂度，貌似面试官对quickselect很感
兴趣问了很多问题，但是最后没让我写，反而让我写了一个O(n)的heapify。。。
7. 一个sorted array，现在插入一个数，求插入的数的index
leetcode原题，binary search，开始写了个recursive的，后被要求改成iterative，
又很仔细的run了几个test base
8. 一个multithread题，记不太清楚了，感觉我回答的挺烂的，被问了monitor，
condition variable，semaphore，synchronized的概念
9. LRU实现，大家应该都很熟悉了，HashMap ＋ LinkedList
onsite感觉并不好，但是第二天hr联系我说feedback还不错，要我提供reference，
reference提供了之后又被要求加一轮电面
1. binary tree的postorder traversal iterative
要求实现三个method：
firstElement（Node root）返回以root为根的binary tree的第一个postorder
traverse Node
nextElement（Node current）返回current的下一个postorder traverse Node
POT（Node root）要call前两个method完成对整个binary tree的traverse
我问了Node存不存parent的reference，得到肯定答覆就开始写
面试官很仔细，会对code进行分析
2. 一大堆record，每个record由几个word组成，假设每个record还有unique的ID，
现在要进行query， query也是由几个word组成，query的结果是要求返回所有符合要求
的record的ID：
如果record的word是query的word的subset，那么record就符合要求
这个题我没给出最优解，跟面试官讨论了很久，面试官很nice，会一步一步的提示，不
需要写代码
给我的感觉是他家很在意code的质量，bug－free和clean很重要，解题的思路需要说的
很清楚。
希望对有兴趣的同学有所帮助，祝大家都能拿到心仪的offer。 |
b***e
发帖数: 1419 | 2 第五题答案应该是不能。根据题意，一共用2*n个操作，每个操作有三种可能性，也就
是说最多有9^n种输出，远小于n!. |
b*****n
发帖数: 618 | 3 可能我没说清楚
N和排列是事先给好的
比如N＝5时，
给定排列如果是23415，那么输出一种操作序列就行
如果是53412，那么应该输出impossible，因为没有符合的操作序列
【在 b***e 的大作中提到】
: 第五题答案应该是不能。根据题意，一共用2*n个操作，每个操作有三种可能性，也就
: 是说最多有9^n种输出，远小于n!.
|
n**m
发帖数: 122 | |
w********p
发帖数: 948 | 5 Treeset provides guaranteed log(n) time cost for the basic operations base
on Red-black tree.
是考红黑树吗？ 那些rotate我还真不知道。
整体觉得好难哦。
4. 一个size n的array，求所有k sliding window最小值的最大值，
我给了用deque的解法，O(n). 被很仔细的分析了code，run了几个test case，然后被
问有其他做法吗
我说可以用heap来做，然后又问我用treeset怎么做，时间复杂度的区别
【在 b*****n 的大作中提到】
: 姑且称为RF吧
: 申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
: online code test，onsite和一次电面。
: 好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
: 一样，
: 第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
: 细看，还有详细的提示也要注意。
: 我遇到的题：
: 1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
: 或者改变激光方向（4个方向）
|
b*****n
发帖数: 618 | 6 呃。。。
不是考TreeSet的实现，只是问一下怎么用而已，估计是考察一下知不知道Java有这个
东西，你想的太复杂了
我忘了说他们家只用Java，有些面试官会要求只能用Java写，刚好我不会C++。。。
【在 w********p 的大作中提到】
: Treeset provides guaranteed log(n) time cost for the basic operations base
: on Red-black tree.
: 是考红黑树吗？ 那些rotate我还真不知道。
: 整体觉得好难哦。
: 4. 一个size n的array，求所有k sliding window最小值的最大值，
: 我给了用deque的解法，O(n). 被很仔细的分析了code，run了几个test case，然后被
: 问有其他做法吗
: 我说可以用heap来做，然后又问我用treeset怎么做，时间复杂度的区别
|
w********p
发帖数: 948 | 7 谢谢。 我最近的面试也出现这样的问题。
题目往难里想， 结果答案简单的想撞豆腐。
【在 b*****n 的大作中提到】
: 呃。。。
: 不是考TreeSet的实现，只是问一下怎么用而已，估计是考察一下知不知道Java有这个
: 东西，你想的太复杂了
: 我忘了说他们家只用Java，有些面试官会要求只能用Java写，刚好我不会C++。。。
|
w******j
发帖数: 185 | |
n*******w
发帖数: 687 | 9 第五题应该是scramble string
push front 只要scramble一次就变成push back了。可以变成顺序push back。
pop back顺序同样可以scramble成逆序。所以只要是逆序54321的所有scramble string
应该都可以。 |
b*****n
发帖数: 618 | 10 这个少考虑了pop的情况吧
试着举个反例
53421是54321的scramble string，但是没有合法的操作
string
【在 n*******w 的大作中提到】
: 第五题应该是scramble string
: push front 只要scramble一次就变成push back了。可以变成顺序push back。
: pop back顺序同样可以scramble成逆序。所以只要是逆序54321的所有scramble string
: 应该都可以。
|
|
|
x***y
发帖数: 633 | 11 Congradulations!
2. For the tracer problem, does that require coding? The idea should be
simple. Sort by the start the time first, and scan them in the reverse order
while inserting the value into a sorted strucutre. (But what structure to
use to guarantee the logn insertion time, red-black tree, avl tree (a little
tricky to code)
5. One Observation is that if number A is poped out, and then later number B
is poped out, if A>B, then all the values between A and B that are still in
the queue should be poped out in the order, right? Also, those values should
come after the in-queue values smaller than B.
like 5 and 2 are popped out, the only possibe order for remaining numbers is
1, 3, 4.
Is there any other observation? Thanks. |
j********x
发帖数: 2330 | |
l***m
发帖数: 16 | 13 5.
//return operations, empty if impossible
vector getOps(string seq) {
int last = -1, pushCount = 0, N = (int)seq.length();
vector v(2*N, "");
for (int i = 0; i < N; ++i) {
int index = seq[i] - '0';
++last;
if (index > pushCount) {
if (pushCount + 1 <= index - 1) {
int head = i + 1, tail = N - 1;
for (int j = index - 1; j >= pushCount + 1; --j) {
int pos = last + j - pushCount - 1;
while (head < N && seq[head] - '0' > index)
++head;
while (tail >= 0 && seq[tail] - '0' > index)
--tail;
if (head == N || tail < 0) {
v.clear();
return v;
}
if (seq[head] - '0' == j) {
v[pos] = "pushBack";
++head;
}
else if (seq[tail] - '0' == j) {
v[pos] = "pushFront";
--tail;
}
else {
v.clear();
return v;
}
}
}
last += index - pushCount;
pushCount = index;
v[last - 1] = "pushBack";
}
v[last] = "POPBACK";
}
return v;
}
【在 b*****n 的大作中提到】
: 姑且称为RF吧
: 申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
: online code test，onsite和一次电面。
: 好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
: 一样，
: 第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
: 细看，还有详细的提示也要注意。
: 我遇到的题：
: 1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
: 或者改变激光方向（4个方向）
|
b*****n
发帖数: 618 | 14 姑且称为RF吧
申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
online code test，onsite和一次电面。
好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
一样，
第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
细看，还有详细的提示也要注意。
我遇到的题：
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
2. 一堆racer，每个racer有出发时间和到达时间，计算每个racer的score，规则如下
：score ＝ 所有出发比自己晚但是到达比自己早的racer数量之和，（所有的出发时间
和到达时间没有重复的）要求时间复杂度
code test过了之后我直接就安排onsite了，onsite本来安排6个人但实际上只面了5个
，题目如下：
1. 两个不一样长度的sorted array，求median。
leetcode原题，我说了binary search的解法，不过面试官只要求我写了O(m+n)的，被
批评code写的不够clean，还有一个bug，翻来覆去改了很久，终于在时间到之前改到他
满意的结果，又问了几个概念和编程习惯问题
2. very large array，can not fit into memory，怎么求median，不需要写code，说
想法就行
貌似是CLRS的median selection解法？divide and conquer，我现场没给出答案
2. 给出n对括号的所有有效排列，150CC原题，就不赘述了，现场run了几个test case
3. reverse binary number， leetcode原题，写了两种方法，被问了bit opeartion的
一些概念
4. 一个size n的array，求所有k sliding window最小值的最大值，
我给了用deque的解法，O(n). 被很仔细的分析了code，run了几个test case，然后被
问有其他做法吗
我说可以用heap来做，然后又问我用treeset怎么做，时间复杂度的区别
5. 一个deque，但是只支持pushBack，pushFront，popBack， 没有popFront
给一个1-N的排列，问能否把1-N按照从小到大的顺序push到deque，pop的时机可以任选
，使得pop出的顺序刚好是给定的排列
比如： 给定 23145， 那么对12345对应的操作序列是pushBack，pushBack，popBack，
pushBack，popBack，popBack，pushBack，popBack，pushBack，popBack
要求如果可能，输出任意一个可能的操作序列，如果没有可能的操作序列，输出
impossible
这道题现场没做出来，只给了一个observation
6. size n的array，求前k个最小的数，假设array可以fit to memory，解法越多越好
我给了quickselect和heap的做法，要分析时间复杂度，貌似面试官对quickselect很感
兴趣问了很多问题，但是最后没让我写，反而让我写了一个O(n)的heapify。。。
7. 一个sorted array，现在插入一个数，求插入的数的index
leetcode原题，binary search，开始写了个recursive的，后被要求改成iterative，
又很仔细的run了几个test base
8. 一个multithread题，记不太清楚了，感觉我回答的挺烂的，被问了monitor，
condition variable，semaphore，synchronized的概念
9. LRU实现，大家应该都很熟悉了，HashMap ＋ LinkedList
onsite感觉并不好，但是第二天hr联系我说feedback还不错，要我提供reference，
reference提供了之后又被要求加一轮电面
1. binary tree的postorder traversal iterative
要求实现三个method：
firstElement（Node root）返回以root为根的binary tree的第一个postorder
traverse Node
nextElement（Node current）返回current的下一个postorder traverse Node
POT（Node root）要call前两个method完成对整个binary tree的traverse
我问了Node存不存parent的reference，得到肯定答覆就开始写
面试官很仔细，会对code进行分析
2. 一大堆record，每个record由几个word组成，假设每个record还有unique的ID，
现在要进行query， query也是由几个word组成，query的结果是要求返回所有符合要求
的record的ID：
如果record的word是query的word的subset，那么record就符合要求
这个题我没给出最优解，跟面试官讨论了很久，面试官很nice，会一步一步的提示，不
需要写代码
给我的感觉是他家很在意code的质量，bug－free和clean很重要，解题的思路需要说的
很清楚。
希望对有兴趣的同学有所帮助，祝大家都能拿到心仪的offer。 |
b***e
发帖数: 1419 | 15 第五题答案应该是不能。根据题意，一共用2*n个操作，每个操作有三种可能性，也就
是说最多有9^n种输出，远小于n!. |
b*****n
发帖数: 618 | 16 可能我没说清楚
N和排列是事先给好的
比如N＝5时，
给定排列如果是23415，那么输出一种操作序列就行
如果是53412，那么应该输出impossible，因为没有符合的操作序列
【在 b***e 的大作中提到】
: 第五题答案应该是不能。根据题意，一共用2*n个操作，每个操作有三种可能性，也就
: 是说最多有9^n种输出，远小于n!.
|
n**m
发帖数: 122 | |
w********p
发帖数: 948 | 18 Treeset provides guaranteed log(n) time cost for the basic operations base
on Red-black tree.
是考红黑树吗？ 那些rotate我还真不知道。
整体觉得好难哦。
4. 一个size n的array，求所有k sliding window最小值的最大值，
我给了用deque的解法，O(n). 被很仔细的分析了code，run了几个test case，然后被
问有其他做法吗
我说可以用heap来做，然后又问我用treeset怎么做，时间复杂度的区别
【在 b*****n 的大作中提到】
: 姑且称为RF吧
: 申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
: online code test，onsite和一次电面。
: 好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
: 一样，
: 第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
: 细看，还有详细的提示也要注意。
: 我遇到的题：
: 1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
: 或者改变激光方向（4个方向）
|
b*****n
发帖数: 618 | 19 呃。。。
不是考TreeSet的实现，只是问一下怎么用而已，估计是考察一下知不知道Java有这个
东西，你想的太复杂了
我忘了说他们家只用Java，有些面试官会要求只能用Java写，刚好我不会C++。。。
【在 w********p 的大作中提到】
: Treeset provides guaranteed log(n) time cost for the basic operations base
: on Red-black tree.
: 是考红黑树吗？ 那些rotate我还真不知道。
: 整体觉得好难哦。
: 4. 一个size n的array，求所有k sliding window最小值的最大值，
: 我给了用deque的解法，O(n). 被很仔细的分析了code，run了几个test case，然后被
: 问有其他做法吗
: 我说可以用heap来做，然后又问我用treeset怎么做，时间复杂度的区别
|
w********p
发帖数: 948 | 20 谢谢。 我最近的面试也出现这样的问题。
题目往难里想， 结果答案简单的想撞豆腐。
【在 b*****n 的大作中提到】
: 呃。。。
: 不是考TreeSet的实现，只是问一下怎么用而已，估计是考察一下知不知道Java有这个
: 东西，你想的太复杂了
: 我忘了说他们家只用Java，有些面试官会要求只能用Java写，刚好我不会C++。。。
|
|
|
w******j
发帖数: 185 | |
n*******w
发帖数: 687 | 22 第五题应该是scramble string
push front 只要scramble一次就变成push back了。可以变成顺序push back。
pop back顺序同样可以scramble成逆序。所以只要是逆序54321的所有scramble string
应该都可以。 |
b*****n
发帖数: 618 | 23 这个少考虑了pop的情况吧
试着举个反例
53421是54321的scramble string，但是没有合法的操作
string
【在 n*******w 的大作中提到】
: 第五题应该是scramble string
: push front 只要scramble一次就变成push back了。可以变成顺序push back。
: pop back顺序同样可以scramble成逆序。所以只要是逆序54321的所有scramble string
: 应该都可以。
|
x***y
发帖数: 633 | 24 Congradulations!
2. For the tracer problem, does that require coding? The idea should be
simple. Sort by the start the time first, and scan them in the reverse order
while inserting the value into a sorted strucutre. (But what structure to
use to guarantee the logn insertion time, red-black tree, avl tree (a little
tricky to code)
5. One Observation is that if number A is poped out, and then later number B
is poped out, if A>B, then all the values between A and B that are still in
the queue should be poped out in the order, right? Also, those values should
come after the in-queue values smaller than B.
like 5 and 2 are popped out, the only possibe order for remaining numbers is
1, 3, 4.
Is there any other observation? Thanks. |
j********x
发帖数: 2330 | |
l***m
发帖数: 16 | 26 5.
//return operations, empty if impossible
vector getOps(string seq) {
int last = -1, pushCount = 0, N = (int)seq.length();
vector v(2*N, "");
for (int i = 0; i < N; ++i) {
int index = seq[i] - '0';
++last;
if (index > pushCount) {
if (pushCount + 1 <= index - 1) {
int head = i + 1, tail = N - 1;
for (int j = index - 1; j >= pushCount + 1; --j) {
int pos = last + j - pushCount - 1;
while (head < N && seq[head] - '0' > index)
++head;
while (tail >= 0 && seq[tail] - '0' > index)
--tail;
if (head == N || tail < 0) {
v.clear();
return v;
}
if (seq[head] - '0' == j) {
v[pos] = "pushBack";
++head;
}
else if (seq[tail] - '0' == j) {
v[pos] = "pushFront";
--tail;
}
else {
v.clear();
return v;
}
}
}
last += index - pushCount;
pushCount = index;
v[last - 1] = "pushBack";
}
v[last] = "POPBACK";
}
return v;
}
【在 b*****n 的大作中提到】
: 姑且称为RF吧
: 申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
: online code test，onsite和一次电面。
: 好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
: 一样，
: 第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
: 细看，还有详细的提示也要注意。
: 我遇到的题：
: 1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
: 或者改变激光方向（4个方向）
|
c******e
发帖数: 26 | 27 可不可以把第一个题目说的更清楚些啊，谢谢！
1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
或者改变激光方向（4个方向）
问激光射出矩阵之前一共经过了多少格子，如果死循环了就输出－1
这是把所有的情况找出来了么？
【在 b*****n 的大作中提到】
: 姑且称为RF吧
: 申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
: online code test，onsite和一次电面。
: 好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
: 一样，
: 第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
: 细看，还有详细的提示也要注意。
: 我遇到的题：
: 1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
: 或者改变激光方向（4个方向）
|
A*********c
发帖数: 430 | 28 这么详细，赞！
【在 b*****n 的大作中提到】
: 姑且称为RF吧
: 申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
: online code test，onsite和一次电面。
: 好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
: 一样，
: 第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
: 细看，还有详细的提示也要注意。
: 我遇到的题：
: 1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
: 或者改变激光方向（4个方向）
|
r******g
发帖数: 138 | |
c**y
发帖数: 9 | 30 多谢楼主哈！
刚刚拿到他家实习offer，在犹豫要不要接；求问full time package如何啊？ |
|
|
l*****n
发帖数: 246 | |
c*******r
发帖数: 870 | 32 RF 是那家公司，FLG中的 F 么？
【在 b*****n 的大作中提到】
: 姑且称为RF吧
: 申请的是fresh grad职位，2月底第一次跟hr联系到这个周拿到offer，中间经历了
: online code test，onsite和一次电面。
: 好像不少人对他家的code test比较感兴趣，4个小时两道题，每个人遇到的题目可能不
: 一样，
: 第一题很简单，主要考察code质量，第二题稍微难一点，每个题目的要求都很详细要仔
: 细看，还有详细的提示也要注意。
: 我遇到的题：
: 1. 一个矩阵，从指定格子向右发射激光，每个格子有以下几种可能：激光直接穿过，
: 或者改变激光方向（4个方向）
|
A******3
发帖数: 5 | |
b*****n
发帖数: 618 | |
