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

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

有什么想法吗?


当前回答

PHP,不使用全局变量:

function f($num) {
  static $mem;

  $answer = $num-$mem;

  if ($mem == 0) {
    $mem = $num*2;
  } else {
    $mem = 0;
  }

  return $answer;
}

适用于整数、浮点数和数字字符串!

只是意识到这会做一些不必要的工作,但是,不管怎样

其他回答

你没说他们期望什么样的语言。。。这是一个静态解决方案(Haskell)。这基本上是在搞乱两个最重要的比特:

f :: Int -> Int
f x | (testBit x 30 /= testBit x 31) = negate $ complementBit x 30
    | otherwise = complementBit x 30

在动态语言(Python)中要容易得多。只需检查参数是否为数字X,并返回返回-X的lambda:

def f(x):
   if isinstance(x,int):
      return (lambda: -x)
   else:
      return x()

在PHP中

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

我相信你能理解其他语言的这种方法的精神。为了让不使用弱类型语言的人更清楚,我明确地将其转换回int。对于某些语言,您必须重载该函数。

这个解决方案的妙处在于,无论您是从字符串还是整数开始,它都是有效的,并且在返回f(n)时不会明显改变任何内容。

在我看来,面试官在问,“这位应聘者是否知道如何标记数据以供以后操作”,以及“这位应聘人员是否知道如何在最少更改数据的情况下标记数据?”你可以使用双精度、字符串或任何其他你想使用的数据类型来实现这一点。

记住你的上一个状态不是一个足够好的答案吗?

int f (int n)
{
    //if count 
    static int count = 0;

    if (count == 0)
        { 
            count = 1;
            return n;
        }

    if (n == 0)
        return 0;
    else if (n > 0)
    {
        count = 0;
        return abs(n)*(-1);
    } 
    else
    {
        count = 0;
        return abs(n);
    }
}

int main()
{
    int n = 42;
    std::cout << f(f(n))
}

没有人说它必须是无国籍的。

int32 f(int32 x) {
    static bool idempotent = false;
    if (!idempotent) {
        idempotent = true;
        return -x;
    } else {
        return x;
    }
}

作弊,但不如很多例子。更糟糕的是,查看堆栈以查看调用者的地址是否为-f,但这将更具可移植性(虽然不是线程安全的……线程安全版本将使用TLS)。更邪恶的是:

int32 f (int32 x) {
    static int32 answer = -x;
    return answer;
}

当然,对于MIN_INT32的情况,这两种方法都不太有效,但除非允许返回更宽的类型,否则对此您几乎无能为力。

我参加这个聚会迟到了,现在可能是墓地了。但我有两个贡献,灵感来自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