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

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

有什么想法吗?


当前回答

这很简单!

每个数字以4为周期映射到另一个数字,其中所需条件成立。

例子:

规则如下:

0→ 0±2³¹ → ±2³¹古怪的→ 甚至,甚至→ -奇数:对于所有k,0<k<2³⁰: (2k-1)→ (2k)→ (-2k+1)→ (-2k)→ (2k-1)

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

在一的补码系统中,存在+0和-0。我们开始了:

对于所有k,0<k<2³⁰: (+2k)→ (+2k+1)→ (-2k)→ (-2k-1)→ (+2k)

其他回答

int f(int n) {
    return ((n>0)? -1 : 1) * abs(n);
}

我参加这个聚会迟到了,现在可能是墓地了。但我有两个贡献,灵感来自viraptor先前使用lambda的Python答案。读者可能认为该解决方案仅在非类型化语言中可行,而在类型化语言中将需要一些明确的额外标记。

但下面是Haskell中的解决方案1(我不是Haskell专家)。它有点作弊,因为从技术上讲,两个f是两个不同的实现。(一个f::Int->()->Int,另一个f::(()->Int)->Int)

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}

module Main where

class Tran σ τ | σ -> τ where
  tran :: σ -> τ

instance Tran Int (() -> Int) where
  tran n = \_ -> (-n)

instance Tran (() -> Int) Int where
  tran g = g ()

f :: Tran σ τ => σ -> τ
f = tran

main :: IO ()
main = do
  print $ f (f (42 :: Int)) -- --> -42
  print $ f (f (0 :: Int)) -- --> 0
  print $ f (f (-69 :: Int)) -- --> 69

接下来是Typed Racket中的解决方案2。这一个满足了最大可能域的属性,因为Racket中的Number最多包含复数:

#lang typed/racket

(: f (case->
      [Number -> (-> Number)]
      [(-> Number) -> Number]))
(define (f x)
  (if (number? x) (λ () (- x)) (x)))

(f (f 42))    ; --> -42
(f (f 0))     ; --> 0
(f (f -69))   ; --> 69
(f (f 3/4))   ; --> -3/4
(f (f 8+7i))  ; --> -8-7i

根据微软/谷歌的面试官通常在面试中提出的问题,我认为提问者指的是一种创新、轻量级、简单的解决方案,它将使用按位操作,而不是那些复杂的高级答案。

灵感来自@eipipuz的回答,我编写了这个C++函数(但没有运行它):

int32_t f(int32_t n){
    int32_t temp = n & 00111111111111111111111111111111;
    x = n >> 30;
    x++;
    x = x << 30;
    return x | temp;
}

它将n的最左边的两位存储在x中,将x加1,然后再次将其替换为n的最左侧的两位。

如果我们继续以另一个f(n)作为参数n运行f(n,则最左边的两个位将如下旋转:

00 --> 01 --> 10 --> 11 --> 00 ...

请注意,最右边的30位不变。8位整数示例:

示例1:

>f(00001111)=01001111>f(01001111)=10001111[这是原始值的负值,00001111]

示例2:

>f(11101010)=00101010>f(00101010)=01101010[这是原始值11101010的负值]

用咖啡脚本打高尔夫:

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

这里有一个解决方案,其灵感来自于不能使用复数来解决这个问题的要求或声明。

乘以-1的平方根是一个想法,但似乎失败了,因为-1没有整数的平方根。但是,使用mathematica这样的程序可以得出如下公式

(18494364652+1)模(232-3)=0。

这几乎和平方根为-1一样好。函数的结果必须是有符号整数。因此,我将使用一个修改的模运算mods(x,n),它返回与x模n最接近0的整数y。只有极少数编程语言能够成功地进行模运算,但它很容易被定义。例如,在python中,它是:

def mods(x, n):
    y = x % n
    if y > n/2: y-= n
    return y

使用上面的公式,问题现在可以解决为

def f(x):
    return mods(x*1849436465, 2**32-3)

对于[-231-2231-2]范围内的所有整数,这满足f(f(x))=-x。f(x)的结果也在这个范围内,但当然计算需要64位整数。