logo标签列表

Designing function f(f(n)) == -n

mathinteger
849

我上次面试时收到的一个问题：

设计一个函数f，使得：

f(f(n)) == -n

当 n 是一个32位的有符号整数时，你不能使用复数运算。

如果你不能为所有数字范围设计这样的函数，那就尽可能地为最大范围设计。

有什么想法吗？

6
这次面试是为了什么职位？ - tymtam
120个回答
6

在PHP中

function f($n) {
    if(is_int($n)) {
        return (string)$n;
    }
    else {
        return (int)$n * (-1);
    }
}

我相信您可以理解这种方法在其他语言中的精神。我明确地将其强制转换为int，以使不使用弱类型语言的人更加清楚。对于某些语言，您需要重载该函数。
这种解决方案的好处是无论您从字符串还是整数开始，当返回f(n)时，它都能正常工作，并且不会在可见性上做出任何改变。
在我看来，面试官正在问：“此候选人是否知道如何标记数据以便稍后操作？”和“此候选人是否知道如何在最少更改数据的情况下标记数据？”您可以使用double、string或任何其他您感觉需要转换的数据类型来实现这一点。
当然，在实际代码中使用这样的黑客技巧是一个可怕的想法。如果您需要在数据中存储状态，请创建一个新类型，如（s，a），并使用绑定运算符仅处理结果。（这与Haskell的状态单子非常相似，但不完全相同。） - jrockway
6

很简单!

每个数字都按4的倍数循环映射到另一个数字，满足所需条件。

例如:

规则如下:

  • 0 → 0

  • ±2³¹ → ±2³¹

  • 奇数→偶数，偶数→-奇数:

    对于所有k，0

唯一不匹配的值是±(2³¹-1)，因为只有两个。 必须有两个不能匹配，因为在二进制补码系统中只能有四的倍数个数字，其中0和±2³¹已经被保留。

在一进制补码系统中，存在+0和-0。我们这样做:

对于所有k，0

5

我有另一种解决方案，但只能有一半的成功率：

def f(x):
    if random.randrange(0, 2):
        return -x
    return x
5

由于对f(x)的输出没有限制，只要考虑f(f(x))就行了，这使得Python的解决方案变得简单易行:

def f(x):
    return (isinstance(x, tuple) and -x[0]) or (x,)
当我第一次听到这个问题时，这就是立刻浮现在我的脑海中的。 - kreativitea
1
(x) 返回 x。我认为你的意思是 (x,)。 - seppo0010
最后了。我简直不敢相信有多少“作弊”解决方案依赖于某些全局状态，即使对于那些状态可以“存储”在函数本身的返回值中的语言也是如此。 - user229044
3
这也是一种解决方案（但我们有点打破规则）：
def f(n):
    if isinstance(n,int):
        return str(n)
    else:
        return -int(n)
3
这个怎么样？
int nasty(int input)
{
    return input + INT_MAX/2;
}
嗯...我相信我打错了字。本质上的目的是让整数变量溢出，直到它进入负值区域。但我相信我在这里搞砸了什么...请忽略。 - Billy ONeal
有趣的解决方案，我也有一个类似的。但是我意识到这不是一个解决方案。说到字节：1+63=64，64+63=127。即使127+1=-128，而不是-1。为什么这个错误的解决方案被投票赞成？ - user unknown
@user：我不太清楚自己犯了什么错误。我相信我在评论中承认了自己搞砸了某些东西。我认为这个观点是正确的，即使这段代码并不完美，所以它被点赞了。我本来想删除这个答案，但因为它是 CW，所以决定不删。 - Billy ONeal
3

虽然问题说n必须是32位整数，但它并没有说参数或返回类型必须是32位整数。这应该可以在Java中编译-在C中，您可以摆脱!= 0。

private final long MAGIC_BIT=1<<38;
long f(long n) {
    return n & MAGIC_BIT != 0 ? -(n & !MAGIC_BIT) : n | MAGIC_BIT;
}

编辑：

这实际上是一个非常好的面试问题。最好的问题是那些难以回答或不可能回答的问题，因为它迫使人们去思考，你可以观察和寻找：

  • 他们会放弃吗？
  • 他们会说这个问题很愚蠢吗？
  • 他们会尝试独特的方法吗？
  • 他们在解决问题时是否与您沟通？
  • 他们是否要求进一步完善需求？

等等。

除非你有非常好的答案，否则永远不要只回答行为问题。始终保持愉快，并尝试让提问者参与进来。不要感到沮丧，也不要轻易放弃！如果你真的没有任何头绪，试试一些完全不合法但可能有效的方法，你将得到几乎满分。

3

我认为这类问题的答案最好通过使用图示来进行解释。当我们忽略零时，我们可以将整数划分为4个数字的小集合：

 1  → 2    3  → 4    5  → 6
 ↑    ↓    ↑    ↓    ↑    ↓   ...
-2 ← -1   -4 ← -3   -6 ← -5

这段内容很容易转换为代码。请注意，偶数会改变符号，奇数会增加或减少1。在C#中，它看起来像这样：

public static int f(int x)
{
    if(x == 0)
        return 0;

    if(x > 0)
        return (x % 2 == 0) ? -x+1 : x+1;

    // we know x is negative at this point
    return (x % 2 == 0) ? -x-1 : x-1;
}

当然，你可以使用巧妙的技巧来缩短这个方法，但我认为这段代码最能解释它本身。
接下来是关于范围的问题。32位整数的范围从-2^31到2^31-1。数字2^31-1、-2^31-1和-2^31超出了f（x）的范围，因为数字2^31丢失了。
3
int f( int n ){
    return n==0?0:(n&1?n:-n)+(n<0?-1:1);
}
1
n＆1类似于布尔值，但返回一个整数。 - Dinah
3
假设这是关于C或C++的内容，那就没问题。 - Kip
3
我的答案...50%的时间是正确的，一直如此。
int f (int num) {
    if (rand () / (double) RAND_MAX > 0.5)
         return ~num + 1;
    return num;
}
输入数字7可能会导致第一步是-7+1，即-6或7。在我看来，这是错误的，100％的时间都是如此。我投反对票。 - user unknown
哦，抱歉，我把波浪号~num和减号-num搞混了。好的 - 现在是正确的。 - user unknown
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接