Interview Question [duplicate]

Question

Possible Duplicate:
solving f(f(x))=g(x)

Here is a nice interview question for computer science people:

Write a unary function f such that

f(f(x)) = -x

Constraints:

1. The function should be pure (i.e. it should have no state and every time its called it should output the same value for the "same" input.).

2. Complex number arithmetic is not allowed. So f(x) = ix is not allowed.

3. You can use plain mathematics or use a program. Choice is yours.

Although I am a student of computer science but I am unable to figure out it's mathematical aspect.

Any help ?

Answer 1

Divide the domain into separate sets of four, each set having the form {x,y,-x,-y}. Now, let f simply rotate within these sets one step. That is, map x to y, and y to -x, and -x to -y, and -y to x. Thus, doing it twice maps every x to -x, as desired. (Also let f(0)=0.)

Answer 2

Here's an example implementation I wrote up.

from math import *

def sgn(x):
   if x<0: return -1
   else: return 1

def f(x):
    if floor(abs(x))%2 == 0:
       return -sgn(x)*(abs(x)+1)
    else:
       return sgn(x)*(abs(x)-1)

g = lambda x: f(f(x))

The strategy is that we switch numbers between odd and even (absolute value up one and then down one), but only change the sign one direction... Thus the absolute value ends up at the same place, but the sign only changes once.

Answer 3

If you're working over the integers then you can approach this problem in a kind of mindless 'lexicographic' way without having to be clever at all. (To attempt to give this a mathematical angle, I was inspired to take this approach by the way you can build the Golay codes lexicographically.)

The idea is to choose $f(x)$ as close to zero as possible consistent with all of the decisions we've made so far. It's easiest to do this by drawing a table with columns headed by $x$, $f(x)$ and $f(f(x))$.

We can choose $f(0)=0$. Now we need to choose $f(1)$. The closest integer to $0$ we can pick is $2$. That means $f(2)$ must be $-1$. Now to pick $f(3)$. The choice closest to $0$ is $4$ and now we know $f(4)=-3$. After a couple more examples it's obvious how $f$ will act on all of the positive integers. Now start working backwards from $0$. We already know $f(x)$ for all negative odd $x$. A few seconds work reveals a simple pattern for negative even $x$.

So in total I'm sorting the integers as $0, 1, 2, 3, ..., -1, -2, -3, ...$ and at each stage choosing $f(x)$ to be the earliest value that is still available.

We get $f(x) = \left\\{ \begin{array}{ll} 0 & x=0\\\\ x+1 & x > 0 \mbox{ and odd}\\\\ -(x-1) & x > 0 \mbox{ and even}\\\\ x-1 & x < 0 \mbox{ and odd}\\\\ -x-1 & x < 0 \mbox{ and even}\\\\ \end{array} \right. $

The entire function was determined for us automatically without having to pull any rabbits out of hats! This is also a fairly general method. I wonder what related problems it also works for. It's not obvious that we can always get away without having to backtrack.

Answer 4

You can use a higher order partial function.

f(x) = λ.(-x) if x is an integer
     = x()    if x is a function evaluating to an integer

To illustrate:

f(f(-5)) = f(λ.(5))
         = λ.(5)()
         = 5