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

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

有什么想法吗?


当前回答

Python 2.6:

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

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

其他回答

int f(int n)
{
  static long counter=0;
  counter++;
  if(counter%2==0)
    return -n;
  else
    return n;
}

这个怎么样:

do
    local function makeFunc()
        local var
        return function(x)
            if x == true then
                return -var
            else
                var = x
                return true
            end
        end

    end
    f = makeFunc()
end
print(f(f(20000)))

这里有一个证明,如果不使用额外信息(除了32位的int),那么对于所有数字,这样的函数都不可能存在:

我们必须使f(0)=0。(证明:假设f(0)=x,则f(x)=f(f(0))=-0=0。现在,-x=f(f(x))=f(0)=x,这意味着x=0。)

此外,对于任何x和y,假设f(x)=y。那么我们希望f(y)=-x。并且f(f(y))=-y=>f(-x)=-y。总结一下:如果f(x)=y,那么f(-x)=-y,f(y)=-x,f(-y)=x。

因此,我们需要将除0之外的所有整数分成4个集合,但我们有奇数个这样的整数;不仅如此,如果我们去掉没有正对应的整数,我们仍然有2(mod4)个数。

如果我们去掉剩下的2个最大数(通过abs值),我们可以得到函数:

int sign(int n)
{
    if(n>0)
        return 1;
    else 
        return -1;
}

int f(int n)
{
    if(n==0) return 0;
    switch(abs(n)%2)
    {
        case 1:
             return sign(n)*(abs(n)+1);
        case 0:
             return -sign(n)*(abs(n)-1);
    }
}   

当然,另一种选择是不遵守0,并获得我们删除的2个数字作为奖励。(但这只是一个愚蠢的假设。)

适用于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
}

用咖啡脚本打高尔夫:

f = (n)-> -n[0] or [n]