HN Explorer

63 comments

[ 7.8 ms ] story [ 151 ms ] thread
ricardobeat
Okay.

    function f(n) { return -Math.abs(n) }
EDIT: something that works for negative numbers:

    function f(n) { return -n[0] || [n] }
pfortuny
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.

comex
n is a 32-bit signed integer, as stated in the link.
pfortuny
Yes, my formula is easily transformed for 32-bit integers with sign. Not that difficult.

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

comex
It is not "not that difficult": as one of the answers explained, it is impossible to create such a function that works for all values - not just -2147483648, which obviously cannot comply, but in your case, also 2147483647.
rcfox
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

pfortuny
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.

richardkiss
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?
pfortuny
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
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)))
[deleted]
(comment deleted)
uvdiv
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
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
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.
danbruc
The best you can do is getting all but one number (2^n - 1) correct.
[deleted]
(comment deleted)
anonymous
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)

colanderman
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.

The parent of your post explicitly said:

all but one number (2^n - 1) correct.

danbruc
Here the example for 3 bits.

   0 ->  0
  +1 -> -2 -> -1 -> +2 -> +1
  +3 -> -4 -> -3 -> -4
The first cycle takes care of 0, the second one of -2, -1, +1 and +2. The interesting thing is the third thing - it consists of the cycle -4 -> -3 -> -4 and the attached chain +3 -> -4 entering the cycle via -4. This one correctly maps +3 to -3 and -4 to -4 (-(2^(n - 1) is its on inverse) and only fails for -3 which is incorrectly mapped to itself, too. There you go, 7 out of 8 correct.

(This is the essence of my way longer answer on Stack Overflow [1] although it is not necessarily any clearer because it evolved a lot.)

[1] http://stackoverflow.com/a/731857

yashg
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
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()
viraptor
Is it a hacky solution? Where's the line between a hacky one and a normal one?
agravier
I think that the leakage of abstraction is mathematically impure, in his view.
bsaul
well, n is supposed to be a 32 bits integer int. Not a lambda. if f(n) returns a lambda, it can't be composed with f again, according to the strict definition of "n".
viraptor
And it is. The question is:

    f(f(n)) == -n
    Where n is a 32 bit signed integer
It's `f(n)` that is not a signed integer. Both `n` and `f(f(n))` are ints, so the answer is within the constraints. There's nothing said about the signature of the function.
bsaul
that seems a bit far fetched. the way i understand n, it means " f input ", as "the parameter that f takes as input, whose type is an integer". Anyway, that's probably just one way of reading the question. Really depends on what the interviewer's intention was.
petercooper
Therein lies a lesson for the interviewer, "your spec is too vague" :-)
est
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_lao
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.

aaron695
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.

shin_lao
To me, it says more about the company, and I wouldn't like to work in that kind of company.

Basically these questions are made to make the interviewer look clever while not assessing any relevant skill.

I've been far more often an interviewer than and interviewee and I never ask that kind of question.

aaron695
But what do you ask? You can't do fuzzbuzz for an hour.

I'm sure I can show you a study that shows some of your questions are wrong.

It's one question, at the end of the day every question can probably in isolation be said to be wrong.

While they are answering a question like this you see many things, how the handle stress, how they handle something they don't know, how they communicate the solution or ask questions.

We all know this question is not meant to be solved right? That bit's not rocket science. It's about how people tackle hard/impossible stuff they don't know.

If you answer a question you don't know the solution to by walking out of the room, that to me is a fail and a good test. If they try and get defensive that to me means they are not good team players and won't ever ask for help.

How else does one see if they are a team play in an interview? It's easy to bag the questions but people aren't really coming up with supposed solutions.

shin_lao
- FizzBuzz like question to eliminate a candidate that cannot code

- Technical questions according to the seniority level of the candidate

- I ask the candidate to solve a problem we are currently working on

- During the whole process check for cultural/managerial fit

bsaul
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.

[deleted]
(comment deleted)
moron4hire
Or maybe he realized he didn't like you.
viraptor
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.

[deleted]
(comment deleted)
thewarrior
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
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
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
Here is a working go implementation...

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

deletes
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
	}
[deleted]
(comment deleted)
[deleted]
(comment deleted)
Raticide
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?
anonymous
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
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
anonymous
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])));
        }
    }
lazyjones
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)));
  }
danbruc
Just look at the answers - all tricks you can come up with are there, this one included.
lazyjones
Indeed, I didn't look that far down, thanks. Too many FP purists on SO apparently. ;-)
danbruc
This wasn't intended to sound that rude - it just happens that I know this question quite well because I wrote one of the first answers. I was just a bit »WtF!?! Why is everybody posting solutions that are already there?« turning this discussion into a unreadable mess within minutes; HN isn't really made for posting code.
lazyjones
I'm used to seeing the "correct" answers on top at SO and since the first couple with many upvotes had deficiencies, I assumed that there were no better solutions (for my personal definition of "better" apparently!). Most of the people who posted on HN probably did the same.
omegote
My take, probably present in the original link tho

  int f(int n) {
    static int timesCalled = 0;
    return ++timesCalled % 2 ? n : -n;
  }
Viper007Bond
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
Isn't the obvious answer, abs and negate? ie

f = negate . abs

That way f always returns a negative regardless of input.

skrebbel
so what if i call f(f(-1))? It should return 1.
[dead] xkcdfanboy
This is the way I look at the problem.

f(f(n)) = -n

   We can solve this by letting f(n)=-n
                           and subsequently f(-n) = -n
That is, f should be a function that gives the value -|n|, and therefore has a fixed point for all negative numbers.

So given that I took this as a math function challenge rather than an actual programming challenge, we can solve it one of two ways

f(x) = -|x|

or f(x) = -(n^2)^.5

The 2nd solution is more pure math because absolute value is a piecewise function.

Now of course, being that the problem is actually about 32-bit integers, we can solve it by doing a two's complement only on values > signed INT_MAX. Someone else posted the bitwise shift version which has some cleverness so I won't elaborate.

[dead] xkcdfanboy
This is the way I look at the problem.

f(f(n)) = -n

   We can solve this by letting f(n)=-n
                           and subsequently f(-n) = -n
That is, f should be a function that gives the value -|n|, and therefore has a fixed point for all negative numbers.

So given that I took this as a math function challenge rather than an actual programming challenge, we can solve it one of two ways

f(x) = -|x|

or f(x) = -(n^2)^.5

The 2nd solution is more pure math because absolute value is a piecewise function.

Now of course, being that the problem is actually about 32-bit integers, we can solve it by doing a two's complement only on values > signed INT_MAX. Someone else posted the bitwise shift version which has some cleverness so I won't elaborate.