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仍然是有可能溢出的。要不去看看汇编码。
|
