探讨IT大公司的hiring bar?# JobHunting - 待字闺中
O*i
1 楼
最近面了一家IT大公司被拒,一共经历了N轮技术面试。自己感觉还不算太坏,但也有
三轮发挥不太完美,所以心里很没底。
结果还是被拒了。
下面是这三轮的详细经历,请大家探讨一下大公司招人的标准。
第i轮是找二叉树从根开始的所有路径,使得该路径上所有节点的值之和等于一个给定
的数。我犯了一个战略错误,因为我在准备过程中看过CarrerCup的更通用的解法,不
要求从根开始,也不要求到叶子结束,于是我直接用了那个思路,在白板上写下了类似
下面的代码
void FindPath(Node* root, int sum, int path[], int level)
{
if (root == NULL)
return;
int s = 0;
for (int i = 0; i < level; i++)
s += path[i];
int value = root->data;
if (s + value == sum)
PrintPath(path, level, value);
path[level] = value;
FindPath(root->left, sum, path, level + 1);
FindPath(root->right, sum, path, level + 1);
}
最初调用这个函数的时候level为0,PrintPath是一个helper函数,打印path栈的内容
再加一个value。
我自己还用一个test case过了一遍程序,确信没有bug了就跟他说好了。
他问我,时间复杂度是多少?
我说这个类似二叉树的先序遍历,如果树的总节点数是N,则复杂度是O(N)
他反问:O(N)? 然后指了指我的那个for语句。我才发现说错了,改口说是O(N*lgN),
如果树是平衡的话,最坏情形是O(N^2)
他又说,我不喜欢你那个PrintPath函数的参数,你可以把value先入栈,这样就不用
value这个参数了。还有,你没有必要用那个for每次计算从根开始到当前节点的数值总
和,可以用一个变量来保存,你再优化一下。
我其实以前也知道这个思路,于是就给FindPath函数增加了一个current_sum的参数,
到这里他才满意。我还跟他指出,这题从根开始,因此能这样优化,但我最早的方法,
可以解决更general的问题,利用path从当前进行回溯就可以。但是,我想他未必给我
好的feedback...
第j轮是一个白人,一上来就问我知不知道优先队列。我说知道,还告诉他这个只是一
个抽象概念,底层可以用数组,链表,或者堆来实现,其中堆是一种最实用的实现方式
。他说那好,你说说优先队列有哪些接口。我说假定优先数越小优先级越大,有
Enqueue和DeleteMin两个接口。
他问我Enqueue的接口是怎样的,我用了C++的模板,写了void Enqueue(const T& data
), 还和他说传引用比传值快。他说不对,我纳闷。他说还有一个参数你漏了,就是优
先数。我承认自己错了,就改写成void Enqueue(int priority, const T& data)。我
事后看过许多书上和网上, 都是用我那样的接口,也就是T重载了比较操作符,T越小
优先级越高,而不是他那样把优先数和数据分离开来,郁闷...
他又问DeleteMin怎么写,我说T DeleteMin()或者T& DeleteMin(), 前者返回值,要调
用拷贝构造函数,因此慢。后者返回引用,快。他说后面那个有问题,然后画了个队列
,好像是说元素被删除出队列后,对象被析构了。
然后他说假如有人已经实现了一个Heap类,你如何利用它实现你的Enqueue?我说优先队
列内部定义一个变量Heap heap,
void Enqueue(int priority, const T& data)
{
heap.insert(priority, data);
}
他又说不对,Heap的insert没有priority参数!
我一急,顺口说那就改为heap.insert(data)好了, 假定T重载了比较操作符,他也就这
样结束了这个问题,问了一个正方形继承矩形的OO设计的题目,我答的不错,提到了
Liskov替换原则。
我事后才想到,应该要引人一个Pair类
class Pair
{
int priority;
T data;
}
重载Pair的比较操作符,用priority来比较。
优先队列内部定义一个变量Heap heap,
void Enqueue(int priority, const T& data)
{
Pair pair(priority, data);
heap.insert(pair);
}
但是他没有指出我的错误,就草草结束了。这题我完全被他牵着鼻子走。我是越说越糊
涂,他大概是越听心里越摇头吧...
第k轮,说有一个类,里头有两个Date对象
class T
{
Date date1;
Date date2;
}
其中Date是形如12/05/2011这样的日期,date1 <= date2,这样T就表示一个时间段。
假如有两个T类型的变量a,b,如果a和b代表的时间段之间没有gap, 也就是a和b
overlap, 则集合{a, b}是连续的。然后他解释扩展到多个时间段,什么情况下他们的
集合是连续的。
我很快发现,每个Date在时间轴上是一个点,每个时间段T的变量是时间轴上的一条线
段,这题完全可以等同于
class Seg
{
int start;
int end;
}
其中 start <= end, 这样Seg就表示数轴上的线段。两条线段如果overlap,包括
overlap于一个点,则连续。他无非想用时间这个概念来使得问题看起来更复杂些。
我和他指出了这个事实,说我下面就化归到数轴上的线段问题来做。
他的问题是,给你一个T类型变量的list,如何判断这个list是连续的还是不连续的。
我一开始就想到并和他提到了,也许可以排序一下。因为我觉得递归是大杀器,鬼使神
差的说我先用递归的方法来做吧。结果越做越陷入死胡同,发现总是有很多特殊情况。
比如前面的三条线段是[4, 6], [8, 10], [2, 3],是不连续的,但最后一条线段是[1
, 11]的话整个list又连续了。
我在白板上写了段递归的代码,发现不对,又改,还是不对,再改,还是无解。眼看时
间不多了,他突然说,为什么不预处理一下?
预处理?莫非就是我开始想到的排序?我马上跟他提到了排序,说我开始也想过的,于
是在白板上排序了一个具体例子。
发现解决问题就容易了:
排序后,如果第一条线段和第二条线段不连续,则整个list不连续,可以返回false,
如果连续,则merge这两条线段,然后再考察merge后的线段和第三条线段,最后或者遍
历完所有的线段,或者中途就返回false。
但是他说面试时间要结束了,我没有时间coding了。我和他解释说我面到最后一轮,大
脑都不太转了,排序的方法我开始也想到过,可惜我想先用递归来实现,没有坚持那个
想法。
最后还是被拒了,官方解释是does not meet the position's technical bar
这样被拒合乎情理么?我知道这三轮的表现都不完美,但也不能一棍子否认吧。
第i轮代码不够优化,但是代码还是正确且没有bug的。以前面别的公司有几个bug, 被
拒我也能理解。而且我的方法是可以解决不从根开始,也不从叶子结束的general case。
第j轮主要还是我一开始假定的接口和他的不一样,导致整个过程被他牵着鼻子走,没
有把握主动权。其实我一开始说的Enqueue的接口,正是网上书上常见的接口,而不是
他的那个要多一个参数,我应该先和他提出我的接口也是合理的,然后再按他的接口做
,而不是简单否定自己先。
第k轮被提示才做出来是硬伤,但是我开始也想到这个提示的。而且我递归的时候,一
直keep talking, 一直在讲我的想法。我听有人说,面试官最喜欢你按照他的指引,一
步一步达到最优解的,这轮面试不就是这样发展的么?
肯定这三轮深刻影响了他们group的讨论结果,做出了我没有达到他们的technical bar
的结论。
我真不理解他们的要求是否就那么高, 我还需要提高哪些方面,要复习准备到什么样的
程度才能meet the bar呢?
三轮发挥不太完美,所以心里很没底。
结果还是被拒了。
下面是这三轮的详细经历,请大家探讨一下大公司招人的标准。
第i轮是找二叉树从根开始的所有路径,使得该路径上所有节点的值之和等于一个给定
的数。我犯了一个战略错误,因为我在准备过程中看过CarrerCup的更通用的解法,不
要求从根开始,也不要求到叶子结束,于是我直接用了那个思路,在白板上写下了类似
下面的代码
void FindPath(Node* root, int sum, int path[], int level)
{
if (root == NULL)
return;
int s = 0;
for (int i = 0; i < level; i++)
s += path[i];
int value = root->data;
if (s + value == sum)
PrintPath(path, level, value);
path[level] = value;
FindPath(root->left, sum, path, level + 1);
FindPath(root->right, sum, path, level + 1);
}
最初调用这个函数的时候level为0,PrintPath是一个helper函数,打印path栈的内容
再加一个value。
我自己还用一个test case过了一遍程序,确信没有bug了就跟他说好了。
他问我,时间复杂度是多少?
我说这个类似二叉树的先序遍历,如果树的总节点数是N,则复杂度是O(N)
他反问:O(N)? 然后指了指我的那个for语句。我才发现说错了,改口说是O(N*lgN),
如果树是平衡的话,最坏情形是O(N^2)
他又说,我不喜欢你那个PrintPath函数的参数,你可以把value先入栈,这样就不用
value这个参数了。还有,你没有必要用那个for每次计算从根开始到当前节点的数值总
和,可以用一个变量来保存,你再优化一下。
我其实以前也知道这个思路,于是就给FindPath函数增加了一个current_sum的参数,
到这里他才满意。我还跟他指出,这题从根开始,因此能这样优化,但我最早的方法,
可以解决更general的问题,利用path从当前进行回溯就可以。但是,我想他未必给我
好的feedback...
第j轮是一个白人,一上来就问我知不知道优先队列。我说知道,还告诉他这个只是一
个抽象概念,底层可以用数组,链表,或者堆来实现,其中堆是一种最实用的实现方式
。他说那好,你说说优先队列有哪些接口。我说假定优先数越小优先级越大,有
Enqueue和DeleteMin两个接口。
他问我Enqueue的接口是怎样的,我用了C++的模板,写了void Enqueue(const T& data
), 还和他说传引用比传值快。他说不对,我纳闷。他说还有一个参数你漏了,就是优
先数。我承认自己错了,就改写成void Enqueue(int priority, const T& data)。我
事后看过许多书上和网上, 都是用我那样的接口,也就是T重载了比较操作符,T越小
优先级越高,而不是他那样把优先数和数据分离开来,郁闷...
他又问DeleteMin怎么写,我说T DeleteMin()或者T& DeleteMin(), 前者返回值,要调
用拷贝构造函数,因此慢。后者返回引用,快。他说后面那个有问题,然后画了个队列
,好像是说元素被删除出队列后,对象被析构了。
然后他说假如有人已经实现了一个Heap类,你如何利用它实现你的Enqueue?我说优先队
列内部定义一个变量Heap
void Enqueue(int priority, const T& data)
{
heap.insert(priority, data);
}
他又说不对,Heap的insert没有priority参数!
我一急,顺口说那就改为heap.insert(data)好了, 假定T重载了比较操作符,他也就这
样结束了这个问题,问了一个正方形继承矩形的OO设计的题目,我答的不错,提到了
Liskov替换原则。
我事后才想到,应该要引人一个Pair类
class Pair
{
int priority;
T data;
}
重载Pair的比较操作符,用priority来比较。
优先队列内部定义一个变量Heap
void Enqueue(int priority, const T& data)
{
Pair pair(priority, data);
heap.insert(pair);
}
但是他没有指出我的错误,就草草结束了。这题我完全被他牵着鼻子走。我是越说越糊
涂,他大概是越听心里越摇头吧...
第k轮,说有一个类,里头有两个Date对象
class T
{
Date date1;
Date date2;
}
其中Date是形如12/05/2011这样的日期,date1 <= date2,这样T就表示一个时间段。
假如有两个T类型的变量a,b,如果a和b代表的时间段之间没有gap, 也就是a和b
overlap, 则集合{a, b}是连续的。然后他解释扩展到多个时间段,什么情况下他们的
集合是连续的。
我很快发现,每个Date在时间轴上是一个点,每个时间段T的变量是时间轴上的一条线
段,这题完全可以等同于
class Seg
{
int start;
int end;
}
其中 start <= end, 这样Seg就表示数轴上的线段。两条线段如果overlap,包括
overlap于一个点,则连续。他无非想用时间这个概念来使得问题看起来更复杂些。
我和他指出了这个事实,说我下面就化归到数轴上的线段问题来做。
他的问题是,给你一个T类型变量的list,如何判断这个list是连续的还是不连续的。
我一开始就想到并和他提到了,也许可以排序一下。因为我觉得递归是大杀器,鬼使神
差的说我先用递归的方法来做吧。结果越做越陷入死胡同,发现总是有很多特殊情况。
比如前面的三条线段是[4, 6], [8, 10], [2, 3],是不连续的,但最后一条线段是[1
, 11]的话整个list又连续了。
我在白板上写了段递归的代码,发现不对,又改,还是不对,再改,还是无解。眼看时
间不多了,他突然说,为什么不预处理一下?
预处理?莫非就是我开始想到的排序?我马上跟他提到了排序,说我开始也想过的,于
是在白板上排序了一个具体例子。
发现解决问题就容易了:
排序后,如果第一条线段和第二条线段不连续,则整个list不连续,可以返回false,
如果连续,则merge这两条线段,然后再考察merge后的线段和第三条线段,最后或者遍
历完所有的线段,或者中途就返回false。
但是他说面试时间要结束了,我没有时间coding了。我和他解释说我面到最后一轮,大
脑都不太转了,排序的方法我开始也想到过,可惜我想先用递归来实现,没有坚持那个
想法。
最后还是被拒了,官方解释是does not meet the position's technical bar
这样被拒合乎情理么?我知道这三轮的表现都不完美,但也不能一棍子否认吧。
第i轮代码不够优化,但是代码还是正确且没有bug的。以前面别的公司有几个bug, 被
拒我也能理解。而且我的方法是可以解决不从根开始,也不从叶子结束的general case。
第j轮主要还是我一开始假定的接口和他的不一样,导致整个过程被他牵着鼻子走,没
有把握主动权。其实我一开始说的Enqueue的接口,正是网上书上常见的接口,而不是
他的那个要多一个参数,我应该先和他提出我的接口也是合理的,然后再按他的接口做
,而不是简单否定自己先。
第k轮被提示才做出来是硬伤,但是我开始也想到这个提示的。而且我递归的时候,一
直keep talking, 一直在讲我的想法。我听有人说,面试官最喜欢你按照他的指引,一
步一步达到最优解的,这轮面试不就是这样发展的么?
肯定这三轮深刻影响了他们group的讨论结果,做出了我没有达到他们的technical bar
的结论。
我真不理解他们的要求是否就那么高, 我还需要提高哪些方面,要复习准备到什么样的
程度才能meet the bar呢?