O******i
发帖数: 269 | 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呢? | y*******g
发帖数: 6599 | 2 被拒了还是爆一下公司名字吧
【在 O******i 的大作中提到】
: 最近面了一家IT大公司被拒，一共经历了N轮技术面试。自己感觉还不算太坏，但也有
: 三轮发挥不太完美，所以心里很没底。
: 结果还是被拒了。
: 下面是这三轮的详细经历，请大家探讨一下大公司招人的标准。
: 第i轮是找二叉树从根开始的所有路径，使得该路径上所有节点的值之和等于一个给定
: 的数。我犯了一个战略错误，因为我在准备过程中看过CarrerCup的更通用的解法，不
: 要求从根开始，也不要求到叶子结束，于是我直接用了那个思路，在白板上写下了类似
: 下面的代码
: void FindPath(Node* root, int sum, int path[], int level)
: {
| s******n
发帖数: 3946 | 3 第一个，思路递归马上能写出来是好，就那个每次叠加的思路确实有缺陷，一般写多递
归的人会对这个比较敏感的。
优先队列应该是指针比较好，搞一引用什么意思呢？假设你加一个data是不是都要执行
operator=函数，而且每次置换元素的时候都要执行operator=？如果我是面试会提示这
个是不是效率有点问题。
第三条一开始思路就就歪了，不过如果我是面试的会一开始就指出来，呵呵，这个面试
官比较坏。 | O******i
发帖数: 269 | 4 第1题我杀鸡用牛刀了。其实那个利用从根开始的特殊要求我原本也是会写的，就是想
用一个general的方法在他面前show off一下，没想到弄巧成拙，这样一来，我必须要
累加了。如果不要求从根开始，则必须倒着累加回溯的。
【在 s******n 的大作中提到】
: 第一个，思路递归马上能写出来是好，就那个每次叠加的思路确实有缺陷，一般写多递
: 归的人会对这个比较敏感的。
: 优先队列应该是指针比较好，搞一引用什么意思呢？假设你加一个data是不是都要执行
: operator=函数，而且每次置换元素的时候都要执行operator=？如果我是面试会提示这
: 个是不是效率有点问题。
: 第三条一开始思路就就歪了，不过如果我是面试的会一开始就指出来，呵呵，这个面试
: 官比较坏。
| O******i
发帖数: 269 | 5 优先队列的接口设计见仁见智吧。
Mark Allen Weiss的数据结构书上就这样的:
void insert(const Comparable& x);
void deleteMin();
void deleteMin(Comparable& minItem);
其实面试官要单独引入优先数这个，是考虑相同的数据可能具有不同的优先数，所以把
优先数和数据分离开来，数据就相当于satellite data了，例如二叉树中附属每个节点
的额外数据域。
【在 s******n 的大作中提到】
: 第一个，思路递归马上能写出来是好，就那个每次叠加的思路确实有缺陷，一般写多递
: 归的人会对这个比较敏感的。
: 优先队列应该是指针比较好，搞一引用什么意思呢？假设你加一个data是不是都要执行
: operator=函数，而且每次置换元素的时候都要执行operator=？如果我是面试会提示这
: 个是不是效率有点问题。
: 第三条一开始思路就就歪了，不过如果我是面试的会一开始就指出来，呵呵，这个面试
: 官比较坏。
| p*****2
发帖数: 21240 | | q****x
发帖数: 7404 | 7 应该不是M。三轮不好就走人了。
【在 p*****2 的大作中提到】
: 是不是G呀？
| O******i
发帖数: 269 | 8 是MFLAG这样的公司，具体哪个还是不说好，毕竟签了NDA。
不过我的体会是，不管哪个大公司，面试都可能遇到不nice的人，也就是所谓的
anti loop, 这种情况只能自求多福了。当然不能只怪运气不好，自己也要准备更充分
一点才是。 | p*****2
发帖数: 21240 | 9
如果是我肯定挂。
【在 O******i 的大作中提到】
: 是MFLAG这样的公司，具体哪个还是不说好，毕竟签了NDA。
: 不过我的体会是，不管哪个大公司，面试都可能遇到不nice的人，也就是所谓的
: anti loop, 这种情况只能自求多福了。当然不能只怪运气不好，自己也要准备更充分
: 一点才是。
| p*****2
发帖数: 21240 | | | | p*****2
发帖数: 21240 | 11 第一题那个path如果用arraylist好搞，如果C的话怎么定义长度呀？假设一个足够大的
长度，还是先遍历一遍找到层数呢？ | O******i
发帖数: 269 | 12 CareerCup是先用一个函数求出最大深度D,
然后 int* path = new int[D];
【在 p*****2 的大作中提到】
: 第一题那个path如果用arraylist好搞，如果C的话怎么定义长度呀？假设一个足够大的
: 长度，还是先遍历一遍找到层数呢？
| p*****2
发帖数: 21240 | 13
是。这题我只是看过没有自己练过。
【在 O******i 的大作中提到】
: CareerCup是先用一个函数求出最大深度D,
: 然后 int* path = new int[D];
| l*****a
发帖数: 14598 | 14 use vector whose internal implementation is dynamic array
to dynamically store the path
【在 p*****2 的大作中提到】
: 第一题那个path如果用arraylist好搞，如果C的话怎么定义长度呀？假设一个足够大的
: 长度，还是先遍历一遍找到层数呢？
| g*********8
发帖数: 64 | 15 楼主的第一道题我写的是这样
void FindPaths_sum(tNode* root,int sum, vector v){
if(root==NULL) return;
v.insert(v.begin(),root->value);
int tmp=sum;
vector left=v,right=v;
for(int i=v.size()-1;i>=0;i--){
tmp-=v[i];
if(tmp==0){
Printlist(v,i);
}
}
FindPaths_sum(root->left,sum,left);
FindPaths_sum(root->right,sum,right);
}
第二道题：priority_queue不就是heap吗?这个stl不是有定义吗？
priority_queue, greater> min_heap;
priority_queue max_heap;
实现就是heap的操作：siftup, siftdown，具体参见编程珠玑
第三道题是不是可以这样想
1）sort all start_i and end_i together
2) scan from the first time stamp (start_i or end_i)
3) if we meet an end_i before we meet all start_i, then all interval s are
not consistent otherwise it is consistent
4) the time complexity is O(nlogn) mainly on sorting
我的灵感来自于编程之美第一章第9道题 | p*****2
发帖数: 21240 | 16 又来C++了呀？要我就用C#里的List,或者ArrayList。
【在 l*****a 的大作中提到】
: use vector whose internal implementation is dynamic array
: to dynamically store the path
| p*****2
发帖数: 21240 | 17 void FindPaths_sum(tNode* root,int sum, vector v){
if(root==NULL) return;
//why insert at beginning? is it efficient?
v.insert(v.begin(),root->value);
int tmp=sum;
//Do you have to declare left and right?
vector left=v,right=v;
for(int i=v.size()-1;i>=0;i--){
tmp-=v[i];
if(tmp==0){
Printlist(v,i);
}
}
FindPaths_sum(root->left,sum,left);
FindPaths_sum(root->right,sum,right);
}
【在 g*********8 的大作中提到】
: 楼主的第一道题我写的是这样
: void FindPaths_sum(tNode* root,int sum, vector v){
: if(root==NULL) return;
:
: v.insert(v.begin(),root->value);
:
: int tmp=sum;
: vector left=v,right=v;
:
: for(int i=v.size()-1;i>=0;i--){
| p*****2
发帖数: 21240 | 18 感觉LZ的方法更对吧。第三步没明白。
第三道题是不是可以这样想
1）sort all start_i and end_i together
2) scan from the first time stamp (start_i or end_i)
3) if we meet an end_i before we meet all start_i, then all interval s are
not consistent otherwise it is consistent
4) the time complexity is O(nlogn) mainly on sorting | g*********8
发帖数: 64 | 19 Since there are many possible paths, so we can't pass vector& v to its
left and right child. We have to copy one to the left child and one to the
right child. v.insert(v.begin(),root->value) is same efficient with v.push_
back(root->value)
【在 p*****2 的大作中提到】
: void FindPaths_sum(tNode* root,int sum, vector v){
: if(root==NULL) return;
:
: //why insert at beginning? is it efficient?
: v.insert(v.begin(),root->value);
:
: int tmp=sum;
: //Do you have to declare left and right?
: vector left=v,right=v;
:
| g*********8
发帖数: 64 | 20 Let's say we have [1,4], [3,5],[2,6],[7,8]
we sort all time stamps to be 1,2,3,4,5,6,7,8
we scan through all time stamps, we find that when we meet 4, we only meet
three start point, which implies that there must be one interval that is not
overlapped with one another. Therefore, the sequence is not consistent.
are
【在 p*****2 的大作中提到】
: 感觉LZ的方法更对吧。第三步没明白。
: 第三道题是不是可以这样想
: 1）sort all start_i and end_i together
: 2) scan from the first time stamp (start_i or end_i)
: 3) if we meet an end_i before we meet all start_i, then all interval s are
: not consistent otherwise it is consistent
: 4) the time complexity is O(nlogn) mainly on sorting
| | | g*********8
发帖数: 64 | 21 恩，第三题想法不对，没有读懂题目，不好意思
是不是可以这样，先sort所有start point，然后从最小的start point开始，如果两个
interval overlap则合并，一直合并到最后，如果还剩一个interval则连续，否则就不
连续
struct interval{
int x;
int y;
interval(int a, int b):x(a),y(b){};
};
bool compare(interval i, interval j){
return (i.x
}
bool isConsistent( vectorxs, vectorys){
assert(xs.size()==ys.size());
vector v;
int n=xs.size();
int i,x,y;
for(i=0;i
interval in(xs[i],ys[i]);
v.push_back(in);
}
sort(v.begin(),v.end(),compare);
stack s;
vector result;
i=0;
while(1){
if(i>n-1) break;
x=v[i].x;
while(i+1
s.push(v[i+1]);
i++;
}
y=v[i].y;
while(!s.empty()){
y=max(y,s.top().y);
s.pop();
}
interval in(x,y);
result.push_back(in);
i++;
}
return result.size()==1;
}
望指正 | p*****2
发帖数: 21240 | 22 我觉得一个v应该够了吧？可以reuse呀。
its
【在 g*********8 的大作中提到】
: Since there are many possible paths, so we can't pass vector& v to its
: left and right child. We have to copy one to the left child and one to the
: right child. v.insert(v.begin(),root->value) is same efficient with v.push_
: back(root->value)
| p*****2
发帖数: 21240 | 23 这就是LZ的思路。
【在 g*********8 的大作中提到】
: 恩，第三题想法不对，没有读懂题目，不好意思
: 是不是可以这样，先sort所有start point，然后从最小的start point开始，如果两个
: interval overlap则合并，一直合并到最后，如果还剩一个interval则连续，否则就不
: 连续
: struct interval{
: int x;
: int y;
: interval(int a, int b):x(a),y(b){};
: };
: bool compare(interval i, interval j){
| g*********8
发帖数: 64 | 24 再看了一遍，同意。
【在 p*****2 的大作中提到】
: 这就是LZ的思路。
| g*********8
发帖数: 64 | 25 我觉得可能不行，用一个v，本质上还是copy，否则如果传引用的话，比如我右边的
traverse中加了一个结点到path上，左边立刻就加了一个，这个不对啊。
【在 p*****2 的大作中提到】
: 我觉得一个v应该够了吧？可以reuse呀。
:
: its
| B*******1
发帖数: 2454 | 26 How about this:
void printlist(vector &result)
{
for (int i = 0; i < result.size(); i++)
cout << result[i]->element << " ";
cout << " " << endl;
}
void FindPaths_sum(Node_t* root,int curSum, int target, vector &v)
{
if(root==NULL) return;
curSum += root->element;
if (curSum == target)
printlist(v);
v.push_back(root->left);
FindPaths_sum(root->left,curSum ,target, v);
v.pop_back();
v.push_back(root->right);
FindPaths_sum(root->right,curSum ,target, v);
v.pop_back();
}
【在 g*********8 的大作中提到】
: 我觉得可能不行，用一个v，本质上还是copy，否则如果传引用的话，比如我右边的
: traverse中加了一个结点到path上，左边立刻就加了一个，这个不对啊。
| l*****a
发帖数: 14598 | 27 why didn't u insert the current node to the vector?
give u a case that there is only one node whose value is target
what will happen with your code
v)
【在 B*******1 的大作中提到】
: How about this:
: void printlist(vector &result)
: {
: for (int i = 0; i < result.size(); i++)
: cout << result[i]->element << " ";
: cout << " " << endl;
: }
: void FindPaths_sum(Node_t* root,int curSum, int target, vector &v)
: {
: if(root==NULL) return;
| B*******1
发帖数: 2454 | 28 大牛果然看的仔细啊，我忘记提一开始我先把root的node push进去result vector，然
后再call这个functon。
我traverse 左右node的时候，在call进去的时候，已经把左右的nodepush到vector上
面了。
【在 l*****a 的大作中提到】
: why didn't u insert the current node to the vector?
: give u a case that there is only one node whose value is target
: what will happen with your code
:
: v)
| p*****2
发帖数: 21240 | 29 仰视大牛。Bayesian1, 你TC搞得如何了？
【在 B*******1 的大作中提到】
: 大牛果然看的仔细啊，我忘记提一开始我先把root的node push进去result vector，然
: 后再call这个functon。
: 我traverse 左右node的时候，在call进去的时候，已经把左右的nodepush到vector上
: 面了。
| B*******1
发帖数: 2454 | 30 下周有个onsite，很底层的工作，等onsite完再回头搞tc。
【在 p*****2 的大作中提到】
: 仰视大牛。Bayesian1, 你TC搞得如何了？
| | | l*****a
发帖数: 14598 | 31 this sounds reasonable
还需要确认的是，题中路径指的是根到叶结点，还是根到任意结点
【在 B*******1 的大作中提到】
: 大牛果然看的仔细啊，我忘记提一开始我先把root的node push进去result vector，然
: 后再call这个functon。
: 我traverse 左右node的时候，在call进去的时候，已经把左右的nodepush到vector上
: 面了。
| p*****2
发帖数: 21240 | 32 Good luck. 底层哥。
【在 B*******1 的大作中提到】
: 下周有个onsite，很底层的工作，等onsite完再回头搞tc。
| B*******1
发帖数: 2454 | 33 How about this one?
class Interval {
public:
Interval(int start_, int end_): start(start_),end(end_){}
int start;
int end;
};
bool comp(Interval &rhs, Interval &lhs)
{
return (rhs.start == lhs.start ? rhs.end < lhs.end : rhs.start < lhs.start);
}
bool check(vector &input)
{
int left = input[0].start;
int right = input[0].end;
for (int i = 1; i < input.size(); i++) {
if (right < input[i].start) {
return false;
} else {
right = max(input[i].end, right);
}
}
return true;
}
int main()
{
vector input;
input.push_back(Interval(4,6));
input.push_back(Interval(8,10));
input.push_back(Interval(2,3));
input.push_back(Interval(1,11));
sort(input.begin(), input.end(), comp);
bool result = check(input);
return 1;
}
【在 g*********8 的大作中提到】
: 恩，第三题想法不对，没有读懂题目，不好意思
: 是不是可以这样，先sort所有start point，然后从最小的start point开始，如果两个
: interval overlap则合并，一直合并到最后，如果还剩一个interval则连续，否则就不
: 连续
: struct interval{
: int x;
: int y;
: interval(int a, int b):x(a),y(b){};
: };
: bool compare(interval i, interval j){
| H***e
发帖数: 476 | 34 What is tc?
【在 p*****2 的大作中提到】
: Good luck. 底层哥。
| l***n
发帖数: 37 | 35 第三题想法可以这样做吗？ sort it based on the start point. then have a for
loop, go through the pair (s0,e0),(s1,e1),(s2,e2)........
we just need to make sure s(j)<=e(j-1). if it is not, we return false,
after the loop, we return true, since it is connected.
Does that make sense?
【在 O******i 的大作中提到】
: 最近面了一家IT大公司被拒，一共经历了N轮技术面试。自己感觉还不算太坏，但也有
: 三轮发挥不太完美，所以心里很没底。
: 结果还是被拒了。
: 下面是这三轮的详细经历，请大家探讨一下大公司招人的标准。
: 第i轮是找二叉树从根开始的所有路径，使得该路径上所有节点的值之和等于一个给定
: 的数。我犯了一个战略错误，因为我在准备过程中看过CarrerCup的更通用的解法，不
: 要求从根开始，也不要求到叶子结束，于是我直接用了那个思路，在白板上写下了类似
: 下面的代码
: void FindPath(Node* root, int sum, int path[], int level)
: {
| l***n
发帖数: 37 | 36 第三题想法可以这样做吗？ sort it based on the start point. then have a for
loop, go through the pair (s0,e0),(s1,e1),(s2,e2)........
we just need to make sure s(j)<=e(j-1). if it is not, we return false,
after the loop, we return true, since it is connected.
Does that make sense?
【在 p*****2 的大作中提到】
: 是不是G呀？
| l***n
发帖数: 37 | 37 第三题想法可以这样做吗？ sort it based on the start point. then have a for
loop, go through the pair (s0,e0),(s1,e1),(s2,e2)........
we just need to make sure s(j)<=e(j-1). if it is not, we return false,
after the loop, we return true, since it is connected.
Does that make sense?
not
【在 g*********8 的大作中提到】
: Let's say we have [1,4], [3,5],[2,6],[7,8]
: we sort all time stamps to be 1,2,3,4,5,6,7,8
: we scan through all time stamps, we find that when we meet 4, we only meet
: three start point, which implies that there must be one interval that is not
: overlapped with one another. Therefore, the sequence is not consistent.
:
: are
| i**d
发帖数: 357 | 38 你deleteMin返回引用，这是个很低级的错误。会让面试官觉得你C++的基本概念都没搞
清楚。
这个地方肯定让你失分不少...
他又问DeleteMin怎么写，我说T DeleteMin()或者T& DeleteMin(), 前者返回值，要调
用拷贝构造函数，因此慢。后者返回引用，快。他说后面那个有问题，然后画了个队列
，好像是说元素被删除出队列后，对象被析构了。
【在 O******i 的大作中提到】
: CareerCup是先用一个函数求出最大深度D,
: 然后 int* path = new int[D];
| O******i
发帖数: 269 | 39 we just need to make sure s(j)<=e(j-1). if it is not, we return false, else
we merge (s(j-1), e(j-1)) and (s(j), e(j)) then continue.
after the loop, we return true, since it is connected.
【在 l***n 的大作中提到】
: 第三题想法可以这样做吗？ sort it based on the start point. then have a for
: loop, go through the pair (s0,e0),(s1,e1),(s2,e2)........
: we just need to make sure s(j)<=e(j-1). if it is not, we return false,
: after the loop, we return true, since it is connected.
: Does that make sense?
:
: not
| w****x
发帖数: 2483 | 40 楼主那个求和的因该用O(N)的， 你把sum做为参数传下去就不用每次计算一遍了， 这
是很明显的重复计算， O(NlogN)的解法是任意节点做起点的情况 | | | g*********8
发帖数: 64 | 41 受教受教，谢谢啦，这个方法很好，解决了空间重复的问题
v)
【在 B*******1 的大作中提到】
: How about this one?
: class Interval {
: public:
: Interval(int start_, int end_): start(start_),end(end_){}
: int start;
: int end;
: };
: bool comp(Interval &rhs, Interval &lhs)
: {
: return (rhs.start == lhs.start ? rhs.end < lhs.end : rhs.start < lhs.start);
| g*********8
发帖数: 64 | 42 en , I think it makes sense. My code is actually a little overkill. It
actually fits for the problem that given a interval [a,b] and a bunch of
intervals vector xs and vector ys. Determine if [a,b] is contained
in those intervals.
【在 l***n 的大作中提到】
: 第三题想法可以这样做吗？ sort it based on the start point. then have a for
: loop, go through the pair (s0,e0),(s1,e1),(s2,e2)........
: we just need to make sure s(j)<=e(j-1). if it is not, we return false,
: after the loop, we return true, since it is connected.
: Does that make sense?
:
: not
| p****j
发帖数: 4762 | | O******i
发帖数: 269 | 44 利用从根开始这个特殊要求，把current_sum作为参数传下去，是可以达到O(N)
不过考虑到PrintPath是O(lgN), 则如果要打印path的话，总体复杂度是否还是要O(N*
lgN)？
【在 w****x 的大作中提到】
: 楼主那个求和的因该用O(N)的， 你把sum做为参数传下去就不用每次计算一遍了， 这
: 是很明显的重复计算， O(NlogN)的解法是任意节点做起点的情况
| w****x
发帖数: 2483 | | O******i
发帖数: 269 | 46 嗯，只有在当前节点发现匹配的时候才打印path, 不是每个节点都要打印。
杀鸡用牛刀真是弄巧成拙啊
从根开始的解法用鸡刀就可以了，O(N)
不一定从根开始的解法要用牛刀，O(N*lgN)
题目要求从根开始，用牛刀做，复杂度大了，而且面官会怀疑你是背题啊。
【在 w****x 的大作中提到】
: 除非是打印所有情况
|
|
