Just for a bit of fun, I saw this question posted on reddit the other day and wondered how *you* would solve this in D?

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

The text from the question:

Design a function f, such that:

f(f(n)) == -n
Where n is a 32 bit signed integer; you can't use complex numbers
arithmetic.

If you can't design such a function for the whole range of
numbers, design it for the largest range possible.

On Wednesday, 26 June 2013 at 20:51:35 UTC, Gary Willoughby wrote:
> Just for a bit of fun, I saw this question posted on reddit the other day and wondered how *you* would solve this in D?

Since they didn't say *pure* function, I'd cheat:

int f(int n) {
  static bool isOddCall;
  isOddCall = !isOddCall;
  if(!isOddCall)
      return -n;
  return n;
}

:P

On Wednesday, 26 June 2013 at 20:51:35 UTC, Gary Willoughby wrote:
> Just for a bit of fun, I saw this question posted on reddit the other day and wondered how *you* would solve this in D?
>
> http://stackoverflow.com/questions/731832/interview-question-ffn-n

First answer port:
http://dpaste.dzfl.pl/0e3d145c

Am Wed, 26 Jun 2013 22:52:17 +0200
schrieb "Gary Willoughby" <dev@kalekold.net>:

> The text from the question:
> 
> Design a function f, such that:
> 
> f(f(n)) == -n
> Where n is a 32 bit signed integer; you can't use complex numbers
> arithmetic.
> 
> If you can't design such a function for the whole range of numbers, design it for the largest range possible.

Well some good answers are given that would work in D, too. I like how this question turns out the nature of the person much more than their general programming skill. Some options:

o downvote the question and close the tab
o face it with humor (e.g. throw NotImplementedException("You
  get the rest of the code when you give me the job"))
o get dirty and hack around the issue, by actually having two
  'f's (by means of C preprocessor abuse, or C++ overloads)
o be the pragmatic Python programmer: no overflows, no problems
o adhere strictly to the problem description and give multiple
  solutions that do or don't handle 0 or -2^31.

Anyway I've yet to see a solution that works for all input ;)

-- 
Marco

> Anyway I've yet to see a solution that works for all input ;)

Scratch that.


-- 
Marco

Am 26.06.2013 22:51, schrieb Gary Willoughby:
> Just for a bit of fun, I saw this question posted on reddit the other day and wondered how *you* would solve this in D?
> 
> http://stackoverflow.com/questions/731832/interview-question-ffn-n

I solved it ;)

http://dpaste.dzfl.pl/5cd56e9d

On 6/26/13, Gary Willoughby <dev@kalekold.net> wrote:
> Just for a bit of fun, I saw this question posted on reddit the other day and wondered how *you* would solve this in D?
>
> http://stackoverflow.com/questions/731832/interview-question-ffn-n

Silly mathematicians, nobody said you had to make it performant.

import std.conv;
import std.string;
import std.stdio;

auto f(T)(T n)
{
    static struct S { int n; }

    static if (is(T == int))
        return S(n);
    else
        return to!int("-" ~ n.n.to!string.chompPrefix("-"));
}

void main()
{
    foreach (i; int.min .. int.max)
    {
        writefln("%s => %s", i, i.f.f);
    }
}

On Wednesday, 26 June 2013 at 22:43:05 UTC, David wrote:
> Am 26.06.2013 22:51, schrieb Gary Willoughby:
>> Just for a bit of fun, I saw this question posted on reddit the other
>> day and wondered how *you* would solve this in D?
>> 
>> http://stackoverflow.com/questions/731832/interview-question-ffn-n
>
> I solved it ;)
>
> http://dpaste.dzfl.pl/5cd56e9d

Let's keep it simple:

int f(uint n) { return n; }
uint f(int n) { return -n; }

On Thu, Jun 27, 2013 at 12:43:04AM +0200, David wrote:
> Am 26.06.2013 22:51, schrieb Gary Willoughby:
> > Just for a bit of fun, I saw this question posted on reddit the other day and wondered how *you* would solve this in D?
> > 
> > http://stackoverflow.com/questions/731832/interview-question-ffn-n
> 
> I solved it ;)
> 
> http://dpaste.dzfl.pl/5cd56e9d
[...]

Well, technically it's invalid because it says "design *a* function f".

But maybe it can be salvaged:

	auto f(T)(T n) {
		static if (is(T==int))
			return cast(double)n;
		else if (is(T==double))
			return -cast(int)n;
		else static assert(0);
	}

Well, it's still cheating, though. :-P I think the 4-cycle algorithm is probably still the best one I've seen.

A more interesting interview question, IMO, would be to design a function of the form:

	bool f(void delegate(int) dg, int n);

which returns true if dg(n) returns, and false otherwise.

:-P


T

-- 
Three out of two people have difficulties with fractions. -- Dirk Eddelbuettel