www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How would you solve this 'interview' question in D?

reply "Gary Willoughby" <dev kalekold.net> writes:
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
Jun 26 2013
next sibling parent reply "Gary Willoughby" <dev kalekold.net> writes:
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.
Jun 26 2013
parent reply Marco Leise <Marco.Leise gmx.de> writes:
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
Jun 26 2013
parent Marco Leise <Marco.Leise gmx.de> writes:
 Anyway I've yet to see a solution that works for all input ;)


 
Scratch that.


-- 
Marco
Jun 26 2013
prev sibling next sibling parent reply "Adam D. Ruppe" <destructionator gmail.com> writes:
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
Jun 26 2013
parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Wednesday, 26 June 2013 at 21:00:42 UTC, Adam D. Ruppe wrote:

 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


Well if you solved it *that* way, *I* wouldn't hire you :p
Jun 27 2013
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 27 Jun 2013 04:09:39 -0400, monarch_dodra <monarchdodra gmail.com>  
wrote:


 On Wednesday, 26 June 2013 at 21:00:42 UTC, Adam D. Ruppe wrote:

 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


 Well if you solved it *that* way, *I* wouldn't hire you :p


TBH, if working there required writing such functions, I wouldn't want to  
:)

-Steve
Jun 27 2013
prev sibling parent "Adam D. Ruppe" <destructionator gmail.com> writes:
On Thursday, 27 June 2013 at 08:09:43 UTC, monarch_dodra wrote:

 Well if you solved it *that* way, *I* wouldn't hire you :p


Did I say I would cheat?

I meant to say "I would deliver a working solution ahead of 
schedule and under budget" :)
Jun 27 2013
prev sibling next sibling parent "Mr. Anonymous" <mailnew4ster gmail.com> writes:
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
Jun 26 2013
prev sibling next sibling parent reply David <d dav1d.de> writes:
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
Jun 26 2013
next sibling parent "Diggory" <diggsey googlemail.com> writes:
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; }
Jun 26 2013
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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
Jun 26 2013
parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 26 June 2013 at 23:14:09 UTC, H. S. Teoh wrote:

 I think the 4-cycle algorithm is
 probably still the best one I've seen.


All (correct) mathematically based answers are 4-cycle.

begin very sloppy proof with mixed up notation:

Let f^2(x) = -x
f^4(x) = f^2(f^2(x))
        = f^2(-x)
        = -(-x)
        = x

Therefore:

f^4 = 1
f^{4n} = 1^n = 1,     n in N
<==> f^{4n}(x) = x
□
Jun 27 2013
prev sibling next sibling parent "MattCoder" <mattcoder hotmail.com> writes:
On Wednesday, 26 June 2013 at 22:43:05 UTC, David wrote:

 Am 26.06.2013 22:51, schrieb Gary Willoughby:
 I solved it ;)

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


Yes, but "maybe" the interviewer is waiting just one function, 
since the question was: "Design a function f". So I rewrote your 
example:

import std.stdio;
import std.string;

auto f(T)(T n){
	if(is(T==float))
		return cast(int)n;
	
	return cast(float)-n;
}

void main() {
	foreach(n; int.min..int.max) {
		assert(f(f(n)) == -n);
	}
}

Again, in the same way, maybe the interviewer want "n" as 32 
signed int not a auto/template etc. :D
Jun 26 2013
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 6/27/13, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:

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


What I don't understand is why the CPU is so slow that it takes ages
to go through int.min .. int.max in a loop.
Jun 26 2013
prev sibling parent reply Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 6/27/13, Andrej Mitrovic <andrej.mitrovich gmail.com> wrote:

 On 6/27/13, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:

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


 What I don't understand is why the CPU is so slow that it takes ages
 to go through int.min .. int.max in a loop.


I mean this takes 31 seconds on my machine (obviously without
optimization flags):

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

void main()
{
    foreach (n; int.min..int.max)
        f(f(n));
}
-----

Maybe I need an upgrade.
Jun 26 2013
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 26 Jun 2013 20:01:16 -0400, Andrej Mitrovic  
<andrej.mitrovich gmail.com> wrote:


 On 6/27/13, Andrej Mitrovic <andrej.mitrovich gmail.com> wrote:

 On 6/27/13, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:

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


 What I don't understand is why the CPU is so slow that it takes ages
 to go through int.min .. int.max in a loop.


 I mean this takes 31 seconds on my machine (obviously without
 optimization flags):

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

 void main()
 {
     foreach (n; int.min..int.max)
         f(f(n));
 }
 -----

 Maybe I need an upgrade.


Nope.  4 billion loops is a lot.  That's just a fact of life.  I have  
quad-core i7 at 2.2Ghz, and it takes a while.

You *could* use parallel foreach :)

Note that in that code, you need to test f(f(int.max)) specifically.

-Steve
Jun 27 2013
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
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);
    }
}
Jun 26 2013
prev sibling next sibling parent "Jesse Phillips" <Jesse.K.Phillips+D gmail.com> writes:
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


Well, considering there is little to that specification:

int f(int num) {
     import std.exception;
     static called = false;
     enforce(num != int.min);
     if(!called) {
         called = true;
         return num;
     } else {
         called = false; // Only for unittesting
         return -num;
     }
}

unittest {
     assert(f(f(3)) == -3);
     assert(f(f(-3)) == 3);
     assert(f(f(int.min+1)) == int.max);
     assert(f(f(int.max)) == int.min+1);
}

int having the issue that not all numbers are representable in 
both +/-.
Jun 26 2013
prev sibling next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
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


The question is ambiguous as to what they mean by -n. Do they 
mean the result of negation on the 32bit signed int, or do they 
mean the negative of the number represented by that int. this 
matters because -int.min evaluates to int.min due to wraparound.

So.. If we assume we want the proper mathematical negation:

Taking note that although the spec specifies n as a 32bit integer 
it says nothing about the signature of the function or the type 
of the result, we can just use implicit int->long

byte s(long n)
{
         return (n & 0x8000000000000000) ? -1 : 1;
}

long f(long x)
{
         if(x == 0)	return 0;
         if(x % 2)	return x + s(x);
         return s(x) - x;
}

unittest
{
         foreach(int n; int.min + 1 .. int.max)
         {
                 assert(f(f(n)) == -n);
         }
	assert(f(f(int.max)) == -int.max);
}
Jun 27 2013
next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 27 June 2013 at 12:38:25 UTC, John Colvin wrote:

Woops, sorry missed an assert

unittest
{
         assert(f(f(int.min)) == -(cast(long)int.min));
         foreach(int n; int.min + 1 .. int.max)
         {
                 assert(f(f(n)) == -n);
         }
  	assert(f(f(int.max)) == -int.max);
}
Jun 27 2013
prev sibling parent reply "MattCodr" <mattcodr hotmail.com> writes:
On Thursday, 27 June 2013 at 12:38:25 UTC, John Colvin wrote:

 The question is ambiguous as to what they mean by -n. Do they 
 mean the result of negation on the 32bit signed int, or do they 
 mean the negative of the number represented by that int. this 
 matters because -int.min evaluates to int.min due to wraparound.


From: February 11, 2008:

Vlad Patryshev said...

...Write a function f on 32-bit integers that, applied twice, it 
negates the integer. f(f(n)) = -n.

Source: 
http://steve-yegge.blogspot.com.br/2008/02/portrait-of-n00b.html

Matheus.
Jun 27 2013
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 27 June 2013 at 15:32:05 UTC, MattCodr wrote:

 On Thursday, 27 June 2013 at 12:38:25 UTC, John Colvin wrote:

 The question is ambiguous as to what they mean by -n. Do they 
 mean the result of negation on the 32bit signed int, or do 
 they mean the negative of the number represented by that int. 
 this matters because -int.min evaluates to int.min due to 
 wraparound.


 From: February 11, 2008:

 Vlad Patryshev said...

 ...Write a function f on 32-bit integers that, applied twice, 
 it negates the integer. f(f(n)) = -n.

 Source: 
 http://steve-yegge.blogspot.com.br/2008/02/portrait-of-n00b.html

 Matheus.


How is that any more specific?
Jun 27 2013
parent "MattCodr" <mattcoder hotmail.com> writes:
On Thursday, 27 June 2013 at 16:02:59 UTC, John Colvin wrote:

 On Thursday, 27 June 2013 at 15:32:05 UTC, MattCodr wrote:

 On Thursday, 27 June 2013 at 12:38:25 UTC, John Colvin wrote:

 The question is ambiguous as to what they mean by -n. Do they 
 mean the result of negation on the 32bit signed int, or do 
 they mean the negative of the number represented by that int. 
 this matters because -int.min evaluates to int.min due to 
 wraparound.


 From: February 11, 2008:

 Vlad Patryshev said...

 ...Write a function f on 32-bit integers that, applied twice, 
 it negates the integer. f(f(n)) = -n.

 Source: 
 http://steve-yegge.blogspot.com.br/2008/02/portrait-of-n00b.html

 Matheus.


 How is that any more specific?


In fact it isn't. This was all that I collected about the problem 
(at work).
Jun 27 2013
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 26 Jun 2013 16:51:33 -0400, 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


int f(int x)
{
     return x < 0 ? (x & 1 ? x+1 : -x+1) : (x & 1 ? x-1 : -x-1);
}

works for all but int.min, but -int.min == int.min, so, I'm not sure what  
to do for that.  Either change argument type for long, in which case the  
result of f(f(int.min)) == int.max + 1LL, or special case int.min to  
return int.min.

-Steve
Jun 27 2013
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 27 Jun 2013 13:43:24 -0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 On Wed, 26 Jun 2013 16:51:33 -0400, 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


 int f(int x)
 {
      return x < 0 ? (x & 1 ? x+1 : -x+1) : (x & 1 ? x-1 : -x-1);
 }

 works for all but int.min, but -int.min == int.min, so, I'm not sure  
 what to do for that.  Either change argument type for long, in which  
 case the result of f(f(int.min)) == int.max + 1LL, or special case  
 int.min to return int.min.


I was wrong, it doesn't work for -1 also.

Hm...

I could special case that too... but I like the simplicity :)

-Steve
Jun 27 2013
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 27 June 2013 at 18:00:21 UTC, Steven Schveighoffer 
wrote:

 On Thu, 27 Jun 2013 13:43:24 -0400, Steven Schveighoffer 
 <schveiguy yahoo.com> wrote:


 On Wed, 26 Jun 2013 16:51:33 -0400, 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


 int f(int x)
 {
     return x < 0 ? (x & 1 ? x+1 : -x+1) : (x & 1 ? x-1 : -x-1);
 }

 works for all but int.min, but -int.min == int.min, so, I'm 
 not sure what to do for that.  Either change argument type for 
 long, in which case the result of f(f(int.min)) == int.max + 
 1LL, or special case int.min to return int.min.


 I was wrong, it doesn't work for -1 also.

 Hm...

 I could special case that too... but I like the simplicity :)

 -Steve


The trick is to move away from 0 in all cases (see my solution)
Jun 27 2013
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 27 Jun 2013 14:09:11 -0400, John Colvin  
<john.loughran.colvin gmail.com> wrote:


 The trick is to move away from 0 in all cases (see my solution)


Yes, but you still have to special case 0:

int f(int x)
{
    return x == 0 ? 0 : x > 0 ? (x & 1 ? x+1 : -x+1) : (x & 1 ? x-1 : -x-1);
}

Works for everything but int.max (and only works for int.min because  
-int.min == int.min).  With long as parameters, it does the mathematically  
correct thing.

I think there isn't any other way to do it, you have to special case 0,  
and possibly the min/max.

-Steve
Jun 27 2013
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 06/26/2013 10:51 PM, 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


int f(int x){ return x?(x&1?x:-x)+(x>0?1:-1):0; }

unittest{
     foreach(x;int.min..int.max)
         assert(f(f(x))==-x);
}
Jun 27 2013
next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 27 Jun 2013 14:37:25 -0400, Timon Gehr <timon.gehr gmx.ch> wrote:


 int f(int x){ return x?(x&1?x:-x)+(x>0?1:-1):0; }


This is similar to mine, but I like the factoring.

Still needs a special case for f(f(int.max)) which in your function  
returns int.max (like mine).

-Steve
Jun 27 2013
prev sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 27 June 2013 at 18:37:26 UTC, Timon Gehr wrote:

 On 06/26/2013 10:51 PM, 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


 int f(int x){ return x?(x&1?x:-x)+(x>0?1:-1):0; }

 unittest{
     foreach(x;int.min..int.max)
         assert(f(f(x))==-x);
 }


That highly compound statement..... Why? Surely you would never 
write anything like this either in production code (unless 
absolutely necessary) or in an interview?

It's fine as a one-off, but a whole code-base full of this style 
would be horrifying.
Jun 27 2013
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 06/27/2013 09:48 PM, John Colvin wrote:

 On Thursday, 27 June 2013 at 18:37:26 UTC, Timon Gehr wrote:

 On 06/26/2013 10:51 PM, 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


 int f(int x){ return x?(x&1?x:-x)+(x>0?1:-1):0; }

 unittest{
     foreach(x;int.min..int.max)
         assert(f(f(x))==-x);
 }


 That highly compound statement..... Why?


It is easy to see what it is doing this way.


 Surely you would never write
 anything like this either in production code (unless absolutely
 necessary)  or in an interview?


Why not? The function fulfills the specification in a straightforward way.


 It's fine as a one-off, but a whole code-base full of this style would
 be horrifying.


I don't know. This depends on the kind of code base and the exact 
meaning of 'this style'. There are many programming languages where it 
is convenient/required to write every function in a single expression 
and those are not horrifying at all.
Jun 27 2013
parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Thursday, 27 June 2013 at 22:31:21 UTC, Timon Gehr wrote:

 On 06/27/2013 09:48 PM, John Colvin wrote:

 On Thursday, 27 June 2013 at 18:37:26 UTC, Timon Gehr wrote:

 On 06/26/2013 10:51 PM, 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


 int f(int x){ return x?(x&1?x:-x)+(x>0?1:-1):0; }

 unittest{
    foreach(x;int.min..int.max)
        assert(f(f(x))==-x);
 }


 That highly compound statement..... Why?


 It is easy to see what it is doing this way.


Unless you're a hardened c/c++ etc. programmer, those 26 
characters in a row are far from immediately obvious.

Personally I learnt to code in C and therefore it only took me 
15-20 seconds to be sure I knew what was happening, but even so 
at first glance it's just an incomprehensible string of symbols.

Perhaps it's just a matter of taste, but I think that there's a 
sweet-spot for compact v.s. verbose and it lies somewhere to the 
verbose side of nested  ternary operators with no spaces.

In this example, just separating the main calculation from the 
special 0 case and adding a few spaces would make it much more 
understandable at first glance.
e.g.
int f(int x) {
     if(x)
         return (x&1 ? x:-x) + (x>0 ? 1:-1);
     return 0;
}
Jun 27 2013