c******t
发帖数: 391 | 1 两周前连着电面了两次他家，自我感觉巨烂，coding题都没做出来。时间刚过半
interviewer就懒得发问草草结束了。结果昨天居然接到HR电话说positive feedback，
让再约一次电面。
不知道T家电面要几轮啊，每次面他家都被问得落花流水，大受打击……
【UPDATE面经】
就两道题，在sharing doc上实现:
1)实现一个min-heap，并用其找无序数组里的top k;
2)实现一个min-stack, 其中min()返回当前栈里的最小值。stack node是Integer，不
能自定义node。 |
w****x
发帖数: 2483 | |
f******t
发帖数: 32 | 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。
|
w****x
发帖数: 2483 | 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。
|
T*********s
发帖数: 17839 | |
c******t
发帖数: 391 | 6 俺自知修行不够，没敢投。是他家一个HR给我发邮件约的面试，看样子是在狂招人……
【在 f******t 的大作中提到】
: T家你投了多久收到联系和电面的？
|
c******t
发帖数: 391 | 7 没有很难，就让实现堆排序之类的算法，另外会不断push到最优解再让实现，电话里感
觉很焦灼啊……
【在 T*********s 的大作中提到】
: 这么难的题啊
|
f******t
发帖数: 32 | 8 这样啊...我是new grad, 投了一个月了，没有消息。 期间有个HR问我啥时候毕业，我
答明年，再follow up就告诉我数月之内会有HR跟我联系，他们先要处理之前毕业的人
。我了个去...
【在 c******t 的大作中提到】
: 俺自知修行不够，没敢投。是他家一个HR给我发邮件约的面试，看样子是在狂招人……
|
w****x
发帖数: 2483 | 9
靠, 实现堆排序还不难....
【在 c******t 的大作中提到】
: 没有很难，就让实现堆排序之类的算法，另外会不断push到最优解再让实现，电话里感
: 觉很焦灼啊……
|
c******t
发帖数: 391 | 10 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
码，手很抖啊……
【在 w****x 的大作中提到】
:
: 靠, 实现堆排序还不难....
|
|
|
l*****a
发帖数: 559 | 11 heap sort太冷门了。
把思路写成code有难度啊。
【在 c******t 的大作中提到】
: 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
: 码，手很抖啊……
|
p*****2
发帖数: 21240 | |
d**********x
发帖数: 4083 | 13 priority queque都用的吧
再说那个heapify的复杂度多impressive啊。
【在 l*****a 的大作中提到】
: heap sort太冷门了。
: 把思路写成code有难度啊。
|
w****x
发帖数: 2483 | 14
我觉得这题不需要实现heapify, 只用实现push,pop和top就可以了, heapify也不难做,
主要记得先实现一个siftdown函数
【在 d**********x 的大作中提到】
: priority queque都用的吧
: 再说那个heapify的复杂度多impressive啊。
|
d**********x
发帖数: 4083 | 15 其实即使是从头写一个heap，总共也就30+行代码。
我电面t的时候，他们让我从头写一个open addressing的hash map.
做,
【在 w****x 的大作中提到】
:
: 我觉得这题不需要实现heapify, 只用实现push,pop和top就可以了, heapify也不难做,
: 主要记得先实现一个siftdown函数
|
d**********x
发帖数: 4083 | 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。
|
w****x
发帖数: 2483 | 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();
}
} |
w****x
发帖数: 2483 | 18
open address的hash很难写啊
【在 d**********x 的大作中提到】
: 其实即使是从头写一个heap，总共也就30+行代码。
: 我电面t的时候，他们让我从头写一个open addressing的hash map.
:
: 做,
|
d**********x
发帖数: 4083 | 19 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
【在 w****x 的大作中提到】
:
: open address的hash很难写啊
|
l*****a
发帖数: 14598 | 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]);
|
|
|
w****x
发帖数: 2483 | 21
不是吧, 要你写多少操作啊, 一个open address的hash table, 要写constructor,
destructor, insert, delete 还TM要写rehash?? 听都没听说个rehash, 谁给写个?
【在 d**********x 的大作中提到】
: 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
: 不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
|
l*****a
发帖数: 14598 | 22 find你得写吧？
【在 w****x 的大作中提到】
:
: 不是吧, 要你写多少操作啊, 一个open address的hash table, 要写constructor,
: destructor, insert, delete 还TM要写rehash?? 听都没听说个rehash, 谁给写个?
|
w****x
发帖数: 2483 | 23
对啊, 顶多写个insert, delete和find
【在 l*****a 的大作中提到】
: find你得写吧？
|
d**********x
发帖数: 4083 | 24 所有操作。。。
还好hashCode()是假设有的。。。
【在 w****x 的大作中提到】
:
: 对啊, 顶多写个insert, delete和find
|
d**********x
发帖数: 4083 | 25 insert过程可能要触发rehash啊。
【在 w****x 的大作中提到】
:
: 对啊, 顶多写个insert, delete和find
|
w****x
发帖数: 2483 | 26
求onsite面经
【在 d**********x 的大作中提到】
: 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
: 不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
|
l*****a
发帖数: 14598 | 27 还没看过你的呢
【在 w****x 的大作中提到】
:
: 求onsite面经
|
w****x
发帖数: 2483 | 28
Java的范畴啊, hashCode, reharsh 啥的搞c++的都没听说过啊
【在 d**********x 的大作中提到】
: 所有操作。。。
: 还好hashCode()是假设有的。。。
|
w****x
发帖数: 2483 | 29
等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
insert函数插进去....
【在 w****x 的大作中提到】
:
: Java的范畴啊, hashCode, reharsh 啥的搞c++的都没听说过啊
|
i**c
发帖数: 753 | 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。
|
|
|
d**********x
发帖数: 4083 | 31 我想想。。
通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
友之类
有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
一时没说明白的是如何序列化一个C++ style的tree
还有一个问题是如何快速给出任何两个人的粉丝交集。
反正，挂了。。
【在 w****x 的大作中提到】
:
: 等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
: insert函数插进去....
|
d**********x
发帖数: 4083 | 32 对的
但是这里面有些状态需要update，不小心就会犯错误。。
【在 w****x 的大作中提到】
:
: 等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
: insert函数插进去....
|
w****x
发帖数: 2483 | 33
水木清华的那个帖子是你发的?
【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
|
d**********x
发帖数: 4083 | 34 恩那。
【在 w****x 的大作中提到】
:
: 水木清华的那个帖子是你发的?
|
w****x
发帖数: 2483 | 35
不明白, 不就把原来的数插进新数组里去吗, 有什么要特别注意的吗
【在 d**********x 的大作中提到】
: 对的
: 但是这里面有些状态需要update，不小心就会犯错误。。
|
w****x
发帖数: 2483 | 36
靠,世界真小
【在 d**********x 的大作中提到】
: 恩那。
|
d**********x
发帖数: 4083 | 37 几个参数需要update吧。。。当时好像少赋了两个值。。。
【在 w****x 的大作中提到】
:
: 靠,世界真小
|
d**********x
发帖数: 4083 | 38 谁说不是呢
【在 w****x 的大作中提到】
:
: 靠,世界真小
|
w****x
发帖数: 2483 | 39
哦~~ 这个无所谓吧, 我觉得一个电面写那个hashtable就够了
【在 d**********x 的大作中提到】
: 几个参数需要update吧。。。当时好像少赋了两个值。。。
|
c******t
发帖数: 391 | 40 电面就够呛了，俺如果去他家onsite的话估计只能纯打酱油了……
【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
|
|
|
c******t
发帖数: 391 | |
g*****e
发帖数: 282 | 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。
|
K*********n
发帖数: 2852 | 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。
|
K*********n
发帖数: 2852 | 44 collabedit真不如googledoc好使……
【在 c******t 的大作中提到】
: 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
: 码，手很抖啊……
|
K*********n
发帖数: 2852 | 45 顶锅盖说，heapify不就是一个siftup, siftdown....
【在 d**********x 的大作中提到】
: priority queque都用的吧
: 再说那个heapify的复杂度多impressive啊。
|
g*****e
发帖数: 282 | 46 google doc不能语法加亮吧？顺便求面经。。。
【在 K*********n 的大作中提到】
: collabedit真不如googledoc好使……
|
w****x
发帖数: 2483 | 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。
|
K*********n
发帖数: 2852 | 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不能语法加亮吧？顺便求面经。。。
|
g*****e
发帖数: 282 | 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。当然环路不一定是回到最开始的数。
: 这个我做对了，这个很快。
: 后来问了一个概率论的题，擦，就没明白他想干啥，没磨出来，后来觉得我给想复杂了
: 。
|
K*********n
发帖数: 2852 | 50 我是这么做的，HashSet更好，不过hashtable问题不大。
应该也没什么可优化的，简单吧？
他说是对的。
overflow
【在 g*****e 的大作中提到】
: 这个题就brute force吧，用hashtable记录出现过的numbers，如果不用考虑overflow
: 的话 =)
:
: 会出
|
|
|
c******t
发帖数: 391 | 51 两次的，由于连着两天面的，就写一起了
【在 w****x 的大作中提到】
:
: 问一下楼主, 你的【UPDATE面经】这一栏是一次电面的还是两次的?
|
K*********n
发帖数: 2852 | 52 我今天用的collabedit字体老是模糊，定位鼠标反应也很迟钝
【在 g*****e 的大作中提到】
: google doc不能语法加亮吧？顺便求面经。。。
|
R********y
发帖数: 88 | 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。
|
g*****e
发帖数: 282 | 54 "还有一个问题是如何快速给出任何两个人的粉丝交集"
预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
=)
【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
|
c******t
发帖数: 391 | 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要更优呢？ |
w****x
发帖数: 2483 | |
f******t
发帖数: 32 | 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三面面经】
|
w****x
发帖数: 2483 | 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三面面经】
|
T*********s
发帖数: 17839 | |
c******t
发帖数: 391 | 60 俺自知修行不够，没敢投。是他家一个HR给我发邮件约的面试，看样子是在狂招人……
【在 f******t 的大作中提到】
: T家你投了多久收到联系和电面的？
|
|
|
c******t
发帖数: 391 | 61 没有很难，就让实现堆排序之类的算法，另外会不断push到最优解再让实现，电话里感
觉很焦灼啊……
【在 T*********s 的大作中提到】
: 这么难的题啊
|
f******t
发帖数: 32 | 62 这样啊...我是new grad, 投了一个月了，没有消息。 期间有个HR问我啥时候毕业，我
答明年，再follow up就告诉我数月之内会有HR跟我联系，他们先要处理之前毕业的人
。我了个去...
【在 c******t 的大作中提到】
: 俺自知修行不够，没敢投。是他家一个HR给我发邮件约的面试，看样子是在狂招人……
|
w****x
发帖数: 2483 | 63
靠, 实现堆排序还不难....
【在 c******t 的大作中提到】
: 没有很难，就让实现堆排序之类的算法，另外会不断push到最优解再让实现，电话里感
: 觉很焦灼啊……
|
c******t
发帖数: 391 | 64 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
码，手很抖啊……
【在 w****x 的大作中提到】
:
: 靠, 实现堆排序还不难....
|
l*****a
发帖数: 559 | 65 heap sort太冷门了。
把思路写成code有难度啊。
【在 c******t 的大作中提到】
: 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
: 码，手很抖啊……
|
p*****2
发帖数: 21240 | |
d**********x
发帖数: 4083 | 67 priority queque都用的吧
再说那个heapify的复杂度多impressive啊。
【在 l*****a 的大作中提到】
: heap sort太冷门了。
: 把思路写成code有难度啊。
|
w****x
发帖数: 2483 | 68
我觉得这题不需要实现heapify, 只用实现push,pop和top就可以了, heapify也不难做,
主要记得先实现一个siftdown函数
【在 d**********x 的大作中提到】
: priority queque都用的吧
: 再说那个heapify的复杂度多impressive啊。
|
d**********x
发帖数: 4083 | 69 其实即使是从头写一个heap，总共也就30+行代码。
我电面t的时候，他们让我从头写一个open addressing的hash map.
做,
【在 w****x 的大作中提到】
:
: 我觉得这题不需要实现heapify, 只用实现push,pop和top就可以了, heapify也不难做,
: 主要记得先实现一个siftdown函数
|
d**********x
发帖数: 4083 | 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三面面经】
|
|
|
w****x
发帖数: 2483 | 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();
}
} |
w****x
发帖数: 2483 | 72
open address的hash很难写啊
【在 d**********x 的大作中提到】
: 其实即使是从头写一个heap，总共也就30+行代码。
: 我电面t的时候，他们让我从头写一个open addressing的hash map.
:
: 做,
|
d**********x
发帖数: 4083 | 73 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
【在 w****x 的大作中提到】
:
: open address的hash很难写啊
|
l*****a
发帖数: 14598 | 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]);
|
w****x
发帖数: 2483 | 75
不是吧, 要你写多少操作啊, 一个open address的hash table, 要写constructor,
destructor, insert, delete 还TM要写rehash?? 听都没听说个rehash, 谁给写个?
【在 d**********x 的大作中提到】
: 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
: 不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
|
l*****a
发帖数: 14598 | 76 find你得写吧？
【在 w****x 的大作中提到】
:
: 不是吧, 要你写多少操作啊, 一个open address的hash table, 要写constructor,
: destructor, insert, delete 还TM要写rehash?? 听都没听说个rehash, 谁给写个?
|
w****x
发帖数: 2483 | 77
对啊, 顶多写个insert, delete和find
【在 l*****a 的大作中提到】
: find你得写吧？
|
d**********x
发帖数: 4083 | 78 所有操作。。。
还好hashCode()是假设有的。。。
【在 w****x 的大作中提到】
:
: 对啊, 顶多写个insert, delete和find
|
d**********x
发帖数: 4083 | 79 insert过程可能要触发rehash啊。
【在 w****x 的大作中提到】
:
: 对啊, 顶多写个insert, delete和find
|
w****x
发帖数: 2483 | 80
求onsite面经
【在 d**********x 的大作中提到】
: 恩。。尤其是rehash的时候有几个坑，当时是给我敲了个警钟。
: 不过他们也没期待能一下就写出来，所以后来电面还是过了。。。onsite灰长悲剧
|
|
|
l*****a
发帖数: 14598 | 81 还没看过你的呢
【在 w****x 的大作中提到】
:
: 求onsite面经
|
w****x
发帖数: 2483 | 82
Java的范畴啊, hashCode, reharsh 啥的搞c++的都没听说过啊
【在 d**********x 的大作中提到】
: 所有操作。。。
: 还好hashCode()是假设有的。。。
|
w****x
发帖数: 2483 | 83
等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
insert函数插进去....
【在 w****x 的大作中提到】
:
: Java的范畴啊, hashCode, reharsh 啥的搞c++的都没听说过啊
|
i**c
发帖数: 753 | 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三面面经】
|
d**********x
发帖数: 4083 | 85 我想想。。
通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
友之类
有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
一时没说明白的是如何序列化一个C++ style的tree
还有一个问题是如何快速给出任何两个人的粉丝交集。
反正，挂了。。
【在 w****x 的大作中提到】
:
: 等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
: insert函数插进去....
|
d**********x
发帖数: 4083 | 86 对的
但是这里面有些状态需要update，不小心就会犯错误。。
【在 w****x 的大作中提到】
:
: 等等, rehash是不是就是再分配一个大点的数组然后把原数组一个个调用已经写好的
: insert函数插进去....
|
w****x
发帖数: 2483 | 87
水木清华的那个帖子是你发的?
【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
|
d**********x
发帖数: 4083 | 88 恩那。
【在 w****x 的大作中提到】
:
: 水木清华的那个帖子是你发的?
|
w****x
发帖数: 2483 | 89
不明白, 不就把原来的数插进新数组里去吗, 有什么要特别注意的吗
【在 d**********x 的大作中提到】
: 对的
: 但是这里面有些状态需要update，不小心就会犯错误。。
|
w****x
发帖数: 2483 | 90
靠,世界真小
【在 d**********x 的大作中提到】
: 恩那。
|
|
|
d**********x
发帖数: 4083 | 91 几个参数需要update吧。。。当时好像少赋了两个值。。。
【在 w****x 的大作中提到】
:
: 靠,世界真小
|
d**********x
发帖数: 4083 | 92 谁说不是呢
【在 w****x 的大作中提到】
:
: 靠,世界真小
|
w****x
发帖数: 2483 | 93
哦~~ 这个无所谓吧, 我觉得一个电面写那个hashtable就够了
【在 d**********x 的大作中提到】
: 几个参数需要update吧。。。当时好像少赋了两个值。。。
|
c******t
发帖数: 391 | 94 电面就够呛了，俺如果去他家onsite的话估计只能纯打酱油了……
【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
|
c******t
发帖数: 391 | |
g*****e
发帖数: 282 | 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三面面经】
|
K*********n
发帖数: 2852 | 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三面面经】
|
K*********n
发帖数: 2852 | 98 collabedit真不如googledoc好使……
【在 c******t 的大作中提到】
: 因为面的前一天刚看过CLRS上的heap sort伪代码，不过第一次用那个collabedit写代
: 码，手很抖啊……
|
K*********n
发帖数: 2852 | 99 顶锅盖说，heapify不就是一个siftup, siftdown....
【在 d**********x 的大作中提到】
: priority queque都用的吧
: 再说那个heapify的复杂度多impressive啊。
|
g*****e
发帖数: 282 | 100 google doc不能语法加亮吧？顺便求面经。。。
【在 K*********n 的大作中提到】
: collabedit真不如googledoc好使……
|
|
|
w****x
发帖数: 2483 | 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三面面经】
|
K*********n
发帖数: 2852 | 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不能语法加亮吧？顺便求面经。。。
|
g*****e
发帖数: 282 | 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。当然环路不一定是回到最开始的数。
: 这个我做对了，这个很快。
: 后来问了一个概率论的题，擦，就没明白他想干啥，没磨出来，后来觉得我给想复杂了
: 。
|
K*********n
发帖数: 2852 | 104 我是这么做的，HashSet更好，不过hashtable问题不大。
应该也没什么可优化的，简单吧？
他说是对的。
overflow
【在 g*****e 的大作中提到】
: 这个题就brute force吧，用hashtable记录出现过的numbers，如果不用考虑overflow
: 的话 =)
:
: 会出
|
c******t
发帖数: 391 | 105 两次的，由于连着两天面的，就写一起了
【在 w****x 的大作中提到】
:
: 问一下楼主, 你的【UPDATE面经】这一栏是一次电面的还是两次的?
|
K*********n
发帖数: 2852 | 106 我今天用的collabedit字体老是模糊，定位鼠标反应也很迟钝
【在 g*****e 的大作中提到】
: google doc不能语法加亮吧？顺便求面经。。。
|
R********y
发帖数: 88 | 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三面面经】
|
g*****e
发帖数: 282 | 108 "还有一个问题是如何快速给出任何两个人的粉丝交集"
预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
=)
【在 d**********x 的大作中提到】
: 我想想。。
: 通俗的就是最长递增子序列，最长公共子序列，如何去掉代码中的注释，最短路径找朋
: 友之类
: 有一个人当时其实考到了n-gram的概念，可惜我当时不懂，瞎答的。。
: 然后我更不懂的就是如何用分布式系统统计search query的频率，如何分布式存储
: 一时没说明白的是如何序列化一个C++ style的tree
: 还有一个问题是如何快速给出任何两个人的粉丝交集。
: 反正，挂了。。
|
l**b
发帖数: 457 | |
q****m
发帖数: 177 | 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。当然环路不一定是回到最开始的数。
: 这个我做对了，这个很快。
: 后来问了一个概率论的题，擦，就没明白他想干啥，没磨出来，后来觉得我给想复杂了
: 。
|
|
|
c******5
发帖数: 84 | 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三面面经】
|
f*********m
发帖数: 726 | 112 这个问题有什么好的答案吗？
给每个人建立一个粉丝list或数组，每个人的粉丝占一个hashtable slot。找交集时先
找到相应的两个slot，然后找他们的交集？
【在 g*****e 的大作中提到】
: "还有一个问题是如何快速给出任何两个人的粉丝交集"
: 预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
: =)
|
A****e
发帖数: 310 | 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三面面经】
|
A****e
发帖数: 310 | 114 是因为qsort的worst case是O(n^2)？
我想面试的时候碰到是不是应该都说一说，看他们喜欢哪种再去实现哪种啦～
【在 g*****e 的大作中提到】
: "还有一个问题是如何快速给出任何两个人的粉丝交集"
: 预处理，上hashtable（O(N))，或者把每个id的粉丝按id排序，然后bs？大家讨论下吧
: =)
|
