yi?民工还在这里当版主呢？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

yi?民工还在这里当版主呢？

yi?民工还在这里当版主呢？# PDA - 掌中宝

p*d2014-10-01 07:10

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);

m*r2014-10-01 07:10

2 楼

htc 的m8怎么样？
target这周有个49块的deal,看着不错呀

p*d2014-10-01 07:10

3 楼

我把我的被鄙视的代码拿出来，明白人看看我是哪里被鄙视了
#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;
}

a*x2014-10-01 07:10

4 楼

鬼啊

【在 m*r 的大作中提到】

: htc 的m8怎么样？
: target这周有个49块的deal,看着不错呀

s*e2014-10-01 07:10

5 楼

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;
}

m*r2014-10-01 07:10

6 楼

8pang, 你还活着？

【在 a***x 的大作中提到】

: 鬼啊

s*r2014-10-01 07:10

7 楼

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: {

a*x2014-10-01 07:10

8 楼

很难讲啊。。。

【在 m*r 的大作中提到】

: 8pang, 你还活着？

J*32014-10-01 07:10

9 楼

我觉得是你判断数组为null那里吧， return type是size_t，return -1 不好吧

【在 p*****d 的大作中提到】

J*32014-10-01 07:10

10 楼

如果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*32014-10-01 07:10

11 楼

如果diff > INT_MAX 怎么办？

【在 s***e 的大作中提到】

p*d2014-10-01 07:10

12 楼

我感觉你这个代码由问题。
你的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 的大作中提到】

p*d2014-10-01 07:10

13 楼

错了，unsigned和singed的比较会被转换为unsigned.
我故意使用unsigned来作为绝对值差这样我的表示范围可以从0-2的32次方-1，而不是
负的2的31次方到正的2的31次方-1

【在 s*****r 的大作中提到】

: MinDlt是unsigned, 而data是signed，不能直接比较

w*02014-10-01 07:10

14 楼

应该也可以拿该value把array都剪过去一遍，然后找绝对值中的最小值吧。。但是感觉
complexity都是O(n)。。

p*d2014-10-01 07:10

15 楼

其实我故意想return 0xffffffff的，但是我觉得写-1更专业？
没准我应该写return （size_t）-1

【在 J****3 的大作中提到】

: 我觉得是你判断数组为null那里吧， return type是size_t，return -1 不好吧

s*e2014-10-01 07:10

16 楼

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*d2014-10-01 07:10

17 楼

所以我的macro就很给力啊，我的macro被cast成unsigned了，我的表示空间就大了，不
明白哪里被鄙视了
#define ABSDelta(a,b) ((unsigned int)((((a)>(b))?((a)-(b)):((b)-(a)))))

【在 s***e 的大作中提到】

: abs返回的就是一个int。所以这里没法处理。

s*e2014-10-01 07:10

18 楼

我觉得是你的那个while循环不漂亮。而且你确定你的那个macro能解决这个问题么？这
里a-b仍然是有可能溢出的。要不去看看汇编码。

【在 p*****d 的大作中提到】

: 所以我的macro就很给力啊，我的macro被cast成unsigned了，我的表示空间就大了，不
: 明白哪里被鄙视了
: #define ABSDelta(a,b) ((unsigned int)((((a)>(b))?((a)-(b)):((b)-(a)))))

p*d2014-10-01 07:10

19 楼

while循环可能是个不好的地方。
我隐约感觉这可能是一个原因，人家希望看到for?
你可以找个例子证明我的macro解决不了问题的

【在 s***e 的大作中提到】

: 我觉得是你的那个while循环不漂亮。而且你确定你的那个macro能解决这个问题么？这
: 里a-b仍然是有可能溢出的。要不去看看汇编码。

s*e2014-10-01 07:10

20 楼

如果是while的话，我想这样写
size_t i = 0;
const char* last = data + count;
while(data != last)
{
...
++data, ++i;
}
然后你可以解释说，这样访问的话指针上的数据是连贯的，有助于利用cpu的cache。反
过来用for你可以解释说，这样的话便于用openmp之类的并行化。

p*d2014-10-01 07:10

21 楼

给解释一下，为什么这样访问有助于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*e2014-10-01 07:10

22 楼

是不是要求用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*d2014-10-01 07:10

23 楼

我觉得有道理，面试前他们专门问我对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;
: }