logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
T家电面一般有几轮？ [UPDATE面经]
avatar
T家电面一般有几轮？ [UPDATE面经]# JobHunting - 待字闺中
c*t
1 楼
两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
让再约一次电面。
不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
【UPDATE面经】
就两道题，在sharing doc上实现:
1)实现一个min-heap，并用其找无序数组里的top k;
2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
能自定义node。
avatar
w*x
2 楼
求题
avatar
f*t
3 楼
T家你投了多久收到联系和电面的？

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
avatar
w*x
4 楼

一般第三面都是后来加的吧

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
avatar
T*s
5 楼
这么难的题啊
avatar
c*t
6 楼
俺自知修行不够，没敢投。是他家一个HR给我发邮件约的面试，看样子是在狂招人……

【在 f******t 的大作中提到】
: T家你投了多久收到联系和电面的？
avatar
c*t
7 楼
没有很难，就让实现堆排序之类的算法，另外会不断push到最优解再让实现，电话里感
觉很焦灼啊……

【在 T*********s 的大作中提到】
: 这么难的题啊
avatar
f*t
8 楼
这样啊...我是new grad, 投了一个月了，没有消息。 期间有个HR问我啥时候毕业，我
答明年，再follow up就告诉我数月之内会有HR跟我联系，他们先要处理之前毕业的人
。我了个去...

【在 c******t 的大作中提到】
: 俺自知修行不够，没敢投。是他家一个HR给我发邮件约的面试，看样子是在狂招人……
avatar
w*x
9 楼

靠, 实现堆排序还不难....

【在 c******t 的大作中提到】
: 没有很难，就让实现堆排序之类的算法，另外会不断push到最优解再让实现，电话里感
: 觉很焦灼啊……
avatar
c*t
10 楼
因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
码，手很抖啊……

【在 w****x 的大作中提到】
:
: 靠, 实现堆排序还不难....
avatar
l*a
11 楼
heap sort太冷门了。
把思路写成code有难度啊。

【在 c******t 的大作中提到】
: 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
: 码，手很抖啊……
avatar
p*2
12 楼
这也会考呀。从来没练过
avatar
d*x
13 楼
priority queque都用的吧
再说那个heapify的复杂度多impressive啊。

【在 l*****a 的大作中提到】
: heap sort太冷门了。
: 把思路写成code有难度啊。
avatar
w*x
14 楼

我觉得这题不需要实现heapify, 只用实现push,pop和top就可以了, heapify也不难做,
主要记得先实现一个siftdown函数

【在 d**********x 的大作中提到】
: priority queque都用的吧
: 再说那个heapify的复杂度多impressive啊。
avatar
d*x
15 楼
其实即使是从头写一个heap，总共也就30+行代码。
我电面t的时候，他们让我从头写一个open addressing的hash map.

做,

【在 w****x 的大作中提到】
:
: 我觉得这题不需要实现heapify, 只用实现push,pop和top就可以了, heapify也不难做,
: 主要记得先实现一个siftdown函数
avatar
d*x
16 楼
我面了两轮，你这个应该是加的一轮。
好运。

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
avatar
w*x
17 楼
随手写了一个,没测
class CMinHeap
{
public:
int GetSize() { return m_vec.size(); }
bool empty() { return m_vec.empty(); }
int top() { return m_vec[0]; }
void pop()
{
swap(m_vec[0], m_vec[m_vec.size()-1]);
m_vec.pop_back();
int nCur = 0;
while (2*nCur+1 < m_vec.size())
{
int nSwap = 2*nCur+1;
if (2*nCur+2 < m_vec.size() && m_vec[2*nCur+2] < m_vec[2*nCur+1])
nSwap = 2*nCur+2;

if (m_vec[nCur] <= m_vec[nSwap])
break;
swap(m_vec[nCur], m_vec[nSwap]);
nCur = nSwap;
}
}
void push(int x)
{
m_vec.push_back(x);
int nCur = m_vec.size()-1;
while (nCur != 0)
{
int nParent = (nCur-1)/2;
if (m_vec[nParent] <= m_vec[nCur])
break;
swap(m_vec[nParent], m_vec[nCur]);
nCur = nParent;
}
}
private:
vector m_vec;
};
void GetTopK(int a[], int n, int k, vector& vecRes)
{
if (NULL == a || n <= 0 || k <= 0 || k > n)
return;
CMinHeap mhp;
for (int i = 0; i < n; i++)
{
if (mhp.size() < k)
mhp.push(a[i]);
else
{
if (a[i] > mhp.top())
{
mhp.pop();
mhp.push(a[i]);
}
}
}
while (!mhp.empty())
{
vecRes.push_back(mhp.top());
mhp.pop();
}
}
avatar
w*x
18 楼

open address的hash很难写啊

【在 d**********x 的大作中提到】
: 其实即使是从头写一个heap，总共也就30+行代码。
: 我电面t的时候，他们让我从头写一个open addressing的hash map.
:
: 做,
avatar
d*x
19 楼
恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧

【在 w****x 的大作中提到】
:
: open address的hash很难写啊
avatar
l*a
20 楼
C++大牛啊

【在 w****x 的大作中提到】
: 随手写了一个,没测
: class CMinHeap
: {
: public:
: int GetSize() { return m_vec.size(); }
: bool empty() { return m_vec.empty(); }
: int top() { return m_vec[0]; }
: void pop()
: {
: swap(m_vec[0], m_vec[m_vec.size()-1]);
avatar
w*x
21 楼

不是吧, 要你写多少操作啊, 一个open address的hash table, 要写constructor,
destructor, insert, delete 还TM要写rehash?? 听都没听说个rehash, 谁给写个?

【在 d**********x 的大作中提到】
: 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
: 不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
avatar
l*a
22 楼
find你得写吧？

【在 w****x 的大作中提到】
:
: 不是吧, 要你写多少操作啊, 一个open address的hash table, 要写constructor,
: destructor, insert, delete 还TM要写rehash?? 听都没听说个rehash, 谁给写个?
avatar
w*x
23 楼

对啊, 顶多写个insert, delete和find

【在 l*****a 的大作中提到】
: find你得写吧？
avatar
d*x
24 楼
所有操作。。。
还好hashCode()是假设有的。。。

【在 w****x 的大作中提到】
:
: 对啊, 顶多写个insert, delete和find
avatar
d*x
25 楼
insert过程可能要触发rehash啊。

【在 w****x 的大作中提到】
:
: 对啊, 顶多写个insert, delete和find
avatar
w*x
26 楼

求onsite面经

【在 d**********x 的大作中提到】
: 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
: 不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
avatar
l*a
27 楼
还没看过你的呢

【在 w****x 的大作中提到】
:
: 求onsite面经
avatar
w*x
28 楼

Java的范畴啊, hashCode, reharsh 啥的搞c++的都没听说过啊

【在 d**********x 的大作中提到】
: 所有操作。。。
: 还好hashCode()是假设有的。。。
avatar
w*x
29 楼

等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
insert函数插进去....

【在 w****x 的大作中提到】
:
: Java的范畴啊, hashCode, reharsh 啥的搞c++的都没听说过啊
avatar
i*c
30 楼
T是哪家啊？

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
avatar
d*x
31 楼
我想想。。
通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
友之类
有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
一时没说明白的是如何序列化一个C++ style的tree
还有一个问题是如何快速给出任何两个人的粉丝交集。
反正，挂了。。

【在 w****x 的大作中提到】
:
: 等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
: insert函数插进去....
avatar
d*x
32 楼
对的
但是这里面有些状态需要update，不小心就会犯错误。。

【在 w****x 的大作中提到】
:
: 等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
: insert函数插进去....
avatar
w*x
33 楼

水木清华的那个帖子是你发的?

【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
avatar
d*x
34 楼
恩那。

【在 w****x 的大作中提到】
:
: 水木清华的那个帖子是你发的?
avatar
w*x
35 楼

不明白, 不就把原来的数插进新数组里去吗, 有什么要特别注意的吗

【在 d**********x 的大作中提到】
: 对的
: 但是这里面有些状态需要update，不小心就会犯错误。。
avatar
w*x
36 楼

靠,世界真小

【在 d**********x 的大作中提到】
: 恩那。
avatar
d*x
37 楼
几个参数需要update吧。。。当时好像少赋了两个值。。。

【在 w****x 的大作中提到】
:
: 靠,世界真小
avatar
d*x
38 楼
谁说不是呢

【在 w****x 的大作中提到】
:
: 靠,世界真小
avatar
w*x
39 楼

哦~~ 这个无所谓吧, 我觉得一个电面写那个hashtable就够了

【在 d**********x 的大作中提到】
: 几个参数需要update吧。。。当时好像少赋了两个值。。。
avatar
c*t
40 楼
电面就够呛了，俺如果去他家onsite的话估计只能纯打酱油了……

【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
avatar
c*t
41 楼
更新了今天最新的面筋……
avatar
g*e
42 楼
k-largest, quick sort, priority queue这种code背下来算了。根本不可能现场无bug
自己实现的
第3题，用heap比类qsort效率更稳定

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
avatar
K*n
43 楼
刚背靠背连面了两个45分钟，5个题做出来4个，估计挂了。

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
avatar
K*n
44 楼
collabedit真不如googledoc好使……

【在 c******t 的大作中提到】
: 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
: 码，手很抖啊……
avatar
K*n
45 楼
顶锅盖说，heapify不就是一个siftup, siftdown....

【在 d**********x 的大作中提到】
: priority queque都用的吧
: 再说那个heapify的复杂度多impressive啊。
avatar
g*e
46 楼
google doc不能语法加亮吧？顺便求面经。。。

【在 K*********n 的大作中提到】
: collabedit真不如googledoc好使……
avatar
w*x
47 楼

问一下楼主, 你的【UPDATE面经】这一栏是一次电面的还是两次的?

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
avatar
K*n
48 楼
我虽然是new grad，但是面的是machine learning组，所以5道题只有1个是一般编程题
，非常简单。happy number问题。
就是给你一个整数，让你看看是不是happy number。定义如下：把这个整数的每一位的
平方加起来，然后持续加下去，如果最终加出来一个1，那就是happy number，否则会出
现一个环，回到你路过的某个数上去，那就不是happy number。
比如：44 -> 4 * 4 + 4 * 4 = 32 -> 13 -> 10 -> 1
但是4就不行，最终你会回到4。当然环路不一定是回到最开始的数。
这个我做对了，这个很快。
后来问了一个概率论的题，擦，就没明白他想干啥，没磨出来，后来觉得我给想复杂了
。

【在 g*****e 的大作中提到】
: google doc不能语法加亮吧？顺便求面经。。。
avatar
g*e
49 楼
这个题就brute force吧，用hashtable记录出现过的numbers，如果不用考虑overflow
的话 =)

会出

【在 K*********n 的大作中提到】
: 我虽然是new grad，但是面的是machine learning组，所以5道题只有1个是一般编程题
: ，非常简单。happy number问题。
: 就是给你一个整数，让你看看是不是happy number。定义如下：把这个整数的每一位的
: 平方加起来，然后持续加下去，如果最终加出来一个1，那就是happy number，否则会出
: 现一个环，回到你路过的某个数上去，那就不是happy number。
: 比如：44 -> 4 * 4 + 4 * 4 = 32 -> 13 -> 10 -> 1
: 但是4就不行，最终你会回到4。当然环路不一定是回到最开始的数。
: 这个我做对了，这个很快。
: 后来问了一个概率论的题，擦，就没明白他想干啥，没磨出来，后来觉得我给想复杂了
: 。
avatar
K*n
50 楼
我是这么做的，HashSet更好，不过hashtable问题不大。
应该也没什么可优化的，简单吧？
他说是对的。

overflow

【在 g*****e 的大作中提到】
: 这个题就brute force吧，用hashtable记录出现过的numbers，如果不用考虑overflow
: 的话 =)
:
: 会出
avatar
c*t
51 楼
两次的，由于连着两天面的，就写一起了

【在 w****x 的大作中提到】
:
: 问一下楼主, 你的【UPDATE面经】这一栏是一次电面的还是两次的?
avatar
K*n
52 楼
我今天用的collabedit字体老是模糊，定位鼠标反应也很迟钝

【在 g*****e 的大作中提到】
: google doc不能语法加亮吧？顺便求面经。。。
avatar
R*y
53 楼
三面的题是order statistic，如果存数组，有O(n)-expected time的解法，如果存二
叉树，有O(log n)解法

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
avatar
g*e
54 楼
"还有一个问题是如何快速给出任何两个人的粉丝交集"
预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
=)

【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
avatar
c*t
55 楼
两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
让再约一次电面。
不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
【UPDATE面经】
就两道题，在sharing doc上实现:
1)实现一个min-heap，并用其找无序数组里的top k;
2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
能自定义node。
【UPDATE三面面经】
让实现函数，返回无序数组里按增序排列后第k个数，比如{3,1,2,4},key=3,就返回3.
先说了naive的排序解法，又说了用max-heap，这哥们貌似第一次听说这个方法，解释
了巨久，指出复杂度O(k)+O((n-k)lgk)后，还让继续找最优算法。经提示后才明白是让
写珠玑里提到的部分快排解法，coding后被指出有个递归的参数传错了，不过时间关系
没有再深入。
这个部分快排的复杂度不还是O(nlgn)么，为啥就比max-heap要更优呢？
avatar
w*x
56 楼
求题
avatar
f*t
57 楼
T家你投了多久收到联系和电面的？

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
w*x
58 楼

一般第三面都是后来加的吧

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
T*s
59 楼
这么难的题啊
avatar
c*t
60 楼
俺自知修行不够，没敢投。是他家一个HR给我发邮件约的面试，看样子是在狂招人……

【在 f******t 的大作中提到】
: T家你投了多久收到联系和电面的？
avatar
c*t
61 楼
没有很难，就让实现堆排序之类的算法，另外会不断push到最优解再让实现，电话里感
觉很焦灼啊……

【在 T*********s 的大作中提到】
: 这么难的题啊
avatar
f*t
62 楼
这样啊...我是new grad, 投了一个月了，没有消息。 期间有个HR问我啥时候毕业，我
答明年，再follow up就告诉我数月之内会有HR跟我联系，他们先要处理之前毕业的人
。我了个去...

【在 c******t 的大作中提到】
: 俺自知修行不够，没敢投。是他家一个HR给我发邮件约的面试，看样子是在狂招人……
avatar
w*x
63 楼

靠, 实现堆排序还不难....

【在 c******t 的大作中提到】
: 没有很难，就让实现堆排序之类的算法，另外会不断push到最优解再让实现，电话里感
: 觉很焦灼啊……
avatar
c*t
64 楼
因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
码，手很抖啊……

【在 w****x 的大作中提到】
:
: 靠, 实现堆排序还不难....
avatar
l*a
65 楼
heap sort太冷门了。
把思路写成code有难度啊。

【在 c******t 的大作中提到】
: 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
: 码，手很抖啊……
avatar
p*2
66 楼
这也会考呀。从来没练过
avatar
d*x
67 楼
priority queque都用的吧
再说那个heapify的复杂度多impressive啊。

【在 l*****a 的大作中提到】
: heap sort太冷门了。
: 把思路写成code有难度啊。
avatar
w*x
68 楼

我觉得这题不需要实现heapify, 只用实现push,pop和top就可以了, heapify也不难做,
主要记得先实现一个siftdown函数

【在 d**********x 的大作中提到】
: priority queque都用的吧
: 再说那个heapify的复杂度多impressive啊。
avatar
d*x
69 楼
其实即使是从头写一个heap，总共也就30+行代码。
我电面t的时候，他们让我从头写一个open addressing的hash map.

做,

【在 w****x 的大作中提到】
:
: 我觉得这题不需要实现heapify, 只用实现push,pop和top就可以了, heapify也不难做,
: 主要记得先实现一个siftdown函数
avatar
d*x
70 楼
我面了两轮，你这个应该是加的一轮。
好运。

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
w*x
71 楼
随手写了一个,没测
class CMinHeap
{
public:
int GetSize() { return m_vec.size(); }
bool empty() { return m_vec.empty(); }
int top() { return m_vec[0]; }
void pop()
{
swap(m_vec[0], m_vec[m_vec.size()-1]);
m_vec.pop_back();
int nCur = 0;
while (2*nCur+1 < m_vec.size())
{
int nSwap = 2*nCur+1;
if (2*nCur+2 < m_vec.size() && m_vec[2*nCur+2] < m_vec[2*nCur+1])
nSwap = 2*nCur+2;

if (m_vec[nCur] <= m_vec[nSwap])
break;
swap(m_vec[nCur], m_vec[nSwap]);
nCur = nSwap;
}
}
void push(int x)
{
m_vec.push_back(x);
int nCur = m_vec.size()-1;
while (nCur != 0)
{
int nParent = (nCur-1)/2;
if (m_vec[nParent] <= m_vec[nCur])
break;
swap(m_vec[nParent], m_vec[nCur]);
nCur = nParent;
}
}
private:
vector m_vec;
};
void GetTopK(int a[], int n, int k, vector& vecRes)
{
if (NULL == a || n <= 0 || k <= 0 || k > n)
return;
CMinHeap mhp;
for (int i = 0; i < n; i++)
{
if (mhp.size() < k)
mhp.push(a[i]);
else
{
if (a[i] > mhp.top())
{
mhp.pop();
mhp.push(a[i]);
}
}
}
while (!mhp.empty())
{
vecRes.push_back(mhp.top());
mhp.pop();
}
}
avatar
w*x
72 楼

open address的hash很难写啊

【在 d**********x 的大作中提到】
: 其实即使是从头写一个heap，总共也就30+行代码。
: 我电面t的时候，他们让我从头写一个open addressing的hash map.
:
: 做,
avatar
d*x
73 楼
恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧

【在 w****x 的大作中提到】
:
: open address的hash很难写啊
avatar
l*a
74 楼
C++大牛啊

【在 w****x 的大作中提到】
: 随手写了一个,没测
: class CMinHeap
: {
: public:
: int GetSize() { return m_vec.size(); }
: bool empty() { return m_vec.empty(); }
: int top() { return m_vec[0]; }
: void pop()
: {
: swap(m_vec[0], m_vec[m_vec.size()-1]);
avatar
w*x
75 楼

不是吧, 要你写多少操作啊, 一个open address的hash table, 要写constructor,
destructor, insert, delete 还TM要写rehash?? 听都没听说个rehash, 谁给写个?

【在 d**********x 的大作中提到】
: 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
: 不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
avatar
l*a
76 楼
find你得写吧？

【在 w****x 的大作中提到】
:
: 不是吧, 要你写多少操作啊, 一个open address的hash table, 要写constructor,
: destructor, insert, delete 还TM要写rehash?? 听都没听说个rehash, 谁给写个?
avatar
w*x
77 楼

对啊, 顶多写个insert, delete和find

【在 l*****a 的大作中提到】
: find你得写吧？
avatar
d*x
78 楼
所有操作。。。
还好hashCode()是假设有的。。。

【在 w****x 的大作中提到】
:
: 对啊, 顶多写个insert, delete和find
avatar
d*x
79 楼
insert过程可能要触发rehash啊。

【在 w****x 的大作中提到】
:
: 对啊, 顶多写个insert, delete和find
avatar
w*x
80 楼

求onsite面经

【在 d**********x 的大作中提到】
: 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
: 不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
avatar
l*a
81 楼
还没看过你的呢

【在 w****x 的大作中提到】
:
: 求onsite面经
avatar
w*x
82 楼

Java的范畴啊, hashCode, reharsh 啥的搞c++的都没听说过啊

【在 d**********x 的大作中提到】
: 所有操作。。。
: 还好hashCode()是假设有的。。。
avatar
w*x
83 楼

等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
insert函数插进去....

【在 w****x 的大作中提到】
:
: Java的范畴啊, hashCode, reharsh 啥的搞c++的都没听说过啊
avatar
i*c
84 楼
T是哪家啊？

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
d*x
85 楼
我想想。。
通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
友之类
有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
一时没说明白的是如何序列化一个C++ style的tree
还有一个问题是如何快速给出任何两个人的粉丝交集。
反正，挂了。。

【在 w****x 的大作中提到】
:
: 等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
: insert函数插进去....
avatar
d*x
86 楼
对的
但是这里面有些状态需要update，不小心就会犯错误。。

【在 w****x 的大作中提到】
:
: 等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
: insert函数插进去....
avatar
w*x
87 楼

水木清华的那个帖子是你发的?

【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
avatar
d*x
88 楼
恩那。

【在 w****x 的大作中提到】
:
: 水木清华的那个帖子是你发的?
avatar
w*x
89 楼

不明白, 不就把原来的数插进新数组里去吗, 有什么要特别注意的吗

【在 d**********x 的大作中提到】
: 对的
: 但是这里面有些状态需要update，不小心就会犯错误。。
avatar
w*x
90 楼

靠,世界真小

【在 d**********x 的大作中提到】
: 恩那。
avatar
d*x
91 楼
几个参数需要update吧。。。当时好像少赋了两个值。。。

【在 w****x 的大作中提到】
:
: 靠,世界真小
avatar
d*x
92 楼
谁说不是呢

【在 w****x 的大作中提到】
:
: 靠,世界真小
avatar
w*x
93 楼

哦~~ 这个无所谓吧, 我觉得一个电面写那个hashtable就够了

【在 d**********x 的大作中提到】
: 几个参数需要update吧。。。当时好像少赋了两个值。。。
avatar
c*t
94 楼
电面就够呛了，俺如果去他家onsite的话估计只能纯打酱油了……

【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
avatar
c*t
95 楼
更新了今天最新的面筋……
avatar
g*e
96 楼
k-largest, quick sort, priority queue这种code背下来算了。根本不可能现场无bug
自己实现的
第3题，用heap比类qsort效率更稳定

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
K*n
97 楼
刚背靠背连面了两个45分钟，5个题做出来4个，估计挂了。

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
K*n
98 楼
collabedit真不如googledoc好使……

【在 c******t 的大作中提到】
: 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
: 码，手很抖啊……
avatar
K*n
99 楼
顶锅盖说，heapify不就是一个siftup, siftdown....

【在 d**********x 的大作中提到】
: priority queque都用的吧
: 再说那个heapify的复杂度多impressive啊。
avatar
g*e
100 楼
google doc不能语法加亮吧？顺便求面经。。。

【在 K*********n 的大作中提到】
: collabedit真不如googledoc好使……
avatar
w*x
101 楼

问一下楼主, 你的【UPDATE面经】这一栏是一次电面的还是两次的?

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
K*n
102 楼
我虽然是new grad，但是面的是machine learning组，所以5道题只有1个是一般编程题
，非常简单。happy number问题。
就是给你一个整数，让你看看是不是happy number。定义如下：把这个整数的每一位的
平方加起来，然后持续加下去，如果最终加出来一个1，那就是happy number，否则会出
现一个环，回到你路过的某个数上去，那就不是happy number。
比如：44 -> 4 * 4 + 4 * 4 = 32 -> 13 -> 10 -> 1
但是4就不行，最终你会回到4。当然环路不一定是回到最开始的数。
这个我做对了，这个很快。
后来问了一个概率论的题，擦，就没明白他想干啥，没磨出来，后来觉得我给想复杂了
。

【在 g*****e 的大作中提到】
: google doc不能语法加亮吧？顺便求面经。。。
avatar
g*e
103 楼
这个题就brute force吧，用hashtable记录出现过的numbers，如果不用考虑overflow
的话 =)

会出

【在 K*********n 的大作中提到】
: 我虽然是new grad，但是面的是machine learning组，所以5道题只有1个是一般编程题
: ，非常简单。happy number问题。
: 就是给你一个整数，让你看看是不是happy number。定义如下：把这个整数的每一位的
: 平方加起来，然后持续加下去，如果最终加出来一个1，那就是happy number，否则会出
: 现一个环，回到你路过的某个数上去，那就不是happy number。
: 比如：44 -> 4 * 4 + 4 * 4 = 32 -> 13 -> 10 -> 1
: 但是4就不行，最终你会回到4。当然环路不一定是回到最开始的数。
: 这个我做对了，这个很快。
: 后来问了一个概率论的题，擦，就没明白他想干啥，没磨出来，后来觉得我给想复杂了
: 。
avatar
K*n
104 楼
我是这么做的，HashSet更好，不过hashtable问题不大。
应该也没什么可优化的，简单吧？
他说是对的。

overflow

【在 g*****e 的大作中提到】
: 这个题就brute force吧，用hashtable记录出现过的numbers，如果不用考虑overflow
: 的话 =)
:
: 会出
avatar
c*t
105 楼
两次的，由于连着两天面的，就写一起了

【在 w****x 的大作中提到】
:
: 问一下楼主, 你的【UPDATE面经】这一栏是一次电面的还是两次的?
avatar
K*n
106 楼
我今天用的collabedit字体老是模糊，定位鼠标反应也很迟钝

【在 g*****e 的大作中提到】
: google doc不能语法加亮吧？顺便求面经。。。
avatar
R*y
107 楼
三面的题是order statistic，如果存数组，有O(n)-expected time的解法，如果存二
叉树，有O(log n)解法

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
g*e
108 楼
"还有一个问题是如何快速给出任何两个人的粉丝交集"
预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
=)

【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
avatar
l*b
109 楼
Mark
avatar
q*m
110 楼
happy number, 是不是要记录下出现的数，然后出县现了重复的而且没有1的话就停止？

会出

【在 K*********n 的大作中提到】
: 我虽然是new grad，但是面的是machine learning组，所以5道题只有1个是一般编程题
: ，非常简单。happy number问题。
: 就是给你一个整数，让你看看是不是happy number。定义如下：把这个整数的每一位的
: 平方加起来，然后持续加下去，如果最终加出来一个1，那就是happy number，否则会出
: 现一个环，回到你路过的某个数上去，那就不是happy number。
: 比如：44 -> 4 * 4 + 4 * 4 = 32 -> 13 -> 10 -> 1
: 但是4就不行，最终你会回到4。当然环路不一定是回到最开始的数。
: 这个我做对了，这个很快。
: 后来问了一个概率论的题，擦，就没明白他想干啥，没磨出来，后来觉得我给想复杂了
: 。
avatar
c*5
111 楼
请问珠玑里提到的部分快排解法大致思想是什么样的呢？
谢谢

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
f*m
112 楼
这个问题有什么好的答案吗？
给每个人建立一个粉丝list或数组，每个人的粉丝占一个hashtable slot。找交集时先
找到相应的两个slot，然后找他们的交集？

【在 g*****e 的大作中提到】
: "还有一个问题是如何快速给出任何两个人的粉丝交集"
: 预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
: =)
avatar
A*e
113 楼
谢谢lz分享～
快排是O(nlgn),因为T(n)=2T(n/2) + O(n),但是用它找top k的时候，每次扔掉一半，
只需要考虑一半的数，递推关系是T(n)=T(n/2)+O(n)
复杂度就是O(n)了。

【在 c******t 的大作中提到】
: 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
: interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
: 让再约一次电面。
: 不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
: 【UPDATE面经】
: 就两道题，在sharing doc上实现:
: 1)实现一个min-heap，并用其找无序数组里的top k;
: 2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
: 能自定义node。
: 【UPDATE三面面经】
avatar
A*e
114 楼
是因为qsort的worst case是O(n^2)？
我想面试的时候碰到是不是应该都说一说，看他们喜欢哪种再去实现哪种啦～

【在 g*****e 的大作中提到】
: "还有一个问题是如何快速给出任何两个人的粉丝交集"
: 预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
: =)
相关阅读
Image Process方面的工作一般会有什么样的面试题？我的on-site interview请教CPT的问题，急！OFFER 没有说 bonus,就是没有bonus吗？要面试了，都准备什么呢急需建议为啥没骑马找貂蝉的故事能不能接受第二个OFFER？一个研发onsite 问题，需要注意什么？上学和上班究竟哪个更累紧急求助，H1b transfer的大问题non-profit H1B(Hiring) Regional sushi SupervisorH1B刚结束amazon二面Immediate opening in New York: Analytics Engineer (转载)OPT申请，对方收到后多久俺能收到receipt啊暑假intern周二面试，周五打电话问结果，好吗LD的两个工作offer的方向，大家帮分析一下哪个好？ (转载)[原创MITBBS首发]2年CS求职打怪升级心得
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。