[Stack Overflow]Design a function f, such that f(f(n)) == -n

http://stackoverflow.com/questions/731832/interview-question-ffn-n

by konjac • 13 years ago

45 55 13 years ago

Okay.

    function f(n) { return -Math.abs(n) }

EDIT: something that works for negative numbers:

    function f(n) { return -n[0] || [n] }

pfortuny4• 13 years ago

f(n)=in

Where i=sqrt(-1), either would do.

Without proper constraints, the problem is trivial. The fact that the variable is called 'n' means nothing.

OTOH, if f is integer-valued and of an integer variable,

    f(0)=0
    f(2n)=-(2n-1)
    f(2n-1)=2n
    f(-(2n-1))=-2n
    f(-2n)=2n-1

Unless I am pretty confused (which may be).

The difficult one is f(f(n))=n^2.

comex2• 13 years ago

n is a 32-bit signed integer, as stated in the link.

pfortuny4• 13 years ago

Yes, my formula is easily transformed for 32-bit integers with sign. Not that difficult.

I leave that as an exercise to the reader. :-)

rcfox• 13 years ago

1) They disallowed complex numbers.

2) You can't just do an operation to the right side and then do the inverse inside of the function on the left side. It has to be done outside of the function.

3) You didn't accomplish anything with your butchered math. We wanted f(f(n)) = -n

pfortuny4• 13 years ago

I guess you do not understand my formula...

Given z a non-zero integer, either z=2n or z=2n-1 or z=-2n or z=-(2n-1), for some natural n>0... f(n) is defined according to each case. Uhu? And AFAIK f(f(n))=-n.

This should not be too hard to express in 32 bit arithmetic. With bitwise shifts etc.

richardkiss2• 13 years ago

f(f(n)) = n^2 is actually easy when you consider it restricted to 32-bit signed integers. Since it's impossible to make it work for any abs(n)>65536 (it's too big), you can reserve all those values as intermediate stopover points for the ones it WILL work for.

f(n)

     = abs(n) + 65536               if n < 65536

     = unsigned32(n & 0xffff) ** 2  if n >= 65536

Cheeky, eh?

pfortuny4• 13 years ago

Ah, yes. But I was thinking of all the integers.

I know, I should have read the OP but I was too lazy.

Really cheeky, though :)

qbrass• 13 years ago

Here's a shady looking Common Lisp macro.

(defmacro f (n)

  (cond ((numberp n) n)
              ((not (listp n)) (error "not a number"))
              ((equal (car n) 'f) `(* -1 ,n))
              (t n)))

uvdiv• 13 years ago

If you want to quickly understand the answers, the key insight is here:

http://stackoverflow.com/a/824878

Paraphrased: defining such a function over a symmetric subset of the reals X is equivalent to partitioning the positive (>0) elements of X into disjoint pairs (a,b). This uniquely describes a satisfying function f, under whose action:

    f:  0 -> 0
    f:  a -> (-b) -> (-a) -> b -> a

And conversely, any such function is uniquely described by such a partition. That's all there is to it!

There is no such partition on the set of int32_t's, because the # of nonzero int32_t's is odd.

For the set of all integers Z, the "obvious" partition is {(1,2), (3,4), (5,6)...}. This is what many of the answers are getting at with even/odd tests.

This also works for some subsets of the integers, such as {-2,1,0,1,2}. These are the symmetric ones with an even number of positive elements. These have 4n or 4n+1 elements total, depending on whether they include zero. [-2^31, 2^31] works (this has one more element than int32_t). As does [-2^31 + 2, 2^31 - 2] -- the largest such subset of int32_t.

This has a natural extension to the rationals, the reals, etc. Namely: (a,b) is a member of the partition iff (floor(a), floor(b)) is a member of the partition for integers, and their fractional parts are equal.

There is no such function on the reals that is (analytically) continuous. Any such f must be bijective (a != b implies f(a) != f(b)). If f : R -> R is both continuous and bijective, it is monotonic, and therefore so is (f . f), which is incompatible with the requirement that (f . f)(x) = -x.

zura• 13 years ago

To say in simpler words, regarding implementation - the main trick is to "store" the flag in the argument itself. It is a quite common trick, I'd say.

ape4• 13 years ago

Or doing something outside the box. Some people used static variables. How about looking at the call stack. If f() is invoked by f() do one thing, if you aren't do something else.

danbruc4• 13 years ago

The best you can do is getting all but one number (2^n - 1) correct.

anonymous3• 13 years ago

Unfortunately no, 0 also can't be handled.

The chains are

1 -> 2 -> -1 -> -2 -> 1

3 -> 4 -> -3 -> -4 -> 3

....

2^31 - 3 -> 2^31 - 2 -> -2^31 + 3 -> -2^31 + 2 -> 2^31 - 3

And now you're left with just 2^31 - 1, -2^31, -2^31 + 1, 0. If you define f(f(0)) = 0, then you have only 3 numbers and you need 4 for a chain.

Possible solutions:

* f(f(0)) = -2^31

* crash on any of the 3

* crash violently

* enter an endless loop (technically if the function never completes, it doesn't return a wrong value)

yashg• 13 years ago

OK am I the only one who thinks this question is on the same lines as hose brainteasers from Google and Microsoft like why are manholes covers round, or how many crows are there in Manhattan?

Honestly, can anyone tell me exactly in what kind of a programming scenario do you have to write a function where f(f(n)) comes out to -n? This is more a math question than a programming one and unless you are expected to do a lot of complex math in your job I don't think such a question is appropriate for a programmer's interview.

narsil• 13 years ago

Definitely a brainteaser if a valid solution is a hacky one like at http://stackoverflow.com/a/732049/827437 :

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

viraptor3• 13 years ago

Is it a hacky solution? Where's the line between a hacky one and a normal one?

est• 13 years ago

It's useful for rotation on an imaginary plane.

In Python:

    >>> f=lambda x:x*1j
    >>> f(1)
    1j
    >>> f(f(1))
    (-1+0j)
    >>> f(f(1)) == -1
    True
    >>>

shin_lao3• 13 years ago

I would probably walk away from an interview (if I ever have to do one again) with such questions.

I would not be interested to work in an environment using that kind of filter to let people in.

aaron6952• 13 years ago

And I'd guess the work place wins by far out of that deal.

A professional person knows for starters the interview is not necessarily the job, especial the kinda person who bases it on one question is not something you'd want to touch with a 10 foot pole.

In many companies HR will be doing the interview, or even one level of it. You have no idea what the team might be like.

Even all that said it's a fun question that I'd like to try, it say a lot about people who won't attempt something fun and unusual.

bsaul3• 13 years ago

carefull with that line of reasonning though. i had one candidate that self destructed with this behavior. he didn't like my questions, and did very poorly on the test ( which i warned him before was very specific, and i knew didn't pretend to assess completely his skills). but the talk i had with him before that convinced me that he was still an interesting candidate.

what happened was, even before i told him anything, the guy decided he wanted to stop the interview. In the case of that guy, the tests showed that he took failure in a very very bad way.

viraptor3• 13 years ago

I don't think this is a brainteaser. This question actually checks some real skills - can you deal with tricky number processing either at bit or math level, do you know that there are more negative than positive number representations in 2-complement.

I agree this may not be the greatest question and some people would fail to find asolution for reasons unrelated to their usual programming skills, but if that's not the only question... I don't see a big issue here.

raviparikh• 13 years ago

I'm pretty sure this isn't what they were looking for but it technically works: http://jsfiddle.net/8c7BE/1/

thewarrior• 13 years ago

Should I be worried that I couldnt come up with a proper solution for this. How do you get better at solving such questions ?

tomp• 13 years ago

1) Write down all you know. Seeing `f(f(n)) == n` is frightening and tells your mind nothing, it just blocks it. If you start with a simple example, say `f(f(1)) == 1`, you then say `f(1) == y` for some `y`, and then you can "generalize": `f(x) == y`, `f(y) == -x`.

2) Simplify and limit the problem: instead of `f : int32 -> int32`, have `f : {-2, -1, 0, 1, 2} -> [-2, 2]`. Then, you would probably think of the sequence `f : 1 -> y -> -1 -> -y`, from which you see that either `y == 2` or `y == -2`. Or, you would figure out another sequence, say `f : 1 -> 0.5 -> -1 -> -0.5` or something similar.

So: write down what you know, and try simple/limited examples first.

homeomorphic• 13 years ago

This has probably been said in the SO thread already, but what is the negation operator supposed to mean for the one int32_t (typically the number -2^31) whose additive inverse (the number 2^31) is not a member of int32_t?

ushi• 13 years ago

Here is a working go implementation...

http://play.golang.org/p/FgZp8xNfPt

deletes• 13 years ago

Nice, but it doesn't work for largest possible signed int value:

-( 2147483647 + 1 ) this overflows ( in C/C++ )

I guess you could change the part of the function to

       if n > 0 {

		if n%2 == 0 {
			return n - 1
		}
		return (-n) + 1   //here
	}

Anon84• 13 years ago

f(n) = i*n ?

richardkiss2• 13 years ago

You can actually use complex numbers to solve this, but using a representation that fits in the regular integers.

https://gist.github.com/richardkiss/5857101

Raticide• 13 years ago

Can I abuse dynamic typing? Javascript:

    function f(n) {
        if (typeof n == 'object')
            return -1 * n.val;
        else
            return {val: n};
    }

The unit test passes, so much be good, right?

anonymous3• 13 years ago

Source:

    /*
     * f(f(n)) = -n
     */

    #include <stdlib.h>
    #include <stdio.h>
    #include <stdint.h>
    
    int32_t f(int32_t n) {
        return (2 * (n & 1) - 1) * n + (2 * ((n & 1) & ((n >> 31) & 1)) - 1);
    }
    
    int main(int argc, char** argv) {
        int32_t n[] = { 1, 2, 3, -1, -2, -3, 0, 5, 6, 10, 20, 50, 0x7fffffff, 0x80000000 };
        int count = sizeof(n) / sizeof(int32_t);
        for (int i = 0; i < count; i++) {
            printf("      f(%d) = %d\n      f(f(%d)) = %d\n", n[i], f(n[i]), n[i], f(f(n[i])));
        }
    }

Result:

      f(1) = 0
      f(f(1)) = -1
      f(2) = -3
      f(f(2)) = -2
      f(3) = 2
      f(f(3)) = -3
      f(-1) = 0
      f(f(-1)) = -1
      f(-2) = 1
      f(f(-2)) = 0
      f(-3) = -2
      f(f(-3)) = 1
      f(0) = -1
      f(f(0)) = 0
      f(5) = 4
      f(f(5)) = -5
      f(6) = -7
      f(f(6)) = -6
      f(10) = -11
      f(f(10)) = -10
      f(20) = -21
      f(f(20)) = -20
      f(50) = -51
      f(f(50)) = -50
      f(2147483647) = 2147483646
      f(f(2147483647)) = -2147483647
      f(-2147483648) = 2147483647
      f(f(-2147483648)) = 2147483646

wrboyce• 13 years ago

Something looks wrong here…

      f(-1) = 0
      f(0) = -1
      f(f(-1)) = -1

Your code doesn't seem to handle the f(f(-n)) == n case

anonymous3• 13 years ago

Yeah, you're right. I had some more time to think, here's an updated, clearer version. I really really hate how you HAVE to define the last loop as 0 -> INT_MIN + 1 -> INT_MIN -> INT_MAX -> 0. And there's no way to do it other than to use ifs. And there's no getting around that f(f(0)) != 0 (if you want the function to be correct in the most possible cases, that is). If you remove the ifs, it fails for INT_MAX, -INT_MAX and 0. Ifs in numeric code always make me uneasy.

    /*
     * f(f(n)) = -n
     */
    
    #include <stdlib.h>
    #include <stdio.h>
    #include <stdint.h>
    
    int32_t f(int32_t n) {
        if (n == 0) {
            return -0x7fffffffL;
        }
        if (n == -0x7fffffffL) {
            return n-1;
        }
        if (n == -0x80000000L) {
            return 0x7fffffffL;
        }
        if (n == 0x7fffffffL) {
            return 0;
        }
    
        int32_t s = 1 - 2 * ((uint32_t)n >> 31);
        int32_t m = 2 * (n & 1) - 1;
        return m * n + s;
    }
    
    int main(int argc, char** argv) {
        int32_t n[] = { 1, 2, 3, -1, -2, -3, 0, 5, 6, 10, 20, 50, 0x7fffffff, 0x80000000, -0x7fffffff };
        int count = sizeof(n) / sizeof(int32_t);
        for (int i = 0; i < count; i++) {
            printf("      f(%d) = %d\n      f(f(%d)) = %d\n", n[i], f(n[i]), n[i], f(f(n[i])));
        }
    }

lazyjones3• 13 years ago

Did it say "free of side effects"? Seems trivial to me.

  #include <stdio.h>

  /* works for all signed integers, but isn't particularly  useful */
  int f(int n)
  {
      static int b;
      return b = !b ? n : -n;
  }

  int main()
  {
      int n=-1234;
      /* int n=1234; */
      printf("%d\n", f(f(n)));
  }

danbruc4• 13 years ago

Just look at the answers - all tricks you can come up with are there, this one included.

lazyjones3• 13 years ago

Indeed, I didn't look that far down, thanks. Too many FP purists on SO apparently. ;-)

omegote• 13 years ago

My take, probably present in the original link tho

  int f(int n) {
    static int timesCalled = 0;
    return ++timesCalled % 2 ? n : -n;
  }

Viper007Bond• 13 years ago

This was my thought as well. So many people jump to complicated math when the question was about a function. KISS applies, as does out of the box thinking. :)

And here's a solution (in PHP, my language of choice) that doesn't use any static variables :

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

Zariel• 13 years ago

Isn't the obvious answer, abs and negate? ie

f = negate . abs

That way f always returns a negative regardless of input.

skrebbel• 13 years ago

so what if i call f(f(-1))? It should return 1.

[Stack Overflow]Design a function f, such that f(f(n)) == -n

Related Stories