p*****d 发帖数: 126 | 1 今天面试被鄙视了,说我的代码不符合他们找的经验,:〈
反正鄙视我了,我就把这题放出来,大家看看怎么做最好,对后人也是帮助
Complete the body of the following function given it's prototype in
either C or C++. You may change the prototype or constrain the input
as long as you justify your choices.
/** Return the index in array data of the element closest to or
equal to value. The array data has exactly data_count
elements. */
size_t find_nearest (int value, const int* data, size_t data_count); |
p*****d 发帖数: 126 | 2 我把我的被鄙视的代码拿出来,明白人看看我是哪里被鄙视了
#define ABSDelta(a,b) ((unsigned int)((((a)>(b))?((a)-(b)):((b)-(a)))))
size_t find_nearest (int value, const int* data, size_t data_count)
{
size_t inx=0,i=0;
size_t dlt=0,MinDlt=(size_t)(-1);
if((data==NULL)||(data_count==0))
return -1;
while(i
{
dlt=ABSDelta(value,*(data+i));
if(dlt==0)
{
inx=i;
break;
}
else if(dlt>=MinDlt)
{
i++;
}
else
{
MinDlt=dlt;
inx=i++;
}
}
return inx;
} |
s***e 发帖数: 403 | 3 size_t findNearest(const int value, const int* data, const size_t count)
{
assert(data);
size_t i;
size_t i_nearest = 0;
int best_approach = MAX_INT;
for(i = 0; i < count; ++i)
{
int diff = abs(data[i] - value);
if (diff == 0)
{
i_nearest = i;
break;
}
else if (diff < best_approach)
{
best_approach = diff;
i_nearest = i;
}
}
return i_nearest;
} |
s*****r 发帖数: 43070 | 4 MinDlt是unsigned, 而data是signed,不能直接比较
【在 p*****d 的大作中提到】 : 我把我的被鄙视的代码拿出来,明白人看看我是哪里被鄙视了 : #define ABSDelta(a,b) ((unsigned int)((((a)>(b))?((a)-(b)):((b)-(a))))) : size_t find_nearest (int value, const int* data, size_t data_count) : { : size_t inx=0,i=0; : size_t dlt=0,MinDlt=(size_t)(-1); : if((data==NULL)||(data_count==0)) : return -1; : while(i: {
|
J****3 发帖数: 427 | 5 我觉得是你判断数组为null那里吧, return type是size_t,return -1 不好吧
【在 p*****d 的大作中提到】 : 我把我的被鄙视的代码拿出来,明白人看看我是哪里被鄙视了 : #define ABSDelta(a,b) ((unsigned int)((((a)>(b))?((a)-(b)):((b)-(a))))) : size_t find_nearest (int value, const int* data, size_t data_count) : { : size_t inx=0,i=0; : size_t dlt=0,MinDlt=(size_t)(-1); : if((data==NULL)||(data_count==0)) : return -1; : while(i: {
|
J****3 发帖数: 427 | 6 如果diff > INT_MAX 怎么办?
【在 s***e 的大作中提到】 : size_t findNearest(const int value, const int* data, const size_t count) : { : assert(data); : size_t i; : size_t i_nearest = 0; : int best_approach = MAX_INT; : for(i = 0; i < count; ++i) : { : int diff = abs(data[i] - value); : if (diff == 0)
|
J****3 发帖数: 427 | 7 如果diff > INT_MAX 怎么办?
【在 s***e 的大作中提到】 : size_t findNearest(const int value, const int* data, const size_t count) : { : assert(data); : size_t i; : size_t i_nearest = 0; : int best_approach = MAX_INT; : for(i = 0; i < count; ++i) : { : int diff = abs(data[i] - value); : if (diff == 0)
|
p*****d 发帖数: 126 | 8 我感觉你这个代码由问题。
你的MAX_INT 按照字面上的意思是应该是2的31次方-1
如果value=(2的31次方-1) 而数组中的一个元素是一个负数,比如-2,那diff就等于
负的2的31次方+1,负的值小于0,而实际你想得到的是个正值(2的31次方+1)
diff应该为unsigned 这样能表示的范围会从0到2的32次方-1,如果diff是unsigned的
话value -(-2) 就是可正确的表示了,因为2的31次方+1在0到2的32次方-1内
【在 s***e 的大作中提到】 : size_t findNearest(const int value, const int* data, const size_t count) : { : assert(data); : size_t i; : size_t i_nearest = 0; : int best_approach = MAX_INT; : for(i = 0; i < count; ++i) : { : int diff = abs(data[i] - value); : if (diff == 0)
|
p*****d 发帖数: 126 | 9 错了,unsigned和singed的比较会被转换为unsigned.
我故意使用unsigned来作为绝对值差这样我的表示范围可以从0-2的32次方-1,而不是
负的2的31次方到正的2的31次方-1
【在 s*****r 的大作中提到】 : MinDlt是unsigned, 而data是signed,不能直接比较
|
w*********0 发帖数: 147 | 10 应该也可以拿该value把array都剪过去一遍,然后找绝对值中的最小值吧。。但是感觉
complexity都是O(n)。。 |
|
|
p*****d 发帖数: 126 | 11 其实我故意想return 0xffffffff的,但是我觉得写-1更专业?
没准我应该写return (size_t)-1
【在 J****3 的大作中提到】 : 我觉得是你判断数组为null那里吧, return type是size_t,return -1 不好吧
|
s***e 发帖数: 403 | 12 abs返回的就是一个int。所以这里没法处理。
【在 p*****d 的大作中提到】 : 我感觉你这个代码由问题。 : 你的MAX_INT 按照字面上的意思是应该是2的31次方-1 : 如果value=(2的31次方-1) 而数组中的一个元素是一个负数,比如-2,那diff就等于 : 负的2的31次方+1,负的值小于0,而实际你想得到的是个正值(2的31次方+1) : diff应该为unsigned 这样能表示的范围会从0到2的32次方-1,如果diff是unsigned的 : 话value -(-2) 就是可正确的表示了,因为2的31次方+1在0到2的32次方-1内
|
p*****d 发帖数: 126 | 13 所以我的macro就很给力啊,我的macro被cast成unsigned了,我的表示空间就大了,不
明白哪里被鄙视了
#define ABSDelta(a,b) ((unsigned int)((((a)>(b))?((a)-(b)):((b)-(a)))))
【在 s***e 的大作中提到】 : abs返回的就是一个int。所以这里没法处理。
|
s***e 发帖数: 403 | 14 我觉得是你的那个while循环不漂亮。而且你确定你的那个macro能解决这个问题么?这
里a-b仍然是有可能溢出的。要不去看看汇编码。
【在 p*****d 的大作中提到】 : 所以我的macro就很给力啊,我的macro被cast成unsigned了,我的表示空间就大了,不 : 明白哪里被鄙视了 : #define ABSDelta(a,b) ((unsigned int)((((a)>(b))?((a)-(b)):((b)-(a)))))
|
p*****d 发帖数: 126 | 15 while循环可能是个不好的地方。
我隐约感觉这可能是一个原因,人家希望看到for?
你可以找个例子证明我的macro解决不了问题的
【在 s***e 的大作中提到】 : 我觉得是你的那个while循环不漂亮。而且你确定你的那个macro能解决这个问题么?这 : 里a-b仍然是有可能溢出的。要不去看看汇编码。
|
s***e 发帖数: 403 | 16 如果是while的话,我想这样写
size_t i = 0;
const char* last = data + count;
while(data != last)
{
...
++data, ++i;
}
然后你可以解释说,这样访问的话指针上的数据是连贯的,有助于利用cpu的cache。反
过来用for你可以解释说,这样的话便于用openmp之类的并行化。 |
p*****d 发帖数: 126 | 17 给解释一下,为什么这样访问有助于cpu的cache, 而我的那个方法比这种办法在cache
上差到哪里?
【在 s***e 的大作中提到】 : 如果是while的话,我想这样写 : size_t i = 0; : const char* last = data + count; : while(data != last) : { : ... : ++data, ++i; : } : 然后你可以解释说,这样访问的话指针上的数据是连贯的,有助于利用cpu的cache。反 : 过来用for你可以解释说,这样的话便于用openmp之类的并行化。
|
b*******e 发帖数: 123 | 18 是不是要求用stl库?可以用 min_element.
size_t find_nearest (int value, const int* data, size_t data_count){
if(data_count == 0) throw 1;
return min_element(data,data+data_count, [&](int x, int y){return abs(x-
value) < abs(y-value);}) -data;
} |
p*****d 发帖数: 126 | 19 我觉得有道理,面试前他们专门问我对C++ 的理解有多少,
我说我明白,但是坦白说,我的经验大部分是C和汇编,硬件,我估计他们在考我C++
【在 b*******e 的大作中提到】 : 是不是要求用stl库?可以用 min_element. : size_t find_nearest (int value, const int* data, size_t data_count){ : if(data_count == 0) throw 1; : return min_element(data,data+data_count, [&](int x, int y){return abs(x- : value) < abs(y-value);}) -data; : }
|
u*****o 发帖数: 1224 | |
|
|
s***e 发帖数: 403 | 21 因为你的内存访问是连续的,这样cache hit的概率会高。不过好像那么做其实也一样
……
看一下CSAPP的优化一章。
cache
【在 p*****d 的大作中提到】 : 给解释一下,为什么这样访问有助于cpu的cache, 而我的那个方法比这种办法在cache : 上差到哪里?
|
s***e 发帖数: 403 | 22 如果是C++的话,输入的为什么是
const int* a, const size_t count
而不是
template
ForwardIterator i_start, ForwardIterator i_end
【在 p*****d 的大作中提到】 : 我觉得有道理,面试前他们专门问我对C++ 的理解有多少, : 我说我明白,但是坦白说,我的经验大部分是C和汇编,硬件,我估计他们在考我C++
|
J****3 发帖数: 427 | 23 如果真是这样就没办法了。。 marco is evil
【在 p*****d 的大作中提到】 : 我觉得有道理,面试前他们专门问我对C++ 的理解有多少, : 我说我明白,但是坦白说,我的经验大部分是C和汇编,硬件,我估计他们在考我C++
|
j*****o 发帖数: 394 | 24 我也觉得是while循环写的有问题。。。
换我是面试官就会觉得不够优美。。。
seele的code就很简洁直观
【在 s***e 的大作中提到】 : 我觉得是你的那个while循环不漂亮。而且你确定你的那个macro能解决这个问题么?这 : 里a-b仍然是有可能溢出的。要不去看看汇编码。
|