我在上次面试中遇到的一个问题是:

设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。

有什么想法吗?


当前回答

好问题!

这花了我大约35秒的时间思考并写下:

int f(int n){
    static int originalN=0;
    if (n!=0)
        originalN=n;
    return n-originalN;
}

其他回答

适用于n=[0..2^31-1]

int f(int n) {
  if (n & (1 << 31)) // highest bit set?
    return -(n & ~(1 << 31)); // return negative of original n
  else
    return n | (1 << 31); // return n with highest bit set
}
int f(const int n)  {
    static int last_n;

    if (n == 0)
        return 0;
    else if (n == last_n)
        return -n;
    else
    {
        last_n = n;
        return n;
    }
}

哈克,但正确。

事实上,我并没有试图给出问题本身的解决方案,但我有几点意见,因为问题表明,提出这个问题是(工作?)面试的一部分:

我会先问“为什么需要这样的函数?这是什么更大的问题?”而不是试图当场解决实际提出的问题。这表明了我是如何思考和解决这样的问题的。谁知道?这甚至可能是在一次采访中首先提出这个问题的真正原因。如果答案是“没关系,假设它是需要的,并告诉我如何设计这个功能。”我会继续这样做。然后,我将编写我将使用的C#测试用例代码(显而易见:从int.MinValue到int.MaxValue的循环,对于该范围内的每个n调用f(f(n)),并检查结果是-n),告诉我将使用测试驱动开发来获得这样的函数。只有当面试官继续要求我解决所提出的问题时,我才真正开始在面试过程中胡乱写下伪代码,试图得到某种答案。然而,如果面试官能说明公司的情况,我真的不认为我会跳下去接受这份工作。。。

哦,这个答案假设面试是针对一个与C#编程相关的职位。如果面试的是与数学相关的职位,那当然是一个愚蠢的答案

我想我会先不看别人的答案就试试这个:

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int f(int n) {
    if(n > 0) {  
        if(n % 2)
            return -(++n);
        else {
            return (--n);

        }
    }
    else {
        if(n % 2)
            return -(--n);
        else {
            return (++n);

        }
    }
}

int main(int argc, char* argv[]) {
    int n;
    for(n = INT_MIN; n < INT_MAX; n++) {
        int N = f(f(n));

        if(N != -n) {
            fprintf(stderr, "FAIL! %i != %i\n", N, -n);
        }
    }
    n = INT_MAX;
    int N = f(f(n));
    if(N != -n) {
        fprintf(stderr, "FAIL! n = %i\n", n);
    }
    return 0;
}

输出:[无]

Python 2.6:

f = lambda n: (n % 2 * n or -n) + (n > 0) - (n < 0)

我意识到这对讨论毫无帮助,但我无法抗拒。