n*******t
发帖数: 6 | 1 我说，“大姐，array.size()，的复杂度是O（n）啊！第二种方法，用了.size(),所以
复杂度至少是O(n), 不能更少了。"
对方说:" 那你给的第一个解法也要用到.size(),那除掉.size()那步，我可以专门选一
个极端的情况，让第二个走n/2， 第一个走 n。 所以第二个快。"
为了说某种算法快，可以去掉这个算法里面O(n)的部分，然后选一个极端的情况，不到
n步，然后这个算法就比另一个O(n)快了？
～～～～～～～～～～～～～～～～～
店面，出了两道题，每道我都给出了两种解法，写出了code。
刚才feedback没有在第一时间给出最优解法，超时5分钟，要求加面。
我写code之前问，有两种解法，这样这样。都有利弊，利在哪，弊在哪。你要哪种？
对方说，随便。
然后我就写了。然后对方说，你没有第一时间给出最优解。
我说，大姐你让我随便的啊。再说都是O(n)啊。
然后对方说，我说过吗？ anyway， 在某些特殊情况下，第二种，要更快，所以你的解
不是最优解。
我说，“大姐，array.size()，的复杂度是O（n）啊！第二种方法，用了.size(),所以
复杂度至少是O(n), 不能更少了。"
对方说:" 那你给的第一个解法也要用到.size(),那除掉.size()那步，我可以专门选一
个极端的情况，让第二个走n/2， 第一个走 n。 所以第二个快。"
为了说某种算法快，可以去掉这个算法里面O(n)的部分，然后选一个极端的情况，不到
n部，然后这个算法就比另一个O(n)快了？
此外，我code里面有，
i=0;
A[i++]=3; 对方问了我好多遍，啥意思。我说是A[0]=3.
对方反复确认为啥是A[0].
花了一分钟解释，对方不太明白，说是A[1]
对方问， are you sure 我说，我sure。对方无语。
后对方又让我写第二题第二种解法的伪代码。
然后我写完了，又改了改，基本上算bug free code了。
对方埋怨我有几行没有空格。
现在都default每到题都要用两种解法吗？要是问题复杂，只有一种解法呢？ |
g*******y
发帖数: 1930 | |
r*******g
发帖数: 1335 | |
S*******C
发帖数: 822 | |
J*****e
发帖数: 158 | 5 都是哪些题？最近面的吗？
【在 n*******t 的大作中提到】
: 我说，“大姐，array.size()，的复杂度是O（n）啊！第二种方法，用了.size(),所以
: 复杂度至少是O(n), 不能更少了。"
: 对方说:" 那你给的第一个解法也要用到.size(),那除掉.size()那步，我可以专门选一
: 个极端的情况，让第二个走n/2， 第一个走 n。 所以第二个快。"
: 为了说某种算法快，可以去掉这个算法里面O(n)的部分，然后选一个极端的情况，不到
: n步，然后这个算法就比另一个O(n)快了？
: ～～～～～～～～～～～～～～～～～
: 店面，出了两道题，每道我都给出了两种解法，写出了code。
: 刚才feedback没有在第一时间给出最优解法，超时5分钟，要求加面。
: 我写code之前问，有两种解法，这样这样。都有利弊，利在哪，弊在哪。你要哪种？
|
x***z
发帖数: 89 | |
q*****a
发帖数: 237 | 7 你题目说清楚啊。。
不一定要求你写出最优解 但是要求你可以理解哪个解法好 神情况好之类的 |
q*****a
发帖数: 237 | 8 a[i++] 这种东西。。真的就是增加阅读难度，非常不好的用法。 |
j******o
发帖数: 4219 | 9 现在人员过剩，面试就像以前宫里选妃，看外貌看才华还要看出身。 |
g*******y
发帖数: 1930 | 10 it's probably surprising, but in c++ 98, complexity of list:: size may be up
to linear
【在 x***z 的大作中提到】
: list.size()时间复杂度是 o(1)
|
|
|
R*********4
发帖数: 293 | 11 A[i++] A[++i++]
这些东西，只有谭浩强的测试题才用。而且懂这个东西一点意义都没有。为了条例清楚
，你尽量避免用这个东西，特别是在面试中。
主要没看到你的题目，我不好评论。
似乎我的感觉是，考试题目，是想要你用 二分法（B search）。但是你用了线性。
这个似乎是差了几个数量级。
比如一个array是事先排好序的。加入有一百万个，用B search找到想要的东西，次数
一般不会超过50次。你线性下去i++，那不知道有多少次了。
这是一小段测试程序:假设都是10000次
time_t start, finish;
int num = 0;
list col;
start = clock();
for(int i=0;i<10000;++i){
col.push_back(i);
num += col.size();
}
finish = clock();
cout<
col.clear();
start = clock();
for(int i=0;i<10000;++i){
col.push_back(i);
}
finish = clock();
cout<
return 0;
得出的结果是这样的:
450
10
看见没？？？ 差了45倍，所以如果您在循坏中使用 list.size()，会延迟很多时间的
。这还是10000，如果是100万，1000万，那会宕机的。
要我面试你，(￣▽￣)"，你肯定挂了。把.size()当成o(1)，是严重错误，而且在很多
手册里，是明确不准用.size()。
B search 一般结构写成这样就行
int BSearch(list A, int min, int max)
{
//
if( xxxxx )
{
min = (min+max)/2;
return BSearch(A,min,max);
}
else if(xxxx)
{
max = (min+max)/2;
return BSearch(A,min, max);
}
eles
{
return A[(min+max)/2];
}
} |
n*******t
发帖数: 6 | 12 你说反了。是面试官不知道.size()是O（n）
碰到这种情况咋办？直接说，你错了。会不会影响到对方的心情，然后挑你刺，比如你
第几行，之前没有空格之类的？
【在 R*********4 的大作中提到】
: A[i++] A[++i++]
: 这些东西，只有谭浩强的测试题才用。而且懂这个东西一点意义都没有。为了条例清楚
: ，你尽量避免用这个东西，特别是在面试中。
: 主要没看到你的题目，我不好评论。
: 似乎我的感觉是，考试题目，是想要你用 二分法（B search）。但是你用了线性。
: 这个似乎是差了几个数量级。
: 比如一个array是事先排好序的。加入有一百万个，用B search找到想要的东西，次数
: 一般不会超过50次。你线性下去i++，那不知道有多少次了。
: 这是一小段测试程序:假设都是10000次
: time_t start, finish;
|
R*********4
发帖数: 293 | |
S********t
发帖数: 3431 | 14 完整的说法是，c++11之前，list::size()是constant or maybe up to linear
C++11以及之后的standard里面，list::size()是constant
再完整的说，某些编译器，比如老版本的gcc，即便是support c++11，也有violation
，比如可能会violate 这个c++11里面对list::size()规定的constant time
complexity的standard。
当然最后还是说写stl的人脑子进水了，之前居然搞个O(n)的size()出来。。。
话说leetcode里面有道题当年刷的时候莫名其妙的time exceeded，后来发现就是list:
:size()搞的鬼
【在 n*******t 的大作中提到】
: 你说反了。是面试官不知道.size()是O（n）
: 碰到这种情况咋办？直接说，你错了。会不会影响到对方的心情，然后挑你刺，比如你
: 第几行，之前没有空格之类的？
|
k***e
发帖数: 1931 | 15 ＋＋i＋＋应该废除，孔乙己，没卵用。
但是A[i++]或者A[++i]都搞不清楚是不是该考虑一下自己到底是不是真的会C++/Java/C
#了？
【在 R*********4 的大作中提到】
: A[i++] A[++i++]
: 这些东西，只有谭浩强的测试题才用。而且懂这个东西一点意义都没有。为了条例清楚
: ，你尽量避免用这个东西，特别是在面试中。
: 主要没看到你的题目，我不好评论。
: 似乎我的感觉是，考试题目，是想要你用 二分法（B search）。但是你用了线性。
: 这个似乎是差了几个数量级。
: 比如一个array是事先排好序的。加入有一百万个，用B search找到想要的东西，次数
: 一般不会超过50次。你线性下去i++，那不知道有多少次了。
: 这是一小段测试程序:假设都是10000次
: time_t start, finish;
|
l******8
发帖数: 1691 | 16 这面试的女老印？明显属于完全不会啊。
【在 n*******t 的大作中提到】
: 我说，“大姐，array.size()，的复杂度是O（n）啊！第二种方法，用了.size(),所以
: 复杂度至少是O(n), 不能更少了。"
: 对方说:" 那你给的第一个解法也要用到.size(),那除掉.size()那步，我可以专门选一
: 个极端的情况，让第二个走n/2， 第一个走 n。 所以第二个快。"
: 为了说某种算法快，可以去掉这个算法里面O(n)的部分，然后选一个极端的情况，不到
: n步，然后这个算法就比另一个O(n)快了？
: ～～～～～～～～～～～～～～～～～
: 店面，出了两道题，每道我都给出了两种解法，写出了code。
: 刚才feedback没有在第一时间给出最优解法，超时5分钟，要求加面。
: 我写code之前问，有两种解法，这样这样。都有利弊，利在哪，弊在哪。你要哪种？
|
