我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
我在上次面试中遇到的一个问题是:
设计函数f,使得:f(f(n))==-n其中n是32位有符号整数;你不能用复数算术。如果你不能为整个数字范围设计这样的函数,那么就尽可能为最大范围设计它。
有什么想法吗?
当前回答
适用于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
}
其他回答
有些类似,但我只是想写下我的第一个想法(用C++)
#include <vector>
vector<int>* f(int n)
{
returnVector = new vector<int>();
returnVector->push_back(n);
return returnVector;
}
int f(vector<int>* n) { return -(n->at(0)); }
仅使用重载使f(f(n))实际调用两个不同的函数
事实上,我并没有试图给出问题本身的解决方案,但我有几点意见,因为问题表明,提出这个问题是(工作?)面试的一部分:
我会先问“为什么需要这样的函数?这是什么更大的问题?”而不是试图当场解决实际提出的问题。这表明了我是如何思考和解决这样的问题的。谁知道?这甚至可能是在一次采访中首先提出这个问题的真正原因。如果答案是“没关系,假设它是需要的,并告诉我如何设计这个功能。”我会继续这样做。然后,我将编写我将使用的C#测试用例代码(显而易见:从int.MinValue到int.MaxValue的循环,对于该范围内的每个n调用f(f(n)),并检查结果是-n),告诉我将使用测试驱动开发来获得这样的函数。只有当面试官继续要求我解决所提出的问题时,我才真正开始在面试过程中胡乱写下伪代码,试图得到某种答案。然而,如果面试官能说明公司的情况,我真的不认为我会跳下去接受这份工作。。。
哦,这个答案假设面试是针对一个与C#编程相关的职位。如果面试的是与数学相关的职位,那当然是一个愚蠢的答案
我参加这个聚会迟到了,现在可能是墓地了。但我有两个贡献,灵感来自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
虽然问题说n必须是32位int,但它没有说参数或返回类型必须是32比特int0
private final long MAGIC_BIT=1<<38;
long f(long n) {
return n & MAGIC_BIT != 0 ? -(n & !MAGIC_BIT) : n | MAGIC_BIT;
}
编辑:
这实际上是一个很好的面试问题。最好的答案是难以或不可能回答的,因为它迫使人们仔细思考,你可以观察并寻找:
他们会放弃吗?他们说这很愚蠢吗?他们是否尝试独特的方法?他们在处理问题时是否与您沟通?他们是否要求进一步细化要求?
etc.
永远不要只回答行为问题,除非你有一个非常好的答案。始终保持愉快,并尝试让提问者参与进来。不要沮丧,不要过早放弃!如果你真的一无所获,尝试一些完全非法的、可能奏效的方法,你将获得几乎全部的学分。
使用全局。。。但事实如此?
bool done = false
f(int n)
{
int out = n;
if(!done)
{
out = n * -1;
done = true;
}
return out;
}