June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to John Colvin | 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).
|
June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to monarch_dodra | 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
|
June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Gary Willoughby | 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
|
June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrej Mitrovic | 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
|
June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | 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
|
June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Steven Schveighoffer | 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)
|
June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Gary Willoughby | 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);
}
|
June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to John Colvin | 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 |
June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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
|
June 27, 2013 Re: How would you solve this 'interview' question in D? | ||||
---|---|---|---|---|
| ||||
Posted in reply to Timon Gehr | 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.
|
Copyright © 1999-2021 by the D Language Foundation